Каждый день мы пользуемся криптографическими схемами, не особо задумываясь об этом. Именно криптография обеспечивает защиту наших коммуникаций через интернет, включая все B2B, B2C и G2C взаимодействия. Без неё не было бы безналичных платежей и онлайн-торговли, электронных госуслуг и других современных технологий, способствующих развитию рынка и общества.

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

Под угрозой окажутся банки, телеком, ритейл, коммерческая и государственная тайна. Удалённая работа, дистанционное обслуживание и многие бизнес-процессы станут попросту невозможны. Поэтому важно разрабатывать альтернативные криптографические схемы, которые базируются на принципиально других математических задачах. Это одно из направлений работы лаборатории криптографии компании «Криптонит». 

Сейчас во многих странах криптографы работают на опережение и разрабатывают постквантовые схемы, которые могут быть реализованы уже сейчас и останутся надёжными даже после наступления эры квантовых вычислений. Конечно, на эти перспективные схемы тоже возможны атаки, но важно трезво оценивать их практическую значимость. 

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

Изначально автор публикации Илей Чен (Yilei Chen, ассистент Института междисциплинарной информатики Университета Цинхуа) утверждал, что нашёл способ решать за полиномиальное время на квантовом компьютере некоторые задачи на решётках, использующиеся в перспективных постквантовых криптосистемах, а также в полностью гомоморфном шифровании (FHE).

Чен опубликовал квантовый алгоритм для решения задачи обучения с ошибками (LWE). Она тесно связана с двумя другими задачами, применяющимися в криптографии. Первая – задача поиска кратчайшего вектора (GapSVP) решётки, а вторая — поиска системы линейно независимых векторов, в которой длина всех векторов минимальна (SIVP).

Как отмечал сам Чен, потенциальная опасность в том, что после некоторой доработки его алгоритм может оказаться эффективным для взлома недавно победивших в конкурсе NIST постквантовых схем: инкапсуляции ключей Kyber и цифровой подписи Dilithium. Если это произойдёт, то они и некоторые другие постквантовые схемы на решётках окажутся ненадёжными.

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

Основных замечаний у Найджела Смарта два:
1. алгоритм пока не позволяет атаковать криптосистемы Kyber, Dilithium или TFHE, но применим к некоторым вариантам BGV;
2. алгоритм подразумевает нереалистично большие физические требования к квантовому компьютеру, решающему данную задачу. При этом Найджел Смарт не отрицает возможности усовершенствования алгоритма.

Позже Илей Чен добавил к своей работе комментарий: «Шаг 9 алгоритма содержит ошибку, которую я не знаю, как исправить». На данную ошибку независимо указали Хонгксун Ву и Томас Видик. Томас комментирует ошибку следующим образом: «… К сожалению, способ, которым Чен выполняет этот шаг, неверен; и на данный момент неизвестно, существует ли альтернативный способ сделать это». Из чего можно сделать вывод, что постквантовая криптография на решётках пока остаётся невзломанной.

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

«Схема подписи «Шиповник», как и протокол инкапсуляции ключа «Кодиеум», разработаны экспертами-криптографами «Криптонита» в рамках деятельности профильной рабочей группы Технического комитета №26 Росстандарта РФ. Оба криптографических механизма в настоящее время устойчивы к атакам с использованием квантового компьютера», — пояснил Иван Чижов, заместитель руководителя лаборатории криптографии по научной работе компании «Криптонит».

Отечественная схема подписи «Шиповник» построена на основе теоретико-кодового протокола идентификации Штерна. Стойкость этой схемы подписи к подделке базируется на сложности задачи декодирования случайного линейного кода. В 1978 году было доказано, что эта задача является NP-полной. В настоящее время считается, что любая задача из класса NP-полных является вычислительно сложной и для квантового компьютера. Более того, алгоритм Чена не решает NP-полных задач на кодах, исправляющих ошибки, поэтому можно с уверенностью считать, что предложенный Ченом алгоритм не повлияет на стойкость схемы подписи «Шиповник».

Ситуация со схемой инкапсуляции ключа «Кодиеум» несколько сложней. «Её стойкость базируется на сложности декодирования случайного кода из некоторого достаточно узкого множества кодов. Задача декодирования линейного кода и задача обучения с ошибками, для которой Чен разработал алгоритм, сильно отличаются. В настоящее время нет эффективных подходов для декодирования линейных кодов над конечными полями с использованием алгоритмов обучения с ошибками» — прокомментировал Иван Чижов. 

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

«Примером, когда данный подход сработал, служит эксперимент Google и Cloudflare. В ходе него для передачи данных применялась комбинация классической схемы X25519 и постквантового протокола обмена ключами SIKE одного из финалистов конкурса NIST. В 2022 году была опубликована атака Кастрика — Декру, которая взламывает SIKE. В ней восстановление секретного ключа было реализовано всего за час на старом процессоре Intel Xeon E5-2630v2. То есть, алгоритм Кастрика — Декру оказался пригоден для выполнения атаки на классическом компьютере за полиномиальное время. Однако из-за параллельного использования в эксперименте Google и Cloudflare схемы X25519 практическая значимость взлома SIKE оказалась сомнительной», — добавил Александр Бахарев.

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