Размер имеет значение
 
21.02.2003
Компьютерра


 
стр. 1
стр. 2 >>
 

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

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

Криптографический алгоритм был RSA, придуман в 1977 году и получил название в честь своих создателей: Ривеста, Шамира и Адлмана2. Сегодня он очень популярен и активно реализуется как в виде самостоятельных криптографических продуктов (к примеру, в защищенных банковских системах — для удаленного обслуживания кредитных карточек), так и в качестве встроенных средств популярных приложений (например, для шифрования в браузерах Netscape и Microsoft). Основой криптостойкости работы RSA является тот факт, что произведение двух простых больших чисел невозможно разложить на множители за обозримое время. Два больших простых числа перемножаются, и их произведение считается открытым ключом, с помощью которого можно зашифровать сообщения. Расшифровать подобное закодированное сообщение можно, только зная один из множителей («секретный ключ»).

К сожалению людей, ценящих гарантии надежности, не все так просто. Несмотря на заверения признанных авторитетов в области криптологиии, в конце января 2003 года появились данные о том, что Ади Шамир5 (Adi Shamir) при поддержке Эрана Тромера6 (Eran Tromer) разработал принципиальную схему устройства, способного факторизовать открытые коды во много раз быстрее, чем считалось возможным. Устройство, TWIRL7 представляет собой интегральную схему, работающую на частоте 1 ГГц и построенную на базе 0,13-микронной технологии. Ученые из израильского научного Института Вейцмана (Weizmann Institute of Science) полагают, что по стоимости вычислений придуманное ими устройство будет на три-четыре порядка эффективнее лучших разработок прошлого, таких, например, как оптоэлектронная система TWINKLE8, предложенная тем же Шамиром в 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-ключи, считающиеся вполне стойкими9. Тогда Арьен Ленстра и Ади Шамир, оценив работу Бернстайна, сделали вывод: предложенное им устройство действительно в некоторых условиях обеспечивает улучшение существующих методов факторизации, но вовсе не в три раза, как полагает автор, а приблизительно в 1,2 раза. Поэтому криптостойкость схемы RSA-1024 методика Бернстайна не поколебала. Но, видимо, его работа все же натолкнула исследователей на определенные идеи (вроде «параллельных ячеек») и оказала влияние на дальнейшие разработки.

Шамир, Ривест и Эйдельман


 
стр. 1
стр. 2 >>


 Все работы хороши? [ "13-я КОМНАТА" ]
 Новости [ "НОВОСТИ" ]
 Дорога домой [ "НОВОСТИ" ]
 Микрофишки [ "НОВОСТИ" ]
 Слесаря вызывали? [ "НОВОСТИ" ]
 Умная пыль на сапогах [ "НОВОСТИ" ]
 Лишь бы работало [ "НОВОСТИ" ]
 Производство варева [ "ТЕМА НОМЕРА" ]
 «ERP»для программистских проектов [ "ТЕМА НОМЕРА" ]
 Управление качеством в процессах разработки программного обеспечения [ "ТЕМА НОМЕРА" ]
 От хвоста до головы Практика разработки средних и крупных программных проектов [ "ТЕМА НОМЕРА" ]
 Символическая новизна [ "SOFTТЕРРА LITE" ]
 Зимний прорыв [ "SOFTТЕРРА LITE" ]
 События [ "SOFTТЕРРА LITE" ]
 Синергия [ "КОМПЬЮFЕРРА LITE" ]
 Перст указующий [ "КОМПЬЮFЕРРА LITE" ]
 Дважды два [ "КОМПЬЮFЕРРА LITE" ]
 Баскетбол для зомби [ "ОПЫТЫ" ]
 Размер имеет значение [ "АНАЛИЗЫ" ]
 Миф в окошке [ "АНАЛИЗЫ" ]
 Где прячется квантовое сознание? [ "КАФЕДРА ВАННАХА" ]
 Масяня и Директора [ "КАРАУЛ" ]
 Что путного сможет сделать тысяча собранных под одной крышей программистов? [ "ВОПРОС НЕДЕЛИ" ]
 Женщины тоже способны мыслить [ "ПИСЬМОНОСЕЦ" ]


Все материалы номера