Размер имеет значение
АрхивЯ тебя породил, я тебя и убью… Создатели алгоритма RSA недавно объявили о том, что для взлома сообщения, зашифрованного с 1024-битным ключом, потребуется всего лишь 10 миллионов долларов и год работы специализированного устройства.
Я тебя породил, я тебя и убью… Создатели алгоритма 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 Иногда в литературе встречается — Эйдельман.
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. — Прим.ред.
Так что же придумали Шамир и Тромер? Предложенное ранее устройство TWINKLE просеивает (рассеивает) ключи последовательно, тогда как TWIRL способно делать тысячи просеиваний параллельно на каждом такте работы. Вдобавок новое устройство меньше по размеру и проще в изготовлении: для обработки 1024-битных ключей понадобится 44 независимых просеивающих устройства на тридцатисантиметровой односторонней пластине.
Основная сложность TWIRL заключается в том, как использовать единственную копию входных данных (или небольшое количество копий) для решения многих подзадач параллельно без коллизий или длительных задержек — это необходимо для обеспечения эффективности работы устройства. Шамир и Тромер полагают, что решить эту задачу можно, если разрабатывать гетерогенное устройство, использующее различные «маршрутизирующие цепи». Построить такое устройство предполагается при помощи разработок, сделанных для TWINKLE, и, уж конечно, оно будет выполнять некоторую часть (наиболее дорогую в вычислительном плане для обычных компьютеров) уже знакомого нам алгоритма NFS.
Алгоритм NFS и устройство TWINKLE
Отмечу, что двумя самыми заметными открытиями в области факторизации стали алгоритм «квадратичного решета», изобретенный Джоном Поллардом в начале 1980-х годов, и алгоритм «решета числового поля», предложенный целой группой математиков в начале 1990-х годов. Для чисел длиной менее 350 бит лучше работает первый алгоритм, для чисел с большей длиной — второй алгоритм. Понятно, что для взлома RSA-1024 полезнее применять именно алгоритм «решета числового поля».
В основе работы алгоритма факторизации NFS лежат, упрощенно говоря, следующие принципы. На первом этапе («шаг просеивания») осуществляется параллельный поиск уравнений с определенным соотношением. Затем, после того как обнаружено определенное количество соотношений, начинается этап матричных операций для решения полученных систем линейных уравнений и нахождения простых множителей.
Для реализации этапа просеивания Шамир в свое время разработал довольно простое оптоэлектронное устройство TWINKLE, способное анализировать 100 млн. больших целых чисел, получаемых при перемножении первых 200 тысяч простых. Он предложил кодировать множество светодиодов различными значениями, соответствующими простым числам, а затем использовать это для разложения чисел на множители. Автор рассчитал, что оптоэлектронный метод позволяет реализовать этап просеивания на скоростях, в тысячу раз превышающих возможности обычных компьютеров. Как уже было сказано, устройство TWINKLE может сделать уязвимыми в лучшем случае 512-битные RSA-ключи.
Оценка стоимости
устройства TWIRL
для взлома RSA-1024
Полное описание устройства TWIRL (и даже краткий пересказ принципов его работы), к сожалению, невозможно опубликовать на страницах журнала. Черновик статьи Шамира и Тромера находится в свободном доступе, и все желающие могут ознакомиться с их выкладками (см. ссылки в конце статьи). Пока же некоторые факты, положенные в оценку стоимости устройства, читателю предлагается принять на веру.
Для устройства взлома 1024-битного ключа RSA потребуется кремниевая пластина площадью 1423 мм2. Из них 71% будет задействован для бо,льших прогрессий (21% отведен под банки памяти DRAM), 24% — для меньших прогрессий и оставшиеся 5% — для небольших.
Одно TWIRL-устройство затратит 110 секунд на каждую просеивающую линию. Таким образом, для полного просеивания понадобится 40 тысяч лет. Мы можем выполнить 44 просеивающих устройства на односторонней 30-см кремниевой пластине стоимостью 5 тысяч долларов. 4,5 миллиона долларов понадобится для построения 40 тысяч независимых устройств, которые, будучи запущены параллельно, могут выполнить полное просеивание менее чем за один год.
К полученной стоимости следует приплюсовать стоимость израсходованной электроэнергии, системы охлаждения, компьютера, сохраняющего результаты, и стоимость ошибок и дефектов. Получается, что для факторизации 1024-битного ключа за один год потребуется 10 миллионов долларов. Однако авторы не отрицают, что из-за сложностей, связанных с «большими простыми числами», сумма может возрасти в пять раз. Что, впрочем, тоже немного по сравнению с другими разработками в этой области.
Аналогичные расчеты показывают, что стоимость устройства для 512-битного просеивания составит 10 тысяч долларов (потребуется менее десяти минут), а 768-битного — 50000 долларов (95 дней).
Заключение
Устройство TWIRL предназначено для выполнения этапа просеивания, предусмотренного алгоритмом «решета числового поля» при факторизации больших чисел. Следует отметить, что накопление результатов и второй этап алгоритма — этап матричных операций для решения СЛУ10 и нахождения простых множителей — предполагается выполнить на компьютере. Вот тут возникает главный вопрос к господам Шамиру и Трумеру. Дело в том, что сложность выполнения второго шага быстро возрастает при увеличении длины ключа. И дело не только во времени, которое понадобится для решения СЛУ, но и в памяти. По оценкам, при 1024-битном ключе матричный шаг потребует 10 Тбайт оперативной памяти. Если все же удастся обойти это препятствие и если все оценки Шамира и Трумера окажутся более или менее верными, тогда схему шифрования RSA-1024 следует считать недостаточно надежной для сохранения конфиденциальности данных. А значит, самые распространенные в Интернете технологии защиты информации могут оказаться неэффективными, поскольку используют ключи не длиннее 1024 бит. Скорее всего, следует ожидать перехода к более длинным ключам, например 2048, 4096, а то и 8192 бит. Хотя, конечно, их нельзя считать панацеей — со временем и этого может не хватить. Вспомним, что в 2000 году корпорация IBM приступила к разработке первого в мире квантового компьютера11, который может выполнять некоторые арифметические операции параллельно. Руководитель группы ученых из IBM, Стэнфордского университета и Университета Калгари Айзек Чуанг (Isaac Chuang) заявил, что при определенных типах вычислений, таких как криптографические алгоритмы, квантовый компьютер, состоящий из нескольких сотен атомов, сможет выполнять миллиарды операций зараз.
Известно, что проблема любого асимметричного алгоритма шифрования информации (как, впрочем, и почти всех симметричных) — зависимость от прогресса в математической теории и в области «железа», что позволяет реализовывать все более и более совершенные устройства для вскрытия указанных выше шифров. И хорошо, что этот прогресс — дело рук известных ученых. В конце концов, если проверкой устойчивости алгоритмов не будут заниматься они, займутся другие. И не факт, что мы узнаем о результатах, пока не столкнемся с последствиями лицом к лицу.
10 СЛУ — система линейных уравнений. — Прим.ред.
11 За создание квантового компьютера не брался только ленивый, но рано или поздно кто-нибудь его все же сделает. — Прим.ред.
Литература:
[1] Adi Shamir, Eran Tromer, Factoring large numbers with the TWIRL device, psifertex.com/download/twirl.pdf.
[2] Daniel Bernstein, Circuits for integer factorization: a proposal, cr.yp.to/papers.html.
[3] Adi Shamir, Factoring large numbers with the TWINKLE device (extended abstract), proceedings of CHES’99, LNCS 1717 2-12, Springer-Verlag, 1999.
[4] Для общего развития: www.ssl.stu.neva.ru/psw/crypto.html.
