Приветствую, Хабр! Долгое время я принадлежал к числу тех, кто скептически относится к возможностям квантового криптоанализа в частности и квантовых вычислений вообще. Мое отношение к этому вопросу кардинально изменилось после того, как я услышал один из докладов на прошедшей конференции «РусКрипто» [1] (перечень источников приведен в конце статьи), авторы которого очень четко показали преимущества криптоанализа на основе гибридных вычислений, совместно использующих традиционные и квантовые компьютеры, по сравнению с классическим криптоанализом.

Дальнейшие события прошедшего года, включающие в себя как усиление возможностей квантовых вычислений «в железе», а не только на бумаге, так и активные действия по разработке и стандартизации постквантовых криптоалгоритмов, показали, что далее игнорировать или относиться скептически к квантовым вычислениям/криптоанализу губительно.

Предлагаю вашему вниманию статью с анализом степени срочности перехода на постквантовые алгоритмы. Справедливости ради, я приведу и недавние высказывания известных экспертов-скептиков, но основная мысль статьи состоит в том, что откладывать далее переход на постквантовые криптоалгоритмы невозможно – начинать их реализацию и думать об их внедрении необходимо прямо сейчас, чтобы, скажем, через 5 лет такой переход был уже осуществлен. Иначе можем опоздать (прежде всего, из-за усиливающихся с каждым годом возможностей гибридных вычислений). Подробности – далее.

Предварительные сведения

Не буду останавливаться на деталях, касающихся квантовых компьютеров и квантовых вычислений. Об этом было написано достаточно много статей, в том числе, на Хабре. Уточню только некоторые из терминов, активно используемых в этой статье:

Для тех читателей, кто недостаточно полно ориентируется в вопросах стойкости современных криптоалгоритмов к квантовому криптоанализу, а также в основных направлениях создания постквантовых криптоалгоритмов приведу здесь некоторые предварительные сведения, которые необходимы для понимания основной темы статьи.

Начнем с обсуждения степени стойкости к квантовому криптоанализу традиционных (т. е. не являющихся постквантовыми) криптоалгоритмов различных категорий, что подробно описано в двух последующих подразделах под катом, а кратко приведено на рисунке:

Таким образом, в отношении симметричных криптоалгоритмов (криптографически стойких) ситуация выглядит следующим образом:

• в случае применения алгоритмов с достаточной размерностью основных параметров (например, использующих 256-битные ключи шифрования или вычисляющих 512-битные хеш-коды) каких-либо срочных действий в связи с угрозой появления квантовых компьютеров предпринимать не требуется;

• при применении алгоритмов с параметрами недостаточного размера было бы неплохо увеличить размеры параметров (если позволяют используемые алгоритмы) или перейти на использование алгоритмов с параметрами большего размера.

С традиционными асимметричными криптоалгоритмами всё более однозначно: для предотвращения атак на использующие их системы с помощью квантового криптоанализа необходимо перейти на применение постквантовых криптоалгоритмов (здесь и далее под постквантовыми будем подразумевать именно асимметричные постквантовые криптоалгоритмы), которые теоретически будут обладать достаточной криптостойкостью при появлении квантовых компьютеров. Под катом – кратко про основные направления разработки постквантовых криптоалгоритмов.

Наконец, необходимо отметить, что подавляющее большинство постквантовых криптоалгоритмов можно разделить на следующие две категории:

• алгоритмы инкапсуляции ключей KEM (Key Encapsulation Mechanism), которые приходят на замену традиционным алгоритмам обмена ключами и существенно отличаются от них по порядку применения (который описан под катом далее);

• алгоритмы электронной подписи, принципы применения которых не отличаются от традиционных.

Процедуры алгоритмов KEM и электронной подписи

