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

Уже через пять-десять лет 1024-битный RSA-шифр будет взломан. С таким прогнозом выступил Арьен Ленстра (Arjen Lenstra), известный криптолог. Совсем недавно под его руководством был взломан эквивалент 700-битного ключа RSA. Арьен Ленстра считает, что в области распределённых вычислений в ближайшие годы можно ожидать существенного прогресса. Во-первых, процессоры становятся мощнее. Во-вторых, улучшаются математические алгоритмы поиска простых чисел-множителей.

Арьен Ленстра рассказал об успешном эксперименте, в рамках которого было найдено два множителя 307-значного числа. Правда, это конкретное число (2¹⁰³⁹ – 1) специально тщательно подобрали так, чтобы оно легче поддавалось факторизации с помощью изобретённого Ленстрой метода «специального решета числового поля» (special number field sieve). При этом процесс занял 11 месяцев в сети из 300–400 компьютеров. В частности, шесть месяцев ушло на высеивание: общее время высеивания было эквивалентно ста годам работы Athlon64/Opteron [2.2GHz]. Решение полученной матрицы заняло 59 дней на 110 процессорах Pentium D [3.0GHz].

Швейцарский профессор уверен, что методы факторизации будут совершенствоваться и взлом 1024-битного шифра станет возможен через пять-десять лет. Бизнесменам и обычным гражданам уже сейчас стоит задуматься об использовании более стойкой криптографии.

via IDG News, Number Theory List