Исследователи взломали RSA-240, крупнейший известный ключ шифрования, за 35 миллионов ядерных часов

Взломан RSA-ключ 795 бит (240 десятичных знаков) за 4000 лет на одном ядре

Всего вычислительное время эквивалентно запуску одного компьютерного ядра на 4000 лет. Вычисления не представляют угрозы для современной компьютерной безопасности.

Шифрование используется для защиты данных, которые вы получаете, храните и отправляете с помощью цифрового устройства. Правительство использует его для защиты классифицированной информации, корпорации — для защиты коммерческих тайн, а частные лица — для защиты личной информации.

Почти все методы шифрования используют длинные строки для защиты онлайн-данных. Одной из самых популярных форм шифрования является криптография RSA. Она основана на факте, что большие целые числа трудно факторизовать.

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

Чтобы показать, насколько безопасно шифрование против современного оборудования, лаборатории RSA опубликовали список полупростых чисел (чисел с только двумя простыми факторами) и бросили вызов найти их исходные простые множители. На данный момент 20 из 54 перечисленных чисел RSA были взломаны.

Недавно исследовательская команда Французского института исследований в информатике и автоматизации (INRIA) факторизовала RSA-240, ключ с 240 десятичными знаками, размером 795 бит. Это самый большой взломанный ключ шифрования на данный момент.

Предыдущий рекорд был установлен в 2009 году с RSA-768, размером 768 бит и 232 десятичными знаками. Хотя RSA-240 больше RSA-768, исследователи смогли получить его простые множители быстрее, чем предыдущий рекорд.

Источник: 795-bit factoring | Wikipedia

Время вычислений

Помимо нахождения простых множителей, исследователи также вычислили дискретный логарифм RSA-240. Это первый случай, когда два рекорда (факторизация целых чисел и дискретный логарифм) побиты вместе с тем же программным и аппаратным обеспечением.

Оба вычисления выполнялись алгоритмом решета числового поля (Number Field Sieve), с использованием открытого программного обеспечения CADO-NFS.

RSA-240 и его простые множители

Факторизация целого числа заняла почти 8 миллионов ядерных часов, в то время как вычисление дискретного логарифма заняло 27 миллионов ядерных часов. Общее вычислительное время эквивалентно запуску одного компьютерного ядра (2,1 ГГц Intel Xeon Gold 6130) на 35 миллионов часов, или 4000 лет.

С точки зрения вычислений, взлом RSA-240 в 2,25 раза сложнее, чем взлом RSA-768. Учитывая тот факт, что исследователи использовали идентичное оборудование и получили результаты в 3 раза быстрее ожидаемого, ускорение можно atribuтировать улучшениям, сделанным в различных алгоритмах за последнее десятилетие. Реализация CADO-NFS, например, была значительно улучшена.

Эти вычисления не несут угрозы для компьютерной безопасности, так как ключи RSA, используемые современными компьютерами, больше по размеру — от 1024 до 4096 бит. Однако появление квантовых компьютеров может кардинально изменить ситуацию.