RSA

/Библиотека/Ста...мы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?

А в чём собственно вопрос? Как найти обратный множитель в кольце чисел?

Опечатка же. Должно тогда быть 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

Интересное число — все частные — единицы.

---

x=частное: x 1 1 1 1 1 1 4 y 1 2 3 5 8 13 60

В общем случае таблица заполняется так:

x₁ = y₁ = первому частному

y₂ = y₁ • x₂ + y₁

y_n = y_n-1 • x_n + y_n-2

Последнее число в таблице 60 = 13 • 4 + 8 считается для
проверки. Предпоследнее перед ним — 13 – это и есть мультипликативное обратное в кольце чисел.

37 • 13 = 481

481 = 60 • 8 + 1 — ну да, всё правильно.

В общем случае найденный обратный множитель по модулю надо проверять, так как не для каждого члена кольца он бывает и можно насчитать фикцию. Впрочем, такое бывает только если gcd не равен 1.

Вместо такой таблицы есть методы представления алгоритма Евклида со скобками, дробями,
но результат естественно одинаковый, вопрос лишь в удобстве.

Большущее Вам спасибо :)

Угу, а если использовать значение, например E=13, то приведенный выше алгоритм выдает фигню. Какой-то очень избирательный алгоритм.

60 = 13 • 4 + 8

13 = 8 • 1 + 5

8 = 5 • 1 + 3

5 = 3 • 1 + 2

3 = 2 • 1 + 1 | gcd (13,60) = 1

2 = 1 • 2 + 0

4 1 1 1 1 2 4 5 9 14 23 60

Здесь просто не учитывался знак.
Если модуль с обратным не сходится, то надо взять обратное значение 60-23=37.

Считайте, что это не каноническое описание расширенного алгоритма Евклида,
а попытка упрощённого объяснения на пальцах.