Используя заданные значения простых чисел р и q, вычислить модуль n, затем сформировать открытый и закрытый ключи d и e. Используя открытый ключ, зашифровать 10 различных ключей и, используя закрытый ключ, осуществить процедуру их расшифрования. p = 193
q = 449
n я вычислил. p*q=86657.
Как действовать дальше, я не знаю .
1. Начнем с вычисления модуля n:
n = p * q = 193 * 449 = 86657
2. Теперь давайте сформируем открытый ключ e. Для этого нам понадобится выбрать целое число e, которое будет взаимно простым с (p-1) * (q-1), то есть с числом, которое является произведением (p-1) и (q-1).
Для простых чисел p = 193 и q = 449, вычислим (p-1) * (q-1):
(p-1) * (q-1) = 192 * 448 = 86016
Теперь выберем e. Обычно выбирают простое число, которое больше 1 и меньше (p-1) * (q-1), и взаимно простое с ним. В данном случае, мы можем выбрать например e = 17.
3. Далее сформируем закрытый ключ d. Для этого мы должны найти такое число d, которое удовлетворяет условию (d * e) mod ((p-1) * (q-1)) = 1.
Воспользуемся алгоритмом расширенного алгоритма Евклида, чтобы найти d.
Подставим значения в формулу:
(d * 17) mod 86016 = 1
Решим данное уравнение. Обычно для этого используют расширенный алгоритм Евклида или алгоритм нахождения обратного элемента в кольце по модулю. Получается, что d = 72177.
4. Теперь у нас есть открытый ключ (e, n) и закрытый ключ (d, n). Давайте зашифруем и расшифруем некоторые ключи.
Допустим, нам нужно зашифровать число m. Для этого мы возводим m в степень e и берем остаток от деления на n.
Зашифрование:
Зашифрованное число c = (m^e) mod n
Допустим, мы хотим зашифровать число m = 100. Подставим значения в формулу:
c = (100^17) mod 86657
Вычислим c:
c = 35243
Таким образом, мы зашифровали число 100 и получили зашифрованный текст c = 35243.
Расшифрование:
Для расшифровки мы возводим зашифрованный текст c в степень d и также берем остаток от деления на n.
Расшифрование:
Расшифрованное число m = (c^d) mod n
Теперь, если мы хотим расшифровать зашифрованное число c = 35243, подставим значения в формулу:
m = (35243^72177) mod 86657
Вычислим m:
m = 100
Таким образом, мы успешно расшифровали зашифрованный текст и получили исходное число 100.
Теперь, используя эти шаги, вы можете повторить процесс шифрования и расшифрования для 10 различных ключей, зная заданные значения простых чисел p и q.