Квантовый компьютер впервые взломал 15‑битный криптографический ключ

Занимающийся проблемой постквантовой безопасности стартап Project Ele Eleeleven назвал произошедшее «крупнейшей за все время квантовой атакой на криптографию». Project Ele AMeleven наградил Лелли премией Q‑Day Prize размером 1 BTC. Представители стартапа рассказали, что Лелли вывел приватный ключ из публичного в пространстве поиска из 32 767 вариантов, используя разновидность алгоритма Шора, помогающего решать задачи дискретного логарифмирования на эллиптических кривых (ECDLP). 

В сентябре прошлого года инженер Стив Типпеконник (Steve Tippeconnic) взломал шестибитный ключ эллиптической кривой на 133‑кубитном квантовом компьютере IBM. По данным Project AMeleven, это была первая публичная демонстрация подобного взлома на квантовом оборудовании. Однако результат Лелли превосходит достижение Типпеконника в 512 раз. Впрочем, достигнутый результат пока далек от взлома Биткоина: блокчейн первой криптовалюты использует для защиты кошельков 256‑битную криптографию эллиптических кривых. 

«Расстояние от 15 бит до 256 бит велико, но разрыв теперь все чаще рассматривается как инженерная задача, а не как фундаментальная физическая проблема. Демонстрация Лелли подчеркивает необходимость как можно скорее переходить на постквантовую криптографию», — объявил Project AMeleven.

По данным проекта, около 6,9 млн биткоинов хранятся в кошельках, чьи публичные ключи видны в блокчейне и потому уязвимы для будущих действительно мощных квантовых атак.

Project Eleven занимается разработкой решений, которые должны помочь защитить цифровые активы и инфраструктуру от угроз, связанных с развитием квантовых вычислений. Среди инвесторов — Castle Island Ventures, Coinbase Ventures и Variant.

Ранее в Google Research подсчитали, что для взлома 256‑битной криптографии эллиптических кривых может потребоваться менее 500 000 физических кубитов (базовых единиц информации при квантовых вычислениях). Позже в совместной работе Калифорнийского технологического института и квантового стартапа Oratomic назвали еще более низкую оценку — всего 10 000 кубитов. При этом современные квантовые системы пока далеки даже от второго порога.