Алгоритм шифрования RSA.
Сгенерировать открытый и закрытый ключи в алгоритме шифрования RSA, выбрав простые числа p и q из первой сотни. Зашифровать сообщение, состоящее из своих инициалов: ФИО.
Решение
Генерация ключей.
Выберем два простых числа p = 17 и q = 41.
Тогда модуль n = pq=17∙41 = 697 и функция Эйлера φ(n)=(p-1)(q-1)=16∙40=640.
Закрытый ключ d выбираем из условий d<φ(n) и d взаимно просто с φ(n), т.е. d и φ(n) не имеют общих делителей.
Пусть d = 21.
Открытый ключ e выбираем из условий e < φ(n) и de=1(mod φ(n)): e<640, 21e=1(mod 640).
Последнее условие означает, что число 21e-1 должно делиться на 640 без остатка.
Таким образом, для определения e нужно подобрать такое число k, что 21e-1 = 640 k.
При k=2 получаем 21e=1280+1 или e=61.
В нашем примере
(61, 697) – открытый ключ,
(21, 697) – секретный ключ.
Шифрование.
Представим шифруемое сообщение «РМА» как последовательность целых чисел
. Пусть буква «Р» соответствует числу 18, буква «М» - числу 14 и
буква «А» - числу 1.
Зашифруем сообщение, используя открытый ключ (61, 697):
183=5832=256 mod 697
186=1832 mod 697=2562 mod 697=65536 mod 697=18 mod 697
1830=1865 mod 697=185 mod 697=1889568 mod 697=1 mod 697
1860=18302 mod 697=12 mod 697=1 mod 697
1861=18∙1860=18∙1 =18
143=2744=653 mod 697
146=1432 mod 697=6532 mod 697=426409 mod 697=542 mod 697
1412=1462 mod 697=5422 mod 697=293764 mod 697=327 mod 697
1424=14122 mod 697=3272 mod 697=106929 mod 697=288 mod 697
1430=146∙1424=7529536∙288 mod 697=2168506368 mod 697=665 mod 697
1460=14302 mod 697=6652 mod 697=442225 mod 697=327 mod 697
1461=14∙1460=14∙327 =4578 mod 697=396 mod 697
161mod 697=1 mod 697
Итак,
C1=(1861) mod 697=18
C2=(1461) mod 697=396
C3= (161) mod 697=1
Таким образом, исходному сообщению (18, 14, 1) соответствует криптограмма (18, 396, 1).
Расшифровывание
Расшифруем сообщение (18, 396, 1), пользуясь секретным ключом (21,697):
187=612220032=324 mod 697
1821=1873 mod 697=3243 mod 697=34012224 mod 697=18 mod 697
3963=62099136=618 mod 697
3969=39633 mod 697=6183 mod 697=236029032 mod 697=437 mod 697
39618=39692 mod 697=4372 mod 697=190969 mod 697=688 mod 697
39621=3963∙39618=62099136∙688 mod 697=42724205568 mod 697=14 mod 697
121mod 697=1 mod 697
Итак,
M1=(1821) mod 697=18
M2=(39621) mod 697=14
M3= (121) mod 697=1
В результате расшифровывания было получено исходное сообщение (18, 14, 1), то есть «РМА».
на новый заказ в Автор24.
