Обзор методов вскрытия криптосистемы 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.

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

Некоторые атаки используют уязвимость криптографического протокола. Важно понимать, что само по себе использование RSA не обеспечивает требуемого уровня безопасности систе­мы. Рассмотрим несколько сценариев.

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

Злоумышленнику удалось перехватить сообщение 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

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

Если Алиса хочет заверить документ, она посылает его нотариусу. Нотариус подписыва­ет его цифровой подписью и отправляет обратно. (Хеш-функции не используются, нотариус шифрует все сообщение на своем секретном ключе.) Злоумышленник хочет, чтобы нота­риус подписал такое сообщение, которое в обычном случае тот никогда не подпишет. Это может быть фальшивая временная метка, либо автором этого сообщения может являться другое лицо. Какой бы ни была причина, нотариус никогда не подпишет это сообщение, если у него будет возможность выбора. Назовем это сообщение т'. Сначала злоумышлен­ник выбирает произвольное значение х и вычисляет у = xе mod п. Параметр e он может получить без труда — это открытый ключ нотариуса, и должен быть опубликован для про­верки подписи последнего. Теперь злоумышленник вычисляет m = ym mod n   и посылает m нотариусу на подпись. Нотариус возвращает md mod n. Далее злоумышленник вычисляет    (md mod n)x-1 mod n, которое равно m¢ d mod n и является подписью m'. На самом деле у злоумышленника есть множество различных способов решения подобной задачи. Описанная атака основана на сохранении мультипликативной структуры арифметической операции возведения в степень:

(хт)d  mod п =xdmd  тоd п.

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

Злоумышленник хочет, чтобы Алиса подписала некое сообщение m3. Для этого он создает два сообщения, m1 и m2, такие, что m3 = m1m2 mod n. Если злоумышленник заставит Алису подписатьm1 и m2, то сможет вычислить подпись для m3:

m3d = (m1d mod n)(m2d mod n).

Отсюда вывод — никогда нельзя использовать RSA для подписи случайных документов. Применение хэш-функции в технологии RSA-подписи строго обязательно. Отметим, что специальный формат блоков стандарта ISO 9796 предотвращает подобную атаку.

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

При реализации RSA можно попробовать раздать всем абонентам криптосети одинаковый модуль n, но каждому — свои значения показателей степени e и d. При этом наиболее оче­видная проблема заключается в том, что если одно и то же сообщение когда-нибудь шифро­валось разными показателями степени (при фиксированном модуле) и эти два показателя — взаимно-простые числа (как обычно и бывает), то открытый текст может быть раскрыт даже при неизвестных ключах дешифрования. Пусть заданы: m — открытый текст, e1 и e2 — два ключа шифрования, n — общий модуль. Шифротекстами сообщения являются:

c1 = me1 mod n,

c2 = me2 mod n,

Криптоаналитик знает n, e1, e2, c1 и c2. Так как e1 и e2 — взаимно-простые числа, то, воспользовавшись расширенным алгоритмом Евклида, можно найти такие числа r и s, что

re1 + se2 = 1.

Полагая r отрицательным (или r, или s должно быть отрицательным), можно снова воспользоваться расширенным алгоритмом Евклида для вычисления c1-1. Тогда

(c1-1)-rc2s = m mod n.

Существует два других, более тонких метода раскрытия подобного типа. Один использует вероятностный метод для разложения n на множители. Другой — детерминированный алгоритм вычисления какого-нибудь секретного ключа без разложения модуля на множители. Таким образом, использование общего для группы пользователей параметра n может отрицательно сказаться на уровне безопасности криптосети.

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

Известно, что криптосистема RSA обладает низкой криптостойкостью при зашифрованном на малом e коротком сообщении. Действительно, при c = me < n открытый текст m может быть восстановлен по шифротексту c при помощи процедуры извлечения корня. Фактически подобная атака возможна и тогда, когда в процессе возведения в степень выполнялось неко­торое количество приведений по модулю. При c > n  трудоемкость такой атаки ниже трудоем­кости исчерпывающего перебора для m. Однако меры противодействия также очевидны, — либо открытый ключ e должен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого e обусловлен соображениями вычислительной эффективности шифрования и проверки подписи. Таким образом, разумный подход заключается в ис­кусственном наращивании коротких открытых текстов («набивки»). При этом необходимо следить за тем, чтобы удлиненный открытый текст при числовом отображении не превра­щался в набор множителей некоторого известного числа P, например  P = 2l, что происходит при дополнении открытого текста последовательностью нулей справа (со стороны младших разрядов).

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

9.      шифрования

Хэстед (J. Hasted) продемонстрировал уязвимость RSA при условии, если криптоаналитик  может получить множество шифротекстов фиксированного сообщения m, зашифрованного при помощи криптосистемы RSA с различными секретными параметрами  p и q, но при ис­пользовании фиксированного открытого ключа e. При соблюдении сформулированных условий можно раскрыть сообщение m. Известен частный случай, когда при заданных l раз­личных результатах шифрования me mod n1,…,me mod nl можно раскрыть m при помощи Китайской теоремы об остатках. В общем случае, при заданных t результатах шифро­вания

(a1m +b1)e mod n1,…,(atm + bt)e mod nt,

где ai и bi, заданы и  t > е(е+1)/2, можно раскрыть сообщение т, воспользовавшись известным математическим методом. Еще раз отметим, что данная атака возможна только при условии, что исходные сообщения получены известным криптоаналитику способом (фиксированное сообщение т является частным случаем).

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

Другая атака позволяет раскрывать d, когда d не превышает четверти размера n, а           e < n  . При случайном выборе e и d, это маловероятно и никогда не произойдет, если значение eмало. Значение d, должно быть большим.

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

При использовании RSA можно атаковать протокол, в котором сообщение шифруется, а за­тем подписывается. Предположим, Алиса желает послать сообщение Бобу. Сначала она шифрует сообщение на открытом ключе Боба, а затем подписывает на своем секретном клю­че. Зашифрованное и подписанное сообщение выглядит следующим образом:      

(meB mod nB)dA mod nA

Однако Боб может доказать, что Алиса послала ему m', а не m. Так как Бобу известно разложение на множители nB (это его собственный модуль), он может вычислить дискретные логарифмы по основанию nB. Следовательно, ему остается найти x, для которого

m¢x = m mod nB

Если он может опубликовать xeB в качестве своего нового открытого показателя степени и сохранить свой прежний модуль nB, он сможет утверждать, что Алиса послала ему сообще­ние m', зашифрованное на xeB. Применение хэш-функции не позволяет решить проблему. Однако ее можно решить путем использования фиксированного показателя шифрования для каждого пользователя криптосети.

Практическая криптостойкость RSA: оценки и прогнозы

Известно, что практическая криптостойкость RSA зависит от вычислительной трудоемкости задачи факторизации — разложения двусоставного модуля (произведение двух простых чи­сел) на сомножители. Факторизация модуля позволяет раскрыть секретный ключ и, как след­ствие, дешифровать любое сообщение, подделать цифровую подпись. Чем больше число, тем выше вычислительная трудоемкость факторизации. Необходимо отметить, что повышение производительности компьютеров положительно сказалось на успехах в области факториза­ции, но криптостойкость RSA при этом также возросла. Эффект объясняется различиями в вычислительной трудоемкости процедур факторизации и шифрования/дешифрования: в результате очередного скачка производительности число, поддающееся факторизации, уве­личивается на два разряда, тогда как RSA-модуль, без потери вычислительной эффективно­сти, — на двенадцать разрядов. Однако факторизация возможна в случае, если рост произ­водительности не учитывается при периодичности смены ключей.

Каким должен быть модуль RSA? Точный ответ вряд ли возможен — развитие методов целочисленной факторизации с трудом поддается прогнозированию. При этом нельзя полно­стью исключить возможность атак на основе иных, отличных от факторизации методов. Кро­ме того, вычислительная трудоемкость модульного возведения в степень (основной операции при шифровании/дешифровании) возрастает с увеличением разрядности модуля. Основная задача при выборе модуля К5А — одновременное обеспечение криптостойкости и вычисли­тельной эффективности процедуры шифрования/дешифрования. Таким образом, при выбо­ре модуля необходимо исходить из реальных оценок роста производительности компьютеров И достижений в области вычислительной теории чисел. Согласно оценкам , для обеспе­чения адекватного уровня практической криптостойкости разрядность модуля RSA должна быть увеличена в ущерб вычислительной эффективности. Однако идея разбалансированной RSA, предложенная Шамиром , позволяет этого избежать.

В настоящее время криптосистема RSA с модулем 512 бит, реализованная во многих крип­тографических приложениях, не гарантирует объявленной криптостойкости. Отметим, что в отличие от строгого обоснования низкой криптостойкости RSA с модулем 512 бит прогнозы на будущее менее конкретны; пока анализируются лишь тенденции роста производительно­сти компьютеров и возможные пути развития вычислительной теории чисел. Оценки опираются на предположение о последовательной природе криптографических алгоритмов и использовании стандартной технологии СБИС при их реализации. Ситуация может резко измениться, если исследования в области квантовых и молекулярных вычис­лений перейдут в практическую фазу.

В большинстве работ при оценке производительности используется единица                   MY (Mips/­Year). Данная единица измерения может быть истолкована следующим образом; компьютер с производительностью один миллион целочисленных инструкций в секунду (million instructions per second = mips) эквивалентен DEC VAX 11/780. тогда 1 MY — год работы VAX11/780. Для разрядности десятичных чисел введем обозначение число_десятичных_ разрядовD. Например, 43D — целое число из 43 десятичных разрядов.

Задача факторизации всегда привлекала внимание математиков. Фундаментальность про­блемы впервые была отмечена Гауссом. Одна из первых попыток (1874г.) ее практической постановки и оценки трудоемкости принадлежит английскому экономисту и логику Джевонсу (W.S. Jevons) , предполагавшему, что никому, кроме него, не удастся разложить на множители число 8 616 460 799 (10D). Однако в 1925 г. число было факторизовано:

8 616 460 799 = 96079 х 89681.

В 1967 г. факторизация числа 25D считалась практически нереализуемой . В 1970 году новый метод факторизации Моррисона-Бриллхарта (Morrison-Brillhart) позволил разложить седьмое число Ферма F7 = 2128 + 1 (39D). Барьер 80D, установленный в 1976 г. , был преодолен через пару лет. В 1977 г. профессор Ривест из Массачусетского технологическо­го университета привел убедительные аргументы в пользу выбора в качестве RSA-модуля числа 129D. Ривест предполагал, что для факторизации понадобится более 40 квадри­льонов             (4 х 1016) лет работы самого быстрого компьютера. Однако факторизация числа была выполнена в 1994 г. по алгоритму квадратичного решета (КР).