<<
>>

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

Теорема Эйлера утверждает, что для любых взаимно простых чисел х

и п (х < п)

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}:

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

<< | >>
Источник: В.Е. Карпов К.А. Коньков. Основы операционных систем. 2005

Еще по теме Теорема Эйлера:

  1. Сверхсветовая Взаимосвязь
  2. Политическая социализация
  3. Бесконечная жизнь духа
  4. ПОНИМАНИЕ
  5. 6. Возвышенное, а не просто высокое…
  6. 4. Приохотить к умственному труду – дело непростое. Надо запастись терпением
  7. II. 1. 3. Отображения.
  8. Ломоносов и научная журналистика
  9. 1. Власть, государство, суверенитет Власть
  10. Собственная динамика прогнозов
  11. ЗНАК ЗАЗЕМЛЕНИЯ «666 И БОЛЕЕ». ХАРАКТЕРИСТИКИ
  12. Рассуждение об обязанностях журналистов при изложении ими сочинений, предназначенное для поддержания свободы философии
  13. Проблемы и их вербализация
  14. Наука и современное общество
  15. 4. Семейная и сексуальная жизнь
  16. НАТУРАЛИСТИЧЕСКОЕ НАПРАВЛЕНИЕ ГЕОГРАФИЧЕСКИЙ ДЕТЕРМИНИЗМ
  17. Приложение III МЕТАТЕОРЕТИЧЕСКИЙ КОНТЕКСТ ПСИХОЛОГИЧЕСКОЙ ПОМОЩИ
  18. 5.3. ПРОБЛЕМНОЕ ОБУЧЕНИЕ
  19. МЕРКУРИЙ.