Об очередном взломе RSA-2048 или причем тут «Шиповник» и «Крыжовник»?

На днях в LinkedIn доктором наук Эдом Герком было опубликовано сообщение о взломе 2048-битного ключа шифрования алгоритма RSA с помощью квантовых вычислений всего за несколько секунд. При этом они осуществлялись с помощью обычного мобильного телефона и настольного компьютера с Linux, без каких-либо криогенных технологий или специальных материалов, что позволяет на порядки сократить стоимость вычислительных устройств для взлома алгоритма, лежащего в основе многих защищенных Интернет-протоколов.

Сейчас исходное сообщение из LinkedIn удалено!

С одной стороны, Эд Герк — не новичок в области квантовых технологий, криптографии и цифрового доверия; у него много различных патентов, исследований, более 220 научных работ в этих сферах. То есть он явно не просто человек со стороны, который что-то ляпнул о взломе стойкой криптографии, как это бывало уже не раз. С другой стороны, пока не было опубликовано никаких доказательств сделанного “открытия”, чтобы специалисты могли проверить ее и убедиться в правоте Герка. Как по мне, так надо было просто опубликовать на arxiv.org или на IACR свои исследования и все. Но нет. Другой вариант — взять число RSA-2048 из Википедии и разложить его на множители, продемонстрировав широкой общественности два числа, перемножение которых и дает RSA-2048. Ни того, ни другого пока так и не было сделано, что, наряду с удалением исходного сообщения, намекает на то, что с «открытием» что-то не так.

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

Еще ранее, в январе этого года, китайские товарищи выложили на arxiv.org исследование, в котором утверждается, что им удалось взломать RSA-2028.

Однако тут стоит вспомнить историю с взломом алгоритма постквантовой криптографии SIKE, который был выбран NIST в качестве одного из четырех дополнительных алгоритмов, которые рассматривались как альтернативы шифрованию в постквантовом мире. Опубликованное исследование показало, что аналог протокола Диффи-Хеллмана на базе суперсингулярной изогении (SIDH) может быть взломан за час на обычном компьютере с помощью достаточно сложной математики, которую никто до этого не принимал в расчет, но которая известна уже не первое десятилетие. Авторы SIKE признали корректность исследования.

В это же время английский центр компьютерной безопасности NCSC опубликовал обновленное руководство по подготовке к пост-квантовой криптографии, которое базируется на их же публикации трехлетней давности на ту же тему. Если кратко, то они рекомендуют использовать стандарт NIST PQC, который базируется на 4 алгоритмах:

• управления ключами — ML-KEM
• цифровой подписи — ML-DSA, SLH-DSA и FALCON.
• два алгоритма хэширования, которые должны применяться только в отдельных сценариях (например, для подписания ПО и обновлений) — LMS и XMSS.

Проекты трех алгоритмов, кроме FALCON, были опубликованы в августе 2023, а их финальные версии должны быть опубликованы в 2024-м году.

В России также ведутся свои работы в области пост-квантовой криптографии, например, алгоритм цифровой подписи «Шиповник» (на основе схемы Фиата-Шамира), «Крыжовник» (на основе решеток), «Гиперикум» (на основе SPHINCS+ и «Стрибог»).

Надо отметить, что 2023-й год оказался очень активным с точки зрения различных новостей по пост-квантовой криптографии и квантовым вычислениям. Чего стоит двухднедельной давности анонс компьютера на 1180 кубитов, созданный американской компанией Atom Computing. Это кажется фантастикой, но именно конец 2023-го года был заявлен IBM в их дорожной карте по созданию квантового компьютера на 1000 кубитов. Правда, с этим анонсом, как и с заявлением Эда Герка, есть нюанс, — не приведено описания одного из ключевых компонентов — двухкубитного шлюза, а точнее его показателей точности. Без этого говорить о практическом применении нового квантового компьютера еще рано.

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

Дополнительная информация

• Устаревшая публикация NIST — «Getting Ready for Post-Quantum Cryptography«
• Публикация NIST (сменила предыдущую) — «Getting Ready for Post-Quantum Cryptography: Exploring Challenges Associated with Adopting and Using Post-Quantum Cryptographic Algorithms«
• Публикация ETSI — «Migration strategies and recommendations to Quantum Safe schemes«
• Материалы симпозиумов «Современные тенденции в криптографии» CTCrypt
• Материалы конференции «Рускрипто«
• Видеозапись эфира «Квантовая и постквантовая криптография«
• Технический комитет 26 «Криптографическая защита информации» и его рабочие группы 2.5 «Постквантовые криптографические механизмы» и 4.5 «Квантовые криптографические системы выработки и распределения ключей».
• Портал по квантовым технологиям информационной безопасности