Алгоритмы KEM функционально близки к алгоритмам вычисления общего ключа, но, в отличие от них, KEM не предусматривают создание общего ключа участниками протокола. Вместо этого при использовании KEM общий секретный симметричный ключ генерируется одной стороной протокола и с помощью KEM безопасно передается другой стороне. Для обеспечения генерации ключа и его безопасной передачи KEM включает в себя следующие процедуры [9]:

• KeyGen – генерация долговременной асимметричной ключевой пары для последующей инкапсуляции/декапсуляции ключей;

• Encaps – генерация и инкапсуляция симметричного ключа;

• Decaps – декапсуляция (извлечение) симметричного ключа.

Основные действия, выполняемые этими процедурами, состоят в следующем (см. рисунок далее):

1. Сторона A выполняет процедуру KeyGen, в результате которой создается пара ключей:

• ключ декапсуляции DK, который сторона A оставляет у себя и хранит в секрете (данный ключ является аналогом секретного ключа асимметричного шифрования, но в KEM для определенности применяется другая терминология);

• ключ инкапсуляции EK, который сторона A отправляет стороне B или публикует в открытом виде (данный ключ является аналогом открытого ключа асимметричного шифрования).

2. Сторона B по мере необходимости выполняет процедуру Encaps, в процессе которой генерируется секретный ключ симметричного шифрования K; сгенерированный ключ зашифровывается с получением шифртекста C, который сторона B отправляет стороне A.

3. Сторона A расшифровывает шифртекст C, в результате чего получает ключ K, идентичный ключу, сгенерированному стороной B; стороны могут использовать имеющиеся копии ключа K напрямую или в диверсифицированном виде для защиты дальнейшего обмена данными между ними.

В отличие от KEM, постквантовые алгоритмы электронной подписи имеют тот же набор процедур, что и классические; они традиционно обозначаются следующим образом:

• KeyGen – генерация долговременной асимметричной ключевой пары для последующей генерации и проверки подписи;

• Sign – генерация подписи;

• Verify – проверка подписи.

Перед тем, как перейти к основной теме статьи, изложу обещанное во введении мнение экспертов, скептически относящихся к возможностям квантовых вычислений и квантового криптоанализа.

Альтернативное (скептическое) мнение о возможностях квантового криптоанализа

Квантовые вычисления (включая лежащие в основе квантового криптоанализа) и выполняющие их квантовые компьютеры в текущий момент обладают рядом ограничений, наиболее значительными из которых можно считать следующие:

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

• инициализировать систему кубитов;

• выполнить квантовые вычисления;

• считать результат.

2. Зашумление квантовых вычислений – наличие определенного процента ошибок в вычислениях (на всех стадиях работы квантовой системы) из-за, в частности, следующих факторов:

• вероятностной природы квантовых вычислений;

• внешних воздействий на квантовую систему.

Необходимо отметить, что существуют методы коррекции квантовых вычислений, позволяющие добиться точности вычислений, близкой к 100 %, но такие методы являются крайне ресурсоемкими.

3. Необходимость максимальной защиты квантовых компьютеров от внешних воздействий (которые увеличивают квантовую декогеренцию и зашумление квантовых вычислений).

Достаточно часто приходится слышать мнение, что квантовый криптоанализ основан на алгоритмах, которые не учитывают сложности физической реализации квантовых вычислений, включая эффекты декогеренции и зашумления. На этой «оторванности» алгоритмов квантового криптоанализа от физической природы квантовых компьютеров и базируется скептическое мнение о возможностях квантового криптоанализа.

В качестве примеров такого мнения можно привести следующие высказывания известных и авторитетных отечественных экспертов в области криптологии (пример 1) и квантовой физики (пример 2):

1. Вместо реальных криптозадач происходит отвлечение на «негодный» объект (квантовый компьютер) и построение фантастически умозрительных конструкций; исходя из текущей траектории развития, готовность квантового компьютера для взлома текущих отечественных стандартов ЭП (т. е. описанных в ГОСТ 34.10-2018 [4]) будет не ранее, чем через 600-1200 лет [10]. В докладе [11] этим же экспертом постквантовая криптография была названа «фантазийной» с аналогичным обоснованием.

