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

Взломан алгоритм шифрования RSA
Филиппинский математик-энтузиаст разработал новый метод декодирования алгоритма шифрования RSA, основанный всего лишь на трех простых формулах, сообщает филиппинская газета Manila Bulletin.


Лео де Велез (Leo de Velez) вывел три формулы позволяющие декодировать сообщения, зашифрованные по алгоритму RSA.

RSA был разработан в 1977 году Роном Ривестом (Ron Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адельманом (Leonard Adleman) и является в настоящее время наиболее часто применяемым механизмом защиты информации. Он включен в состав браузеров от компаний Netscape и Microsoft, а также таких известных продуктов, как Lotus Notes, Intuit Quicken и др.

Основой криптостойкости работы RSA является тот факт, что произведение двух простых больших чисел невозможно разложить на множители за обозримое время. Два больших простых числа перемножаются и их произведение считается открытым ключом, с помощью которого можно зашифровать сообщения. Расшифровать подобное закодированное сообщение можно только зная один из множителей ("секретный ключ"). Более подробную информацию о работе алгоритма можно найти на веб-сайте RSA.


CNews.ru http://www.cnews.ru/topnews/2001/02/05/content4.shtml

От блин, а я уже больше года в rc5 Russian Team, мы этот РСА перебором ломаем... Блиииин, если правда - то перебор 40% 64-битного ключа теперь никома не нужен...

Конечно, нужны было в SETIhome участвовать, вместо RC5, ибо там прогресса до сих пор не видно

---

wbr, muxel (Mechanical Upgraded Xenocide and Exploration Lifeform)

Ну я считаю - это не правда. Спросил у друга, который занимается криптографией (и даже её преподаванием в МИФИ) и получил [ожидаемый] ответ:

Torn:Думаю, что туфта. Взлом RSA - это решение сложной математической проблемы. Как минимум математику-энтузиасту ) она не по зубам. Для этого надо обладать фундаментальной подготовкой, собственно к шифрванию никакого отношени яне имеющей. Интересно было бы почитать, какую конкретно туфту на этот раз представили, как взлом RSA Ж))

Torn:Ну и лашки же ))) http://www.mb.com.ph/INFO/2001-02/IT020201.asp

2 CaRRibeaN: так что успокойся Реальность, она обладает определенной инерцией и ничего вот так вот, с бухты-барахты не меняетс ....

Нет, ну все устаканилось, его способ оказался не быстрее простого перебора

2Муксел
Зато в SETI большой прогресс.

quote:

---

Originally posted by Artiom:
Ну я считаю - это не правда.

---

 

Почему же неправда, PGP тоже считался крутой и надежной штукой, пока автор в АНБ не перешел работать. После это кучу багов стали находть в PGP 5.5

И с чего это вдруг АНБ не разрешавшя ничего длиннее 40 бит, вдруг сразу разрешил 128. А ведь это в порядки сложнее.

Сдаеться мне что DES и RSA слабые алгоритмы в основе.
Наше ФАПСИ меньше чем 1К ключи даже не рассматривает.
Это вам не в битики играть. Даже 1000 ГГц процы картину и на долю процента не сдвинут.

too fast (too high )

PGP - программа, реализующая шифрование с открытым ключом и имеющая обыкновенные программные баги и дыры. Аналогичных программ - море. (И более удобных между прочим)

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

Стойкость алгоритмов RSA основана на очень ресурсоемкой задаче нахождения пары простых чисел для определения криптографического ключа. Т.е. нет такого простого алгоритма, чтобы рраз - и огромное число разложить на нужную пару простых чисел. Приходится подбирать. При достаточной длине ключа это занимает огромное время. Даже на суперкомпьютерах. На сегодня стойким ключом можно считать 1024-битную последовательность (PGP RSA). Однако, совсем недавно математик Дэвид Бернштейн нашел способ увеличить скорость разложения больших чисел на простые множители. Говорят о том, что это - "прорыв десятилетия в криптографии". Ключи длиной 1024 бит больше не считаются достаточными для военных применений.

