Автор работы: Пользователь скрыл имя, 19 Октября 2015 в 21:26, курсовая работа
Криптосистема RSA предложена Ривестом (R. Rivest), Шамиром (A. Shamir), Адлеманом (L. Adleman) в 1977 г. Предназначена как для цифровой подписи, так и для шифрования. Данная криптосистема используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании THALES (Racal).
ОБЗОР МЕТОДОВ ВСКРЫТИЯ КРИПТОСИСТЕМЫ RSA
Курсовой проект
студента 2 курса
дневной формы обучения
группы 427
Ивацевича Владимира Анатольевича
Научный руководитель:
Малашук Сергея Фёдоровича
ОГЛАВЛЕНИЕ
Криптосистема RSA предложена Ривестом (R. Rivest), Шамиром (A. Shamir), Адлеманом (L. Adleman) в 1977 г. Предназначена как для цифровой подписи, так и для шифрования. Данная криптосистема используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании THALES (Racal). Кроме того, криптосистема RSA широко применяется в составе различных стандартов и протоколов Internet, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.
ГЛАВА 1 ОБЩИЕ СВЕДЕНИЯ КРИПТОСИСТЕМЫ 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.
RSA многие годы противостоит интенсивному криптоанализу. Криптостойкость основана на трудоемкости разложения на множители (факторизации) больших чисел. Открытый и секретный ключи являются функциями двух больших (100 ~ 200 двоичных разрядов или даже больше) простых чисел. Предполагается, что задача восстановления открытого текста по шифротексту и открытому ключу эквивалентна задаче факторизации.
Для генерации парных ключей
берутся два больших случайных простых
числа p и q. В целях максимальной
криптостойкости p и q выбираю
Наконец расширенный алгоритм
Евклида используется для вычисления
ключа дешифрования d, такого, что ed=1 mod f(n). Число d
Таблица 1.
Открытый ключ: (public) |
n- произведение друз простых чисел p иq (должны храниться в секрете); e – число, взаимно простое с f(n) |
Секретный ключ: (private) |
d = e-1mod f(n) |
Шифрование: |
c = me mod n |
Дешифрование: |
m = cd mod n |
Числа 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, возможен любой выбор.
Методы "быстрого умножения" – например, методы основанные на Быстром Преобразовании Фурье (FFT – Fast Fourier Transform) – выполняются меньшим количеством шагов; тем не менее они не получили широкого распространения из-за сложности программного обеспечения, а также потому, что с типичными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования, реализующих алгоритм RSA быстро увеличиваются.
Алгоритм RSA намного медленнее, чем DES и другие алгоритмы блокового шифрования. Программная реализация DES работает быстрее, по крайней мере, в 100 раз и от 1,000 до 10,000 – в аппаратной реализации (в зависимости от конкретного устройства). Благодаря ведущимся разработкам, работа алгоритма 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 будет три или более делителей. Соответственно некоторые делители будут меньше рекомендованной величины, что, в свою очередь открывает возможности для атаки путем факторизации модуля. Другая опасность заключается в генерации псевдопростых чисел (чисел Кармайкла), удовлетворяющих тестам на простоту, но при этом не являющихся простыми. Однако вероятность генерации таких чисел пренебрежимо мала. На практике, последовательно применяя набор различных тестов на простоту, можно свести вероятность генерации составного числа до необходимого минимума.
ГЛАВА 2 МЕТОДЫ ВСКРЫТИЯ КРИПТОСИСТЕМЫ RSA
Существует несколько способов взлома RSA.
Наиболее эффективная атака: найти частный (private) ключ, соответствующий необходимому открытому (public) ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n – p и q. На основании p, q и e (общий показатель), нападающий может легко вычислить частный показатель d. Основная сложность – поиск главных сомножителей (факторинг) n; безопасность RSA зависит от разложения на сомножители (факторинга), что является трудноразрешимой задачей, не имеющей эффективных способов решения.
Фактически, задача восстановления частного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот можно использовать n для поиска d. Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы.
Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку c = me(mod n), то корнем степени e из (mod n) является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако, в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки – единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.
Существуют и другие типы атак, позволяющие, однако, вскрыть только одно сообщение и не позволяющие нападающему вскрыть прочие сообщения, зашифрованные тем же ключом.
Самое простое нападение на единственное сообщение – атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст, например, "Нападение на рассвете", затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака единственного сообщения применяется в том случае, если кто-то посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение M. Такую атаку можно предотвратить, вводя в сообщение перед каждым шифрованием несколько случайных бит. Также существуют несколько атак по зашифрованному тексту (или атаки отдельных сообщений с целью подделки подписи), при которых нападающий создает некоторый зашифрованный текст и получает соответствующий открытый текст, например, заставляя обманным путем зарегистрированного пользователя расшифровать поддельное сообщение.
Разумеется, существуют и атаки нацеленные не на криптосистему непосредственно, а на уязвимые места всей системы коммуникаций в целом; такие атаки не могут рассматриваться как взлом RSA, так как говорят не о слабости алгоритма RSA, а скорее об уязвимости его конкретной реализации. Например, нападающий может завладеть частным ключом, если тот хранится без должных предосторожностей. Необходимо подчеркнуть, что для полной защиты недостаточно защитить выполнение алгоритма RSA и принять меры вычислительной безопасности, то есть использовать ключ достаточной длины.
Некоторые атаки используют уязвимость криптографического протокола. Важно понимать, что само по себе использование RSA не обеспечивает требуемого уровня безопасности системы. Рассмотрим несколько сценариев.
Злоумышленнику удалось перехватить сообщение c, зашифрованное с помощью открытого RSA-ключа Алисы. Он хочет прочитать сообщение. Для раскрытия m = сd он сначала выбирает первое случайное число r, меньшее n, и затем, воспользовавшись открытым ключом Алисы е, вычисляет
x = re mod n,
y = xc mod n,
t = r-1 mod n.
Если х = re mod n , то r= xdmod n
Далее злоумышленник вынуждает Алису подписать сообщение y. Таким образом, процедура вычисления подписи на секретном ключе соответствует процедуре дешифрования сообщения y. (Отметим, что Алиса должна подписать сообщение, а не значение хэш-функции.) Такой обман вполне реален, так как Алиса никогда раньше не видела y. Алиса посылает злоумышленнику
u = yd mod n
Теперь злоумышленник раскрывает m, вычисляя
tu mod n =r-1yd mod n = r-1 xdcd mod n =cd mod n = m
Если Алиса хочет заверить документ,
она посылает его нотариусу. Нотариус
подписывает его цифровой подписью и отправляет
обратно. (Хеш-функции не используются,
нотариус шифрует все сообщение на своем
секретном ключе.) Злоумышленник хочет,
чтобы нотариус подписал такое сообщение,
которое в обычном случае тот никогда
не подпишет. Это может быть фальшивая
временная метка, либо автором этого сообщения
может являться другое лицо. Какой бы ни
была причина, нотариус никогда не подпишет
это сообщение, если у него будет возможность
выбора. Назовем это сообщение т'. Сначала злоумышленник
выбирает произвольное значение х и вычисляет у = xе mod п. Параме