Постквантовый мир прикладной криптографии

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

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

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

“Квантовый алгоритм” – это какой? Главная особенность квантовых алгоритмов в том, что они, – по крайней мере, в своей квантовой части, – не подразумевают вычислений в привычном по классическим устройствам смысле слова. Классический вариант предполагает пошаговое проведение операций с некоторыми значениями. В квантовом случае всё хитрее: здесь сама схема, реализующая алгоритм, устраивается таким образом, чтобы после измерения она с высокой вероятностью оказалась в состоянии, соответствующем искомому ответу. Максимизация вероятности получения полезного ответа реализуется благодаря интерференции квантовых состояний, в которых вычислитель пребывает одновременно. Поэтому неверно говорить, что “квантовый компьютер параллельно проверяет множество вариантов” – напротив, квантовый компьютер ничего не проверяет, однако само пространство всех возможных его состояний оказывается устроено так, что после измерения оно с высокой вероятностью схлопнется в один из искомых вариантов, который и есть решение. Всякий эффективный квантовый алгоритм подразумевает, что за решаемой задачей стоит некоторая точная математическая структура, которую классический компьютер может найти только перебором вариантов, а квантовый – в результате применения некоторого набора квантовых преобразований сразу ко всему пространству состояний. То есть, необходимых для решения задачи циклов работы квантового компьютера оказывается существенно меньше.

Например, когда говорят о задаче криптографии с открытым ключом, речь идёт об алгоритме Шора. Квантовая часть этого алгоритма позволяет найти значение (период известной функции), знание которого делает возможным быстрое вычисление разложения заданного числа на множители уже на классическом компьютере. Искомый период функции здесь и есть отражение структуры, соответствующей разложению на множители. Собственно, разложение на множители актуально для криптосистемы RSA, однако тот же алгоритм позволяет взломать и криптосистемы, основанные на задаче дискретного логарифмирования, например, подпись ECDSA или распространённые сейчас реализации алгоритма Диффи-Хеллмана.

Итак, алгоритм Шора, в теории, позволяет взять произвольный открытый ключ RSA, за часы или дни найти для него разложение на простые множители, после чего практически мгновенно получить соответствующий секретный ключ. В чуть больших деталях этот процесс мог бы выглядеть так: открытый ключ RSA уже известен, он состоит из модуля M и “шифрующей экспоненты” e – это два целых числа; модуль является произведением двух простых чисел M = p*q; секретный ключ представляет собой “расшифровывающую экспоненту” d (опять целое число), которая соответствует “шифрующей”. Знание p и q позволяет очень быстро вычислить d для заданной экспоненты e на обычном компьютере (собственно, это вычисление проводится всякий раз, когда генерируется пара ключей RSA).

Сколько кубитов потребуется для атаки на практически используемые ключи RSA? Типичная битовая длина RSA-модуля сейчас 2048 бит. А вот оценки для количества кубитов – очень разные. Из свойств алгоритма Шора понятно, что потребуется, как минимум, двойная разрядность, то есть, 4096 кубитов. Однако эта оценка очень оптимистична: предполагается, что в зависимости от физического воплощения квантового компьютера и реализации алгоритма Шора может потребоваться и десятикратное увеличение (то есть, 20480 кубитов), и даже миллионы кубитов. Так или иначе, сейчас, когда говорят об универсальных квантовых компьютерах, имеют в виду единичные устройства с несколькими десятками кубитов (например, 53 кубита у Google и IBM). Поэтому до практических разрядностей ещё далеко. Тут, впрочем, есть два интересных момента: во-первых, вполне вероятно, что получив работающий универсальный квантовый компьютер с сотней кубитов, его смогут быстро масштабировать на тысячи и далее; во-вторых, для атаки на широко применяемые сейчас криптосистемы, использующие арифметику эллиптических кривых (ECDSA), кубитов нужно меньше, чем в случае с RSA, потому что меньше разрядность.

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

Такие криптосистемы разрабатываются давно, некоторые из них были даже предложены задолго до публикации алгоритма Шора (опубликован в 1994). Естественно, совсем старые системы не позиционировались как постквантовые, это свойство возникает у них в качестве дополнительного – просто, для их криптоанализа не подходит метод, основанный на нахождении периода функций. К сожалению, для использования они не годятся по другим причинам: либо оказались уязвимы для классического криптоанализа (стойкость к взлому при помощи квантового алгоритма вовсе не означает, что криптосистема будет стойкой и в классическом случае), либо просто чрезвычайно неудобны на практике.

NIST уже несколько лет выполняет программу по выбору постквантовых криптосистем. Есть надежда, что внезапно возникший квантовый компьютер вряд ли “сломает всю мировую криптографию”, хоть такой вариант и нельзя полностью исключать, прежде всего, по причине его особой литературной ценности. Более вероятно, что к моменту создания этого самого компьютера – постквантовые криптосистемы уже давно войдут в практику. Или даже так: постквантовые криптосистемы уже будут широко использоваться, а подходящий для взлома 1024-битной RSA квантовый компьютер всё ещё будут пытаться построить.

Тем не менее, на данный момент, массово внедрённых постквантовых криптосистем с открытым ключом – нет. Существуют только экспериментальные варианты. Но некоторые из них даже внедрялись в браузере Chrome.

Скорее всего, на практике будет использован тот или иной вариант криптосистемы на эллиптических кривых. Для генерации общего секрета – протокол Диффи-Хеллмана (DH). С этим протоколом связано одно из расхожих заблуждений, что, якобы, он не обладает постквантовой стойкостью. В реальности, уязвимости возникают вовсе не в протоколе Диффи-Хеллмана, а в применении алгоритма Шора к математическими объектами, стоящим за классическими реализациями DH. Криптоанализ на квантовом компьютере позволяет быстро решать задачу дискретного логарифмирования в конкретном математическом окружении, но протокол Диффи-Хеллмана прекрасно обобщается на другие математические конструкции. Поэтому сразу несколько кандидатов в постквантовые криптосистемы используют DH (примеры: SIDH, CSIDH).

Постквантовые криптосистемы необходимы для решения двух высокоуровневых задач: электронная подпись и генерация общего секрета (распределение симметричных ключей). Третья фундаментальная часть практической криптографии – симметричные шифры — не столь подвержена квантовым атакам: несмотря на то, что возможны какие-то квантовые улучшения для атак на конкретные шифры, считается, что в целом использование мощного квантового компьютера позволяет получить лишь квадратичный прирост в скорости перебора. То есть, добротный шифр с 256-битным ключом даёт 128 бит постквантовой стойкости, а этого более чем достаточно. Отсюда выводится весьма консервативная рекомендация: если вы опасаетесь за секретность передаваемых данных в ситуации наступления эры квантовых компьютеров, то проще всего сейчас отказаться от асимметричных криптосистем, перейти исключительно на симметричные шифры. Таким образом, “конец асимметричной криптографии” наступит в отдельно взятом случае ещё раньше, чем появится квантовый компьютер. Конечно, это не очень-то практичное решение. В некоторых особенно “специальных” случаях, действительно, такими решениями пользуются, как применяют и абсолютно стойкий шифр Вернама, но представить, что от асимметричных криптосистем полностью отказались в массовых протоколах вроде TLS – непросто. Причина понятна: большую проблему составляет распределение ключей. (Но в случае небольшого закрытого списка корреспондентов и наличия возможности обмениваться твердотельными носителями информации – задача распределения ключей решаема.)

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

Оставим предложение отказаться от асимметричной криптографии за скобками, как слишком прямолинейное, строгое и непрактичное. Что ещё можно запланировать в качестве мер защиты информации, ожидая появления квантовых компьютеров? Вариант ровно один, и он банален: придётся точно так же ждать, пока появятся и пройдут оценку стойкости постквантовые криптосистемы распределения ключей и электронной подписи, а потом оперативно обновить программное обеспечение, перейдя на новые алгоритмы как можно раньше. Первыми будут вводиться в строй криптосистемы, позволяющие получить общий секрет (распределение ключей). Это как раз связано с риском раскрытия трафика записанных сессий: чем раньше появятся стойкие симметричные сессионные ключи, тем больше устареет информация в записанных сессиях к моменту появления квантовых компьютеров. Не предполагается быстрый переход исключительно на постквантовые системы. Напротив, их будут вводить в качестве дополнительного инструмента, работающего вместе с классическими, хорошо проверенными. То есть, если в том или ином рекомендованном постквантовом алгоритме вдруг позже обнаружится серьёзный дефект, или такой дефект возникнет в какой-то реализации алгоритма (что существенно более вероятно), ситуация, по крайней мере, не станет хуже: классическая криптосистема всё ещё будет обеспечивать защиту данных.

Адрес записки: https://dxdt.ru/2019/12/21/8845/

Похожие записки:



Далее - мнения и дискуссии

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

Написать комментарий

Ваш комментарий:

Введите ключевое слово "7DG5S" латиницей СПРАВА НАЛЕВО (<--) без кавычек: (это необходимо для защиты от спама).

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