Да и вообще, ключами короче 2048 пользоваться просто не рекомендуют. Пока выход относительно простой - пользуйтесь более длинными ключами - не менее 8К. Но это, похоже, тоже временная мера.

Так что, вся криптография на несимметричных ключах стала менее надежной.

Подробнее об этом можно почитать здесь (англ.)


//

cooler.it

// cooler.it

 

А я когда-то занимался самостоятельной реализацией RSA, точнее эффективной реализацией арифметики на Wintel для сколь угодно больших целых беззнаковых. Каждое число представленно как динамический массив DWORD'ов произвольной длины. Класс С++ HugeInt с операторами реализованными на инлайн-ассемблере. (И уж ессно не побитовые операции...)
А в проекте rc5 тоже участвую...

А как дело в надежностью нашего родного ГОСТа-89?

Родной ГОСТ 28147-89 - это блочная СИММЕТРИЧНАЯ криптосистема, никакого отношения к RSA не имеющая. Он приходится, скорее дальним родственником DESу (Да и то лишь по сходной структуре итераций. Шаг шифрования у него совсем другой). Ключ у него "всего" 256 бит. Но учтите, что это 256 СЛУЧАЙНЫХ бит. Так что для прямой атаки на ключ нам надо перебрать ВСЕ 2²⁵⁶ ключей(это куда круче, чем в случае RSA-1024), что ФИЗИЧЕСКИ не реализуемо: при минимальном энергопотреблении взламывающего вычислителя(оно определяется исходя из квантовой теории) оказывается, что для обспечения энергией такого вычислителя нам необходимо рвануть сверхновую . На самом деле, конечно, перебор идет не втупую, но и при таком раскладе стойкость симметричного ГОСТа ФАПСИ считает вполне достаточной, разумеется при разумном его применении.
Однако в коммерческом шифровании обычно используются гибридные шифрсистемы (PGP, отечественный Крипто-Про CSP и проч.). В таких системах шифрование информации ведется симметричным шифром по случайно сгенерированному сеансовому ключу, а сам ключ шифруется несимметричной криптосистемой и передается в таком виде вместе с сообщением. В таком случае стойкость всей системы определяется стойкостью несимметричного шифра.
В РФ в настоящее время действуют 2 стандарта на ЭЦП(читай - несимметричное шифрование): ГОСТ - 34.11.94 (1024 открытый и 256 бит закрытый ключ) насколько я помню, он представляет из себя вариант системы Эль-Гамаля; и ГОСТ-34.11.01 - это шифрсистема на эллиптических кривых. Длина его ключа 512 бит, но считается, что он значительно превосходит по стойкости RSA-1024, т.к. задача его перебора гораздо сложнее.

Artiom>Причем здесь длина ключа? Это - частности.

А при том, что 40 битный код защиты pdf файла я за 13 дней открываю на офисном компе (он только этим и занимался день и ночь ).

Народ, объясните, неужели проще создавать эти супер коды, чем расслабиться и придумать алгоритм или алгоритмы, которые просто обезличивали бы данные, а потом их слегка шифровали?
Т.е. расшифровать будет просто, но какой из тьмы вариантов правилен - не видно. Т.е. использовать не стандартный, а специфический алгоритм, или даже сильно зависящий от ключа метод преобразования/шифрования?

Например, чтобы закодировать звук, можно подвергнуть его какому-то преобразованию, например на пакетах вэйвлетов собственной конструкции. Как восстановить такое, иначе как комплементарным пакетом, понятия не имею, т.е. без участия человека.. а у человека скорость пониже будет

