Теорема Эйлера
Теорема Эйлера утверждает, что для любых взаимно простых чисел x и n (x < n)
x?(n)mod n = 1
или в более общем виде
xk?(n)+1mod n = 1
Сформулируем еще один важный результат. Для любого m>0 и 0<e<m, где e и m взаимно просты, найдется единственное 0<d<m, такое, что
de mod m = 1.
Здесь d легко можно найти по обобщенному алгоритму Евклида (см., например, Д. Кнут. Искусство программирования на ЭВМ, т.2, 4.5.2). Известно, что вычислительная сложность алгоритма Евклида ~ ln n.
Подставляя ?(n) вместо m, получим de mod?(n)=1
или
de = k?(n)+1
Тогда прямой функцией будет
?(x) = xe mod n
где x – положительное целое, x<n=pq, p и q – целые простые числа и, следовательно,
?(n)=(p-1)(q-1)
где e – положительное целое и e<?(n). Здесь e и n открыты. Однако p и q неизвестны (чтобы их найти, нужно выполнить разбиение n на множители), следовательно, неизвестна и ?(n), а именно они и составляют потайной ход.
Вычислим обратную функцию
?-1(y) = yd mod n = xed mod n = xk?(n)+1 mod n = x
Последнее преобразование справедливо, поскольку x<n и x и n взаимно просты.
При практическом использовании алгоритма RSA вначале необходимо выполнить генерацию ключей. Для этого нужно:
- Выбрать два очень больших простых числа p и q;
- Вычислить произведение n=p?q;
- Выбрать большое случайное число d, не имеющее общих сомножителей с числом (p-1)?(q-1);
- Определить число e, чтобы выполнялось
(e?d)mod((p-1)?(q-1))=1.
Тогда открытым ключом будут числа e и n, а секретным ключом – числа d и n.
Теперь, чтобы зашифровать данные по известному ключу {e,n}, необходимо сделать следующее.
- Разбить шифруемый текст на блоки, где i-й блок представить в виде числа M, величина которого меньше, чем n. Это можно сделать различными способами, например используя вместо букв их номера в алфавите.
- Зашифровать текст, рассматриваемый как последовательность чисел m(i), по формуле c(i)=(m(i)e)mod n.
Чтобы расшифровать эти данные, используя секретный ключ {d,n}, необходимо вычислить: m(i) = (c(i)d) mod n. В результате будет получено множество чисел m(i), которые представляют собой часть исходного текста.
Например, зашифруем и расшифруем сообщение "AБВ", которое представим как число 123.
Выбираем p=5 и q=11 (числа на самом деле должны быть большими).
Находим n=5?11=55.
Определяем (p-1)?(q-1)=40. Тогда d будет равно, например, 7.
Выберем e, исходя из (e?7) mod 40=1. Например, e=3.
Теперь зашифруем сообщение, используя открытый ключ {3,55}
C1 = (13) mod 55 = 1 C2 = (23) mod 55 = 8 C3 = (33) mod 55 = 27
Теперь расшифруем эти данные, используя закрытый ключ {7,55}.
M1 = (17) mod 55 = 1 M2 = (87) mod 55 = 2097152 mod 55 = 2 M3 = (277) mod 55 = 10460353203 mod 55 = 3
Таким образом, все данные расшифрованы.
