До конца эры традиционного шифрования осталось не больше двух лет
Китайские исследователи продемонстрировали возможность взлома длинных RSA-ключей с помощью квантовых компьютеров. Так, для вскрытия 48-битного RSA оказалось достаточно 10-кьюбитного квантового компьютера, а для 2048-битного - системы из 372 кьюбитов. А мощность IBM Osprey, ввод которого должен состояться уже совсем скоро, составит 433 кьюбита. Раньше считалось, что для взлома RSA понадобится не менее 20 млн кьюбитов, причем даже такой системе, появления которой стоило ожидать не менее 25 лет, будет необходимо восемь часов работы.
Успех китайских исследователей обусловлен тем, что им удалось объединить классические методы факторизации с уменьшением решетки с алгоритмом квантовой приближенной оптимизации. Также применены методики германского исследователя Клауса Петера Шнорра, причем удалось преодолеть их ограничения, за которые разработки Шнорра критиковали.
Авторитетный криптограф и один из разработчиков блочных шифров Twofish и Blowfish Брюс Шнайер предлагает отнестись к данному исследованию со всей серьезностью: "Исследователи объединили классические методы факторинга редукции решетки с алгоритмом квантовой приближенной оптимизации. Это означает, что им нужен только квантовый компьютер с 372 кьюбитами, что вполне возможно сегодня. У китайской группы исследователей не было такого большого квантового компьютера для работы. Они смогли учесть 48-битные числа, используя 10-кьюбитный квантовый компьютер. И хотя всегда есть потенциальные проблемы при масштабировании чего-то подобного в 50 раз, очевидных барьеров нет. Удивительно лишь, что китайское правительство не засекретило эти исследования".
"И хотя про взломы RSA уже не один фейк опубликован, в данном случае стоит прислушаться к Брюсу Шнайеру. И хотя еще предстоит перепроверить результаты исследований китайцев, есть вероятность, что они действительно сделали то, что пишут, а именно - сломали 2048-битный ключ RSA. А значит, 2023 г. поставит перед многими ИБ-специалистами совершенно новые задачи и заставит пересмотреть все свои планы. Менять основы ИБ, лежащие в фундаменте многих систем электронной коммерции, - штука непростая..." - такие далеко идущие выводы делает ведущий блога "Бизнес без опасности" Алексей Лукацкий.
Однако и до опубликования результатов данного исследования участники рынка средств криптозащиты обращали внимание, что появление работающих квантовых вычислителей приведет к полной компрометации традиционного шифрования, вопрос был лишь в том, как скоро это случится. "Сейчас активно развивается квантовая компонентная база, а все текущие методы шифрования являются квантово-неустойчивыми. Для нас разумно ориентироваться на альтернативные архитектуры, для которых не разработано так много средств взлома, как для x86", - предупреждала директор по стратегическому развитию АО "Микрон" Карина Абагян в ходе онлайн-конференции "Аппаратное обеспечение российской ИБ".
"Речь пока идет о возможной компрометации одной конкретной, но весьма распространенной за рубежом асимметричной криптосистемы – RSA. И тут могут быть разные, но преодолимые последствия. Если окажется, что подход китайских исследователей работает, но применим только к задаче разложения целых чисел на множители, то система RSA, очевидно, будет выведена из обращения. Это вызовет определенные организационные затруднения: замена этой системы на альтернативные системы, в частности на основе эллиптических кривых, замена пользовательских и корневых сертификатов открытых ключей системы RSA в компьютерах, серверах и мобильных устройствах по всему миру. Это не быстро, это потребует усилий, но принципиальных затруднений не представляет. Это можно сделать, - считает заместитель генерального директора по науке и инновациям "ИнфоТеКС" Алексей Уривский. - Если же окажется, что подход можно будет обобщить и на решение других трудных задач, в первую очередь на вычисление дискретных алгоритмов, тогда выводить из обращения придется фактически всю используемую сегодня на практике асимметричную криптографию. Впрочем, именно такой сценарий и рассматривается в ожидании создания достаточно мощного квантового компьютера. И человечество постепенно готовится к такому сценарию, развивая так называемые квантовоустойчивые или постквантовые криптографические механизмы. Именно на постквантовые механизмы, по-видимому, случится замена современных асимметричных криптосистем. Усилий и времени потребуется много, но и это реализуемо".
И средства квантового шифрования уже появляются на рынке, в том числе и российском. В ноябре 2022 г. первое устройство ViPNET QSS от "ИнфоТеКС" получило сертификат ФСБ.
Вместе с тем специалист в области теории вычислительных машин и систем, преподаватель факультета компьютерных наук Техасского университета в Остине Скотт Аарансон высказал очень серьезный скептицизм в отношении работы китайских исследователей. Главной причиной является неоднозначная сходимость алгоритмов квантовой приближенной оптимизации, которую Скотт Аарансон назвал пригодной лишь для решения сугубо теоретических задач. Также у эксперта вызвала сомнения работоспособность методик Клауса Шнорра.
Многие российские эксперты также проявляют скептицизм. Так, например, руководитель научной группы "Квантовые информационные технологии" Российского квантового центра Алексей Федоров так прокомментировал результаты китайских исследователей: "Метод Шнорра до сих пор не имеет корректной оценки сложности. Предполагается, что она является экспоненциальной, причем основная трудоемкость сосредоточена не в решении SVP, а в наборе достаточного количества таких задач - как в методе решета числового поля для факторизации требуется набор достаточного количества соотношений. Отсюда следует, что метод, по всей видимости, Шнорра не масштабируется на числа RSA, реально использующиеся в современной криптографии. Метод позволяет получить лишь приближенное решение SVP, которое относительно легко скорректировать для небольших чисел и решеток малой размерности, но практически невозможно для реально используемых параметров криптосистем. Метод Шнорра не переносится на криптосистемы на эллиптических кривых (ГОСТ 34.10-2018)".
В итоге Алексей Федоров делает вывод: "Данный метод, по всей видимости, не ведет к мгновенному взлому существующих криптоалгоритмов, поэтому появление новых классических и квантовых алгоритмов криптоанализа является важным аргументом на пути к внедрению постквантовой криптографии".
Исполнительный директор QApp Антон Гугля также считает, что заявления китайских исследователей далеки от действительности: "Алгоритм Шнорра хорошо работает для небольших чисел, но не может быть применен на практике для атаки на реально используемые криптографические механизмы. Оценка параметров необходимого для реализации этой атаки квантового компьютера в 372 кьюбита является, по всей видимости, значительно заниженной. Более реалистичной представляется корректно обоснованная оценка, полученная в 2021 г., которая составляет 20 млн кьюбитов".
Алексей Уривский считает результаты китайских исследователей лишь гипотезой, которые появляются регулярно: "Во-первых, ни у кого на данный момент нет в доступе квантового вычислителя с нужным числом и – это важно! – качеством кубит, чтобы проверить вычислимость. Сейчас исследователи провели эксперимент только на "игрушечном" по размеру модуле. Во-вторых, при формулировании гипотезы использованы эмпирические оценки сложности алгоритма Шнорра, предложенного в 2021 году, который исследователи ускорили квантовыми вычислениями. Однако эти эмпирические оценки не были ни подтверждены, ни тем более доказаны. Поэтому гипотеза китайских исследователей пока остается лишь гипотезой. А гипотезы, выдаваемые за результат, о взломе какого-нибудь известного криптографического механизма появляются достаточно регулярно".
Тем не менее Антон Гугля считает, что если не предпринимать меры уже сейчас, то последствия компрометации традиционного шифрования могут стать поистине катастрофическими - почти все данные, когда-либо переданные по Сети, в том числе персональные, финансовые, медицинские, будут доступны злоумышленнику, сохраняющему сегодня сетевой трафик для его дешифрования в будущем: разрушатся системы электронного банкинга и электронного документооборота, цифровые активы потеряют ценность. Однако, по его мнению, международное научно-технологическое сообщество активно готовится к такому сценарию, развивая программные решения информационной безопасности, построенные на основе постквантовой криптографии - новых методах шифрования, защищающих данные от атак с использованием как классических, так и квантовых компьютеров.
