Квантовые вызовы

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

Пока, вроде бы, достаточно мощного квантового компьютера ни одна страна мира не имеет, но что мы знаем о работе в этой области таких структур, как АНБ (Агентство национальной безопасности) в США или ФСБ в России? А ничего не знаем.

Далеко не случайно самые мощные государства и отдельные корпорации давно развернули работы в области практического внедрения пост-квантовой криптографии. Соответствующие алгоритмы изобретены и подвергаются проверке. Есть и практические наработки в конкретных компьютерных приложениях. Так, компания Google четыре года назад провела эксперимент с внедрением пост-квантового криптографического алгоритма “New Hope” в свой браузер Chrome Canary. https://security.googleblog.com/2016/07/experimenting-with-post-quantum.html

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

Ученые-криптографы предложили несколько алгоритмов, которые, по первоначальным оценкам, будут устойчивы к взлому на квантовом компьютере. С 2006 года по проблемам квантовой криптографии проводятся научные конференции. NIST (National Institute of Standards and Technology – Национальный институт стандартов и технологий США) в 2016 году объявил конкурс на алгоритмы будущего криптографического стандарта США для цифровой подписи и обмена ключами. https://csrc.nist.gov/projects/post-quantum-cryptography В 2017 г. было принято 69 алгоритмов-кандидатов, отвечавшим минимальным критериям для допуска к конкурсу. В январе 2019 г. их осталось 26 и начался второй раунд тщательного изучения и оценки алгоритмов-кандидатов с точки зрения безопасности, стоимости и производительности и некоторых других характеристик. Недавно, в июле 2020 года были объявлены финалисты второго раунда конкурса, это алгоритмы для обмена ключами Classic McEliece, CRYSTALS-KYBER, NTRU и SABER и алгоритмы для цифровой подписи CRYSTALS-DILITHIUM, FALCON, and Rainbow. Их NIST счел наиболее обещающими и по окончании третьего раунда 1-2 алгоритма-победителя из их числа для шифрования и обмена ключами и 1-2 алгоритма-победителя для цифровой подписи могут стать стандартом. Кроме того, к третьему раунду допущены 8 альтернативных алгоритмов-кандидатов, которые также еще рассматриваются для включения в стандарт, но вряд ли это произойдет к концу третьего раунда. Они либо нуждаются в дополнительном времени для полной готовности, либо нацелены для применения в специальных приложениях. Процесс их рассмотрения продолжится после третьего раунда и они также имеют шансы стать частью стандарта.

В отчете NIST по результатам второго раунда подробно разобраны сильные и слабые стороны алгоритмов-кандидатов https://doi.org/10.6028/NIST.IR.8309

В NIST планируют в 1922 году выпустить первый стандарт для пост-квантовой криптографии.

Кстати сказать, пост-квантовый алгоритм “New Hope”, который тестировал интернет-гигант Google, в третий раунд конкурса не прошел. Научный поиск иногда ведет к разочарованию. А вот алгоритм McEliece, напротив, был предложен в далеком 1978 году, когда компьютеры были большие, энергоемкие и использовались на крупных предприятиях. Алгоритм распространения не получил ввиду не очень эффективной реализации, так как открытый ключ у McEliece имеет очень, очень большой размер (для рекомендуемых параметров более 500000 бит), а зашифрованный текст превышает исходный текст примерно в 1.6 раза (что, в общем-то, не так критично). Алгоритм был почти забыт. Но вот мы видим его новое рождение в пост-квантовой криптографии.