. , . , . , , . - , . - (public-key distribution system), .
-, 1976 , .
, , , , . , K, . , - .
N - , G - ,
1 <= G <= N-1.
.
1. N G ( , ).
2. X
XX = G^X MOD N.
Y
YY = G^Y MOD N.
XX YY. ( , , , - ). X Y .
3. YY,
K(1) = YY^X MOD N,
-
K(2) = XX^Y MOD N.
(!)
YY^X MOD N = G^(X*Y) MOD N = XX^Y MOD N,
,
K(1) = K(2) = K.
K , .
? , G, N, XX YY, K. X G, N, XX , , X',
G^X' MOD N = X,
YY^X' MOD N = K.
, .
- . , . M, - .
|
|
. . , , , , , .
, .
: E D . E , , , D . , E . , D . , E D :
D(E(M)) = M,
M.
, , E D. , E , E D.
, . , . , , , , .
RSA
RSA, (Rivest, Shamir Adleman). RSA, .
, 1 . , , 1.
RSA , :
1. p q.
2. n p q (n = p*q).
3. , d. (p-1) * (q-1).
4. , : (e * d) mod ((p-1) * (q-1)) = 1.
5. n, d n.
, {e,n}, :
- ,
M(i) = 0, 1,..., n-1; - , M(i), :
(i) = (M(i)^e) mod n.
{d,n}, : M(i) = (C(i)^d) mod n. M(i), .
RSA "CAB". ( ).
|
|
1. = 3 q = 11.
2. n = 3*11 = 33.
3. (-1) * (q-1) = 20. d , 20, d = 3.
4. e. , (e*3) mod 20 = 1, 7.
5. 0...32. A 1, B - 2, C - 3. 3 1 2.
, {7,33}:
C1 = (3^7) mod 33 = 2187 mod 33 = 9,
C2 = (1^7) mod 33 = 1 mod 33 = 1,
C3 = (2^7) mod 33 = 128 mod 33 = 29.
6. {9,1,29}, {3,33}:
M1 = (9^3) mod 33 = 729 mod 33 = 3,
M2 = (1^3) mod 33 = 1 mod 33 = 1,
M3 = (29^3) mod 33 = 24389 mod 33 = 2.
, "CAB".
RSA , , . NP - . , . , NP - . , 200 ( ), ( 1023).
P ( ) :
P ( ) | x | ( ) | 109 /c |
2*1012 | 7*106 | ||
1016 | 108 | ||
9*1017 | 109 | ||
4*1024 | 3*1012 | 100 | |
1034 | 1017 | ||
1041 | 8*1020 | ||
7*1047 | 1024 | ||
1050 | 1025 | ||
. . . , . " : , C" .
( ) | ( ) |
, . . . . , .
|
|
, , . (, DES), , . , . - , . , , .