Баричев С. Криптография без секретов

Методическое пособие - Компьютеры, программирование

, - RSA, 1977 : , .

, , . ( ), RSA . , .

RSA . RSA , ( ).

RSA , SSL, S-HHTP, S-MIME, S/WAN, STT PCT.

, .

Теорема 1. (Малая теорема Ферма.)

Если р - простое число, то

xp-1 = 1 (mod p) (1)

для любого х, простого относительно р, и

xp = х (mod p) (2)

для любого х.

. (1) (2) Zp. .

, (8.2.2) =0 1.

xp=(x-1+1)p= C(p,j)(x-1)j=(x-1)p+1 (mod p),

0jp

C(p,j)=0(mod p) 0<j<p. .

Определение. Функцией Эйлера (n) называется число положительных целых, меньших n и простых относительно n.

n23456789101112(n)122326464104

Теорема 2. Если n=pq, (p и q - отличные друг от друга простые числа), то

(n)=(p-1)(q-1).

Теорема 3. Если n=pq, (p и q - отличные друг от друга простые числа) и х - простое относительно р и q, то

x(n) = 1 (mod n).

Следствие . Если n=pq, (p и q - отличные друг от друга простые числа) и е простое относительно (n), то отображение

Еe,n: xxe (mod n)

является взаимно однозначным на Zn.

, - (n), d, ,

ed = 1 (mod (n)) (3)

RSA.

n=pq, p q -