Лабораторная работа №3

1.

Лабораторная работа № 3
Программная реализация
ассиметричного алгоритма шифрования
RSA.
Время: 2 лабораторных занятия (4 часа)
В ходе лабораторной работы необходимо реализовать алгоритм ассиметричного
шифрования RSA с помощью какого-либо языка программирования (без использования
встроенных средств шифрования языка программирования). Программа должна
вычислять числа n, φ(n), e, d, осуществлять шифрование и расшифровку по
приведенному выше алгоритму, вывод на экран незашифрованного, зашифрованного
и расшифрованного сообщения, открытый и закрытые ключи, а также число φ(n).
Ссылка на страницу лабораторной:
https://edu.vsu.ru/mod/assign/view.php?id=215237
Варианты ключей выбираются согласно списку группы.

2.

Системы шифрования с открытым ключом
Слабое место любой криптографической системы - проблема распределения ключей. Для того,
чтобы был возможен обмен конфиденциальной информацией между двумя субъектами, ключ
должен быть сгенерирован одним из них, а затем каким-то образом опять же в конфиденциальном
порядке передан другому. Т.е. в общем случае для передачи ключа опять же требуется
использование какой-то криптосистемы.
Для решения этой проблемы на основе результатов, полученных классической и современной
алгеброй, были предложены системы с открытым ключом (СОК). Суть их состоит в том, что каждым
адресатом генерируются два ключа, связанные между собой по определенному правилу. Один
ключ объявляется открытым, а другой закрытым. Открытый ключ публикуется и доступен любому,
кто желает послать сообщение адресату. Секретный ключ сохраняется в тайне.
Исходный текст шифруется открытым ключом адресата и передается ему. Зашифрованный текст в
принципе не может быть расшифрован тем же открытым ключом. Дешифрование сообщение
возможно только с использованием закрытого ключа, который известен только самому адресату.
Криптографические системы с открытым ключом используют так называемые необратимые или
односторонние функции, которые обладают следующим свойством: при заданном значении x
относительно просто вычислить значение f(x), однако если y=f(x), то нет простого пути для
вычисления значения x.
Под необратимостью понимается не теоретическая необратимость, а практическая невозможность
вычислить обратное значение используя современные вычислительные средства за обозримый
интервал времени.

3.

Системы шифрования с открытым ключом
Для того чтобы гарантировать надежную защиту информации, к системам с открытым ключом
предъявляются два важных и очевидных требования:
1. Преобразование исходного текста должно быть необратимым и исключать его восстановление
на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть невозможным на
современном технологическом уровне. При этом желательна точная нижняя оценка сложности
(количества операций) раскрытия шифра.
Алгоритмы шифрования с открытым ключом получили широкое распространение в современных
информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых
систем.
Вообще же все предлагаемые сегодня криптосистемы с открытым ключом опираются на один из
следующих типов необратимых преобразований:
-Разложение больших чисел на простые множители.
-Вычисление логарифма в конечном поле.
-Вычисление корней алгебраических уравнений.
Алгоритмы СОК более трудоемки, чем традиционные криптосистемы. Поэтому часто на практике
рационально с их помощью распределять ключи, объем которых как информации незначителен.
А потом с помощью обычных алгоритмов осуществлять обмен большими информационными
потоками.

4.

Преимущества и недостатки СОК
Преимущества асимметричных шифров перед симметричными:
- не нужно предварительно передавать секретный ключ по надёжному каналу;
- только одной стороне известен ключ дешифрования, который нужно держать в секрете (в
симметричной криптографии такой ключ известен обеим сторонам и должен держаться в секрете
обеими);
- в больших сетях число ключей в асимметричной криптосистеме значительно меньше, чем в
симметричной.
Недостатки алгоритма несимметричного шифрования в сравнении с симметричным:
- в алгоритм сложнее внести изменения;
- более длинные ключи — например, ключ для алгоритма шифрования RSA длинной в 2304 бит
будет соответствовать ключу симметричного алгоритма длиной всего лишь 128 бит аналогичной
криптостойкости;
- шифрование-расшифровывание с использованием пары ключей проходит на два-три порядка
медленнее, чем шифрование-расшифрование того же текста симметричным алгоритмом;
- требуются существенно бо́льшие вычислительные ресурсы, поэтому на практике
асимметричные криптосистемы используются в сочетании с другими алгоритмами. Таким
образом для шифрования они используются в форме гибридных криптосистем, где большие
объёмы данных шифруются симметричным шифром на сеансовом ключе, а с помощью
асимметричного шифра передаётся только сам сеансовый ключ.

