Алгоритм шифрования данных RSA

Алгоритм предложен в 1978 году авторами Rivest, Shamir и Aldeman и основан на трудности разложения больших целых чисел на простые множители. В результате реализации алгоритма имеем пару ключей: первый в дальнейшем используется только для шифрования (открытый ключ), второй для дешифрования (закрытый ключ). При этом, знание одного из ключей не позволяет определить другой ключ. Сгенерированные ключи могут многократно использоваться для шифрования информации.

Последовательность действий пользователя для получения ключей:

1. Получатель выбирает 2 больших простых целых числа p и q, на основе которых вычисляет N = p* q; M = (p -1) * (q -1).

2. Получатель выбирает целое случайное число d, которое является взаимно простым со значением М.

3. Вычисляем значение е из условия (ed) mod M = 1.

4. d и N публикуются как открытый ключ, е и N являются закрытым ключом.

Действия по шифрованию сообщения.

5. Если S – сообщениеи его длина: 1 < Len(S) < N, то оно шифруется выполнением операции S _ш = S^d mod N (то есть, открытым ключом).

Действия по дешифрованию сообщения.

6. Получатель дешифровывает сообщение с помощью закрытого ключа выполнением операции S = S _ш ^e mod N.

Если длина сообщения превышает N, то сообщение делится на фрагменты длины, не превосходящие N.

Рассмотрим реализацию алгоритма на примере. Заметим, что в реальных алгоритмах в качестве простых чисел выбираются отстоящие друг от друга большие числа, порядка 2¹²⁸ – 2¹⁰²⁴, поиск которых, вообще говоря, и определяют сложность алгоритма для криптоанализа.

Далее представлены шаги алгоритма:

1. Выбираем p = 19, q = 13,  N = p*q = 247,

2. Вычисляем формулу Эйлера  M = (p – 1)*(q – 1) = 18 х 12 = 216.

3. Выбираем целое случайное число d, взаимно простое с M, d = 35. (Действительно, d и M не имеют общих делителей 35 = 7 х 5, 216 = 2 х 2 х 2 х 3 х 3 х 3).

4. Вычисляем e такое, что (e d) mod M = 1,     e = 179.

5. (d,N) открытый ключ, т.е. (35,247), (e,N) – закрытый ключ (179, 247).

6.   Шифрование сообщения 2 3 5, используя открытый ключ (35, 247)   по формуле           S _ш = S ^d mod N:

Таким образом, шифрованное сообщение имеет вид 124 165 99.

7. Дешифровка сообщения 124 165 99, используя закрытый ключ (179, 247)   по формуле  S = S _ш ^e mod N:

Расшифрованное сообщение 2 3 5.

8.  Для получения математических расчетов (численной реализации алгоритма RSA)  использовать https://web 2.0 calc.com.

МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ВЫПОЛНЕНИЯ
КОНТРОЛЬНОЙ РАБОТЫ

Контрольная работа представляет собой

a) Титульный лист (Приложение №1);

b)  Задание, выполненное согласно номеру варианта;

c) Список использованной литературы.