Задача №3. Алгоритм шифрования rsa.

Сгенерируйте открытый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифруйте сообщение, состоящее из ваших инициалов: ФИО.

Решение

I.Генерация ключей.

Выберем два простых числа р = 17 и q = 23

Тогда модуль

n = p*q=17*23 = 391

и функция Эйлера

(n) = (p-1)*(q-1) = (17-1)*(23-1)=16*22=352.

Закрытый ключ d выбираем из условий d < (n) и d взаимно просто с (n), т.е. d и (n) не имеют общих делителей.

Пусть d = 41.

Открытый ключ e выбираем из условий e<(n) и de=1(mod (n)): e<352,

41e=1(mod 352).

Последнее условие означает, что число 41e-1 должно делиться на 352 без остатка.

Таким образом, для определения e нужно подобрать такое число k, что

41e-1 = 352 k.

При k=29 получаем 41e=10208+1 или

e=249.

Получаем

(249, 391) – открытый ключ (KU),

( 41, 391) – секретный ключ (KR).

II. Шифрование.

Представим шифруемое сообщение «ГИН» как последовательность целых чисел. Пусть буква «Г» соответствует числу 22, буква «И» - числу 4 и буква «Н» - числу 9.

Зашифруем сообщение, используя открытый ключ (249, 391):

С₁ = (22²⁴⁹) mod 391= 114

С₂ = (4²⁴⁹) mod 391=123

С₃ = (9²⁴⁹) mod 391= 349

Таким образом, исходному сообщению (22, 4, 9) соответствует криптограмма (114, 123, 349).

III. Расшифрование

Расшифруем сообщение (114, 123, 349), пользуясь секретным ключом (41, 391):

М₁ = ( 114⁴¹) mod 391=22

М₂ = (123⁴¹) mod 391= 4

М_З = ( 349⁴¹) mod 391=9

В результате расшифрования было получено исходное сообщение (22, 4, 9), то есть "ГИН".