Российские ученые о возможности взлома квантовых алгоритмов

По сообщению НИТУ МИСИС, коллектив ученых из МИСИС, Российского квантового центра (РКЦ) и Сбера опубликовал данные анализа вычислений, использованных исследователями из Китая при имитации взлома криптосистемы с помощью 400+ кубитного квантового компьютера. Российские ученые поставили под сомнение сенсационный вывод о революции в криптографии – они считают, что алгоритм коллег нерабочий из-за «подводных камней» в классической части и сложности реализации квантовой. Подробности исследования опубликованы в журнале IEEE Access.

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

В декабре 2022 г. ученые из Китая опубликовали статью, в которой рассказали, что им удалось разложить на множители 48-битовое число, смоделировав взлом RSA-алгоритма, с помощью 10-кубитного квантового компьютера. Основываясь на классическом методе факторизации Шнорра, авторы используют квантовое ускорение для решения задачи поиска короткого вектора в решетке (SVP, shortest vector problem) небольшой размерности – что позволило им сделать сенсационное заявление о том, что для факторизации, т.е. разложения большого числа на множители, требуется меньше кубитов, чем его длина, а также квантовые схемы меньшей глубины, чем считалось ранее. Исследователи пришли к выводу, что можно взломать 2048-битовое число с помощью компьютера с 372 физическими кубитами, хотя ранее считалось, что для этих целей необходимо 20 млн.  После того как IBM продемонстрировала готовность 433-кубитового квантового процессора Osprey, многие усомнились в надежности современной асимметричной криптографии и постквантовых криптосистем, основанных на SVP-вычислениях.

Исследователи НИТУ МИСИС, РКЦ и Сбера считают вывод о возможности взлома 2048-битового RSA-алгоритма поспешным. Как поясняет Алексей Федоров, директор Института физики и квантовой инженерии НИТУ МИСИС, руководитель научной группы «Квантовые информационные технологии» РКЦ, метод Шнорра не имеет точной оценки сложности. Основная трудность заключается не в решении одной кратчайшей векторной задачи, а в правильном подборе и решении множества таких задач. Из этого следует, что этот способ, вероятно, не подходит для чисел RSA таких размеров, которые используются в современной криптографии.

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