Лисп-реализация алгоритма кодирования информации RSA (стр. 1 из 2)
Введение
1. Постановка задачи
2. Математические и алгоритмические основы решения задачи
3. Функциональные модели и блок-схемы решения задачи
4. Программная реализация решения задачи
5. Пример выполнения программы
Заключение
Список использованных источников и литературы
Введение
Испокон веков не было ценности большей, чем информация. ХХ век – век информатики и информатизации. Технология дает возможность передавать и хранить все большие объемы информации. Это благо имеет и оборотную сторону. Информация становится все более уязвимой по разным причинам:
• возрастающие объемы хранимых и передаваемых данных;
• расширение круга пользователей, имеющих доступ к ресурсам ЭВМ, программам и данным;
• усложнение режимов эксплуатации вычислительных систем.
Поэтому все большую важность приобретает проблема защиты информации от несанкционированного доступа (НСД) при передаче и хранении. Сущность этой проблемы – постоянная борьба специалистов по защите информации со своими «оппонентами».
Для того чтобы ваша информация, пройдя шифрование, превратилась в «информационный мусор», бессмысленный набор символов для постороннего, используются специально разработанные методы – алгоритмы шифрования. Такие алгоритмы разрабатываются учеными математиками или целыми коллективами сотрудников компаний или научных центров.
Алгоритмы шифрования делятся на два больших класса: симметричные (AES, ГОСТ, Blowfish, CAST, DES) и асимметричные (RSA, El-Gamal). Симметричные алгоритмы шифрования используют один и тот же ключ для зашифровывания информации и для ее расшифровывания, а асимметричные алгоритмы используют два ключа – один для зашифровывания, другой для расшифровывания.
Если зашифрованную информацию необходимо передавать в другое место, то в этом надо передавать и ключ для расшифрования. Слабое место здесь – это канал передачи данных – если он не защищенный или его прослушивают, то ключ для расшифрования может попасть к злоумышленику. Системы на ассиметричных алгоритмах лишены этого недостатка. Поскольку каждый участник такой системы обладает парой ключей: Открытым и Секретным Ключом.
Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исследователями – математиками Рональдом Ривестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Адльманом (L. Adleman) в 1977–78 годах.
1. Постановка задачи
Разработать и отладить программу на языке Лисп реализующую криптографический алгоритм кодирования информации с открытым ключом – RSA.
Шифрование:
Входные данные: M – сообщение, состоящее из целых чисел.
Выходные данные: T – Зашифрованное сообщение.
Дешифрование:
Входные данные: T – Результат шифрования.
Выходные данные: M – изначальное сообщение.
Пример 1.
1. Выбираем два простых числа: p = 3557, q = 2579.
2. Вычисляем их произведение: n = p · q = 3557 · 2579 = 9173503.
3. Вычисляем функцию Эйлера: φ(n) = (p-1) (q-1) = 9167368.
4. Выбираем открытый показатель: e = 3.
5. Вычисляем секретный показатель: d = 6111579.
6. Публикуем открытый ключ: (e, n) = (3, 9173503).
7. Сохраняем секретный ключ: (d, n) = (6111579, 9173503).
8. Выбираем открытый текст: M = 127.
9. Вычисляем шифротекст: P(M) = Memodn= 10223mod 9173503 = 116.
10.Вычислить исходное сообщение: S(C) = Cdmodn= 1166111579mod 9173503 = 1022.
Пример 2.
1. Выбираем два простых числа: p = 79, q = 71.
2. Вычисляем их произведение: n = p · q = 79 · 71 = 5609.
3. Вычисляем функцию Эйлера: φ(n) = (p-1) (q-1) = 5460.
4. Выбираем открытый показатель: e = 5363.
5. Вычисляем секретный показатель: d = 2927.
6. Публикуем открытый ключ: (e, n) = (5363, 5609).
7. Сохраняем секретный ключ: (d, n) = (2927, 5609).
8. Выбираем открытый текст: M = 23.
9. Вычисляем шифротекст: P(M) = Memodn= 235363mod5609 = 5348.
10.Вычислить исходное сообщение: S(C) = Cdmodn= 53482927mod5609 = 23.
2. Математические и алгоритмические основы решения задачи
Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа «по всему миру». Для алгоритма RSA этап создания ключей состоит из следующих операций:
1). Выбираются два простых числа p и q
2). Вычисляется их произведение n (=p*q)
3). Выбирается произвольное число e (e<n), такое, что
НОД (e, (p-1) (q-1))=1,
то есть e должно быть взаимно простым с числом (p-1) (q-1).
4). Методом Евклида решается в целых числах уравнение
e*d+(p-1) (q-1)*y=1.
Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах.
5). Два числа (e, n) – публикуются как открытый ключ.
6). Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e, n).
Как же производится собственно шифрование с помощью этих чисел:
Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.
Подобный блок может быть интерпретирован как число из диапазона (0; 2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение
ci=((mi)e) mod n.
Блоки ci и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название «логарифмирование в конечном поле» и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.
А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство
(x(p-1)(q-1)) mod n = 1.
Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень
(-y): (x(-y)(p-1)(q-1)) mod n = 1(-y) = 1.
Теперь умножим обе ее части на x:
(x(-y)(p-1)(q-1)+1) mod n = 1*x = x.
А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что
e*d+(p-1) (q-1)*y=1,
то есть
e*d=(-y) (p-1) (q-1)+1.
Следовательно, в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем
(xe*d) mod n = x.
То есть для того чтобы прочесть сообщение ci=((mi)e) mod n достаточно возвести его в степень d по модулю m:
((ci)d) mod n = ((mi)e*d) mod n = mi.
На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла.
Скорость работы алгоритма RSA
Как при шифровании и расшифровке, так и при создании и проверке подписи алгоритм RSA по существу состоит из возведения в степень, которое выполняется как ряд умножений.
В практических приложениях для открытого (public) ключа обычно выбирается относительно небольшой показатель, а зачастую группы пользователей используют один и тот же открытый (public) показатель, но каждый с различным модулем. (Если открытый (public) показатель неизменен, вводятся некоторые ограничения на главные делители (факторы) модуля.) При этом шифрование данных идет быстрее чем расшифровка, а проверка подписи – быстрее чем подписание.
Если k – количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов необходимых для выполнения операции с открытым (public) ключом пропорционально второй степени k, количество шагов для операций частного (private) ключа – третьей степени k, количество шагов для операции создания ключей – четвертой степени k.
Методы «быстрого умножения» – например, методы основанные на Быстром Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования реализующих алгоритм RSA быстро увеличиваются.
Алгоритм RSA намного медленнее чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее по крайней мере в 100 раз и от 1,000 до 10,000 – в аппаратной реализации (в зависимости от конкретного устройства). Благдаря ведущимся разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блокового шифрования.
3. Функциональные модели и блок-схемы решения задачи
Функциональные модели и блок-схемы решения задачи представлены на рисунках 1 – 6.
Условные обозначения:
· P и Q – случайные простые числа;
· N – произведение простых чисел P и Q;
· PHI – значение функции Эйлера;
· E – взаимно простое число с PHI;
· PRIVATE_KEY – секретный ключ;
· LST – список простых чисел;
· NUM – число для шифрования / дешифрования;
· I, IO, I1, J, JO, R, L – рабочие переменные.
Рисунок 1 – Функциональная модель решения задачи для функции SIMPLE_NUMBER
Рисунок 2 – Функциональная модель решения задачи для функции ENCRYPT
Рисунок 3 – Функциональная модель решения задачи для функции DECODING