Борисенко, Moscow State University fur-floor-mat

Unlike symmetric coding at which decoding procedure is easily restored on procedure of enciphering and back, in the scheme of coding with an open key it is impossible to calculate decoding procedure, knowing enciphering procedure. More precisely, the operating time of the algorithm calculating procedure of decoding, is so great that it cannot be executed on any modern computers, no less than on any computers of the future. Such schemes of coding name asymmetric.

So, we have two displays:

Where S - set of the every possible not ciphered messages, T - set of the ciphered messages. The letter "E" - the first letter of a word "Encoding", the letter "D" - the first letter of a word "Decoding". Display

Translates the initial message s in the ciphered message t, display

Translates the ciphered message t back in s. That fact that D is decoding procedure, in mathematical language means that the composition of displays DE is identical display: for everyone s it is fair

All it is fair for any scheme of asymmetric coding. We will pass directly to scheme RSA named so under the first letters of surnames of its authors - Rumley, Shamir, Adleman. We will notice at once that scheme RSA possesses two additional very useful properties.

1. The set of initial messages S coincides with set of coded messages T; as this set the ring of deductions on the module m, where m - product of two big simple numbers (decimal record m has length not less than 200) is used.

2. Not only DE = 1, but also ED = 1! Thus, D and E - two it is mutual the return display. It allows the owner of confidential procedure of decoding D to apply it to coding. Thus all can decode this message, using open procedure E, but only the owner of confidential procedure D can send it. Such "return" scheme of application of an open key allows to certify the sender of the message. In practical applications (for аутентификации the sender) the return scheme even is more important, than a straight line.

So, in scheme RSA as set of the initial and ciphered messages the ring of deductions Z_m, where is used

Product of two big simple numbers (the length of decimal record of each of numbers p and q is not less 100). Any message is represented in the form of element Z_m. (Any собщение is a sequence of bits which can be considered as the big integer. If the length of the message more than length of binary record m it breaks into blocks, and each block is ciphered separately.)

Number m opened, however decomposition m on a multiplier - confidential. Decomposition allows to calculate Euler's function (a consequence 3):

It is easy to show that the knowledge of function of Euler gives the chance to factorize number so complexity of a problem of breaking up of an open key is equal to complexity of a problem of decomposition on a multiplier. Mathematicians believe that it really challenge though any satisfactory estimations from below now it is not received. (And hardly it is a NP-full problem.)

Let's generate a stochastic element e in a ring of deductions on the module phi (m), such that it is reversible in this ring (i.e. it is mutually simple with phi (m)). The pair (m, e) is an open key. Display E consists in exponentiation e in a ring of deductions on the module m.

The algorithm of fast exponentiation is applied to practical calculation.

For an element e the return element d in a ring of deductions on the module phi (m) is calculated.

It easily becomes by means of the expanded algorithm of Evklida. The pair (m, d) is a confidential key. Display D consists in exponentiation d in a ring of deductions on the module m.

Let's show that display D is the left return to E, i.e. for everyone ссобщения s equality D (E (s)) = s is carried out. We have

So, DE = 1. It is similarly proved that ED = 1.

The set of messages Z_m, where m - product of two big simple numbers is considered: m = p*q. The number m is opened, but its decomposition on a multiplier - confidential. The knowledge of decomposition allows to calculate Euler's function phi (m) = (p-1) * (q-1). The reversible element e in a ring of deductions on the module phi (m) In a random way gets out. For it it is calculated (by means of the expanded algorithm of Evklida) a return element d in a ring of deductions on the module phi (m). Display E is set by pair (m, e) and consists in exponentiation e on the module m:

Display D is set by pair (m, d) and consists in exponentiation d on the module m:

These two displays are mutually return. The pair (m, e) is an open key (public key), the pair (m, d) is a confidential key (private key).

Example. We will consider an example with small numbers only to illustrate scheme RSA. In real appendices use the big integers, an order of 200-400 decimal figures.

Let m = 11*13 = 143. We will calculate Euler's function phi (m) = 10*12 = 120. We will choose e = 113, then d = 17 - return to e an element in ring Z₁₂₀.

The pair (143, 113) makes an open key, pair (143, 17) - a confidential key. Display E consists in exponentiation 113 on the module 143, display D - in degree 17 on the module 143. We will consider any message s = 123. Then

Thus, 41 is the coded message. We will apply to it decoding procedure:

We have received the initial message.

In connection with scheme RSA there is a number of algorithmic problems.

1. For generation of keys we should to be able generate the big simple numbers. A close problem is check of simplicity of an integer.

2. For key breaking up in RSA it is necessary to be able to display an integer on a multiplier (or that practically the same to be able to calculate Euler's function). Key breaking can interest only criminals, but, on the other hand, those who try to protect the information, should be assured that the decomposition problem on a multiplier is difficult enough.