Успешно прозведена факторизация RSA640

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

Сдаётся мне что кто-то не различает алгоритмы открытого и алгоритмы закрытого ключа.

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

Шаман, число у тебя в нике это твой возраст?
Зачем пропускать подобную желтую прессу?

Если я не ошибаюсь то сложность взлома растет экспоненциально с ростом длины ключа... вот когда взломают 2048 бит тогда и поговорим... ждем квантового компьютера

чет них#^на не понимаю. обычная статейка о несимметричном шифровании с открытым ключом. с чего сыр-бор то?

зы: по слухам Ферма умел в уме находить простые множители, вот если бы этот алгоритм откопали... мир бы ждала краткая и мучительная агония.

> зы: по слухам Ферма умел в уме находить простые множители, вот если бы этот алгоритм откопали... мир бы ждала краткая и мучительная агония.

это он тебе на ухо нашептал? ;)))

на емуляторе квантового компьютера за пущенном в свеже придуманной JVM

> на емуляторе квантового компьютера за пущенном в свеже придуманной JVM

Столько не живут, Брат.
Да пребудет с тобой Томми.

> Поубивал бы журналистов Ленты.Вру, --прим. ivlad

Спасибо за исправления. Полностью согласен относительно журналюг: их нужно изолировать - идиоты зачастую опаснее безумцев.

>Если я не ошибаюсь то сложность взлома растет экспоненциально с ростом длины ключа... вот когда взломают 2048 бит тогда и поговорим... ждем квантового компьютера

Сложность должна расти экспоненциально.

Однако, уже пару лет как в Индии был разработан метод быстрого разложения на простые множители. И рост - полиномиальный))

ага, Ферма на мой взгляд был большим п*ном,
его фраза типа полей не хватает, поэтому я доказательства не напишу,
но оно тривиальное чего стоит.

Что за метод? Где о нём можно почитать?

http://en.wikipedia.org/wiki/Sieve_of_Atkin

In mathematics, the Sieve of Atkin is a fast, modern algorithm for finding all prime numbers up to a specified integer. It is an optimized version of the ancient Sieve of Eratosthenes...

A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.

Primegen is a small, fast library to generate prime numbers in order. It generates the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350; it prints them in decimal in just 35 seconds.

http://ru.wikipedia.org/wiki/Простое_число

Существует множество полиномиальных алгоритмов проверки того, является ли данное число n простым, называемых тестами простоты. Большинство таких алгоритмов являются вероятностыми (например, тест Миллера-Рабина) и используются для нужд криптографии. Только в 2002 году было доказано (http://mathworld.wolfram.com/AKSPrimalityTest.html), что задача проверки на простоту в общем виде полиномиально разрешима, но предложенный детерминированный алгоритм имеет довольно большую сложность, что затрудняет его практическое применение.

> Однако, уже пару лет как в Индии был разработан метод быстрого разложения на простые множители. И рост - полиномиальный))

Не разложения, а проверки на простоту.

так что ребята с http://www.distributed.net/rc5/ не успели?

>Поубивал бы журналистов Ленты.Вру, --прим. ivlad.

Точно. Налицо глубокое незнание автором статьи предмета, о котором он пишет. Отписал редакции, в письме дал линк на это обсуждение, будем ждать реакции.

По существу: произведенная факторизация сама по себе ничего не дает, это просто своеобразный математический опыт. Алгоритм RSA не взломан, и еще очень долго не будет взломан. Так что лемминги могут спать спокойно.

>Однако, уже пару лет как в Индии был разработан метод быстрого разложения на простые множители. И рост - полиномиальный))

Правда, что-ли? С полиномиальным ростом?!! А ссылочку можно?

Да пробегала с год назад ссылка. Там один индус сказал, что разработал полиномиальный метод; потом оказалось, просто идиот был...

>задача проверки на простоту в общем виде полиномиально разрешима

Возможно я ошибаюсь, но, IMHO, задача проверки на простоту (алгоритмическое доказательство неразложимости данного числа) и задача нахождения сомножителей непростого большого числа - суть разные задачи. Меня интересует, существует ли, хотя бы, _полиномиальный_алгоритм_ разложения больших чисел.

А эта новость всего лишь о том, что при помощи мощной числодробилки удалось разложить конкретное n-значное число за приемлемое время.

>ждем квантового компьютера
Долго ждать придётся.

Опоздал в школу. Гулял с собакой. Админам похоже нравится черкать.

> Меня интересует, существует ли, хотя бы, _полиномиальный_алгоритм_ разложения больших чисел

Может и существует, но о нем пока никому неизвестно.

да-да. правильно поправили - проверка простоты разработана, а с разложением пока туго.

>>ждем квантового компьютера >Долго ждать придётся.

Кстати, компы, заточенные под определённые задачи, уже есть. Я запамятовал название города, но даже у нас ведутся весьма успешные разработки с последующим внедрением.

Однако, уже пару лет как в Индии был разработан метод быстрого разложения на простые множители. И рост - полиномиальный))

RRD (*) (13.11.2005 17:33:30)

Угу. Вот только обычно говорят степенной, потому как в полиноме если это действительно полином пренебрегают членами с младшими показателями степени в пользу самого старшего.

В этой связи хотелось бы знать степень?

ivlad, спасибо за оригинальную ссылку и исправления :-)

"На стене было написано: 'Штирлиц скотина и русский шпион'. Штирлиц зачеркнул слово 'шпион' и написал сверху: 'разведчик'"...

Навеяло чирканым постом ;)

Да пусть ломают чё хотят! Кому мы нужны? :)

А шифровать лучше всего вообще "белым шумом".

Добрый день. Этот текст написал я.

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

Давайте поговорим о зачеркнутом.

>сумели взломать алгоритм шифрования RSA

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

Вопрос: если сообщение, закодированное 640-битным ключом, можно прочесть через три часа (утверждение - на совести комментаторов Шнейера, но им я отчего-то склонен доверять), то почему это - не взлом?

>В этом не было ничего противозаконного

В этом было что-то противозаконное?

>Однако "нестойкость" математического алгоритма может стоить куда больших денег тем, кто пользуется шифрованием в Интернете.

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

Жду вопросов.

>Отписал редакции, в письме дал линк на это обсуждение, будем ждать реакции.

Zlyden, а Вашего письма мы не получали. Продублируйте, а? Мы коллекционируем, это довольно увлекательно.

Ждете вопросов? Пожалуйста!

Почему вы не написали "в который раз взломан алгоритм RSA?" или так было бы менее похоже на сенсацию?

> Однако "нестойкость" математического алгоритма может стоить куда больших денег тем, кто пользуется шифрованием в Интернете.

вы хотели намекнуть на то, что файлы пересылаемые по почте в запароленном архиве могут быть легко перхвачены? или вы пугаете пользователя тем, что его SSL сессия может быть расшифрована?

тогда почему вы не написали о том, что сейчас обычно применяются ключи длиной 1024–2048, в то время как взломан был ключ длины 640?

Не стесняйтесь, расскажите правду. Вас здесь поймут - "работа такая" и т.д.

>В этом не было ничего противозаконного

Почему вы не написали "ни одно животное не пострадало?"

> алгоритм предъявлялся как невзламываемый за разумное время

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

Факторизация 640-битного ключа просто наглядно показала, что эта длина заведома мала, вот и все. Это было и так известно.

Сам RSA от этого хуже не стал.

Ужас какой. 10 штук баксов за два года усилий (если учесть что только этой херней и надо заниматься все время) плюс сомнительная известность. Минус красные глаза, геморрой и т.д.

-edward

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

Ну, новость, безусловно, нужная: надо же быть в курсе, где там "ковырятели" еще топчутся.

Вы снова игнорируете самое основное :"Сотрудники Федерального агентства по информационной безопасности Германии сумели взломать алгоритм шифрования RSA." - ваша фраза?

Так вот, алгоритм взломан не был. Только одно число было разложено на множители. Это никак не характеризует алгоритм. Это только говорит о том, что ключ надо длиннее делать. А это, как здесь уже говорили, не новость. Разве это не искажение фактов, ради красивого заголовка статьи? И насколько это этично? По-моему это как минимум некрасиво по отношению к читателям, которые не разбираются в теме и не могут отличить одно от другого. Хотелось бы услышать Ваши комментарии именно по этому поводу.

>1024 для гражданских целей

Вот какая штука: в 2001 году, то есть через год после снятия запрета на экспорт сильной криптографии, Microsoft <a href=http://www.microsoft.com/windows/ie/downloads/recommended/128bit/default.mspx>;встраивал</a> в свой IE5.5 поддержку 128-битного шифрования. Не более чем. Это называлось High Encryption Pack.

1024 бита, и пусть никто не удйет обиженным. На слэшдоте, например, об угрозе взлома 1024-битных ключей <a href=http://slashdot.org/it/02/03/25/2125211.shtml>;писали</a> еще в 2002 году со ссылкой на DJB.

Что касается сверхдлинных ключей (а даже GnuPG, например, не предлагает создавать более чем 1024-битный RSA-ключ), то, как говорят, из-за них будут тормозить уже не машины взломщиков, а машины пользователей. То есть шифрование (не говоря уже о подписывании) будет длиться заметно дольше, чем хотелось бы.

>Налицо глубокое незнание автором статьи предмета, о котором он пишет. Отписал редакции, в письме дал линк на это обсуждение, будем ждать реакции.

Смешно. Там же написано сверху: "Lenta.ru - издание Rambler". Проще говоря, бараны по определению.

>> 1024 для гражданских целей

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

Слово ``гражданских'' вы ведь намеренно проигнорировали?

Я отлично помню эту историю со статьей Берштейна. И отлично помню примерную стоимость создания описываемой машины - 1 миллион долларов. Покажите мне _гражданина_, ради которого потратят столько денег, чтобы расшифровать его любовную переписку.

В серьезных делах длины ключей всегда были больше.

Кончайте трепать. Проблема факторизации больших чисел не решена, RSA не взломан.

Фраза - моя. Вы хотите понимать под взломом алгоритма математически чистый способ раскладывать число на множители за полиномиальное время. Я - способ прочитать данные, зашифрованные пользователем с помощью "сверхнадежного" метода.

"Сверхнадежность" оказалась ниже - один и тот же GNFS работает лет семь как и дает взломать не "удачные" ключи, а все подряд (до определенной длины) на не бог весть каких машинах.

Кстати, квантовый алгоритм взлома с полиномиальным временем придумали еще в 93-м году, причем 5-кубитный IBM'овский компьютер тестировали как раз с его помощью. Разумеется, говорить, что таким способом "уже взламывают", наверное, нельзя. Взламывают вполне классическими методами, а данных по суперкомпьютерам как раз нет. Что заставляет беспокоиться и беспокоить читателей.

Примерно это я имею в виду.

>Проблема факторизации больших чисел не решена, RSA не взломан.

Тут даже обсуждать нечего. Просто глупо обвинять машину за то, что в нее можно залить бензин не лучшего качества. Да и мой пост он сознательно игнорирует. По-моему, пора ему слив засчитать.

Расскажите, где в определении Рамблера упомянуты бараны. Можете ограничиться ссылкой (не на себя). Больше ссылок - коллекция интересней.

Предыдущий пост прошу не учитывать, слова забираю обратно. Поторопился. Мои извинения.

>Вы хотите понимать под взломом алгоритма математически чистый способ раскладывать число на множители за полиномиальное время. Я - способ прочитать данные, зашифрованные пользователем с помощью "сверхнадежного" метода.

Как раз наоборот. Это Вы из того, что число разложили на множители сделали вывод о том, что алгоритм взломан. Я же говорю об обратном. Алгоритм не взломан. Это лишь показывает, что длина ключа должна быть больше. Еще раз повторю, это не новость.

И снова повторю, что не стоит винить машину в том, что в нее можно залить некачественный бензин. Это не ее недостаток. То, что разложили на множители ЭТО число, не говорит о том, что теперь с легкостью будут раскладывать и все прочие, независимо от их размера. Это не есть показатель качества RSA.

>Вы хотите понимать под взломом алгоритма математически чистый способ раскладывать число на множители за полиномиальное время. Я - способ прочитать данные, зашифрованные пользователем с помощью "сверхнадежного" метода.

Если совсем честно, то для того, чтобы прочитать данны зашифрованные RSA, просто необходимо это уметь. :)

А может быть, поделитесь коллекцией?

А что такого? Прогу написал, запустил на полсотни компов юзверям и пусть разлагает на множители по вероятностному алгоритму - авось разложит ко второму пришествию. Я себе такую фигню в init.d уже положил - памяти жрёт мало. Когда-нибудь разложит, если повезёт. А что, двести штук-то нелишние.

Так и вспоминается из рекламы: А чё, 10 баксов-то не лишние. :)