1024-битный шифр RSA взломают через пять лет

[@Dogen]

Мы-то здесь все знаем, что теоретическая стойкость алгоритма - не вполне достаточный показатель стойкости к внешним воздействиям всей информационной системы, рассматриваемой вместе с "потребителями" и операторами :)

И мы же здесь договорились, что будем рулить квантовыми компьютерами? Зачем нам очередные криптострашилки :)

[@drJonnie]

Запрещает. Только насчет 128 бит я не совсем уверен. И, кажется, это только в США.

[@uranik]

У нас ограничение только для информации не содержащей сведений, составляющих государственную тайну.

[@uranik]

В России сейчас разрешен 256 закрытый / 512 открытый ключ (см ГОСТ Р 34.10 2001) хотя раньше можно было использовать 256 / 1024 (ГОСТ Р 34.10 94) но видимо его органам было сложно ломать, поэтому подрезали :)

[@sgnppv]

Только всем класть на эти ограничения, ну кому нужно конечно.

[@ppx]

чтобы "врагов народа" вычислять :)

[@pietrovich]

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

и вроде далеко не на все системы...

>>Интересно, с какой целью?
да всё с той-же - суметь расшифровать при необходимости.

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

З.Ы.: статье речь не про SSL, но вопрос про 128 касается именно его...

[@blv]

В РФ есть ограничения на использования шифрования. Знаю случай, когда дело дошло до суда, за то что контора использовала программу для шифрования, которая чем-то не устраивало органы.

[@pietrovich]

не знал. теперь буду знать.

[@pietrovich]

доступ к необходимым мощностям... я так думаю :)

[@pietrovich]

!это всего-лишь мое мнение, оно может не совпадать с действительностью...

[@ecne]

это относится к симметричным системам.
с асимметричными история совсем другая, 1024бит — это вообще разумный минимум (пока)

вот еще, кстати, из википедии:
15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys.

[@alexiso]

Российское законодательство относит изготовление, распространение и обслуживание средств защиты информации, в том числе шифрсистем, к лицензируемой деятельности. Лицензии выдает ФСТЭК, а для средств используемых в государственной деятельности, также Техкоммиссия при Президенте. Законодательно установленных ограничений на длины ключей нет, но какими будут условия лицензии... известно, только сами знаете кому. В личных целях млжно использовать шифрсистемы любых типов и любой сложности. Дискуссия по этому повожу уже была.

[@sgnppv]

Спасибо, буду знать!

[@ecne]

RSA — это система шифрования с открытым ключом, почему в тэгах наоборот? :)

[@alizar]

Открытым ключом зашифровывают текст для конкретного человека, чтобы тот мог расшифровать его с помощью своего закрытого ключа. Это и есть главаная идея систем шифрования с открытым ключом.

[@gribozavr]

Арьен Ленстра рассказал об успешном эксперименте, в рамках которого было разложено на два множителя 307-значное число.
Там три множителя. Хотя один из 7 десятичных знаков, а другие два — 80 и 277.

2^1039-1 = p7*p80*p227

Первый делитель p7 был уже давно известен.

Для высеивания было затрачено 6 календарных месяцев. Были задействованы различные компьютеры и кластеры в EPFL, NTT и в университете города Бонн. Общее время высеивания эквивалентно 100 лет работы Athlon64/Opteron [2.2GHz].

Решение полученной матрицы заняло 59 дней на 110 процессорах Pentium D [3.0GHz]. Календарное время составляет 69 дней, но были периоды, когда вычисления не производились, поэтому общее время работы эквивалентно 59 дням непрерывных вычислений.

http://listserv.nodak.edu/cgi-bin/wa.exe…

[@alizar]

Круто. Добавил в текст, спасибо.

[@eterevsky]

Вообще-то к стойкости криптосистем это имеет достаточно слабое отношение, так как простые делители чисел Мерсенна (2^p - 1) имеют весьма специальный вид и искать их гораздо легче, чем простые делители произвольного числа.

[@bulbazaur]

Всем, кто увлекается криптографией, советую почитать "Цифровую крепость" Брауна.

[@fanex]

Всем, кто увлекается витрувианским человеком и теорией заговора, читать "Код даВинчи" ;)

Я прочитал "Ангелы и демоны" и "К дВ" Брауна, первые лучше были. За "Крепость" браться не хочу, т.к. Демоны интересней.

[@alizar]

А лучше "Криптономикон" Стивенсона. Там реальные шифры и листинги исходников даже есть. Брюс Шнайер помогал.

[@Dogen]

Именно, что "увлекается" :) Я читал, уже забыл, но ощущение "автор не в теме" осталось ;)

[@dreamwind]

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

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

[@alexiso]

Криптостойкость RSA-1024 - 3*10^11 MIPS-лет. Intel Core Duo E6600 - 22100 MIPS. Итого для взлома в течении года RSA-1024 нужно 13 млн компьютеров, что составляет немногим более 1% общего числа пользователей Интернет. Объединяем их в грид и, так как это вероятностный процесс, в среднем через полгода 100000$ у нас в кармане. Чтобы привлечь клиентов, организуем партнерку, где 10К получает собственно взломавший, а по 1К его 10 партнеров. Чистая прибыль 80 штук.

[@gribozavr]

RSA factoring chellenge отменено. Больше призы не выдаются.

http://www.rsa.com/rsalabs/node.asp?id=2…
http://www.rsa.com/rsalabs/node.asp?id=2…

[@alexiso]

Чегтовски жаль. А я уже поделил эти 80 штук.

[@sgnppv]

Вот возьми и найди 13 миллионов человек с кор2дуо Е6600 согласных в течении года жечь электроэнергию и не выключать компьютеры. Интересно какое количество энергии будет затрачено?

Моё предложение - закупаем Cell (по моему один проц стоит 600 баксов) в количестве десяти тыщ штук, обьединяем, денег много не получим зато получим самый производительный суперкомпьютер на планете :) 10 млн баксов - пустяки :)

[@Vox]

Ну сломали вы этот код и что дальше? За год информация которая была зашифрована скорее всего уже будет известна из открытых источников.

[@sgnppv]

Ну и я вот думаю что смысла нет.

[@alexiso]

Дело в том, что RSA, а точнее RSA-PSS активно используется для реализации цифровой подписи. Ключи, например в банковской сфере, могут не меняться годами. Я думаю нет необходимости объяснять, какие преимущества может дать знание закрытого ключа для организации подложной подписи.

[@Vox]

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

[@alexiso]

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

[@Dogen]

Еще большие преимущества даст успешная вербовка банковского админа. "И по деньгам дешевле".

[@alexiso]

Ну так года хватит. А вот мне всегда было интересно, как они депонируют открытые ключи - на броневике развозят по банкам? :)

[@alexiso]

Я имел в виду банки. Яндекс - это несерьезно. Обновление ключей через интернет поддается атаке man-in-the-middle.

[@dreamwind]

рассчитай вероятность того, что 1% пользователей будет объединен в сеть (например, с помощью вируса)

[@gribozavr]

Просто — нет. Но вполне реально для тех, кто имеет необходимые вычислительные мощности и квалифицированных специалистов.

[@alexiso]

Кстати если учесть закон Мура, то через 10 лет для вскрытия RSA-1024 в среднем, в течении полугода, нужно будет всего 420 тыс компьютеров, объединенных в грид. Для сравнения к известным серверам Осла за раз подключается больше народу.

[@dreamwind]

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

[@OlegUfaev]

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

[@Dogen]

Нельзя ли ссылку не на эллиптические кривые, а на ассиметричное шифрование основанное на эллиптических кривых?

[@alexiso]

http://en.wikipedia.org/wiki/Elliptical_…

[@Dogen]

А где-нибудь подобные технологии дальше накладывания ЭЦП ушли? ЭЦП неинтересно.

[@alexiso]

ЭЦП, обмен ключами, аутентификация, широковещательный криптообмен, разделение секрета и много другое... Могу порекомендовать книгу Брюса Шнайдера "Прикладная криптография": очень широкий охват темы, популярность и особенности реализации алгоритмов.
(Этот текст других прошу не читать - pdf 3.41Мб)

[@Dogen]

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

[@saw]

вспомнил советских разведчиков и одноразовые блокноты.
p.s. спасибо за статью. да и комментарии тоже познавательные.

[@Dogen]

Почитайте "Криптономикон", про одноразовые блокноты :))) гарантии случайности нет.

[@Borodean]

Ну и чего? Есть успехи?