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

Далее злоумышленник вычисляет    (md mod n)x-1 mod n, которое равно m¢ d mod n и является подписью m'. На самом деле у злоумышленника есть множество различных способов решения подобной задачи. Описанная атака основана на сохранении мультипликативной структуры арифметической операции возведения в степень:

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

Сценарий 3.

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

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

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

2.2 Атака на основе общего 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 может отрицательно сказаться на уровне безопасности криптосети.

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

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

 

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

Шифрования

Хэстед (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, можно раскрыть сообщение т, воспользовавшись известным математическим методом.

Еще раз отметим, что данная атака возможна только при условии, что исходные сообщения получены известным криптоаналитику способом.

Дешифрования

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

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

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

(meB mod nB)dA mod nA

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

m¢x = m mod nB

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

 

 

 

ГЛАВА 3 КРИПТОСТОЙКОСТЬ 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 г. по алгоритму квадратичного решета (КР).

В целях развития математических методов факторизации корпорация RSA Data Security, Inc. объявила открытый конкурс на факторизацию RSA-модулей и учредила специальную денежную премию. В 1996 г. число RSA-130 (130D) было факторизовано при помощи алгоритма обобщенного числового решета (ОЧР). За счет применения алгоритма ОЧР эффективность факторизации RSA-130 возросла на порядок по сравнению с факторизацией числа RSA-129. Проект RSA-130 был коллективным.

К моменту факторизации RSA-130 четыре из объявленных ранее модулей были факторизованы при помощи алгоритма КР . Таким образом, возможность успешной атаки на криптосистемуRSA с 512-битным модулем (» 160D) подтверждается результатами:  

 

 

 Таблица 1.

Проект	Разрядность	Месяц	Год	MY	Алгоритм
RSA-100	100D	Апрель	1991	7	КР
RSA-110	110D	Апрель	1992	75	КР
RSA-120	120D	Июнь	1993	830	КР
RSA-129	129D	Апрель	1994	5000	КР
RSA-130	130D	Апрель	1996	500(1000)	ОЧР
RSA-140	140D	Февраль	1999	2000	ОЧР

 

  

 

В настоящее время рекомендуемая минимальная длина RSA-модуля — 768 бит (w 230D). Исходя из оценки трудоемкости проекта RSA-130, производительность компьютера для эффективной факторизации числа 230D должна быть не меньше 108 MY.

В феврале 1999 г. методом ОЧР был факторизован модуль RSA-140. Данный проект, также как и RSA-130.

Суммарная производительность проекта RSA-140 достигла 2000MY, а объем оперативной памяти (на одной рабочей станции) при реализации ключевого этапа алгоритма ОЧР составил 800 Мбайт.

Данные о трудоемкости проекта RSA-140 позволяют построить прогноз относительно количества ресурсов, необходимых для факторизации модулей с разрядностью 512, 768, 1024 бит: 

 

Разрядность (в битах)	512	768	1024
Сложность (в разах)	6,5	4 х 104	49 х 106
Оперативная память (в разах)	2,5	2 х 102	7 х 103

 

 

В следующей таблице приведены сведения о достижениях в области целочисленной факторизации за последние тридцать лет, а также указана производительность компьютера, достаточная для успешной факторизации чисел заданной разрядности. 

 

Год	1964	1974	1984	1994	1996
Разрядность	20D	54D	71D	129D	130D
MY	-	0.001	0.1	5000	500

 

  

 

Отметим, что для эффективной факторизации RSA-129 по алгоритму ОЧР потребуется 1000 MY вместо 5000 MY при факторизации по алгоритму КР.

Существенный скачок в производительности компьютеров в период между 1984 и 1994 годами обусловлен интенсивным развитием компьютерных сетей и, как следствие, практической реализацией метода распределенных вычислений. Идея использования свободного времени рабочих станций сети для факторизации принадлежит Силверману        (В. Silverman). (К сожалению, более ранняя попытка Шреппеля (R. Schroeppel) использовать сетевые ресурсы для факторизации восьмого числа Ферма F8 = 2256 + 1 не привлекла внимания специалистов.) Дальнейшее развитие идея распределенных вычислений получила в исследованиях Ленстры (A. Lenstra) и Мэнэсса (М. Manasse). В проекте RSA-129 было задействовано около 1600 рабочих станций в течение восьми месяцев. В отличие от традиционного подхода, когда для эффективной силовой атаки необходимо построить специальный компьютер, атака на основе идеи распределенных вычислений не требует значительных инвестиций и технических ресурсов.