RSA again

[vitus_wagner]

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

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

Comments

[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. Там использовался именно он, судя по всему. Да и он все равно остается сверхполиномиальным.