Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

Читать онлайн книгу.

Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen


Скачать книгу
rel="nofollow" href="#fb3_img_img_8ac4b956-f13f-5dc4-9e10-3e45eed4a00e.png" alt="d"/> is 23.

       Several remarks are in order.

      1 The fact that B deciphers to recover the message by simply using the deciphering algorithm explained above is proved in Chapter 19.

      2 Having found a decryption index by the official (hard) way, let us find an easier method. All we need is the unique integer, let us call it , between 1 and 20, such that gives a remainder of 1 when divided by 20. Why 20? Well, instead of using , we can use any positive integer divisible by both and . With and , we choose the number 20, and get . Then it is easy to check that the remainder of upon division by 55 is 6. It is much easier to use the decryption index 3 instead of the decryption index 23.

      3 The security of RSA rests on the mathematically unproven assumption that, even given , , , an individual (other than B) cannot recover in a reasonable amount of time if and are large.

      Given e and the two factors p comma q of upper N it is easy to calculate d and thus to obtain upper M from upper C (see Chapter 19). Thus, if one can solve the problem of factoring upper N quickly one can calculate d quickly and thus upper M, given upper C. On the other hand, if we can find d, then we can get upper M (but also p and q).

      It is now time to give a formal description of the RSA algorithm, as follows.