2. «Практическое осуществление квантового компьютера основано на манипулировании на микроскопическом уровне и с грандиозной точностью многоэлементной физической системой с непрерывными степенями свободы. Очевидно, что для достаточно большой системы, квантовой или классической, эта задача становится невыполнимой, именно поэтому такие системы переходят из ведения микроскопической физики в область статистической физики. Представляется ли система из N = 10³ ÷ 10⁵ квантовых спинов, необходимая, чтобы превзойти классический компьютер в решении ограниченного числа специальных задач, достаточно большой в этом смысле? Сможем ли мы когда-либо научиться контролировать 10³⁰⁰ (по меньшей мере) амплитуд, определяющих квантовое состояние такой системы? Мой ответ – “нет, никогда”» [12].

Общим в высказываниях экспертов, скептически относящихся к идее квантовых вычислений, является констатация того факта, что на текущий момент и в обозримом будущем квантовые вычисления остаются реализуемыми только теоретически, на практике квантовые вычисления встречают массу проблем, препятствующих их полноценной реализации. «По контрасту с экспериментом, теория квантовых вычислений, резко доминирующая в КК литературе, не встречает, похоже, никаких трудностей, оперируя миллионами кубитов… Перспективы квантовых вычислений представляются крайне сомнительными» [12].

Несмотря на то, что скептическое мнение выглядит логичным и обоснованным, преобладающим мнением по возможности реализации квантовых компьютеров, способных к реальному взлому современных криптографических алгоритмов, является мнение об их реализуемости и потенциальной (уже сейчас или в перспективе ближайших лет) опасности для современной (в первую очередь, асимметричной) криптографии, о чем и поговорим далее.

Гибридные квантово-классические системы

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

Возьмем для примера алгоритм Шора (упрощенная схема алгоритма приведена на рисунке далее), благодаря которому возникла масштабная угроза использованию традиционной асимметричной криптографии.

Видно, что та часть вычислений, где достижимо квантовое превосходство, выполняется на квантовом компьютере, после чего результаты измерений квантового регистра обрабатываются уже с помощью классического компьютера (с перезапуском квантовой части алгоритма при необходимости).
Создание гибридных квантово-классических вычислительных систем, объединяющих квантовые и традиционные компьютеры в едином вычислительном кластере, является одной из тенденций развития квантовых вычислений. Речь идет уже о создании квантово-классических суперкомпьютеров; в качестве примера можно привести недавнюю новость о таком суперкомпьютере – совместной разработке японского Института физических и химических исследований Riken и компании IBM [13]. Разработки гибридных квантово-классических систем ведутся и в России [14].
Экспертами неоднократно (в частности, на недавно прошедшей конференции «Микроэлектроника» [14, 15]) произносился следующий тезис (который выделю ввиду его важности):

«Именно гибридные квантово-классические вычислительные системы в течение ближайшего десятилетия будут представлять основную угрозу для асимметричных криптоалгоритмов.»

На основании всего вышесказанного рискну также сформулировать предположение, что настоящий прорыв в квантовых вычислениях наступит с разработкой новых квантово-классических алгоритмов, создаваемых специально для таких гибридных вычислительных систем, что позволило бы достигать квантового превосходства/преимущества за счет точечных квантовых вычислений (например, в упоминавшейся мной в начале статьи работе [1] описана атака, для реализации которой требуется осуществление всего одного запроса к квантовому оракулу) с переносом основной вычислительной нагрузки на традиционные компьютеры, не подверженные явлениям декогеренции и зашумления вычислений.
Порассуждаем далее на тему, является ли неотвратимым процесс создания квантовых и гибридных компьютеров и насколько срочно требуется осуществлять переход на постквантовые асимметричные криптоалгоритмы.

 Так пора ли переходить на постквантовые криптоалгоритмы уже сейчас?

