Взломан алгоритм шифрования RSA

Krendils

Взломан алгоритм шифрования RSA
http://www.iraqwar.mirror-world.ru/article/69874
Неверная кодировка
Искатели простых чисел снова взломали главный криптоалгоритм
Сотрудники Федерального агентства по информационной безопасности Германии сумели взломать алгоритм шифрования 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 в России или Китае не могли воспользоваться более чем 64-битными ключами при отправке шифрованных сообщений стандартными средствами. Напомним, что первый взломанный RSA-шифр был 425-битным.
В 2000 году ограничение, к радости интернет-общественности, было, наконец, снято - с оговорками, касающимися разве что "стран-изгоев" по версии Госдепартамента США. Продвинутые пользователи остального мира смогли, наконец, легально воспользоваться сверхдлинными ключами. Программы, позволяющие делать так, в большинстве случаев бесплатны и распространяются вместе с исходным кодом. Все это, само собой, легко истолковать в духе "теории заговора": никто не препятствует их распространению как раз потому, что уже интерес к шифрам позволяет выделить из общего потока тех, кому есть что скрывать. А сама расшифровка не слишком трудна.
Любопытно, что опасения конспирологов разделяют вполне серьезные люди. В октябре 2005 года стало известно, что в американских паспортах появится "радиочип" (RFID) с парой достаточно длинных ключей. Ключи нужны для того, чтобы разрешать удаленное считывание информации о пользователе только доверенным приборам. Первыми назвали такое решение "недостаточно безопасным" сотрудники RSA Laboratories. По их мнению, криптозащита может "сдаться", например, иностранным пограничникам (в чьих руках, следует думать, паспорт находится недостаточно долго для того, чтобы запустить суперкомпьютерный расчет).
Так или иначе, если даже современные методы интернет-криптографии и безопасны, то могут лишиться этого свойства весьма скоро. Об этом, кстати, предупреждает при первом запуске популярный браузер Internet Explorer: "Сведения, переданные в Интернет, могут быть доступны другим пользователям". Более удачно то же сформулировал Иосиф Бродский: "Не выходи на улицу, не совершай ошибку". Там разное бывает.
Борислав Козловский

_mrz

да уж
содержание статьи хорошо соответствует подписи того, кто постит.
Удивительно безграмотные бредни любят писать интернет-журналисты.
Заголовок и интерпретация почти каждого упомянутого факта настолько безграмотны, что просто офигеваешь.
Алгоритм RSA взломан только тогда, когда представлен не более чем полиномиальный по времени относительно длинны входного числа алгоритм разложения оного на простые множители. А то, что кто-то взломал какое-то вонючее 512 битное число - это просто рядовое, совершенно предсказуемое явление, осуществимое на приличном суперкомпе за пару часов, что ясно даже из этой статьи.
Подробно комментировать этот бред привлекающий внимание громким заголовком не соответствующим содержанию как-то лениво, но руки так и чешутся.
Даже перевод некоторых терминов с английского с потрохами выдает "суперкомпетентность" этого журналиста. Надо же "гражданская криптография" Это он наверно так перевел public cryptography (или даже public key cryptography, проигнорив слово key).

stm7543347

Из статьи только очевидно, что это займет три месяца.

_mrz

