Читать книгу Cryptography, Information Theory, and Error-Correction - Aiden A. Bruen - Страница 61

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.