Коллектив ученых Университета МИСИС, РКЦ и Сбер провел глубокий анализ вычислений, которые исследователи из Китая использовали при имитации взлома криптосистемы с помощью 400+ кубитного квантового компьютера. Они поставили под сомнение сенсационный вывод о революции в криптографии. Российские ученые считают, что алгоритм коллег нерабочий из-за «подводных камней» в классической части и сложности реализации квантовой.
RSA — одна из первых криптосистем с открытым ключом. Она широко используется для безопасной передачи данных. Считается, что большинство используемых в настоящее время криптосистем с открытым ключом защищены от атак через обычные мощные компьютеры, но не через квантовые.
О чем речь
В декабре 2022 года ученые из Китая опубликовали статью, в которой рассказали, что им удалось разложить на множители 48-битовое число, смоделировав взлом RSA-алгоритма, с помощью 10-кубитного квантового компьютера. Основываясь на классическом методе факторизации Шнорра, авторы используют квантовое ускорение для решения задачи поиска короткого вектора в решетке (SVP, shortest vector problem) небольшой размерности. Это позволило им сделать сенсационное заявление о том, что для факторизации, т.е. разложения большого числа на множители, требуется меньше кубитов, чем его длина, а также квантовые схемы меньшей глубины, чем считалось ранее.
Исследователи пришли к выводу, что можно взломать 2048-битовое число с помощью компьютера с 372 физическими кубитами. Ранее считалось, что для этих целей необходимо 20 миллионов. После того как IBM продемонстрировала готовность 433-кубитового квантового процессора Osprey, многие усомнились в надежности современной асимметричной криптографии и постквантовых криптосистем, основанных на SVP-вычислениях.
Что говорят российские ученые
Исследователи НИТУ МИСИС, РКЦ и Сбер считают вывод о возможности взлома 2048-битового RSA-алгоритма поспешным.
«Метод Шнорра не имеет точной оценки сложности. Основная трудность заключается не в решении одной кратчайшей векторной задачи, а в правильном подборе и решении множества таких задач. Из этого следует, что этот способ, вероятно, не подходит для чисел RSA таких размеров, которые используются в современной криптографии», — говорит Алексей Федоров, директор Института физики и квантовой инженерии НИТУ МИСИС, руководитель научной группы «Квантовые информационные технологии» РКЦ.
Ученые подчеркивают, что метод, используемый исследователями из Китая, дает только приближенное решение задачи, которое можно легко получить для небольших чисел и маленьких решеток, но практически невозможно для реальных параметров криптосистем. Подробности исследования опубликованы в одном из ведущих научных журналов IEEE Access (Q1).
«Наука двигается вперед не только за счет получения собственных позитивных результатов, но и за счет скрупулезного, критического анализа результатов других исследовательских команд. Мы показали подводные камни, которые возникают в предложенном китайскими коллегами алгоритме для взлома современных алгоритмов шифрования», — говорит Альберт Ефимов, к. ф. н., заведующий кафедрой инженерной кибернетики НИТУ МИСИС, вице-президент-директор Управления исследований и инноваций ПАО «Сбербанк».
Эксперт дополняет: «Конкретная реализация может быть неэффективной, но квантовый компьютер все же может стать серьезным риском информационной безопасности в будущем. Поэтому уже сейчас имеет смысл рассматривать способы минимизации этих рисков».
Вывод
Метод ученых из Китая не ведет к мгновенному взлому существующих криптоалгоритмов, однако появление новых классических и квантовых алгоритмов криптоанализа — это неизбежный шаг к внедрению постквантовой криптографии.