au>Народ, объясните, неужели проще создавать эти супер коды, чем расслабиться и придумать алгоритм или алгоритмы, которые просто обезличивали бы данные, а потом их слегка шифровали?
Сложнее, но сколько надо таких хитрых алгоритмов? Много. Поэтому в результате оказывается дешевле иметь ОДИН алгоритм т менять ключи. Кстати в ГОСТ часть алгоритма (S блоки) тоже являются частью ключа.
au>Т.е. расшифровать будет просто, но какой из тьмы вариантов правилен - не видно. Т.е. использовать не стандартный, а специфический алгоритм, или даже сильно зависящий от ключа метод преобразования/шифрования?
Давно известный абсолютный шифр - одноразовый шифроблокнот, вот только пользоваться им не удобно

au>Например, чтобы закодировать звук, можно подвергнуть его какому-то преобразованию, например на пакетах вэйвлетов собственной конструкции. Как восстановить такое, иначе как комплементарным пакетом, понятия не имею, т.е. без участия человека.. а у человека скорость пониже будет
Потому, что я утащу у тебя программу расшифровки и все...
На самом деле у тебя получается ключ = алгоритм.
А вообще почитай прикладную криптографию Шнайдера. Очень полезно.

Вообще-то таблица замен в ГОСТе действительно является произвольной и может являться частью ключа. Однако на практике так не делают. Обычно в рамках одного криптоузла используется фиксированная таблица замен (в криптопровайдере Крипто-Про, к примеру, она одна на всех пользователей и никто особенно не расчитывает, что она останется секретом, ведь код программы общедоступен). На самом деле даже разглашение такой таблицы не делает наш ГОСТ неустойчивым к взлому. Зато использование самостоятельно сгенерированных таблиц связано с риском попасть на слабую таблицу и обрушить весь шифр. Ведь у Вас же нет всей полноты информации о ГОСТе и тех возможностей, какими располагает ФАПСИ, так что проверить самопальную таблицу замен на слабость Вы не сможете.

2au
Обезличивание данных без ключа действительно чревато теми последствиями, которые Вам описали. Вообще все серьезные криптосистемы проектируются из расчета, что противнику известен алгоритм шифрования во всех подробностях , известен открытый текст некоторых шифровок (ведь их разведка не зря хлеб ест) и неизвестен лишь ключ шифрования. Вот при таких жутких условиях шифр и должен обеспечить защиту данных. Наши ГОСТы, к примеру, таким требованиям соответствуют (по крайней мере с точки зрения ФАПСИ ). Коммерческие криптологи вообще относятся с огромным подозрением к тем авторам систем шифрования, которые пытаются скрыть алгоритм: кому надо, его все равно украдут, а отсутствие информации по алгоритму оставляет большие сомнения по поводу его надежности, т.к. делает невозможным анализ стойкости независимыми экспертами.
Правда обезличивание данных (точнее, выравнивание статистики сообщения) зачастую является одним из этапов шифрования сообщения. Обычно сначала шифровка кодируется оптимальным кодом, ужимающим ее размер и выравнивающим статистику сообщения(для этого может быть использованы стандартные, либо чуть модифицированные программы-архиваторы), а затем уже такое сообщение закрывается стойким шифром. При этом стойкость такой шифровки будет выше чем при обычном шифровании, т.к. затрудняется атака на шифр по известной статистике открытого текста (у архивированного текста она почти ровная). Таким макаром работает, к примеру, общеизвестный PGP.

Lamer>А вообще почитай прикладную криптографию Шнайдера. Очень полезно.

Чрезвычайно, хотя книга и не математическая. Кстати, там и про Российский гост сказано.

