RSA again

[vitus_wagner]

Шнайер пишет о том, что разложено на множители 1023-битное число. Работа заняла 11 месяцев на каком-то там кластере. Всего лишь столетие процессоного времени. Соберите кластер из 10000 процессоров (или ботнет) и можно ломать 1024-битные RSA-ключи за неделю.

Что характерно, аналогичных результатов по дискретному логарифмированию (DSA, ГОСТ Р 34.10-94) пока нет. Тем не менее со следуюдего года ГОСТ Р 34.10-94 перестает действовать. Пользуйтесь ГОСТ Р 34.10-2001. Эллиптические кривые ещё никто не ломал.

Comments

[shaplov.livejournal.com]

А как же его ФСБ ломает? Ведь не могли одобрить стандарт для юзеров, который сами не могли бы взломать?

[besm6.livejournal.com]

Могли. Умение ломать - палка как минимум о двух концах.

[silly_sad.livejournal.com]

а они его и не ломают !
у них там бэкдор

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

( а вы думали зачем все продукты проходят сертификацию ? )

[vitus_wagner]

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

[tobotras]

Надо так же просить бутылку коньяка, если не найдет :)

[vitus_wagner]

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

[os80.livejournal.com]

А как соотносится между собой число попыток взлома RSA и ГОСТ Р 34.10-2001?
Не делаются ли из неполной инфы неверные выводы?

[stefashka.livejournal.com]

Так уже давно говорят, что для RSA надёжным является 2048-битные ключи. 1024 бит - "для лохов" уже несколько лет как.

Да и при таком раскладе 100 лет процвремени - не так уж мало. Овчинка должна выделк стоить, как-никак.

[vitus_wagner]

Электронная подпись по которой можно получить деньги явно стоит "выделки". Ни разу не меньше чем возможность разослать спамовые письма миллиону пользователей. (а под спам и DDoS ботнеты из десятков тысяч машин уже не просто заводят, а продают на черном рынке) И самое главное - подделка электронной подписи - это не сниффинг TLS-траффика. Задержка в неделю, а то и в месяц ничего не меняет. А что касается 2048битного ключа, надо алгоритм посмотреть. Может там зависимость от длины ключа уже близка к линейной.

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


Алгоритмы нормальные надо использовать. Те, которые США и Россия в качестве стандартов принимают, а не древний RSA, который хорош только тем, что был исторически первым.

[lightjedi.livejournal.com]

>>А что касается 2048битного ключа, надо алгоритм посмотреть. Может там зависимость от длины ключа уже близка к линейной.

Она не то что не близка к линейной, не близка даже к полиномиальной. Примерно е в степени кубический корень из длины ключа.

[avryabov.livejournal.com]

По такой оценке, выходит, что если на 1024 нужно 11 месяцев, то на 2048 - 138 месяцев, на 4096 - 3331 месяц.
ИМХО хреново растет время от сложности ключа.

[vitus_wagner]

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

[avryabov.livejournal.com]

В моем понимании текущая надежность 4096 уже становиться неудовлетворительной. Нужно хотя бы 16K

[avryabov.livejournal.com]

Если я опять же правильно считал, то 16К с учетом закона мура даст ~31 год. Что вполне прилично.

[lightjedi.livejournal.com]

Эта оценка грубая, там еще как минимум логарифм в показателе как множитель.

[avryabov.livejournal.com]

не понял.
O(length)=exp((length)^(1/3))
time=C*exp((length)^(1/3))
что не так?

[lightjedi.livejournal.com]

time=C1*exp(C2(length)^(1/3)*(log(length))^{2/3}).

[avryabov.livejournal.com]

Мда, я забыл про C2, а оно важнее, чем log(lenth)
ибо может капитально менять наклон графика.

[vitus_wagner]

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

[vitus_wagner]

Да, действительно - там обыкновенный SNFS. Со сложностью, пропоорциональной кубическому корню.
И в общем-то для дискретного логарифмирования в поле вычетов сравнимые оценки есть. Но есть та засада, что
там сложность определяется p, а размеры подписи - q, которое заметно меньше.

[temporalescha.livejournal.com]

Вообще, на таких длинах самым эффективным является на сегодняшний день GNFS. Там использовался именно он, судя по всему. Да и он все равно остается сверхполиномиальным.

[avryabov.livejournal.com]

А что сейчас США использует для открытого ключа?

[vitus_wagner]

Используют или принято в качестве стандарта? Используют в основном RSA. А стандартом является DSA.

[avryabov.livejournal.com]

А как у DSA со сложностью взлома?

[temporalescha.livejournal.com]

В США, собственно, 3 СТАНДАРТНЫХ варианта подписи. Сам стандарт описывает один (DSA) и ссылается на два других - ECDSA (на ЭК) и RSADSA (понятно, на чем).

[stefashka.livejournal.com]

В бизнесе задержка на неделю, а тем более - месяц, может стоить очень много :-) Что касается сложности взлома RSA, то она с битностью растёт экспоненциально.

RSA - вполне приличный алгоритм, неплохо исследован. Единственный "конкурент" поблизости - алгоритм Эль-Гамаля. Эллиптические кривые весьма перспективны, но они пока ещё молоды и недостаточно хорошо исследованы.

[cathody.livejournal.com]

И это при том, что ломают на машинах, не созданных под конкретную задачу.
Интересно было бы посмотреть на скорость взлома на "заказных" микросхемах.

[max630.livejournal.com]

http://www.usenix.org/events/sec05/tech/bono/bono.pdf

[slobin.livejournal.com]

Мне нравится оценка времени взлома, которой пользуется автор 7zip. Он считает время тупого перебора и закон Мура. Да, результатов "сравнимо с возрастом Галактики" не получается. Но сорок лет с учётом удвоения быстродействия каждые два года -- тоже неплохо.

... Позвонит однорукий водолаз - делай, что скажет ...

[vitus_wagner]

Кроме закона Мура стоит учитывать ещё количество процессоров, которые могут быть 0wned. Их число растет сейчас заметно быстрее, чем быстродействие отдельного процессора.

[slobin.livejournal.com]

Но зато быстродействие отдельного процессора уже почти не растёт. Если закон Мура понимать не в узком смысле -- про транзисторы на кристалле, а в широком -- про быстродействие, доступное для одной задачи, то со времён ЭНИАКа ничего, похоже, не менялось. Кста, ты видел статью (я нашёл по ссылке с ycombinator) про историю взлёта и упадка Thinking Machines?

... Dagor Bragollach - битва внезапного флейма ...

[vitus_wagner]

Кста, ты видел статью (я нашёл по ссылке с ycombinator) про историю взлёта и упадка Thinking Machines?
Не видел.

[slobin.livejournal.com]

http://www.inc.com/magazine/19950915/2622.html

Такая ностальгия -- на втором курсе мы этими машинами бредили. Кстати, я всерьёз полагаю, что в ближайшие лет пять-десять кому-нибудь обязательно надо будет достать с дальней полки наработанную Thinking Machines алгоритмику и как следует её изучить. Их аппаратные решения безнадёжно устарели, а вот идеи, как распараллеливать задачи -- лучше, насколько я знаю, никто с тех пор не придумал.

... На моей планете голубая осень ...

[relf.livejournal.com]

это SNFS, раскладывали число (2^1039-1)/5080711
до разложения модулей RSA такого размера еще пяток лет понадобится

[coctic]

Ботнет особо не пойдет, там алгоритмы довольно сильно связные.