2 декабря 2019 года в рассылке по теории чисел nmbrthry@listserv.nodak.edu сообщили о факторизации числа RSA-240 (240 десятичных знаков, 795 бит). Это новое достижение в криптографии и теории чисел и очередное выполненное задание из списка RSA Factoring Challenge.

Вот число и его множители:

RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099
= 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517
* 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447

Исходя из текущего тренда можно примерно представить, когда будут взломаны RSA-1024 (309 десятичных знаков) и RSA-2048 (617 знаков).

Предыдущими достижениями была факторизация 768-битного числа (232 десятичных знака) в 2009 году и дискретное логарифмирование 768-битного числа в 2016 году.



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

Всё более сложные шифры постепенно поддаются взлому по мере роста производительности CPU и благодаря совершенствованию алгоритмов.

После изобретения алгоритма решета числового поля (general number field sieve, GNFS) в начале 90–х в области факторизации целых чисел не появилось ничего революционного, хотя проведены некоторые существенные оптимизации. Например, в последние несколько лет исследователи смогли сильно ускорить фазу нахождения подходящего многочлена.

Факторизация RSA-240 тоже выбивается из общего ряда, потому что была проведена не только за счёт увеличения вычислительной мощности, но и благодаря оптимизации программного обеспечения и алгоритмов. Чтобы доказать эффективность сделанных изменений, исследователи запустили программу на таком же оборудовании, что использовалось для вычисления 768-битного дискретного логарифма в 2016 году. Они обнаружили, что просеивание матрицы 795-битных чисел на нём выполняется на 25% быстрее, чем просеивание матрицы 768-битных чисел без оптимизации.

Та же группа исследователей вычислила и дискретный логарифм того же размера. Впервые в истории рекорды на дискретное логарфмирование и факторизация чисел одинакового размера установлены одновременно, да ещё на одном и том же оборудовании и программном обеспечении.

Благодаря оптимизации алгоритмов и программного обеспечения дискретное логарифмирование 795-битного числа ускорилось на 33% по сравнению с логарифмированием 768-битного числа без оптимизации на том же оборудовании.

Согласно теории, логарифмирование 795-битного числа в 2,25 раза сложнее 768-битного. Это означает, что эффект оптимизаций на самом деле трёхкратный (2,25?1,33=3).

Оба типа вычислений проводились с помощью алгоритма решета числового поля в опенсорсной программе CADO-NFS. Среди оптимизаций — улучшенная параллелизация и использование памяти, а также большая работа по нахождению более оптимальных параметров расчёта (было разработано специальное программное обеспечения для тестирования и ранжирования разных параметров расчёта).

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

Грубая разбивка времени на факторизацию и логарифмирование:

• Просеивание RSA-240: 800 ядро-лет
  
• Матрица RSA-240: 100 ядро-лет
  
• Просеивание DLP-240: 2400 ядро-лет
  
• Матрица DLP-240: 700 ядро-лет

Достижение записала на свой счёт научная группа под руководством Эммануэля Томе (Emmanuel Thome), ведущего исследователя Французского национального института информатики и прикладной математики.

Изобретатели шифра RSA опубликовали числа RSA всех размеров вплоть до RSA-2048. Все желающие могут попробовать их взломать.

Исходя из текущего тренда можно посчитать, когда будут взломаны RSA-1024 (309 знаков) и RSA-2048 (617 знаков). Если экстраполировать график, получаются примерно 2031 год и 2073 год, соответственно. Но мы видим, что оптимизация программного обеспечения и алгоритмов способны существенно приблизить этот срок. Возможно, RSA-2048 взломают ещё при нашей жизни.

На практике подтверждаются рекомендации RSA использовать минимальный размер ключей RSA 2048 иди 4096 бит.

Судя по развитию квантовых компьютеров, они нескоро приблизятся к взлому ключей такого размера, хотя здесь трудно что-то прогнозировать. В 2012 году алгоритм Шора справился с факторизацией числа 21 (3?7), пять бит энтропии. Это число долго оставалось рекордом квантовой факторизации, но в 2018 году на 5- и 16-кубитных процессорах IBM была продемонстрирована факторизация произведения простых чисел 4088459, а это уже 22 бита.