Короче, ГОСТ'а следует избегать всеми возможными средствами. Особенно потому что он сертифицированный. В частности он плох ещё и потому, что не допускает эффективной реализации без соответствующего железа. (Так?)
А вообще - против одноразового ключа(лома) - нет приема т.е. длина ключа - равна длине сообщения и ключ никогда не повторяется (разумеется, для симметричных криптосистем). И вот это уже допускает в наше время эффективную реализацию на бытовом уровне - пишем случайную последовательность, сгенерированную физическим генератором случайных чисел на пару CD (или на другой подобный высокоёмкий носитель) - и не имеем проблем (кроме оборота ключей ). Кстати, идея описана у того же Клэнси - вроде бы такой криптосистемой пользуется ЦРУ.
Несомненно, родное для U235 ФАПСИ будет всеми силами противодействовать повсеместному внедрению подобных систем - так он/оно имеет неплохой навар за каждую установку ГОСТА("невскрываемость" которого для ФАПСИ/КГБ под бо-ольшим вопросом...) Ведь сертифицируется (и оплачивается!) не весь криптоалгоритм или программа в целом - а каждая установка!
Так что, IMHO, большого будущего у симметричных криптосистем нет. Их убивает широкое распространение дешёвых высокоемкх и компактных носителей информации. Какое-то будущее у криптографии как науки связано только с несимметричными криптоалгоритмами по типу RSA - но у несимметричных криптосистем довольно специфическое и ограниченное поле применения (хотя не сказать что маленькое) - т.е. цифровая подпись.
Ну что, обсудить ещё бытовой физический генератор случайных чисел - или и так очевидно как его выпечь?

>Короче, ГОСТ'а следует избегать всеми возможными средствами.

Что за бред??

>Особенно потому что он сертифицированный.

И что теперь?? Одно дело красивая коробочка или програмка с окошками в которой абсолютно_не_ломаемый_алгоритм. А другое дело описание алгоритма, который можете попытаться взломать. Если сможете. А реализация... Пишете сами - и как минимум будете уверены что дырок нет и прога на вас не стучит

>В частности он плох ещё и потому, что не допускает эффективной реализации без соответствующего железа. (Так?)

Абсолютно не так - ГОСТ довольно эффективный алгоритм для реализации на любом компе, DES по сравнению с ним отдыхает.

>А вообще - против одноразового ключа(лома) - нет приема т.е. длина ключа - равна длине сообщения и ключ никогда не повторяется

А ключи вы как передавать будете? Это ГЛАВНАЯ проблема - передать ключ, так чтобы противник его не стырил. Потому и возникли алгоритмы с открытыми ключами и своими проблемами. (к примеру подмена ключей).

>Ведь сертифицируется (и оплачивается!) не весь криптоалгоритм или программа в целом - а каждая установка!

А нафига вам это надо - менять красивые бумажки(деньги) на красивые бумажки(сертификаты)? Криптостойкость алгоритмов от этого не меняется.

>Так что, IMHO, большого будущего у симметричных криптосистем нет.
Весьма спорно.

>Их убивает широкое распространение дешёвых высокоемкх и компактных носителей информации.

А это тут причем?

>Ну что, обсудить ещё бытовой физический генератор случайных чисел - или и так очевидно как его выпечь?

А что его обсуждать - белый шум+АЦП.

>>Короче, ГОСТ'а следует избегать всеми возможными средствами.
TEvg>Что за бред??
U235> Ведь у Вас же нет всей полноты информации о ГОСТе и тех возможностей, какими располагает ФАПСИ, так что проверить самопальную таблицу замен на слабость Вы не сможете.
Так же как и проверить предлагаему "сверху" таблицу.

TEvg>Одно дело красивая коробочка или програмка с окошками в которой абсолютно_не_ломаемый_алгоритм. А другое дело описание алгоритма, который можете попытаться взломать. Если сможете. А реализация... Пишете сами - и как минимум будете уверены что дырок нет и прога на вас не стучит
Да дырки в проге - это из другой оперы. И, кстати, я - писал. Здесь обсуждается стойкость алгоритмов.

>>В частности он плох ещё и потому, что не допускает эффективной реализации без соответствующего железа. (Так?)
TEvg>Абсолютно не так - ГОСТ довольно эффективный алгоритм для реализации на любом компе, DES по сравнению с ним отдыхает.
Ха! Ну в точности наоборот - ГОСТ 28147-89 - страшне-ёйшая муть по сравнению с DES. Ну просто и рядом не лежал! Эффективная реализация - только на заказных микросхемах (по крайней мере лет 6 назад).

