Курсовая работа: Лисп-реализация алгоритма кодирования информации RSA
3. Вычисляем функцию Эйлера: φ(n) = (p-1) (q-1) = 9167368.
4. Выбираем открытый показатель: e = 3.
5. Вычисляем секретный показатель: d = 6111579.
6. Публикуем открытый ключ: (e, n) = (3, 9173503).
7. Сохраняем секретный ключ: (d, n) = (6111579, 9173503).
8. Выбираем открытый текст: M = 127.
9. Вычисляем шифротекст: P(M) = Me modn = 10223 mod 9173503 = 116.
10.Вычислить исходное сообщение: S(C) = Cd modn = 1166111579 mod 9173503 = 1022.
Пример 2.
1. Выбираем два простых числа: p = 79, q = 71.
2. Вычисляем их произведение: n = p · q = 79 · 71 = 5609.
3. Вычисляем функцию Эйлера: φ(n) = (p-1) (q-1) = 5460.
4. Выбираем открытый показатель: e = 5363.
5. Вычисляем секретный показатель: d = 2927.
6. Публикуем открытый ключ: (e, n) = (5363, 5609).
7. Сохраняем секретный ключ: (d, n) = (2927, 5609).
8. Выбираем открытый текст: M = 23.
9. Вычисляем шифротекст: P(M) = Me modn = 235363 mod5609 = 5348.
10.Вычислить исходное сообщение: S(C) = Cd modn = 53482927 mod5609 = 23.
2. Математические и алгоритмические основы решения задачи
Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа «по всему миру». Для алгоритма RSA этап создания ключей состоит из следующих операций:
1). Выбираются два простых числа p и q
2). Вычисляется их произведение n (=p*q)
3). Выбирается произвольное число e (e<n), такое, что
НОД (e, (p-1) (q-1))=1,
то есть e должно быть взаимно простым с числом (p-1) (q-1).
4). Методом Евклида решается в целых числах уравнение
e*d+(p-1) (q-1)*y=1.
Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах.