05.06 // Крипто // Новый рекорд факторизации и его применение к RSA



Опубликованы подробности работы "A kilobit special number field sieve factorization"[link1] по последнему рекорду факторизации[link2].

K.Aoki, J.Franke, T.Kleinjung, A.K.Lenstra, D.A.Osvik смогли разложить 1039-битное число Мерсенна, используя сеть из 110 компьютеров Pentium D 3.0GHz и 36 компьютеров Dual Core2Duo 2.66GHz, за примерно 59 дней: разные этапы вычислений занимали разное время и не все были распараллелены.

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

RSA-1024 пока ещё можно считать условно безопасным для некритических приложений в течении ближайших нескольких лет, однако исследователи рекомендуют переход к ключам длиной 2048 битов.

Источник: Cryptology ePrint Archive[link1]

Ссылки
[link1] http://eprint.iacr.org/2007/205

[link2] http://crypto-world.com/announcements/m1039.txt