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.
In technical language, the problem of recovering
Given
It is now time to give a formal description of the RSA algorithm, as follows.
3.3 The General RSA Algorithm
A (=Alice) wants to send a secret message
Because of the conditions imposed on