6
RSA
: RSA .
RSA
RSA (Rivest, Shamir, Adleman). , , .. . RSA .
p q ( 100 ). : n = pq j(n) = (p-1)(q-1), j (n) n. d >1, , (d, j(n)) = 1, e,
1 < e < j(n), : ed º 1 mod j(n).
n, e d , .
n e , p,q, j(n) d . . , p (, , n e), :
q = n/p; j(n) = (p-1)(q-1); d : ed º 1 mod j(n).
S e n. d.
Se º C mod n. C .
Cd = Sed = S1+j(n)k = Sj(n)k S º S mod n. (*)
(*) , ed º 1 mod j(n) ,
ed = 1 + j(n)k, k .
. p = 11, q = 13. n = 143, j(n) = 120.
d : (d, j(n)) = 1, , d = 37, : ed º 1 mod j(n) e = 13. , 13*37 = 481 º 1 mod 120.
, , , S = 42. 4213 º 3 mod 143, .. C = 3.
3 37: 337 º 42 mod 143. , .
, .
1). A, B, C, . p, , p-1 . N = p1p2p3pk . p-1 , :
a1a2 º b1b2 º c1c2 º 1 mod (p-1).
A S B. a1: Sa1 º S1 mod p B. b1: S1b1 º S2 mod p A. A a2 B: S2a2 º S3 mod p. B b2 . : a1b1a2b2 º 1 mod (p 1).
|
|
. A, B C p = 103. , 103-1 = 102 , : 102 = 2*3*17. :
A: a1 = 25, a2 = 49,
B: b1 = 19, b2 = 43,
C: c1 = 35, c2 = 35.
A B S = 67. 25 103: 6725 º 86 mod 103. B b2 = 19 A: 8619 º 96 mod 103. A 49 B: 9649 º 21 mod 103. B , 43 : 2143 º 67 mod 103. , S = 67.
p. .
2). . g p , . A k1, B k2 ( ). A B gk1 mod p, B A gk2 mod p. B k2, k1. : gk1k2 = gk2k1 º K mod p, () .
, v1,v2,vk B (). , B .
B N = PQ, P Q . vi (i = 1,2,3,,k) ni = piqi, , N > ni. , j (N) j (ni) .
D -, di :
0 < D < j (N), (D, j (N)) = 1
0 < di < j (ni), (di, j (ni))= 1 .
T ti :
DT º 1 mod j (N), 0 < T < j (N) ,
dt º 1 mod j (ni), 0 < t < j (ni) .
:
B: N, D
vi: ni, di.
vi m B. ( m ti mod ni, : m1 º mti mod ni, m2 º m1D mod N. m2 . , m2 T, di vi. :
|
|
m3 º m2T mod N, m4 º m3di mod ni. m4 = m, .. B , () . . , N < ni, , .
. P = 23, Q = 11; v: p = 13, q = 7. : j(23*11) = 220; j (13*7) = 72, , : D = 71, T = 31; d = 29, t = 5. : P*Q = 253, p*q = 91, D = 71, d = 29. T = 31, t = 5.
m = 41. t, D:
415 º 6 mod 91, 671 º 94 mod 253. ( 94) . T, d: 94 31 º 6 mod 253, 629 º 41 mod 77. 41.
1. RSA. ( 1 30). : . p g p. g p , g1,g2,gn-1 . k1 k2 (). , K. .
2. . p q, n= pq j(n). d (d, j(n)) = 1 . , . , ASCII . . . , . () j(n) d . .
3. . B, P Q; vi, pi qi, . . , . ASCII . . . , . , . .
1. RSA.
2. .
3. .
1. .., . . . . 2001.
2. .. . . . .2001.
|
|