Я тебя породил, я тебя и убью… Создатели алгоритма RSA недавно объявили о том, что для взлома сообщения, зашифрованного с 1024-битным ключом, потребуется всего лишь 10 миллионов долларов и год работы специализированного устройства. Еще несколько лет назад казалось, что RSA-1024 абсолютно безопасен, по крайней мере до появления квантовых компьютеров. Однако теперь, если открытие Шамира подтвердится, всему цивилизованному миру придется переходить на новые стандарты безопасности.

Что происходит с RSA-1024
Принципиальный взлом RSA (в смысле изобретения формул для определения секретного ключа¹) — это решение сложной математической проблемы и нахождение «альтернативного» входа. Случись он, и всему цивилизованному миру придется немедленно переделывать свои криптосистемы защиты данных — известно, что девять из десяти коммерческих проектов в Интернете защищают себя и своих клиентов при помощи алгоритма RSA. Однако частичная дешифровка возможна. «Частичная» в смысле определенной длины ключа. Сразу же оговорюсь, что речь идет не о формулах вскрытия секретного ключа, а об изобретении устройств или методов, способных факторизовать большие числа очень быстро. Другими словами, мы говорим о «лобовой атаке» на код. По прогнозам специалистов, вскрытие шифра RSA с длиной ключа 1024 бита (такая длина часто используется в информационных системах) займет в лучшем случае — при проведении распределенных вычислений на тысячах мощных ПК — не менее пятнадцати лет³. Предполагается, что за такое время информация устаревает, а в силу того, что для взлома требуются громадные вычислительные ресурсы, взлом получается экономически невыгодным. Для сравнения отмечу, что в 1999 году большое распределенное задание, включающее работу сотен компьютеров на протяжении нескольких месяцев, позволило вскрыть 512-битный секретный ключ алгоритма RSA⁴. Понятно, что RSA-1024 достаточно надежный (криптостойкий) шифр, несмотря на быстрое увеличение производительности компьютеров.

К сожалению людей, ценящих гарантии надежности, не все так просто. Несмотря на заверения признанных авторитетов в области криптологиии, в конце января 2003 года появились данные о том, что Ади Шамир⁵ (Adi Shamir) при поддержке Эрана Тромера⁶ (Eran Tromer) разработал принципиальную схему устройства, способного факторизовать открытые коды во много раз быстрее, чем считалось возможным. Устройство, TWIRL⁷ представляет собой интегральную схему, работающую на частоте 1 ГГц и построенную на базе 0,13-микронной технологии. Ученые из израильского научного Института Вейцмана (Weizmann Institute of Science) полагают, что по стоимости вычислений придуманное ими устройство будет на три-четыре порядка эффективнее лучших разработок прошлого, таких, например, как оптоэлектронная система TWINKLE⁸, предложенная тем же Шамиром в 1999 году на криптографической конференции Eurocrypt ’99, или «просеивающее устройство», основанное на решетке. Шамир и Тромер, основываясь на детальном анализе всех критических компонентов устройства, заявляют, что взлом 1024-битного ключа при помощи TWIRL стоимостью около 10 миллионов долларов можно произвести меньше чем за год, а дешифровка 512-битного ключа потребует всего-навсего десять минут и более простого устройства стоимостью всего 10 тысяч долларов. Таким образом, если их предположения окажутся верны, то схему шифрования RSA-1024, а тем более RSA-512 следует считать недостаточно надежной для сохранения секретности в ближайшем будущем.

Хронология устройств
для взлома RSA
На сложности факторизации больших чисел основано множество различных криптосистем. Быть может, поэтому проблема факторизации чисел подвергается математиками особенно тщательному исследованию. Лучшим для разложения больших чисел считается алгоритм «решета числового поля» (NFS, Number Field Sieve), который был успешно применен для вскрытия 512-битных ключей RSA. Однако оказалось, что эффективно реализовать NFS на ПК не представляется возможным, и поэтому взлом 1024-битного ключа практически нереален. Недавно было предложено использовать специализированное устройство для дорогих в вычислительном плане шагов алгоритма «решета числового поля». Появились разработки «просеивающих» устройств, такие как TWINKLE, или «просеивающее устройство», основанное на решетке, и т. д. Но на практике ни одна из них не позволяла обрабатывать 1024-битную ключевую информацию.
Шамир и Тромер использовали интуитивное предположение Даниэла Бернстайна (Daniel Bernstein) о том, что «неэффективно применять ячейки памяти просто для хранения данных», и ввели параллелизм. Кстати, стоит заметить, что Бернстайн в свое время разработал метод «вскрытия» криптосистемы RSA с помощью специализированного аппаратного обеспечения и утверждал, что, по теоретическим оценкам, метод настолько прогрессивен, что ставит под угрозу факторизации числа длиной 1024 бита, то есть RSA-ключи, считающиеся вполне стойкими⁹. Тогда Арьен Ленстра и Ади Шамир, оценив работу Бернстайна, сделали вывод: предложенное им устройство действительно в некоторых условиях обеспечивает улучшение существующих методов факторизации, но вовсе не в три раза, как полагает автор, а приблизительно в 1,2 раза. Поэтому криптостойкость схемы RSA-1024 методика Бернстайна не поколебала. Но, видимо, его работа все же натолкнула исследователей на определенные идеи (вроде «параллельных ячеек») и оказала влияние на дальнейшие разработки.

1 Вообще говоря, не факт, что это возможно в принципе. — Прим.ред.
2 Иногда в литературе встречается — Эйдельман.
3 Насколько изменились наши вычислительные возможности за последнюю четверть века, можно судить хотя бы по названию одной из первых статей, посвященных RSA: «A New Kind of Cipher That Would Take Millions of Years to Break» («Новый шифр, для взлома которого потребуются миллионы лет»). Статья была написана небезызвестным у нас Мартином Гарднером в 1977 году (Scientific American, August 1977, 120-124). — Прим.ред.
4 www.rsasecurity.com/rsalabs/challenges/factoring/rsa155.html. — Прим.ред.
5 Тот самый, которому аббревиатура RSA обязана буквой S. — Прим.ред.
6 www.tromer.org.
7 От «The Weizmann Institute Relation Locator», что можно перевести как «относительный локатор (отыскиватель) Института Вейцмана», или «кружение». На сленге twirl обозначает также дубликат ключа или отмычку.
8 От «The Weizmann Institute Key Locating Engine». В переводе — «устройство Института Вейцмана для отыскания ключа», или просто «мерцание», что отражает оптоэлектронную природу машины.
9 Одну из нашумевших статей Бернстайна, в которой он заявлял о компрометации RSA-1024 еще в марте прошлого года, можно найти по адресу cr.yp.to/papers/nfscircuit.ps. — Прим.ред.

стр. 2>>