Существует распространенное мнение, что появления первых атак на реальные криптосистемы с помощью квантовых компьютеров можно ожидать уже до 2030 года. В частности, в посвященном данной теме отчете [16] эксперты международной консалтинговой компании McKinsey предполагают, что к 2030 г. появятся квантовые компьютеры с практически полной коррекцией ошибок квантовых вычислений и достаточной мощности для успешного криптоанализа реально применяемых классических асимметричных криптоалгоритмов.
Очень важным фактором для принятия решения о переходе на постквантовую криптографию также является тот факт, что уже сейчас распространен метод HNDL (Harvest Now, Decrypt Later – «Собери сейчас, расшифруй позже»), состоящий в сборе и хранении злоумышленниками зашифрованных современными криптоалгоритмами данных (предположительно, имеющих ценность) в надежде на относительно скорое появление квантовых компьютеров и возможность легкого расшифрования собранных данных в относительно ближайшем будущем (см., например, [17]).
Следовательно, данные, имеющие ценность и передаваемые с помощью открытых каналов связи в зашифрованном виде, могут быть в настоящий момент накоплены злоумышленниками и расшифрованы ими уже в предположительно обозримом будущем (поскольку современные протоколы обмена ключами, в основном, не являются стойкими к квантовому криптоанализу), что может привести к значительным потерям. В отчете [16] сказано, что основной целью такой тактики является сбор информации, сочетающей в себе следующие свойства:

• необходимость обеспечения конфиденциальности;

• ценность;

• длительный жизненный цикл.

Там же приводятся примеры подобной информации:

• секретные правительственные данные;

• персональная информация (как минимум, информация о состоянии здоровья);

• технологические, производственные ноу-хау, торговые секреты и т. п.

Отдельно в отчете [16] упомянуто программное обеспечение различных систем, имеющих отношение к безопасности (в качестве примера приведено автомобильное ПО), с длительным циклом использования (до нескольких десятков лет), для обновления которого используются защитные механизмы типа электронной подписи. Подобные механизмы обновления ПО также будут находиться под прямой угрозой несанкционированных обновлений после появления полноценных квантовых или гибридных компьютеров.

Эксперты McKinsey выделили три возможных пути реагирования на угрозу появления квантовых компьютеров (см. рисунок далее – перевод рисунка из отчета [16]):

1. Начинать внедрение постквантовых криптографических механизмов уже сейчас (возможно, с последующим переключением на реализации постквантовых криптографических стандартов, отсутствующих в текущий момент; отметим, что отчет McKinsey вышел в 2022 г., т. е. до принятия в 2024 г. стандартов США на постквантовые криптоалгоритмы; сейчас уже можно сразу инициировать переход на стандартные постквантовые криптоалгоритмы – по крайней мере, для организаций в США).

2. Внедрять постквантовую криптографию позже, когда уже будет понимание относительно будущих постквантовых криптографических стандартов (опять же, в США такие стандарты уже появились).

3. Сфокусироваться на усилении традиционных криптографических протоколов.

