RSA, 1977 . .
( ). () Q,
N = P × Q j (N) = (P 1)×(Q 1).
e : e < j (N), (e, j (N)) = 1, d : d < N, .
(e, N) . . d .
RSA . 4.7.
. 4.7. RSA. |
, . ( , , ) - h () m: m = h (M).
S , - m d:
S = md (mod N).
(M, S) - , S, S d.
(M, S) - . - m' S e:
m' = S e (mod N).
, - h (): m = h (M). , .. S e (mod N) = h (M), (M, S) . , d S , d e , N .
, , S , S d, e. e "" .
RSA.
1. N, e d RSA , . , . .
2. RSA , , ( DES), .. 1018, N, d e 2512 ( 10154) , , 20...30% .
|
|
3. RSA . , RSA d , .
, 1 2 3, - m 1 = h (M 1), m 2 = h (M 2), m 3 = h (M 3), m 3 = m 1 × m 2 (mod N). , M 1 2 S 1 = m 1 d (mod N) S 2 = m 2 d (mod N). S 3 3 d: S 3 = S 1 × S 2 (mod N). ,
S 1 × S 2 (mod N) = m 1 d × m 2 d (mod N) = (m 1 × m 2) d (mod N) = m 3 d (mod N) = S 3.