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

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

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

Исследователи НИТУ МИСИС, РКЦ и Сбер считают вывод о возможности взлома 2048-битового RSA-алгоритма поспешным.

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

Ученые подчеркивают, что метод, используемый исследователями из Китая, дает только приближенное решение задачи, которое можно легко получить для небольших чисел и маленьких решеток, но практически невозможно для реальных параметров криптосистем. Подробности исследования опубликованы в одном из ведущих научных журналов IEEE Access (Q1).

«Наука двигается вперед не только за счет получения собственных позитивных результатов, но и за счет скрупулезного, критического анализа результатов других исследовательских команд. Мы показали подводные камни, которые возникают в предложенном китайскими коллегами алгоритме для взлома современных алгоритмов шифрования. Однако, несмотря на то, что конкретная реализация может быть неэффективной, квантовый компьютер все же может стать серьезным риском информационной безопасности в будущем. Поэтому уже сейчас имеет смысл рассматривать способы минимизации этих рисков», — отметил Альберт Ефимов, к.ф.н., заведующий кафедрой инженерной кибернетики НИТУ МИСИС, вице-президент-директор Управления исследований и инноваций ПАО «Сбербанк».

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