5.

Алгоритм шифрования RSA
(аббревиатура от фамилий Rivest, Shamir и Adleman)
Несмотря на довольно большое число различных СОК, наиболее популярна криптосистема
RSA, разработанная в 1977 году и получившая название в честь ее создателей: Рона Ривеста ,
Ади Шамира и Леонарда Эйдельмана. Они воспользовались тем фактом, что нахождение
больших простых чисел в вычислительном отношении осуществляется легко, но разложение
на множители произведения двух таких чисел практически невыполнимо.
Доказано, что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой
длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом
производительности современных компьютеров оценить и необходимое на это время.
Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин
популярности этой СОК на фоне десятков других схем.
В 2010 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США
удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа
стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось общим
методом решета числового поля. По словам исследователей, после их работы в качестве
надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и
более.
В настоящее время алгоритм RSA широко используется в банковских компьютерных сетях,
особенно для работы с удаленными клиентами (обслуживание кредитных карточек).
Указанный алгоритм используется во многих стандартах, среди которых SSL, S-HHTP, S-MIME,
S/WAN, STT и PCT, а также в системах электронной цифровой подписи (ЭЦП).

6.

Схема шифрования по алгоритму RSA
Схема шифрования выглядит следующим образом:
1. Выбираются два простых числа p и q . (Например, p=7 и q=17).
2. Вычисляется n = p٠q. (n = 119).
3. Определяется φ(n)=(p – 1)(q – 1). (φ(n)=96).
4. По алгоритму Евклида вычисляем наименьшее число e как взаимно простого с
φ(n), причем e < φ(n). (e = 5).
5. Вычисляется d = e-1 mod φ(n)
(Определяется такое d, что (d٠e) mod 96 = 1 и e < 96.
Соответствующим значением будет d = 77, так как 77٠5 = 385 = 4٠96+1).
6. Открытым ключом является {e, n}. ({e, n}={5, 119}).
7. Закрытым ключом является {d, n}. ({d, n}={77, 119}).
8. Шифрование C = Memod n
9. Дешифрование M = Cdmod n

7.

Немного о сложностях
На самом деле, изложенный способ шифрования очень слаб и никогда не используется.
Причина проста — шифрование по буквам. Одна и та же буква будет шифроваться одним и тем
же числом. Если злоумышленник перехватит достаточно большое сообщение, он сможет
догадаться о его содержимом. Таким образом, злоумышленнику не придётся отгадывать ваши
секретные ключи. Он взломает ваше сообщение, не зная их.
Чтобы этого не происходило, используются специальные дополнительные алгоритмы, суть
которых в том, что каждая предыдущая часть сообщения начинает влиять на следующую.
Упрощённо, это выглядит так.
Перед шифрованием, мы применяем к сообщению правило: b := (b + a) mod n.
Где a — предыдущая часть сообщения, а b — следующая.
Допустим у нас есть наше сообщение (11, 17, 15, 19). Оно изменится следующим образом:
11 остаётся без изменений. 17 превращается в (11 + 17) mod 119 = 28.
15 становится (15 + 28) mod 119 = 43. A 19 превращается в 62.
Последовательность (11, 28, 43, 62) получается «запутанной». Все буквы в ней как бы
перемешаны, в том смысле, что на каждый код влияет не одна буква, а все предыдущие.
Тот, кто получит ваше сообщение, должен будет проделать обратную операцию, со знаком
«минус»: b := (b - a) mod n. И только тогда он получит коды букв.

8.

Немного о сложностях
На практике, в исходное сообщение специально добавляются случайные и бессмысленные
буквы в начало. Чтобы даже по первому коду было невозможно ничего понять. Получатель
просто отбрасывает начало сообщения.
То есть мы можем добавить случайное число в начало и получить (299, 11, 17, 15, 19). После
перемешивания получится: 299, 72, 89, 104, 4. После шифрования уже невозможно будет
догадаться где была какая буква.
В реальной жизни всё ещё немного сложнее. Блоки, на которые бьётся сообщение длиннее
одной буквы. Поэтому, сперва применяются алгоритмы выравнивания, потом алгоритмы
разбиения на блоки с перепутыванием, и только потом применяется само RSA-шифрование.
Получатель делает всё в обратном порядке: расшифровывает, «распутывает» блоки и
отбрасывает ненужную информацию, добавленную просто для выравнивания (чтобы
сообщение можно было разбить на целое число блоков).