Алгоритм RSA. Генерация ключей и функция шифрования

1. Выбираем два очень больших простых числа p и q.

2. Определяем M =(p -1)*(q -1) и N=p*q.

3. Определяем D взаимопростое с M. (D^M). (Расширенный алгоритм Евклида). Заметим, что любое простое число Dявляется и взаимопростым с M, если оно не является делителем M.

4. Определяем E такое, что (E*D)mod M =1

5. Назовем (D, N)-открытым ключом, (E,N)-закрытым ключом.

Процедура шифрования/расшифрования выполняется по формуле, где t_i и s_i блоки открытого и шифртекста соответственно.

Пример. Выполним последовательно п. 1-5 генерации ключей.

1. Выберем p =3, q =11.

2. Определим M =20, N =33.

3. Определим D =7.

4. Определим E =3

5. (7,33)-открытый ключ, (3,33)-закрытый ключ.

Пусть открытый текст представлен последовательностью цифр T = 1, 2, 3. Тогда процесс шифрования выглядит следующим образом:

За нахождение простых чисел из более чем 100 000 000 и 1 000 000 000 десятичных цифр EFF назначила денежные призы соответственно в 150 000 и 250 000 USD. Ранее EFF уже присуждала призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр.

Основная операция этого алгоритма - возведение в степень по модулю, для реализации которой предлагается рекурсивный алгоритм, построенный по следующему правилу: (a+b) mod c =((a mod c)+(b mod c))mod c

a^e mod n==f(a, e, n),

f (a, e, n)== f (k, a, e, n), где k =1.

e =0à k mod n, exit; 1

k < n à f (k*a, a, e- 1, n); 2

f (k-n, a, e, n) 3

Номер итерации	Функция	Правило
	f(1, 2, 7, 33)
	f(2, 2, 6, 33)
	f(4, 2, 5, 33)
	f(8, 2, 4, 33)
	f(16, 2, 3, 33)
	f(32, 2, 2, 33)
	f(64, 2, 1, 33)
	f(31, 2, 1, 33)
	f(62, 2, 0, 33)
	62 mod 33=29	Результат

Примердругого метода возведения в степень по модулю [Menezes p.71, 72]

a^k mod n = 5⁵⁹⁶ mod 1234=1013

, k =4+16+64+512=596.

2.143 Algorithm Repeated square-and-multiply algorithm for exponentiation in Zn

INPUT: a Î Z_n, and integer 0 £ k < n whose binary representation is

OUTPUT: a^k mod n.

1. Set b 1. If k = 0 then return(b).

2. Set Aa.

3. If k ₀ = 1 then set ba.

4. For i from 1 to t do the following:

4.1 Set AA ² mod n.

4.2 If k_i = 1 then set bA*b mod n.

5. Return(b).

i
ki
2^i
A
b

Пояснения:

k₉ =1 тогда 1013=1059² mod1234

k₈ =0тогда 1059=1059

925=947²mod 1234

Дляпоискапростыхчиселиспользуетсяалгоритмназываемый «РешетоЭратосфена». Пример алгоритма показан на рисунке ниже.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

1 2 3 4 5 6 7 8910 11 12 13 141516 17 18 19 202122 23 24

1 2 34 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Таким образом, в данном примере после трех шагов алгоритма мы получили после последовательность простых чисел: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23.

Пример[Menezes p.287]

8.4 Example (RSA encryption with artificially small parameters)

Key generation. Entity A chooses the primes p = 2357, q = 2551, and computes n = pq =6012707 and M = (p −1)(q −1) = 6007800. A chooses e =3674911and, using theextended Euclidean algorithm, finds d = 422191 such that e^d == 1 (mod M). A’s public key is the pair (n =6012707; e =3674911), while A’s private key is d = 422191.

Encryption. To encrypt a message m =5234673, B uses an algorithm for modular exponentiation (e.g., Algorithm 2.143) to compute c = m^e mod n =5234673^3674911 mod 6012707 = 3650502; and sends this to A.

Decryption. To decrypt c, A computes c^d mod n = 3650502⁴²²¹⁹¹ mod 6012707=5234673:

Дата добавления: 2015-07-07