NIST утвердил алгоритмы шифрования, устойчивые к квантовым вычислениям

Национальный институт стандартов и технологий США (NIST) объявил победителей конкурса криптоалгоритмов, стойких к подбору на квантовом компьютере. Конкурс был организован шесть лет назад и нацелен на выбор алгоритмов постквантовой криптографии, пригодных для выдвижения в качестве стандартов. В процессе проведения конкурса предложенные международными командами исследователей алгоритмы были изучены независимыми экспертами на предмет возможных уязвимостей и слабых мест.

Победителем среди универсальных алгоритмов, которые можно использовать для защиты передачи информации в компьютерных сетях, выбран CRYSTALS-Kyber, сильными сторонами которого являются относительно небольшой размер ключей и высокая скорость работы. CRYSTALS-Kyber рекомендован для перевода в разряд стандартов. Кроме CRYSTALS-Kyber выделены ещё четыре алгоритма общего назначения - BIKE, Classic McEliece, HQC и SIKE, которые требуют доработки. Авторам данных алгоритмов предоставлена возможность до 1 октября обновить спецификации и устранить недочёты в реализациях, после чего они также могут быть включены в число финалистов.

Из алгоритмов, нацеленных на работу с цифровыми подписями, выделены CRYSTALS-Dilithium, FALCON и SPHINCS+. Алгоритмы CRYSTALS-Dilithium и FALCON отличаются высокой эффективностью. В качестве первичного алгоритма для цифровых подписей рекомендован CRYSTALS-Dilithium, а FALCON ориентирован на решения, в которых требуется минимальный размер подписи. SPHINCS+ отстаёт от первых двух алгоритмов по размеру подписей и скорости работы, но он оставлен в числе финалистов в качестве запасного варианта, так как базируется на принципиально иных математических принципах.

В частности, в алгоритмах CRYSTALS-Kyber, CRYSTALS-Dilithium и FALCON используются методы криптографии, основанные на решении задач теории решёток, время решения которых не отличается на обычных и квантовых компьютерах. Алгоритм SPHINCS+ применяет методы криптографии на основе хеш-функций.

Оставленные для доработки универсальные алгоритмы также основаны на иных принципах - в BIKE и HQC используются элементы теории алгебраического кодирования и линейные коды, также применяемые в схемах коррекции ошибок. NIST намерен дополнительно стандартизировать один из этих алгоритмов для оставления альтернативы уже выбранному алгоритму CRYSTALS-Kyber, основанному на теории решёток. Алгоритм SIKE базируется на использовании суперсингулярной изогении (кружение в суперсингулярном изогенном графе) и также рассматривается в качестве кандидата на стандартизацию, так как отличается наименьшим размером ключа. Алгоритм Classic McEliece включён в число финалистов, но пока не будет стандартизован из-за очень большого размера открытого ключа.

Необходимость разработки и стандартизации новых криптоалгоритмов обусловлена тем, что активно развивающиеся последнее время квантовые компьютеры кардинально быстрее решают задачи разложения натурального числа на простые множители (RSA, DSA) и дискретного логарифмирования точек эллиптической кривой (ECDSA), которые лежат в основе современных асимметричных алгоритмов шифрования по открытым ключам и эффективно не решаемы на классических процессорах. На текущем этапе развития возможностей квантовых компьютеров пока недостаточно для взлома актуальных классических алгоритмов шифрования и цифровых подписей на базе открытых ключей, таких как ECDSA, но предполагается, что ситуация может измениться в течение 10 лет и необходимо подготовить базу для перевода криптосистем на новые стандарты.