Реализация постквантовых алгоритмов на Java и Go
В последнее время в СМИ много публикаций о новых квантовых компьютерах, которые представляют угрозу для современной криптографии. Например, недавно Google сообщила о разработке квантового процессора Willow, который в специально сформулированной задаче превышает производительность самого мощного суперкомпьютера в септиллион раз (септиллион = 1025).
Хотя квантовая криптография быстро развивается, ей ещё далеко до того, чтобы угрожать современной криптографии. Более того, разработан ряд постквантовых алгоритмов и шифров, которые устойчивы к квантовым вычислениям.
Квантовые компьютеры
По информации Google, новый квантовый процессор Willow — самый высокопроизводительный квантовый чип из существующих.
Другие компании тоже объявили о собственных разработках. Например, китайские исследователи недавно создали квантовый компьютер Tianyan-504, который по своим характеристикам даже превосходит Willow, и будет доступен для клиентов через облачный сервис.
Корпорация IBM тестирует квантовый процессор Condor с более чем 1000 кубитов. Такие чипы IBM называет Quantum Processing Unit (QPU). Уже создана промышленная версия QPU под названием Heron на 133 кубитах.
IBM разработала долгосрочный план по разработке QPU до 2033 года и дальше:
Квантовые вычисления быстро развиваются как отрасль программирования. Например, разработаны экспериментальные версии языка программирования и операционной системы для квантовых компьютеров.
Язык программирования Twist представляет определённый академический интерес, с примерами специфического кода для квантовых вычислений (например, здесь отбрасывание кубита — это измерение значения).
Прогресс квантовых вычислений настораживает некоторых специалистов по компьютерной безопасности. Дошло до того, что например Австралия решила отказаться от части современной криптографии. Австралийское управление связи (Australian Signals Directorate, ASD) опубликовало руководство по использованию «криптографического оборудования высокой надёжности» (High Assurance Cryptographic Equipment, HACE) — устройств, отправляющих и/или получающих конфиденциальную информацию, — которое предусматривает запрет на использование криптографических алгоритмов SHA-256, RSA, ECDSA и ECDH, среди прочих, к 2030 году. То есть их можно использовать ещё четыре года, после чего следует заменить постквантовой криптографией.
Постквантовая криптография
Постквантовая криптография — это часть криптографии, которая устойчива к квантовым атакам. Большинство традиционных криптосистем опирается на факторизацию целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах. Постквантовые алгоритмы опираются на другие вычислительно сложные задачи, имея ряд существенных отличий от указанных выше систем, из-за чего их гораздо сложнее решить.
При этом постквантовая криптография отличается от квантовой криптографии, которая занимается методами защиты коммуникаций, основанных на принципах квантовой физики.
В августе 2024 года институт по стандартам NIST одобрил три постквантовых криптографических алгоритма ML-KEM, ML-DSA и SLH-DSA.
Три месяца спустя организация опубликовала проект руководства «Переход к постквантовым стандартам криптографии». Согласно этому предложению, некоторые стандарты будут признаны устаревшими к 2030 году (среди них алгоритм RSA) и полностью запрещены к использованию к 2035 году.
Как и в случае с ASD, руководство NIST направлено на снижение риска того, что криптографические стандарты «могут быть уязвимы для атаки криптографически релевантного квантового компьютера (CRQC)» к 2035 году.
В сентябре 2024 года Агентство национальной безопасности США выпустило аналогичное руководство и также установило 2035 год в качестве даты перехода.
Алгоритм Dilithium
NIST уже восемь лет ведёт отбор постквантовых алгоритмов для создания шифров, устойчивых к квантовым атакам. Так, в 2022 году она среди прочих отметила постквантовый алгоритма Dilithium.
Dilithium является частью набора алгоритмов CRYSTALS и основан на алгебраических решётках. Если использовать понятия линейной алгебры, то можно представить, что записи матрицы/вектора являются полиномами в кольце Rq = Zq[X] / (Xn + 1). Более подробную информацию (включая спецификацию и эталонную реализацию на языке C) можно найти на официальном сайте CRYSTALS.
Вскоре после одобрения Dilithium со стороны NIST независимые разработчики представили Java-реализацию этого алгоритма. Как и эталонная реализация, она поддерживает все три документированных уровня безопасности (уровни 2, 3 и 5), используя схему детерминированной подписи. Реализация поддерживает сериализацию и десериализацию с использованием документированных форматов.
Dilithium и его реализация на Java — не единственный алгоритм постквантовой криптографии. Например, в 2024 году был опубликован пакет mlkem768, это реализация метода квантово-устойчивого инкапсулирования ключей ML-KEM (ранее известного как Kyber) на языке Go.
Хотя современной криптографии в данный момент ничего не угрожает, но есть смысл подготовиться к переходу на постквантовые шифры в случае необходимости. И хорошо, что разработчики выпускают опенсорсные библиотеки, готовые к использованию в такой ситуации.