>>А вообще - против одноразового ключа(лома) - нет приема... TEvg>А ключи вы как передавать будете? Это ГЛАВНАЯ проблема - передать ключ, так чтобы противник его не стырил. Потому и возникли алгоритмы с открытыми ключами и своими проблемами. (к примеру подмена ключей).
Ну так - естественно! Проблема симметричных криптосистем - передача ключа, проблема несимметричных - производительность на длинных сообщениях. Поэтому в настоящее время и используются гибридные криптосистемы, где обмен сеансовыми ключами симметричных алгоритмов обеспечивается путем использования несимметричных алгоритмов. И, конечно же, для использования в такой гибридной криптосистеме одноразовый ключ совершенно не подходит.

>>Ведь сертифицируется (и оплачивается!) не весь криптоалгоритм или программа в целом - а каждая установка!
TEvg>А нафига вам это надо - менять красивые бумажки(деньги) на красивые бумажки(сертификаты)?
Ну, Вы очевидно не в курсе. Дело в том, что в ряде случаев законодательно вменено использовать сертифицированные криптосистемы. (В банках например). И во многих других случаях тоже...
TEvg>Криптостойкость алгоритмов от этого не меняется.
Ессно. Другое дело, что сложный криптоалгоритм может быть специально сконструирован для того, чтобы иметь способ эффективного его вскрытия (для авторов). А оценивать стойкость сложного алгоритма, в частности для того чтобы проверить и это предположение - занятие в пользу бедных. Гораздо проще не ломать себе на этом голову и не закладывать мину на будущее - а обеспечить надёжный канал обмена одноразовыми ключами.

>>Их убивает широкое распространение дешёвых высокоемкх и компактных носителей информации.
TEvg>А это тут причем?
Это СИЛЬНО упрощает обмен ОДНОРАЗОВЫМИ ключами. Имеется в виду физический канал передачи ключей. (Курьер в танке! С чемоданом СD! Один раз в 10 лет!)

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

Так что, если хотите иметь удобство гибридных и несимметричных криптосистем - добро пожаловать. Но всегда за счёт надёжности. (И простоты/производительности )

U235> Ведь у Вас же нет всей полноты информации о ГОСТе и тех возможностей, какими располагает ФАПСИ, так что проверить самопальную таблицу замен на слабость Вы не сможете.

Разумеется.

>Так же как и проверить предлагаему "сверху" таблицу.

Вывод - не пользуйтесь чужими таблицами.
Вообще вероятность что случайно сгенереная таблица не будет слабой достаточно велика.

>Ха! Ну в точности наоборот - ГОСТ 28147-89 - страшне-ёйшая муть по сравнению с DES. Ну просто и рядом не лежал! Эффективная реализация - только на заказных микросхемах (по крайней мере лет 6 назад).

Ну что вы. Это на жесткой логике муть. При наличии микропроцессора и асемблера задача решается тривиально.

>Поэтому в настоящее время и используются гибридные криптосистемы, где обмен сеансовыми ключами симметричных алгоритмов обеспечивается путем использования несимметричных алгоритмов. И, конечно же, для использования в такой гибридной криптосистеме одноразовый ключ совершенно не подходит.

Криптостойкость в таком случае целиком определяется криптостойкостью несимметричных алгоритмов для шифрования ключа.

TEvg>Вывод - не пользуйтесь чужими таблицами.
TEvg>Вообще вероятность что случайно сгенереная таблица не будет слабой достаточно велика.
Вывод - избегайте ГОСТ'а, если можете. А если не можете - передавайте по сертифицированным каналам информацию, уже защищённую каким-либо другим альтернативным криптоалгоритмом.

