Has sent Stalker

This section comprises any descriptions of attacks to one of the schemes of open enciphering most popular nowadays and the digital signature - RSA. Considered methods assume presence of certain mathematical weaknesses of the scheme which are not considered at reckless realisation. Also counteraction measures to these attacks are resulted. They are necessary for taking into consideration at realisation of scheme RSA or the reports based on it.

1. Bezkljuchevoe reading RSA.

2. Attack to signature RSA in the scheme with the notary.

3. Attack to signature RSA on chosen ш.т.

First of all we will recollect the scheme of an island ш and ЭЦП RSA.

1. Get out p, q - the big simple numbers. Product n=pq is calculated.
2. The number e - such that (e, ф (n)) =1 (т.е e and ф (n) - взаимнопросты), where ф (n) - Euler's function from n gets out.
3. From the equation ed=1 (mod ф (n)) there is a number d.

The received numbers e, n - an open key of the user, and d - a confidential key.

Procedure зашифрования: C=E _{(e, n)} (M) =M^e (mod n), where S-received ш.т., M - an island т., satisfying to a following condition: M^{ф (n)} =1 (mod n).

Procedure расшифрования: M=D _{(d, n)} (C) =C^d (mod n).

Generation of the digital signature: digital signature Q=M^d (mod n).

Check of the digital signature: Q^e (mod n)? = M.

1. A method безключевого readings RSA.

Entry conditions. To the opponent are known an open key (e, n) and шифротекст With.

Problem. To find initial text M.

The opponent selects number j for which the following parity is carried out: ^ej. I.e. the opponent simply spends j time зашифрование on an open key intercepted шифротекста (it looks as follows: ^ee) ^e.) ^e (mod n) =^ej). Having found such j, the opponent calculates ^ej-1 (i.e. j-1 time repeats operation зашифрования) is a value and there is clear text M! It follows from this that ^ej (mod n) = (C^ej-1e=C. Т.е some number ^ej-1 in degree e gives шифротекст With. And what it, how not clear text M?

Example (on Sinmons and Norris). p=983, q=563, e=49, M=123456.

C=M⁴⁹ (mod n) =1603, C⁴⁹⁷ (mod n) =85978, C⁴⁹⁸ (mod n) =123456, C⁴⁹⁹ (mod n) =1603.

2. Attack to signature RSA in the scheme with the notary.

Entry conditions. There is the electronic notary signing documents passing through it. N - some clear text, which notary does not wish to sign. To the opponent are known an open key (e, n) the notary.

Problem. To sign this text N.

The opponent develops a certain random number x which взаимнопросто with N and calculates y=x^e (mod n). Then receives value M=yN and transfers it to the signature to the notary. That signs (after all it any more text N!) ^d (mod n) =S. Т.е it is received that ^d (mod n) =y^dN^d = (x^e) ^dN^d =xN^d so ^d=Sx^-1 (mod n).Т.е it is necessary to divide simply received S on x.

Protection. At the signature to add some random number in the message (for example, time). Distortion of number M Thus will turn out at the signature, т.е M _{(after addition)}... yN.

3. Attack to signature RSA on chosen шифротексту.

Entry conditions. Is available шифротекст C. To the opponent are known an open key (e, n) the sender of the message.

Problem. To find initial text M

The opponent develops certain r: r <n, (r, n) =1 also calculates x=r^e (mod n). Then about calculates t=r^-1 (mod n) and y=xC (mod n) and sends y for the signature to the sender.

The sender, suspecting nothing, signs the text y: w=y^d (mod n) also sends w back.

The opponent calculates tw (mod n) =r^-1y^d (mod n) = (as r=x^d mod n) =x^-dx^dC^d (mod n) =C^d=M.

The opponent cannot send at once C for the signature since the sender looks through the messages received as a result of the signature and can notice provocation.

Attack has a little hypothetical character, but nevertheless allows to make some the important conclusions: it is necessary to sign and cipher different keys, or to add a casual vector at the signature or to use hesh-function.