При этом те же эксперты однозначно не рекомендуют третий путь, поскольку он оставляет данные уязвимыми к квантовому криптоанализу (напомню, что подавляющее большинство современных криптографических протоколов согласования ключей / вычисления общего ключа, основанных на асимметричных схемах, являются уязвимыми перед квантовым криптоанализом, поскольку при применении квантовых вычислений в отношении них пропадает экспоненциальный разрыв в трудоемкости между легальным пользователем (обладающим секретным ключом) и злоумышленником (скажем, подбирающим секретный ключ); усиление путем экстенсивного увеличения размерностей параметров создать такой разрыв не поможет).
Второй из перечисленных путей рекомендуется использовать только в комбинации с тщательным планированием и предварительной подготовкой последующего перехода к реализации постквантовых криптоалгоритмов, чтобы впоследствии, при принятии решения о переходе, он был выполнен максимально быстро, по разработанным заранее планам. Для тех же организаций, которые работают с данными, имеющими перечисленные выше свойства, первый путь обозначен как единственно возможный.
Важным для принятия решения о возможном переходе на постквантовую криптографию выглядит еще и факт отношения пользователей к квантовым вычислениям и их возможностям. Несмотря на то, что скептическое отношение к возможностям квантовых вычислений в теории может быть верным, распространенное мнение о квантовом криптоанализе как «убийце» традиционной криптографии может привести к опасениям потребителей криптосредств (т. е. средств криптографической защиты информации – СКЗИ) лишиться свойств защищенности (целостности и конфиденциальности) важной для них информации в ближайшем (или, как минимум, обозримом) будущем.
В результате потребители могут начать требовать наличия возможностей противостояния квантовому криптоанализу (т. е. наличия механизмов постквантовой криптографии) в используемых ими СКЗИ. Наиболее актуальным это выглядит для потребителей, обрабатывающих конфиденциальные данные с длительным жизненным циклом (примеры таких данных были приведены ранее).
Стоит отметить также, что экспертами прогнозируется значительный (близкий к среднегодовому удвоению) рост рынка решений, включающих в себя постквантовую криптографию; в мире в абсолютных числах прогнозируется рост со 158 миллионов долларов США в 2024 г. до 8 миллиардов долларов США в 2030 году [18]. Это косвенно, но определенно говорит нам о том, что многие организации уже приняли решение пойти по первому из описанных выше путей, т. е. инициировать переход на постквантовые криптоалгоритмы (и соответствующим образом инвестировать в новые системы с поддержкой PQC) уже сейчас.
Упомянутые ранее постквантовые стандарты США на алгоритмы KEM и электронной подписи были разработаны Институтом стандартов и технологий США NIST (National Institute of Standards and Technology) и утверждены в августе прошлого года. Описание данных стандартов находится за рамками настоящей статьи (но я обязательно вернусь к этому вопросу в будущих публикациях на Хабре). Однако здесь необходимо упомянуть тот факт, что в сопровождавшем публикацию стандартов официальном документе [19] NIST подчеркивает их готовность «к немедленному применению»; реализацию новых постквантовых стандартов эксперты NIST также призывают «начать немедленно, поскольку полная интеграция [новых стандартов с существующими системами] займет много времени».
С учетом необходимости в значительном времени на разработку постквантовых решений можно согласиться с утверждением о том, что актуальность реализации постквантовых алгоритмов уже существует и, следовательно, уже сейчас для производителей СКЗИ выглядит целесообразной постановка задач на разработку СКЗИ, содержащих в своем составе реализации постквантовых криптографических алгоритмов.
Таким образом, на мой взгляд, ответ на поставленный выше вопрос, пора ли переходить на постквантовые криптоалгоритмы уже сейчас, выглядит так: «однозначно пора, запланируйте переход на постквантовые алгоритмы прямо сейчас и незамедлительно начинайте выполнять план перехода».

Обсудим теперь возможные подходы к осуществлению перехода на постквантовые криптоалгоритмы. 

Как же перейти на постквантовую криптографию?

К сожалению, при осуществлении перехода на постквантовую криптографию проблемы, которые потребуется решить при таком переходе, не ограничиваются техническими – к ним обязательно прибавятся законодательные и организационные. На прошлогодней конференции «РусКрипто» одним известным и авторитетным отечественным экспертом были озвучены два следующих возможных подхода к реализации постквантовой криптографии [20]:

1. Замена текущих криптографических стандартов (и прочих используемых криптоалгоритмов, не обладающих стойкостью к квантовому криптоанализу) на постквантовые криптоалгоритмы (желательно, стандартизованные), стойкие к атакам как на основе традиционных, так и квантовых вычислений.

2. Одновременное последовательное использование стандартных алгоритмов, не стойких к квантовому криптоанализу, и постквантовых криптоалгоритмов.

