Лабораторная работа № 11
Криптоалгоритмы с открытыми ключами (RSA)
Цель работы
Освоить методику работы ассиметричных алгоритмов шифрования, где существует два ключа: один для шифрования, другой для дешифрования.
Указание к работе
Алгоритм RSA был разработан в 1977 году Роном Ривестом, Ади Шамиром и Леном Адлеманом и опубликованный в 1978 году. С тех пор алгоритм Rivest-Shamir-Adleman (RSA) широко применяется практически во всех приложениях, использующих криптографию с открытым ключом.
Алгоритм RSA состоит из трёх этапов:
I. Вычисление ключей. Важным моментом в этом криптоалгоритме является создание пары ключей: открытого и закрытого. Для алгоритма RSA этап создания ключей состоит из следующих операций:
1. Выбираются два простых различных числа p и q. Вычисляется их произведение n = p∙q, называемое модулем.
2. Вычисляется функция Эйлера Φ(n) = (p–1)∙(q–1).
3. Выбирается произвольное число e (e < n), такое, что 1 < e < Φ(n) и не имеет с числом (p–1)∙(q–1) других общих делителей, кроме 1 (т. е. оно является взаимно простым с ним).
4. Вычисляется d (расширенным алгоритмом Евклида) таким образом, что (e∙d–1) делилось на (p–1)∙(q–1).
5. Два числа (е, n) публикуются как открытый ключ.
6. Число d хранится в секрете. Закрытый ключ есть пара (d, n), который позволит читать все послания, зашифрованные с помощью пары чисел (е, n).
II. Шифрование с помощью этих чисел производится так:
1. Отправитель разбивает свое сообщение M на блоки mi. Значение mi < n, поэтому длина блока открытого текста mi в битах не больше k = [log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа. Например, если n=21, то максимальная длина блока открытого текста k = [log2(21)]=[4.39…]=4 бита.
2. Подобный блок может быть интерпретирован как число из диапазона (0; 2k–1). Для каждого такого числа mi вычисляется выражение (ci – зашифрованное сообщение):
ci = (mi)e mod n.
В качестве размера блока зашифрованного текста следует брать 
бит, где операция 
– это округление вверх до ближайшего целого.
Необходимо добавлять нулевые биты слева в двоичное представление блока ci до размера ke бит.
III. Дешифрование.
1. Чтобы получить открытый текст, надо каждый блок зашифрованного текста длиной ke бит дешифровать отдельно:
mi = (ci)d mod n.
Пример:
Выбрать два простых числа:
р = 7, q = 17.
Вычислить:
n = p·q = 7·17 = 119.
Вычислить:
Ф(n) = (p–1)·(q–1) = 96.
Выбрать е так, чтобы е было взаимно простым с Ф(n) = 96 и меньше, чем Ф(n):
е = 5.
Определить d так, чтобы d·e ≡ 1 mod 96 и d < 96:
d = 77, так как 77·5 = 385 = 4·96 + 1.
Результирующие ключи:
открытый ключ (5, 119) и закрытый ключ (77, 119).
Например, требуется зашифровать сообщение М = 19:
195 = 66 (mod 119); С = 66.
Для дешифрования вычисляется 6677 (mod 119) = 19.
Задание
I. Реализовать приложение, вычисляющее открытый и закрытый ключи для алгоритма RSA.
1. Числа p и q генерируются программой или задаются из файла.
2. Сгенерированные ключи сохраняются в файлы: открытый ключ (е, n) в один файл, закрытый (d, n) в другой.
II. Реализовать приложение, позволяющее шифровать данные по алгоритму RSA.
1. Шифруемый текст должен храниться в одном файле, а открытый ключ – в другом.
2. Зашифрованный текст должен сохраняться в файле.
3. Требования к приложению:
· в процессе шифрования предусмотреть возможность просмотра и изменения шифруемого текста в двоичном, восьмеричном, шестнадцатеричном и символьном виде;
· должно измеряться время, в течение которого происходит шифрование по алгоритму RSA;
· программа должна уметь работать с текстом произвольной длины, при этом размер блока шифруемого текста k определяется в зависимости от n.
III. Реализовать приложение, позволяющее дешифровать данные по алгоритму RSA.
1. Зашифрованный текст должен храниться в одном файле, а закрытый ключ – в другом.
2. Расшифрованный текст должен сохраняться в файл.
3. В процессе дешифрования предусмотреть возможность просмотра и изменения зашифрованного текста в двоичном, восьмеричном, шестнадцатеричном и символьном виде.
IV. С помощью реализованных приложений выполнить следующие задания.
1. Протестировать правильность работы разработанных приложений.
2. Сделать выводы о проделанной работе.
Требования к оформлению отчёта
Отчёт должен содержать:
· титульный лист (обязат.);
· задание на лабораторную работу (обязат.);
· описание разработанного программного средства;
· описание проведённых исследований, построенные графики лавинного эффекта (обязат.);
· программный код, написанный непосредственно студентами (обязат.);
· тестирование программы.
Отчёт не должен содержать орфографических, пунктуационных и смысловых ошибок.
Все его разделы должны быть выдержаны в едином стиле оформления.
Критерии оценивания качества работы
1. Наглядность приложений:
1 – приложения позволяют просматривать и изменять шифруемый и зашифрованный тексты во всех предусмотренных заданием представлениях;
0 – приложения позволяют просматривать ключи, шифруемый и зашифрованный тексты в любых двух представлениях;
Л. р. не принимается – иначе.
2. Выполнение требований к оформлению отчёта:
1 – отчёт удовлетворяет всем требованиям;
0 – отчёт не удовлетворяет всем требованиям, но содержит обязательные разделы;
Л. р. не принимается – в отчёте нет хотя бы одного обязательного раздела.
3. Обработка ошибок:
1 – все возможные ошибки и нестандартные ситуации (например, неудачная попытка открытия файла) обрабатываются программой, которая выдаёт соответствующее сообщение;
0 – не все возможные ошибки обрабатываются программой.
4. Применение принципов структурного программирования:
1 – все повторяющиеся либо логически целостные фрагменты программы выделены в качестве функций; работа каждой функции полностью определяется её параметрами (т. е. не используются глобальные переменные, все данные, нужные функции для работы, передаются ей через параметры); программа позволяет без перекомпиляции изменять все параметры, от которых зависит её работа; в тексте программы отсутствуют числовые константы (все необходимые константы объявляются как поименованные);
0 – иначе (не выполняется что-либо из перечисленного).
5. Наличие комментариев в тексте программы:
1 – комментариев достаточно для документирования исходных кодов;
0 – комментариев недостаточно.
6. Глубина понимания материала лабораторной работы каждым членом бригады:
1 – быстрые и правильные ответы на все вопросы;
0 – не на все вопросы ответы правильные и быстрые.
Л. р. не принимается – на половину вопросов ответы неправильные.
Контрольные вопросы
1. Дайте определение алгоритма с открытым ключом.
2. Какие этапы содержит алгоритм RSA?
3. В чем заключается вычисление ключей алгоритма RSA?
4. Как происходит шифрование в алгоритме RSA?
5. Как происходит дешифрование в алгоритме RSA?
