Методические указания по выполнению работы
Цель работы
Целью работы является изучение системы шифрования с открытым ключом RSA, получение навыков шифрования и выбора параметров шифросистемы.
Предварительная подготовка
1.2.1 Необходимо ознакомиться с основными сведениями о системах шифрования с открытыми ключами.
1.2.2. Исследовать принцип работы программы RSA.
Рабочее задание
1.3.1 Используя значения p и q, заданные таблицей построить ключевую пару (e, d) для алгоритма RSA.
Таблица 1
| № | 7 | |||||||||||
| p | 29 | |||||||||||
| q | 7 |
1.3.2 Зашифровать с помощью открытого ключа напарника (n, e) сообщение, состоящее из первых букв собственной фамилии, имени и отчества и передать его адресату.
1.3.3 Получив от напарника зашифрованное сообщение, расшифровать его, используя собственный секретный ключ.
1.3.4 Используя программную реализацию алгоритма RSA, с помощью компьютера проверить правильность результатов, полученных при шифровании и расшифровании сообщений, используемых в пункте 1.3.2.
1.3.5. Вычислить цифровую подпись открытого сообщения, передаваемого в п. 1.3.2. Для этого использовать экспоненту расшифрования, определенную в пункте 1.3.1, и программу, реализующую алгоритм RSA на компьютере.
1.3.6 Проверить полученную в п.1.3.5 цифровую подпись, используя экспоненту расшифрования и программу, реализующую алгоритм RSA.
Методические указания по выполнению работы
1.4.1 Наиболее важной частью алгоритма RSA, как и других алгоритмов с открытым ключом, является процесс создания пары открытый/секретный ключи. В RSA он состоит из следующих шагов.
1. Согласно номеру компьютера выберите значения двух секретных простых чисел, p и q, p¹q. Допустим, что p=11, q=13.
2. Вычислите n=p*q=11*13=143.
3. Согласно заданной формуле, рассчитайте функцию Эйлера 
.
4. Пользуясь методом подбора, который должен отвечать условию 
, рассчитайте значения e, k и d. Открытый (e) и секретный (d) ключи должны быть взаимно простыми. В нашем случае e=7, k=6, d=103.
Существует второй способ нахождения ключевой пары (e, d). При нахождении значений e и d, удовлетворяющих условию 
, значение e обычно задают таким образом, чтобы оно было взаимно простым с 
, а значение d определяют из уравнения
x + ed = 1.
В общем случае это уравнение имеет вид 
(где 
) и называется Диафантовым уравнением.
Решение этого уравнения
можно получить с помощью разложения отношения 
в цепную дробь.
где 
– порядок цепной дроби, т.е. индекс коэффициента дроби, у которого остаток равен нулю,
а для всех членов, начиная с третьего справедливо
Таким образом, для решения уравнения необходимо представить отношение a/b в виде цепной дроби, определить при этом значения r0, r1…rм и м. Потом определяются значения ai, bi, а также x и y.
1.4.2.Чтобы зашифровать данные открытым ключом (n, e), необходимо:
1. Разбить исходный текст на блоки, каждый из которых может быть представлен в виде числа M(i)=0, 1, ..., n-1.
Допустим, наше сообщение имеет следующий вид: ААА. Представим данное сообщение в виде последовательности чисел, содержащихся в интервале 0…526. Для этого буквы А, А и A закодируем пятимерными двоичными векторами, воспользовавшись двоичной записью их порядковых номеров в алфавите:
А = 1 = (00001), А = 1 (00001), A = 1 (00001).
Тогда AАА = (000010000100001). Укладываясь в заданный интервал 0…526, получаем следующее представление:
ААА = (000010000), (100001) = (M1 = 16, M2 = 33).
2. Необходимо зашифровать последовательность чисел по формуле 
.
Таким образом,
.
1.4.3 Чтобы расшифровать эти данные секретным ключом (n, d), необходимо выполнить следующие вычисления 
.
Таким образом,
Возвращаясь к буквенной записи, получаем после расшифрования ААА.
1.4.4 Используя программную реализацию алгоритма RSA версии 1.1.0, с помощью компьютера проверим правильность результатов, полученных при шифровании и расшифровании сообщений.
Вводим p, e и q. Производим расчет.
Рисунок 1 – Формирование ключей для
шифрования сообщения «ПРИМКУЛОВА»
Далее переходим на следующую вкладку «Шифрование» и пишем свое сообщение в поле «Открытый текст». Нажимаем на кнопку «Шифрование». У нас появляется шифрограмма.
Рисунок 2 – Шифрование сообщения «ТУЛЕНОВ»
без цифровой подписи.
Дешифрование представляет собой обратный процесс. Переходим по вкладке «Дешифрование» и нажимаем кнопку «Дешифрование». В поле «Открытый текст» появляется расшифрованное сообщение «RSA».
Рисунок 3 – Дешифрование шифрограммы «81 167 138 174 75 64 75 38»
без цифровой подписи.
1.4.5 Для шифрования с цифровой подписью в поле «Цифровая подпись» вводим некоторый текст, который и станет цифровой подписью - «Защита». При этом необходимо в поле «Секретный ключ» указать значение d. После шифрования, в поле «Шифрограмма» появляется зашифрованное сообщение с добавленной цифровой подписью.
Рисунок 4 – Шифрование сообщения «ТУЛЕНОВ»
с цифровой подписью.
При дешифровании с цифровой подписью необходимо в поле «Открытый ключ» указать значение е.
Рисунок 5 – Дешифрование шифрограммы «81 167 138 174 75 64 75 38»
с цифровой подписью.
Контрольные вопросы
1. Какие числа являются простыми, взаимно простыми? Как проверить, является ли выбранное число простым?
2. Дайте определение несимметричных шифров.
3. Как осуществляется шифрование и расшифрование сообщений в алгоритме RSA.
4. Какие соображения следует принимать при выборе чисел p, q, n?
5. Сложностью какой математической задачи определяется стойкость системы RSA?
6. Что общего между обычной и цифровой подписями? Чем они различаются?
7. Какие задачи позволяет решать цифровая подпись?
Вывод
В ходе данной лабораторной работы были изучены системы шифрования с открытым ключом RSA, получены навыки шифрования и выбора параметров шифросистемы.
Было проверено, что действительно в системах шифрования с открытым ключом RSA, открытый ключ не требуется сохранять в тайне. Необходимо лишь обеспечить его аутентичность, что, как правило, сделать легче, чем обеспечить рассылку и сохранность секретных ключей.
Каждый из корреспондентов системы обладает ключом k = (k1,k2), состоящим из открытого ключа k1 и секретного ключа k2. Открытый ключ определяет правило зашифрования Ek, а секретный ключ – правило расшифрования Dk.