Из статьи только очевидно, что это займет три месяца.
ага, на дешевенькой вычислительной станции с какими-то вонючими 80 opteron-ами. Этому компу до современных суперкомпьютеров как до Луны, о чем почти прямо сказано в этой статье.
Там еще мимоходом довольно смешным образом упоминается IBM-овская машина за пару миллионов (общедоступная и универсальная причем) и приводится оценка в несколько часов вычислений (которая кажется все же заниженной) плюс какие-то мутные оговорки. А если сделать машину из высокопроизводительных технически совершенных (алгоритмическим дизайном микросхемы на уровне нынешних знаний) криптопроцессоров, реализующих быструю арифметику длинных чисел на уровне оборудования (чем заинтересованные органы наверняка уже давно озаботились может даже задача факторизациии 512 битного числа будет решаться чуть ли не в реальном времени.
В этом контексте удивления в статье по поводу того, что не встречаются в подобных новостях упоминания о суперкомпьютерах помощнее, просто блещут своей наивностью.

defaler

Устраивайся в этот журнал редактором!

avgustinka

> Взломан алгоритм шифрования RSA
Спасибо, посмеялся.

JOKER19890727

ага, на дешевенькой вычислительной станции с какими-то вонючими 80 opteron-ами. Этому компу до современных суперкомпьютеров как до Луны, о чем почти прямо сказано в этой статье.
Там еще мимоходом довольно смешным образом упоминается IBM-овская машина за пару миллионов (общедоступная и универсальная причем) и приводится оценка в несколько часов вычислений (которая кажется все же заниженной) плюс какие-то мутные оговорки.
За пару миллионов американских долларов у IBM не удастся купить машину существенно более мощную, чем "дешёвенькие" 80 оптеронов.

oofc

Сравнил NUMA с кластером...

natunchik

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

JOKER19890727

OK, поправлюсь: за пару миллионов американских долларов у IBM не удастся купить HPC-кластер существенно более мощный, чем кластер на "дешёвеньких" 80 оптеронах.

PETERPETER

Надо же, забавные статьи в разделе бывают (редко заглядываю сюда).
Безграмотность журналиста в первую очередь всплывает в том, что он вообще не понимает разницы между алгоритмами на закрытых ключах и на открытых. Так есть очень примечательный абзац:

Трудно предположить, что сверхмощные кластеры оставили в стороне только ради сохранения их репутации. Криптография всегда интересовала тех, кто занимается вопросами национальной безопасности самых разных государств. В США, например, до 2000 года существовал явный запрет на экспорт криптотехнологий. На практике это означало, например, что пользователи "локализованной" Windows в России или Китае не могли воспользоваться более чем 64-битными ключами при отправке шифрованных сообщений стандартными средствами. Напомним, что первый взломанный RSA-шифр был 425-битным.
Потому как технологии симметричного шифрования (это про те 64 бита и RSA - это совершенно разные области, с совершенно разными проблемами.
Кроме того, afaik ограничение было в 40 бит, а не 64. Причём при учёте того, что 40 бит ломались на обычном PC за несколько дней, ограничение это - явно абсурдное. Потом его заменили на 64 бита, а потом - отменили вообще. Впрочем, могу немного ошибаться, но цифры в 40, 64 в плане ограничений были.
Заголовок и интерпретация почти каждого упомянутого факта настолько безграмотны, что просто офигеваешь.
Алгоритм RSA взломан только тогда, когда представлен не более чем полиномиальный по времени относительно длинны входного числа алгоритм разложения оного на простые множители.
Для практических целей - не обязательно. Во-первых, существуют вероятностные алгоритмы (я не про конкретную область, а вообще и если средняя сложность у него будет полиномиальной, то формальная, зачастую - экспоненциальной. Пример - qsort, имеющий среднюю сложность n*log(n в то время как формальная - n^2. Во-вторых, даже если сложность выше, чем полиномиальная, это не значит, что практический перебор не осуществим (и этот взлом - наглядное тому подтверждение равно как наличие полиномиального алгоритма не означает, что можно на практике вскрыть (вдруг полином будет n^100).
Проблема, на самом деле, существует. Дело в том, что чтобы взломать хотя бы 256-ти битный ключ, нужно использовать уже довольно сложные алгоритмы, это совсем не простой перебор вариантов разложения (в отличии от того, как обычно взламывают симметричные алгоритмы). Математика там совершенно убойная (пытался одно время заботать - жуть! и не факт, что завтра не придумают алгоритма, которых при тех же вычислительных затратах будет ломать ключ в 4096 бит, например, имея при этом большую сложность, чем полином. Так что перспективы у области - не самые радужные...

zuzaka

Я не особо хорошо знаком с законодательством в области криптования, но, надеюсь, меня не обвинят в том, что я не отличаю шифрования открытыми и закрытыми ключами и т.д. Так вот, по моим сведениям, полученным от юриста компании, разработавшей (точнее, впаривавшей) широко известные криптосистемы Верба, Верекс и что-то там еще, - по сведениям от этой юристки, фраза "На практике это означало, например, что пользователи в России не могли воспользоваться более чем 64-битными ключами при отправке шифрованных сообщений" - правда.
Кста, насколько я знаю, первый сломанный RSA был 127-битным.
Оставить комментарий
Имя или ник:
Комментарий: