RSA
Здравствуйте. Объясните, пожалуйста, как найти секретную экспоненту d? Пытаюсь понять алгоритм на примере из Вики. Откуда там d=6111579?
Спасибо.
|
||||||||||||||||||||||||||
|
||||||||||||||||||||||||||
Нормы пользования. Некоторые права на материалы сайта защищены по условиям лицензии CreativeCommons. Движок
openSpace 0.8.25a и дизайн сайта © 2006-2007 Vlad "SATtva" Miller.
|
||||||||||||||||||||||||||
комментариев: 11558 документов: 1036 редакций: 4118
/Библиотека/Ста...мыPGP/АсимметричныеАлгоритмы#p1
Вот пример из книги:
Пусть р = 1
и q = 11. Тогда N = 77, a {р — l){q — 1) = 6 • 10 = 60. В качестве открытой
шифрующей экспоненты возьмем число Е = 37, поскольку
ПОД (37,60) = 1. Применяя расширенный алгоритм Евклида, найдем
d = 13, т. к.
37-13 = 481 = 1 (mod 60).
Вот каким образом d=13?
комментариев: 9796 документов: 488 редакций: 5664
А в чём собственно вопрос? Как найти обратный множитель в кольце чисел?
Опечатка же. Должно тогда быть p = 7
d = e -1 mod (p-1)(q-1)
d = 37 -1 mod 60
60 = 37 • 1 + 23
37 = 23 • 1 + 14
23 = 14 • 1 + 9
14 = 9 • 1 + 5
9 = 5 • 1 + 4
5 = 4 • 1 + 1 | gcd (37,60) = 1
4 = 1 • 4 + 0
Интересное число — все частные — единицы.
В общем случае таблица заполняется так:
x1 = y1 = первому частному
y2 = y1 • x2 + y1
yn = yn-1 • xn + yn-2
Последнее число в таблице 60 = 13 • 4 + 8 считается для
проверки. Предпоследнее перед ним — 13 – это и есть мультипликативное обратное в кольце чисел.
37 • 13 = 481
481 = 60 • 8 + 1 — ну да, всё правильно.
В общем случае найденный обратный множитель по модулю надо проверять, так как не для каждого члена кольца он бывает и можно насчитать фикцию. Впрочем, такое бывает только если gcd не равен 1.
Вместо такой таблицы есть методы представления алгоритма Евклида со скобками, дробями,
но результат естественно одинаковый, вопрос лишь в удобстве.
комментариев: 9796 документов: 488 редакций: 5664
13 = 8 • 1 + 5
8 = 5 • 1 + 3
5 = 3 • 1 + 2
3 = 2 • 1 + 1 | gcd (13,60) = 1
2 = 1 • 2 + 0
Здесь просто не учитывался знак.
Если модуль с обратным не сходится, то надо взять обратное значение 60-23=37.
Считайте, что это не каноническое описание расширенного алгоритма Евклида,
а попытка упрощённого объяснения на пальцах.