Неверная кодировка

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

Алгоритм RSA в том или ином виде встроен в большинство браузеров и почтовых программ. Криптографический модуль "просыпается" в тот момент, когда человек за клавиатурой расплачивается электронными деньгами, отправляет свой пароль почтовому серверу или выбирает местное самоуправление. Эти процедуры давно описаны и стандартизованы - по крайней мере там, где госчиновники перестали бояться Интернета.

Криптопротоколов и криптопрограмм существует довольно много. В основе их лежит всего несколько методов шифрования, и 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 в России или Китае не могли воспользоваться более чем 56-битными ключами при отправке шифрованных сообщений стандартными средствами. Напомним, что первый взломанный RSA-шифр был 425-битным.

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

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

Так или иначе, если даже современные методы интернет-криптографии и безопасны, то могут лишиться этого свойства весьма скоро. Об этом, кстати, предупреждает при первом запуске популярный браузер Internet Explorer: "Сведения, переданные в Интернет, могут быть доступны другим пользователям". Более удачно то же сформулировал Иосиф Бродский: "Не выходи из комнаты, не совершай ошибку". Вне комнаты - разное бывает.