Взломан очередной RSA ключ

Сотрудники Федерального агентства по информационной безопасности Германии сумели взломать алгоритм шифрования RSA. В этом не было ничего противозаконного. Организация RSA Security выплатит взломщикам 20 тысяч долларов и готова потратить еще большие суммы на благо хакеров. Однако "нестойкость" математического алгоритма может стоить куда больших денег тем, кто пользуется шифрованием в Интернете.

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

Рон Ривест, Ади Шамир и Леонард Адлеман придумали RSA в 1977 году. Годом раньше двое других математиков, Диффи и Хеллман, сформулировали самый важный принцип этого алгоритма в своей статье "Новые направления в криптографии". В ней рассматривался такой способ обмена секретной информацией, при котором людям на разных концах провода не нужно договариваться о ключах и паролях вне сети - даже если сеть "прослушивается" непрерывно. Математики сумели предугадать, что может понадобиться будущему Интернету, с неожиданной точностью. Так появилась гражданская криптография.

Для взлома RSA достаточно уметь раскладывать большие числа на множители. Чем больше число, тем, разумеется, сложнее это следать, а удлинение числа на несколько бит увеличивает сложность задачи во много раз. После того как статья Райвеста, Шамира и Адлемана была опубликована, ее дополнили шифром и уведомлением о том, что его вскрытие потребует нескольких квадрилиионов лет компьютерного времени. Тем, кто сможет это опровергнуть, предлагалось сто долларов в качестве компенсации. Публичный ключ (вернее, число, множители которого следовало найти самостоятельно) содержал 425 бит или 129 обычных цифр: 114 381 625 757 888 867 669 235 779 976 146 612 010 218 296 721 242 362 562 561 842 935 706 935 245 733 897 830 597 123 563 958 705 058 989 075 147 599 290 026 879 543 541. Первые желающие получить по 78 центов за один десятичный знак в записи его сомножителей появились семнадцать лет спустя. 600 добровольцев и 1600 компьютеров потратили на расшифровку полгода. Фраза выглядела так: "Магические слова - брезгливый стервятник". 100 долларов пожертовали на развитие свободного программного обеспечения, а "брезгливый стервятник" сделался частым фигурантом серьезных математических статей. Принято считать, что эта задача стала первым распределенным интернет-проектом и самым ресурсоемким из всех научных расчетов.

Затем все ускорилось. RSA Laboratories опубликовала цепочку ключей возрастающей длины и назначила награду за "взлом" каждого следующего числа. Сейчас таких чисел восемь, причем последнее, длиной в 2048 бит (оно записывается 617 десятичными знаками), оценили в 200 тысяч долларов. 200-значное - разложили на множители в мае этого года. Новое достижение принадлежит той же группе исследователей из Бонна. Его можно было бы назвать шагом назад: "ноябрьское число" RSA-576 содержит на 7 знаков меньше. Вычислителям потребовалось 80 2,2-гигагерцовых процессоров Opteron, которые были непрерывно загружены пять месяцев подряд.

На сайте rsasecurity.com очередную (и, надо заметить, предсказуемую) победу над ключом оценивают как поражение. Аргументы понятны: чтобы взломать не самый сложный шифр, все еще требуются месяцы работы современного вычислительного кластера. Любопытно другое. 80 процессоров - далеко не последнее слово техники: существуют куда более мощные суперкомпьютеры. Однако даже общедоступные BlueGene с 1024 процессорами, которые компания IBM распродает по два миллиона долларов, ни разу за последнее время не упоминались в новостях, посвященных борьбе со стареющим алгоритмом.

Одно из объяснений этому приводится в блоге Брюса Шнейера, известного специалиста по компьютерной безопасности. По словам его комментаторов, только первую стадию вычислений удалось бы с явной выгодой перенести на суперкомпьютер. ЭВМ с быстродействием 280 терафлопов обсчитывала бы ее полтора часа вместо трех месяцев. Если бы со второй стадией все обстояло так же просто, вся процедура заняла бы меньше времени, чем писалась эта статья. Но, считает эксперт, у такого подхода есть алгоритмические препятствия, и результат суперкомпьютера никого бы не впечатлил.

Трудно предположить, что сверхмощные кластеры оставили в стороне только ради сохранения их репутации. Криптография всегда интересовала тех, кто занимается вопросами национальной безопасности самых разных государств. В США, например, до 2000 года существовал явный запрет на экспорт криптотехнологий. На практике это означало, например, что пользователи "локализованной" Windows в России или Китае не могли воспользоваться более чем 64-битными ключами при отправке шифрованных сообщений стандартными средствами.

В 2000 году ограничение, к радости интернет-общественности, было, наконец, снято - с оговорками, касающимися разве что "стран-изгоев" по версии Госдепартамента США. Продвинутые пользователи остального мира смогли, наконец, легально воспользоваться сверхдлинными ключами. Программы, позволяющие делать так, в большинстве случаев бесплатны и распространяются вместе с исходным кодом. Все это, само собой, легко истолковать в духе "теории заговора": никто не препятствует их распространению как раз потому, что уже интерес к шифрам позволяет выделить из общего потока тех, кому есть что скрывать. А сама расшифровка не слишком трудна.

lenta.ru