Обзор методов вскрытия криптосистемы RSA

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ ЭЛЕКТРОНИКИ И МАТЕМАТИКИ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

Курсовая работа по криптографии

«ОБЗОР МЕТОДОВ ВСКРЫТИЯ КРИПТОСИСТЕМЫ RSA»

МОСКВА 2003

КРИПТОСИСТЕМА RSA.............................................................................................................. 2

1. Немного истории................................................................................................................ 2

2. Стандарты безопасности применяющие RSA................................................................. 3

3. Описание криптосистемы................................................................................................. 4

4. Скорость работы алгоритма RSA...................................................................................... 5

5. Криптостойкость RSA....................................................................................................... 6

СПОСОБЫ ВЗЛОМА КРИПТОСИСТЕМЫ RSA....................................................................... 6

Атака на основе выборочного шифротекста...................................................................... 8

Сценарий 1............................................................................................................................. 8

Сценарий 2............................................................................................................................. 8

Сценарий 3............................................................................................................................. 9

Атака на основе общего RSA-модуля.................................................................................... 9

Атака «шифрование коротких сообщений»...................................................................... 10

Раскрытие малого показателя…......................................................................................... 10

1. шифрования...................................................................................................................... 10

2. дешифрования................................................................................................................... 11

Атака на протокол................................................................................................................ 11

ПРАКТИЧЕСКАЯ КРИПТОСТОЙКОСТЬ RSA: ОЦЕНКИ И ПРОГНОЗЫ........................... 11

РАЗБАЛАНСИРОВАННАЯ RSA................................................................................................ 18

ПАКЕТНАЯ RSA.......................................................................................................................... 23

РЕКОМЕНДУЕМАЯ ДЛИНА КЛЮЧА...................................................................................... 23

ИТОГИ........................................................................................................................................... 25

ЛИТЕРАТУРА:.............................................................................................................................. 26

Криптосистема RSA

1.      Немного истории

Данная криптосистема предложена Ривестом (R. Rivest), Шамиром (A. Shamir), Адлеманом (L. Adleman) в 1977 г. Предназначена как для цифровой подписи, так и для шифрования. Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании THALES (Racal). Кроме того,  криптосистема RSA широко применяется в составе  различных стандартов и протоколов Internet, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.

2.      Стандарты безопасности применяющие RSA

Криптосистема RSA – часть многих стандартов. Стандарт ISO 9796 описывает RSA как совместимый криптографический алгоритм, соответствующий стандарту безопасности ITU-T X.509. Кроме этого криптосистема RSA является частью стандартов SWIFT, ANSI X9.31 rDSA и проекта стандарта X9.44 для американских банков. Австралийский стандарт управления ключами AS2805.6.5.3 также включает систему RSA.

Алгоритм RSA используется в Internet, в частности он входит в такие протоколы как S/MIME, IPSEC (Internet Protocol Security) и TLS (которым предполагается заменить SSL), а также в стандарт PKCS, применяемый в важных приложениях. 
Для разработчиков приложений с применением PKCS организация OSI Implementers Workshop (OIW) выпустила соглашение, которое в частности посвящено алгоритму RSA.
Множество других разрабатываемых в настоящее время стандартов включают в себя либо сам алгоритм RSA или его поддержку либо рекомендуют криптосистему RSA для обеспечения секретности и/или установления подлинности (аутентификации). Например, включают в себя систему RSA рекомендации IEEE P1363 и WAP WTLS.

Технологию шифрования RSA BSAFE используют около 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего ключа в мире и это количество имеет явную тенденцию к увеличению по мере роста Internet.

3.      Описание криптосистемы

RSA многие годы противостоит интенсивному криптоанализу. Криптостойкость основана на трудоемкости разложения на множители (факторизации) больших чисел. Открытый и секретный ключи являются функциями двух больших (100 ~ 200 двоичных разрядов или даже больше) простых чисел. Предполагается, что задача восстановления открытого текста по шифротексту и открытому ключу эквивалентна задаче факторизации.

Для генерации парных ключей берутся два больших  случайных простых числа p и q. В целях максимальной криптостойкости p и q  выбираются равной длины. Затем  вычисляется их произведение n=pq (n называется модулем). Далее случайным образом выбирается число e (ключ шифрования), удовлетворяющее условию: 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое)    с числом f(n)=(p-1)*(q-1).

