Квантовая угроза и как ей противостоять

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

Александр Сазонов, технический руководитель направления персонализированных ИИ-сервисов во Future Crew, принял участие во встрече и рассказал нам о том, какие подходы к противодействию квантовой угрозе обсуждались.

В контексте квантовой угрозы рассматриваются в первую очередь два алгоритма:

• алгоритм Гровера, вдвое уменьшающего эффективную длину любого симметричного криптографического алгоритма;

• алгоритм Шора, ломающий классические алгоритмы с открытым ключом.

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

Атаки с использованием алгоритма Шора практическую угрозу несут и, по оценке экспертов, станут актуальными ориентировочно в 2028-2030 гг. К тому времени должен появиться квантовый компьютер с числом логических кубитов, в 3 раза превышающим размер ключа (в 1.5 раза превышающим размер поля). Т.е. для взлома зашифрованного ключом длиной 2048 бит (длина ключа, рекомендованная NIST, The National Institute of Standards and Technology) сообщения, должен появиться квантовый компьютер размерностью более 6150 логических кубитов. Важно отметить, что при этом количество физических кубитов в зависимости от технологии может быть на порядки больше.

Противостоять атакам с использованием квантовых компьютеров призваны т.н. постквантовые криптографические механизмы. ТК 26 (Технический комитет по стандартизации «Криптографическая защита информации» (ТК 26) Росстандарта) сейчас ведет работу над следующими такого рода механизмами:

• механизмы на основе кодов, исправляющих ошибки (идет процесс стандартизации схемы подписи «Шиповник»);

• механизмы на основе алгебраических решеток (разработана схема подписи «Крыжовник»);

• механизмы на основе хэш-функций (в разработке схемы подписи «Иггдрасиль» и «Гиперикум»);

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

Кроме этого, в экспертном сообществе рассматриваются другие методы противодействия квантовой угрозе. Среди них перспективными считаются:

• комбинированные схемы с дополнительным симметричным ключом;

• использование постквантовых криптографических примитивов при вычислении сеансовых ключей.

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

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