Методические указания по выполнению работы. Целью работы является изучение системы шифрования с открытым ключом RSA, получение навыков шифрования и выбора параметров шифросистемы.

Цель работы

Целью работы является изучение системы шифрования с открытым ключом 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.