Жизнь бьет ключом

Не прошло и суток с момента отыскания самого большого простого числа, а математики радуют мир новым известием: подобрана пара для криптоключа RSA-576.

Последние дни выдались поистине золотыми для математики: не прошло и суток с момента официального объявления об отыскании 40-го числа Мерсенна группой энтузиастов, работающих в рамках проекта GIMPS, как другой - уже гораздо более скромной командой из Германии - было сообщено о взломе образцового 576-битного криптографического ключа, предложенного компанией RSA Security (т.н. числа RSA-576). Что случилось, что это означает и какая выгода может быть извлечена из всего этого - давайте разберёмся. А начать лучше всего с уже упоминавшихся в этой колонке на прошлой неделе простых чисел.

У простого числа всего два делителя. Иначе говоря, оно делится без остатка только на самое себя и единичку. Таковы числа 2, 3, 5, 7, 11 и далее по возрастающей. Если первых представителей этой последовательности отыскать несложно, то с ростом величины числа возрастает и сложность проверки его на простоту. Впрочем, существуют алгоритмы, позволяющие сравнительно быстро сгенерировать простое число нужной величины. В свою очередь числа RSA являются производными от простых: у каждого такого числа, помимо его самого и единицы, есть ещё два (и только два) делителя, причём они обязательно простые. Таким образом для получения числа RSA необходимо сгенерировать пару простых чисел и перемножить их. Даже при сравнительно большой длине (в многие сотни бит), время, необходимое на генерацию числа RSA измеряется секундами. Замечательное свойство чисел RSA заключается в несравненно более высокой сложности их разложения на делители: процесс поиска делителей называется факторизацией и - при использовании известных математикам алгоритмов - требует вычислительных затрат на много порядков больших, чем для генерации этих делителей. Методов факторизации много, одним из лучших считается алгоритм общего решета числового поля (General Number Field Sieve, GNFS). Но даже с применением самых современных достижений математики и техники, по считающимся сегодня хорошими оценкам, факторизация числа RSA длиною в 1020 бит потребует непрерывной работы 342 миллионов персональных компьютеров на протяжении одного года.

Несоразмерная сложность генерации чисел RSA и их факторизации в 1977-м году была положена в основу асимметричной криптографии: алгоритм RSA, предложенный группой учёных, позднее основавших одноимённую компанию (и, собственно, давших название тем числам, о которым мы говорим с самого начала), стал первым в своём роде. Поступившись деталями можно сказать, что все современные коммерческие асимметричные криптосистемы - те, что используют пару ключей: приватный и публичный - основываются на подобных алгоритмах (впрочем, для разных из них одинаковая сложность взлома может достигаться при разной длине ключей). А потому для вскрытия сообщения, зашифрованного, к примеру, по алгоритму RSA с ключом длиной в 576 бит, необходимо решить задачу факторизации числа именно такой длины. Конечно, факт успешного взлома одного 576-битного ключа ещё не означает, что использование ключей такой длины для шифрования данных уже ненадёжно. Это всего лишь позволяет трезво оценить время и усилия, необходимые для взлома такого шифра.

Эпопея с взломом чисел RSA началась в тот же год, когда этот алгоритм был разработан. Тогда авторы RSA опубликовали 129-значное число (здесь речь идёт о десятичных разрядах - в двоичной форме длину ключа стали выражать позднее), предположив, что на факторизацию его уйдёт несколько миллионов лет. Достижения электроники опровергли это утверждение и ключ был "взломан" уже в 1994-м. "Взломщики" получили назначенную RSA Security награду в сто долларов, а сама компания к тому времени учредила конкурс, действующий и поныне - RSA Factoring Challenge, в рамках которого всем желающим предлагается собственноручно попробовать сломать ключи длиною от 576 до 2048 бит. В соответствии с традицией, за каждый из них назначено вознаграждение - от 10 тысяч долларов за RSA-576 до 200 тысяч за RSA-2048. Суммы впечатляют, но, как уверяют в RSA Security, по сравнению со стоимостью машинного времени, необходимого для решения поставленной задачи традиционными (заметьте: традиционными!) методами, все эти долларовые кучи - символическая награда.

Естественно, что за числами RSA ведётся охота и желающие могут присоединиться, к примеру, к распределённому проекту RSAttack576. Впрочем, всем участникам поиска теперь предстоит штурмовать следующую высоту: ведь 576-битный ключ RSA сломан. Сделали это немецкие математики (группа включает исследователей из Университа Бонна, Федерального бюро информационной безопасности Германии и других учреждений), использовавшие упоминавшийся выше алгоритм GNFS и собственный суперкомпьютер. Детали ещё не опубликованы (и RSA Security пока не признала официально факт победы), но, по всей видимости, на решение задачи ушло лишь около полугода. На очереди - RSA-640 и 20 тысяч долларов. Не желаете попробовать?