Теорема Эйлера

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

Таким образом, все данные расшифрованы.

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий