, - .
.
, , . , , . , . , . .
.
. k. , k , , . B M A, A C = Fk (M). C A, M, k. A, k.
, . . , .
RSA, -, .
RSA
RSA 1978 . : . (Rivest), . (Shamir) . (Adleman). . RSA , , .
.
RSA e, d
N : . Q . Q .
ZN N N.
|
|
e , :
,
,
, (a,b) a b. 1 N, N. , e . d, ,
.
RSA e , d .
d e , : a b (), x, y, c, , ax + by = c, c = (a,b).
.
: a b:
: c = (a, b) x, y: ax + by = c.
1. x2:=1, x1:=0, y2:=0, y1:=1
2. b > 0 2.1 2.2
2.1. q:= a div b, r:= a qb, x:= x2 qx1, y:= y2 qy1
2.2. a:= b, b:= r, x2:= x1, x1:= x, y2:= y1, y1:= y
3. c:= a, x:= x2, y:= y2 (c, x, y). .
d a = b = e. d y.
RSA ( e, ) :
.
N.
, .. , e N, .
, ( d, ) :
.
:
1) : P = 7, Q = 17;
2) ;
3) ;
4) , , : = 5;
5) d , d < 96: d = 77, ..
77×5 = 385 = 4×96 + 1;
6) = 19:
;
7) C = 66: .
/ RSA .
1. , e d, , . N e , . P, Q d .
2. , N e, . , , . :
.
, .
3. , d :
.
, M.