Теорема Эйлера утверждает, что для любых взаимно простых чисел 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
Таким образом, все данные расшифрованы.