Наконец расширенный алгоритм Евклида используется для вычисления ключа дешифрования d, такого, что ed=1 mod f(n).   Число d  такое,  что    (ed - 1)   делится    на      (p - 1)(q–1).

Числа d и n  - также взаимно простые числа.

Числа e и n – открытый ключ, а d – секретный.

Два простых числа  p и q хранятся в секрете.

Для шифрования сообщения m необходимо выполнить его разбивку на блоки, каждый из которых меньше n (для двоичных данных выбирается самая большая степень числа 2, меньшая n). То есть если p и q  - 100 разрядные простые числа, то n будет содержать около 20 разрядов и каждый блок сообщения mi  должен иметь такое же число разрядов. Если же нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями слева, чтобы гарантировать, что блоки всегда будут меньше n. Зашифрованное сообщение с будет состоять из блоков ciтой же самой длины. Шифрование сводиться к вычислению

ci =mie mod n.

При дешифровании для каждого зашифрованного блока ci вычисляется

mi = cid mod n

Последнее справедливо, так как

cid = (mie)d = mied = mikf(n)+1 = mi·1 = mi

Все вычисления выполняются по mod n. Сообщение может быть зашифровано с помощью d, а дешифровано с помощью e, возможен любой выбор.

4.      Скорость работы алгоритма RSA

Как при шифровании/дешифровании, так и при создании и проверке подписи алгоритм RSA по существу состоит из возведения в степень, которое выполняется как ряд умножений.

В практических приложениях для открытого ключа обычно выбирается относительно небольшой показатель, а зачастую группы пользователей используют один и тот же открытый показатель, но каждый с различным модулем. (Если открытый показатель неизменен, вводятся некоторые ограничения на главные делители (факторы) модуля.) При этом шифрование данных идет быстрее, чем расшифровка, а проверка подписи – быстрее, чем подписание. Если k – количество битов в модуле, то в обычно используемых для RSA алгоритмах количество шагов необходимых для выполнения операции с открытым ключом пропорционально второй степени k, количество шагов для операций частного ключа – третьей степени k, количество шагов для операции создания ключей – четвертой степени k.

Методы "быстрого умножения" – например, методы основанные на Быстром Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования, реализующих алгоритм RSA быстро увеличиваются.

Алгоритм RSA намного медленнее, чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее, по крайней мере, в 100 раз и от 1,000 до 10,000 – в аппаратной реализации (в зависимости от конкретного устройства). Благодаря ведущимся разработкам, работа алгоритма RSA, вероятно, ускорится, но аналогично ускорится и работа алгоритмов блочного шифрования.

5.      Криптостойкость RSA

Предполагается, что криптостойкость RSA  зависит от проблемы разложения на множители больших чисел. Однако никогда не было доказано математически, что нужно n разложить на множители. Чтобы восстановить  m по с и e. Не  исключено, что может быть открыт совсем иной способ криптоанализа  RSA. Однако, если этот новый способ позволит криптоаналитику получить d , он также может быть использован для разложения на множители больших чисел. Также можно атаковать RSA, угадав значение (p-1)(q-1). Однако этот метод не проще разложения nна множители. При использовании RSA раскрытие даже нескольких битов информации по шифротексту не легче, чем дешифрование всего сообщения. Самой очевидной атакой на RSA является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрования  d, противник должен разложить n на множители. Криптоаналитик может перебирать все возможные d, пока не подберет правильное значение. Но подобная силовая атака даже  менее эффективна, чем попытка разложения n на множители. В 1993 г. был предложен метод криптоанализа, основанный на малой теореме Ферма. К сожалению, этот метод оказался медленнее  разложения на множители. Существует еще одна проблема. Большинство общепринятых тестов устанавливает простоту числа с некоторой вероятностью. Что произойдет если p или q окажется составным? Тогда у модуля n будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых  чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.

Способы взлома криптосистемы RSA

Существует несколько способов взлома RSA. Наиболее эффективная атака: найти частный (private) ключ, соответствующий необходимому открытому (public) ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель), нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n; безопасность RSA зависит от разложения на сомножители (факторинга), что является трудонразрешимой задачей, не имеющей эффективных способов решения.