795 бит — новый рекорд взлома ключей шифрования

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

В 1977 году один из авторов криптографического стандарта RSA, Рон Райвест (Ron Rivest), подсчитал, что для вычисления полупростого числа (натурального произведения двух простых чисел) из 125 цифр потребуется 40 квадриллионов лет, если использовать лучший алгоритм и самые быстрые компьютеры того времени. Уже этот результат делал дебютировавший тогда RSA практически неприступным для взломщиков. Тем не менее, в своей оригинальной статье Райвест с коллегами рекомендовал использовать 200-значные (663-битные) простые числа для обеспечения гарантированного запаса прочности против любых будущих разработок.

Однако совершенствование компьютеров и программных алгоритмов привело к тому, что такое невозможное будущее наступило уже в 2005 году. И этот прогресс продолжается, вынуждая индустрию внедрять всё более длинные ключи шифрования.

В 2010 г. рекорд факторизации составлял 768 бит или 232 десятичных цифры. А недавно международная команда компьютерных инженеров сообщила об очередном рекордном достижении: её участники факторизовали 795-значный ключ и вычислили дискретный логарифм числа такой же длины, израсходовав на всё это «всего» 35 млн часов компьютерного времени.

До сих пор было принято считать, что проблема дискретного логарифма примерно на порядок сложнее разложения на простые множители. Поэтому логарифм для 768-значного числа был вычислен на 6 лет позже факторизации числа такого же размера. Новая работа показала, что в действительности эти две проблемы различаются по вычислительной трудности гораздо меньше — примерно в три раза.

В нынешних коммерческих системах асимметричного шифрования рекомендуемая длина RSA-ключа превышает 1024 бит. Таким образом, прямой угрозы новый рекорд не представляет, но это сигнал, заставляющий отделы безопасности задуматься о ближайших перспективах, ведь текст, зашифрованный с помощью неуязвимого в 1977 году алгоритма RSA-129 сейчас взламывается на публичном облачном сервисе менее, чем за 30 долларов и за одни сутки.

Ready, set, buy! Посібник для початківців - як придбати Copilot для Microsoft 365