Оба данных подхода, теоретически, позволяют достичь криптостойкости как к классическим, так и к квантовым атакам. Первый из них требует масштабной подготовки с целью, в числе прочего, обеспечения доказательства надлежащего уровня защиты от обоих классов атак, достигаемого с использованием новых постквантовых стандартов (поскольку текущие алгоритмы, тщательно проанализированные ранее, в этом подходе выводятся из применения). Это предполагает выполнение следующих этапов (опуская некоторые приведенные в первоисточнике этапы, в основном являющиеся опциональными) [20]:

• синтез и анализ постквантового криптографического алгоритма;

• стандартизация данного алгоритма;

• синтез и анализ сопутствующих алгоритмов;

• стандартизация сопутствующих алгоритмов;

• разработка и исследования порядка применения в протоколах;

• стандартизация порядка применения в протоколах;

• разработка или модернизация плюс сертификация СКЗИ с реализацией постквантовых криптоалгоритмов;

• встраивание в информационные системы;

• внедрение новых СКЗИ.

Видно, что задачи из данного списка являются сложными и трудоемкими, что усугубляется значительной спецификой постквантовых криптоалгоритмов. В докладе [20] перечислены некоторые дополнительные сложности, возникающие при разработке и реализации постквантовых криптоалгоритмов и протоколов на их основе, включая следующие:

• другие (увеличенные, часто значительно) размеры сертификатов, открытых ключей и значений подписи;

• вместо схем выработки общего ключа – KEM (что, в частности, концептуально меняет подход к работе с ключами во многих сетевых протоколах);

• более сложный в реализации математический аппарат, который влечет за собой увеличение сложности разработки и сертификации СКЗИ.

Второй из рассмотренных экспертом в том же докладе подходов (гибридное использование криптоалгоритмов) предложен как более соответствующий текущим реалиям, поскольку он, прежде всего, сохраняет соответствие текущим криптографическим стандартам (так как они продолжают использоваться в СКЗИ). Несмотря на это, гибридное использование классических и квантовых алгоритмов позволяет [20]:

• защититься от классических и квантовых атак;

• защититься от дешифрования защищаемых данных в будущем (т. е. обеспечивается защита от метода HNDL);

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

Автор доклада [20] призывает начинать прорабатывать (и разрабатывать) СКЗИ на основе данной гибридной схемы уже сейчас, не дожидаясь стандартизации постквантовых криптоалгоритмов в России, что позволит в дальнейшем (после принятия соответствующих стандартов) значительно сэкономить время на разработку и сертификацию гибридных СКЗИ. Гибридный подход активно обсуждается и другими экспертами в данной области – см., например, [17] и [21].

Основным недостатком данного подхода можно считать более значительное (по сравнению с первым подходом) увеличение размеров ключей, поскольку ключи становятся «композитными», т. е. гибридными, когда каждый ключ состоит из двух ключей: для текущего криптостандарта и постквантового криптоалгоритма. Это может потребовать (и во многих случаях – наверняка потребует) модификации вышележащих криптографических протоколов.

Интересен также взгляд на эту проблему «из-за океана»: в ноябре прошлого года был опубликован драфт рекомендаций NIST по переходу с классических стандартных криптографических алгоритмов электронной подписи и вычисления общего ключа, потенциально атакуемых с помощью квантовых компьютеров с достаточными ресурсами, на постквантовые алгоритмы электронной подписи и KEM, описанные в уже принятых и ожидающихся к принятию стандартах на постквантовые криптоалгоритмы [22]. Предлагаемый NIST порядок также основан на постепенном переходе на постквантовые криптоалгоритмы с совместным применением на первой стадии такого перехода классических и постквантовых криптоалгоритмов; думаю, что в этой части финальный вариант рекомендаций NIST не претерпит кардинальных изменений по сравнению с вышедшим драфтом. 

Заключение

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

А вы как думаете?