Ghola>>Ха! Ну в точности наоборот - ГОСТ 28147-89 - страшне-ёйшая муть по сравнению с DES. Ну просто и рядом не лежал! Эффективная реализация - только на заказных микросхемах (по крайней мере лет 6 назад).
TEvg>Ну что вы. Это на жесткой логике муть. При наличии микропроцессора и асемблера задача решается тривиально.
Ну что Вы мне говорите. Что Вы называете жёсткой логикой? Или, быть может, Вы имеете в виду использование математического сопроцессора? Чем он тут может помочь? Делать надо на целочисленных операциях основного процессора. (Как раз и есть жёсткая логика, IMHO) Речь идёт об эффективной реализации (в смысле высокой производительности).
Я как раз и занимался реализацией на аСсемблере. (Но к счастью не ГОСТ'а!) У меня на столе лежит описание ГОСТ'а. Задача конечно решается. Несомненно. Причем может решаться и без ассемблера. Но - значительно труднее чем DES, который, кстати, прекрасно реализуется и без ассеммблера.

Ghola>>Поэтому в настоящее время и используются гибридные криптосистемы...
TEvg>Криптостойкость в таком случае целиком определяется криптостойкостью несимметричных алгоритмов для шифрования ключа.
Безусловно. Потому я говорю, что за ними будущее. Как раз цифровая подпись и есть.
Ghola>>Так что, IMHO, большого будущего у симметричных криптосистем нет.
TEvg>Весьма спорно.

? Заметьте гибридные vs симметричных!

А вообще, доверие к критоалгоритму определяется в большой степени доверием к его разработчику. Я вот, например, не сомневаюсь что ФАПСИ/АНБ(NSA) способны разработать надёжный криптоалгоритм. Так же я не сомневаюсь, что если у них есть возможность встроить в криптоалгоритм (подчёркиваю в алгоритм), предлагаемый к повсеместному использованию "заднюю дверь" - то они такую возможность несомненно используют.
Ну а в случае с одноразовым ключом - такая проблема не возникает. Так к чему умножать сущности?

>>Вывод - избегайте ГОСТ'а, если можете.
TEvg>Блин! Ну с какого фига? КГБ вашу инфу прочтет? Дык эта опасность есть ВСЕГДА. ПРИ ИСПОЛЬЗОВАНИИ ЛЮБОГО АЛГОРИТМА. В случае DES вашу инфу не сможет прочесть только ленивый.
Ну, не всё так однозначно. По крайней мере в случае тройного DES. Но я имел в виду в первую очередь шифрование с одноразовым ключом...

TEvg>О каких заказных ИС речь? Что это за схемы такие? iP55 не подойдет? кстати прекрасно шифрует звук ГОСТом в реальном времени.
Уточнить типы ИС не могу - не знаю. А что касается шифрования звука в реальном времени - так например голос можно предварительно ужимать до 3.6 Кб/сек. (А то и менее... Как бы не 1.5 Кб/сек...) Шифровать такой поток - не слишком большое достижение. Лучше уж скажите производительность по потоку.

TEvg>ГОСТ в несколько раз БЫСТРЕЕ на ПИСЮКЕ чем DES.
Вот это новость. А ссылку не кинете? Я до сих пор встречал только обратные оценки. Или, быть может, сравнивалась кривая/самопальная реализация DES с оптимизированным ГОСТ'ом? К примеру испытания проводились не независимыми экспертами, а производителями криптосистемы на основе ГОСТ'а? Нет?

TEvg>В отличие от прочих алгоритмов которые время от времени ломают (DES, MD5..) я никогда не слышал о взломе ГОСТа. Могет и есть такие умные, только ничего об этом не слышно.
Неуловимый Джо? ("А кому он на хрен нужен?") Шучу...

TEvg>К тому же ГОСТ делался не для того чтобы КГБ было в курсе всего, а для внутреннего применения, для того чтобы империалисты наши секреты не узнали. Для этого специально делали слабый и дырявый алгоритм?
Как сказать, как сказать. Алгоритм гражданский - не военный, так? Посмотрите на год введения - 1989-тый. Расцвет перестройки, становление кооперативов - и т.п. По-моему уже рекламу "Инком-банка" крутили по ТВ. Думаю, как предпочтительный вариант подразумевалась бы защита от капиталистов и доступ к информации для ГБ. Я не говорю, что это безусловно так. Просто этого нельзя исключить. Аналогично и для DES.