Основы информационной безопасности

Лекция 8. Криптографическая система RSA
План лекции:
2. Алгоритм шифрования RSA
1. Введение
3. Расшифрование RSA
4. Особенности применения криптографической системы RSA

Лекция 8. Криптографическая система RSA
1. Введение
RSA – криптографическая система открытого ключа, обеспечивающая такие механизмы защиты как шифрование и аутентификация – установление подлинности. Криптосистема RSA разработана в 1977 году и названа в честь ее разработчиков: Rivest, Shamir и Adleman.
На данный момент асимметричное шифрование на основе открытого ключа RSA использует большинство продуктов на рынке информационной безопасности.

Лекция 8. Криптографическая система RSA
Его криптостойкость основывается на сложности разложения на множители больших чисел, а именно - на исключительной трудности задачи определить секретный ключ на основании открытого, так как для этого потребуется решить задачу о существовании делителей целого числа.
В настоящее время Лаборатория RSA рекомендует для обычных задач ключи размером 1024 бита, а для особо важных задач – 2048 битов.

Лекция 8. Криптографическая система RSA
2. Алгоритм шифрования RSA
Сгенерировать открытый и секретные ключи:
Возьмем два больших простых числа p и q.
Определим n как результат умножения p на q
n= p*q
Выберем случайное число, которое назовем d. Это число должно быть взаимно простым (не иметь ни одного общего делителя, кроме 1) с результатом умножения (p-1)*(q-1).

Лекция 8. Криптографическая система RSA
Определим такое число е (1< e < (p-1)*(q-1)), не имеющее общих делителей кроме 1 (взаимно простое) с числом (p-1)*(q-1), для которого является истинным следующее соотношение
(e*d) mod ((p-1)*(q-1))=1.
Назовем открытым ключом числа e и n, а секретным - d и n.

Лекция 8. Криптографическая система RSA
Разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа
M(i)=0,1,2..., n-1 ( т.е. только до n-1).
Зашифровать текст, рассматриваемый как последовательность чисел M(i) по формуле
C(i)=(M(i)e) mod n.

Лекция 8. Криптографическая система RSA
3. Расшифрование RSA
Чтобы расшифровать данные, используя секретный ключ {d, n}, необходимо выполнить следующие вычисления:
M(i) = (C(i)d) mod n.
В результате будет получено множество чисел M(i), которые представляют собой исходный текст.

Лекция 8. Криптографическая система RSA
Пример.
Рассмотрим небольшой пример, иллюстрирующий применение алгоритма RSA.
Пусть требуется зашифровать сообщение «САВ».
Для простоты будем использовать маленькие числа (на практике применяются гораздо большие). Пошагово проследим процессы шифрования и дешифрования.

Лекция 8. Криптографическая система RSA
1 шаг. Выберем p = 3 и q = 11.
2 шаг. Определим n = 3 * 11 = 33.
3 шаг. Найдем (p – 1)(q – 1) = 20. Следовательно, в качестве d можно взять число, взаимно простое с 20, напpимеp, d = 3.
4 шаг. Выберем число e. В качестве такого числа может быть взято любое число, для которого выполняется соотношение (e*3) mod 20 = 1, напpимеp 7.

Лекция 8. Криптографическая система RSA
5 шаг. Представим шифруемое сообщение как последовательность целых чисел в диапазоне от 0 до 32 (до n-1!). Буква А=1, В=2, С=3 с помощью отображения: А -> 1, В-> 2, С-> 3. Тогда исходное открытое сообщение принимает вид M = (3,1,2).
6 шаг. Зашифруем сообщение с помощью ключа {7, 33}:
s1 = (37) (mod 33) = 2187 (mod 33) = 9
s2 = (17) (mod 33) = 1 (mod 33) = 1
s3 = (27) (mod 33) = 128 (mod 33) = 29
Зашифрованное сообщение после этого примет вид S = (9, 1, 29).

Лекция 8. Криптографическая система RSA
Расшифруем полученное зашифрованное сообщение (9, 1, 29) на основе секретного ключа {3, 33}:
m1 = (93) (mod 33) = 729 (mod 33) = 3,
m2= (13) (mod 33) = 1 (mod 33) = 1,
m3 = (293) (mod 33) = 24389 (mod 33) = 2.
Как можем видеть, дешифрование шифртекста S = (9, 1, 29) привело к исходному открытому тексту M = (3, 1, 2).

Лекция 8. Криптографическая система RSA
Замечание. Делители p и q можно уничтожить или сохранить вместе с секретным ключом.
Если бы существовали эффективные методы разложения на сомножители, то, разложив n на сомножители p и q, можно было бы получить секретный ключ d.
Таким образом, надежность криптосистемы RSA основана на трудноразрешимой (практически неразрешимой) задаче разложения n на сомножители, так как в настоящее время эффективного способа поиска сомножителей не существует.

Лекция 8. Криптографическая система RSA
4. Особенности применения криптографической системы RSA
Криптосистема RSA может использоваться для подтверждения подлинности или идентификации. Это возможно потому, что каждый зарегистрированный пользователь криптосистемы имеет свой уникальный секретный ключ, который (теоретически) больше никому недоступен. Именно это делает возможным положительную и уникальную идентификацию.

Лекция 8. Криптографическая система RSA
Скорость работы алгоритма RSA.
Как при шифровании и расшифровке, так и при создании и проверке подписи алгоритм RSA по существу состоит из возведения в степень, которое выполняется как ряд умножений.
В практических приложениях для открытого ключа обычно выбирается относительно небольшой показатель (e), а зачастую группы пользователей используют один и тот же открытый показатель (e), но каждый с различным модулем.

Лекция 8. Криптографическая система RSA
При этом шифрование данных идет быстрее чем расшифровка, а проверка подписи – быстрее чем подписание.
Алгоритм RSA намного медленнее чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее по крайней мере в 100 раз и от 1000 до 10000 – в аппаратной реализации (в зависимости от конкретного устройства).

Лекция 8. Криптографическая система RSA
Процесс создания RSA 1024-битовой пары ключей и сохранение ключа в ключевой набор базовых поставщиков службы криптографии Microsoft Cryptographic Provider v1.0 BobKeys

Лекция 8. Криптографическая система RSA
Способы взлома криптосистемы RSA.
Существует несколько способов взлома RSA. Наиболее эффективная атака: найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом и подделывать подписи.

Лекция 8. Криптографическая система RSA
Такую атаку можно провести, найдя главные сомножители общего модуля n – p и q. На основании p, q и e, нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей n; безопасность RSA зависит от разложения на сомножители.
Фактически, задача восстановления секретного ключа эквивалентна задаче разложения на множители модуля: можно использовать d для поиска сомножителей n, и наоборот, можно использовать n для поиска d.

Лекция 8. Криптографическая система RSA
Усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.
Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из С(mod n).

Лекция 8. Криптографическая система RSA
Поскольку C(i)=(M(i)e) mod n, то корнем степени e из С (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом.
Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

Лекция 8. Криптографическая система RSA
Рекомендуемая длина ключа.
Размер ключа в алгоритме RSA связан с размером модуля n. Два числа p и q, произведением которых является модуль, должны иметь приблизительно одинаковую длину, поскольку в этом случае найти сомножители сложнее, чем в случае когда длина чисел значительно различается. Например, если предполагается использовать 768-битный модуль, то каждое число должно иметь длину приблизительно 384 бита.

Лекция 8. Криптографическая система RSA
Если два числа чрезвычайно близки друг к другу или их разность близка к некоторому предопределенному значению, то возникает потенциальная угроза безопасности, однако такая вероятность – близость двух случайно выбранных чисел – незначительна.
Как доказано Эвклидом более двух тысяч лет назад, существует бесконечное множество простых чисел. Поскольку алгоритм RSA оперирует с ключами определенной длины, то количество возможных простых чисел конечно, хотя и очень велико.

Лекция 8. Криптографическая система RSA
По теореме о Простых Числах количество простых чисел, меньших некоторого n приближается к n = ln(n).
Следовательно, количество простых чисел для ключа длиной 512 битов или меньше приблизительно составляет 10150. Это больше, чем количество атомов в известной Вселенной.

Лекция 8. Криптографическая система RSA
Контрольные вопросы:
1. На чем основывается криптостойкость RSA?
2. Сформулировать алгоритм шифрования RSA.
3. Каковы сравнительные характеристики RSA и DES-алгоритма?
4. Дать краткое описание способов взлома RSA.
5. Какова рекомендуемая длина ключа RSA?

Список используемых источников:
Бубнов А.А. Основы информационной безопасности. – М.: Академия, 2017. - 256 с.
Ерохин В.В. Безопасность информационных систем. - М. : Флинта, 2016. - 184 с.
Гашков С.Б. Криптографические методы защиты информации. - М.: Академия, 2010. - 300с.
Мельников В.П. Информационная безопасность. – М.: Академия, 2013. - 336 с.