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

is 23.

       Several remarks are in order.

Remark 3.1

      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 is said to be computationally infeasible (= infeasible) or intractable. The enciphering function transforming is conjectured to be a one‐way function, i.e. it is easy to calculate given , but it is impossible to undo this calculation.

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

      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 to B (=Bob). Bob has already chosen two large unequal prime¹ numbers and . Bob multiplies and together to get . Bob also chooses some integer bigger than 1. The integer ( for enciphering) must have no factors in common with and no factors in common with . In other words, the greatest common divisor of and is 1 (and similarly for and ). In symbols, we write and . Thus, the only number dividing both and is 1, and the only number dividing both and is 1. We say also that is relatively prime to and to . It follows that .

Because of the conditions imposed on , namely that is relatively prime to , there exists a unique integer ( for deciphering) which is greater than 1 but less than and is such that the remainder of when divided by is 1. It is easy for Bob to calculate