Теорема Эйлера
и п (х < п)
x*ln)mod n = 1 или в более общем виде
хкф(п|+1т0с1 п = 1.
Сформулируем еще один важный результат. Для любого ш> 0 и 0 < е < т, где е и т взаимно просты, найдется единственное 0 < d < m, такое, что
de mod m = 1.
Здесь d легко можно найти по обобщенному алгоритму Евклида (см., например, Д. Кнут. Искусство программирования на ЭВМ, т. 2, 4.5.2). Известно, что вычислительная сложность алгоритма Евклида ~ In п.
Подставляя ф (п) вместо ш, получим
de modф(п)=1
или
de = кф(п)+1.
Тогда прямой функцией будет
f(х) = хе mod п
где х — положительное целое, х < n = pq, р и q — целые простые числа и,следовательно,
ф(п)—(р—1)(q-1)
где е — положительное целое и е < ф (п). Здесь е и п открыты. Однако р и q неизвестны (чтобы их найти, нужно выполнить разбиение п на множители), следовательно, неизвестна и ф(п), а именно они и составляют потайной ход.
Вычислим обратную функцию
Последнее преобразование справедливо, поскольку х < пихип взаимно просты.
При практическом использовании алгоритма RSA вначале необходимо выполнить генерацию ключей. Для этого нужно:
1) Выбрать два очень больших простых числа р и q;
2) Вычислить произведение n = р х q;
3) Выбрать большое случайное число d, не имеющее общих сомножителей с числом (p-l)x(q-l);
4) Определить число е, чтобы выполнялось
(exd)mod((p-l)x(q-l))=1.
Тогда открытым ключом будут числа еип, а секретным ключом — числа d и п.
Теперь, чтобы зашифровать данные по известному ключу {е,п}, необходимо сделать следующее:
• Разбить шифруемый текст на блоки, где i-й блок представить в виде числа м, величина которого меньше, чем п.
Это можно сделать различными способами, например используя вместо букв их номера в алфавите.• Зашифровать текст, рассматриваемый как последовательность чисел
m ( i), по формуле c(i) = (m(i)e) mod n.
Чтобы расшифровать эти данные, используя секретный ключ {d, п}, необходимо вычислить: m( i) = (c(i)d) mod п. В результате будет получено множество чисел m (i), которые представляют собой часть исходного текста.
Например, зашифруем и расшифруем сообщение «АБВ», которое представим как число 12 3.
Выбираем p=5Hq=ll (числа на самом деле должны быть большими). Находим п = 5x11 = 55.
Определяем (p-l)x(q-l) = 4 0. Тогда d будет равно, например, 7. Выберем е, исходя из (ех7) mod 40 = 1. Например, е = 3. Теперь зашифруем сообщение, используя открытый ключ {3,55} :
Ci = (l3)mod 5 5 = 1
Теперь расшифруем эти данные, используя закрытый ключ {7,55}:
Таким образом, все данные расшифрованы.
Еще по теме Теорема Эйлера:
- Сверхсветовая Взаимосвязь
- Политическая социализация
- Бесконечная жизнь духа
- ПОНИМАНИЕ
- 6. Возвышенное, а не просто высокое…
- 4. Приохотить к умственному труду – дело непростое. Надо запастись терпением
- II. 1. 3. Отображения.
- Ломоносов и научная журналистика
- 1. Власть, государство, суверенитет Власть
- Собственная динамика прогнозов
- ЗНАК ЗАЗЕМЛЕНИЯ «666 И БОЛЕЕ». ХАРАКТЕРИСТИКИ
- Рассуждение об обязанностях журналистов при изложении ими сочинений, предназначенное для поддержания свободы философии
- Проблемы и их вербализация
- Наука и современное общество
- 4. Семейная и сексуальная жизнь
- НАТУРАЛИСТИЧЕСКОЕ НАПРАВЛЕНИЕ ГЕОГРАФИЧЕСКИЙ ДЕТЕРМИНИЗМ
- Приложение III МЕТАТЕОРЕТИЧЕСКИЙ КОНТЕКСТ ПСИХОЛОГИЧЕСКОЙ ПОМОЩИ
- 5.3. ПРОБЛЕМНОЕ ОБУЧЕНИЕ
- МЕРКУРИЙ.