Взлом 1024-битного ключа RSA близится к завершению

Алгоритм шифрования RSA с 1024-битным ключом может быть взломан менее чем за год, утверждают исследователи из Швейцарии и Японии, ведущие совместный проект по расшифровке. На прошлой неделе они продемонстрировали, как можно разложить на простые множители число Мерсена длиной 307 бит за рекордно короткое время – 11 месяцев.

Процесс был выполнен с использованием специального метода просеивания поля чисел, разработанного профессором криптологии Ариеном Ленстра (Arien Lenstra), его братом Хендриком (Hendrik), впоследствии ставшим профессором Университета Калифорнии в Беркли, английским математиком Джоном Поллардом (John Pollard) и Марком Манасси (Mark Manassee) из DEC в конце 1980-х. Метод позволяет разложить на простые множители число (21039-1) примерно за 100 лет вычислений, сообщил PCPro.co.uk.

Сложность в разложении длинных простых чисел на множители за приемлемое время лежит в основе криптоалгоритма RSA, названного по первым буквам фамилий его разработчиков: Рональда Ривеста (Ronald Rivest), Ади Шамира (Adi Shamir) и Леонарда Эйдлмана (Leonard Adleman).

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

По словам Ленстра, увеличение скорости вычислений позволит взламывать 1024-битные ключи за довольно короткое время. «Последний раз у нас ушло 9 лет на число из 155 цифр. Я не буду делать предсказания, но могу только сказать, что продолжение работы – хорошая идея», - уверен Ариен Ленстра.