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