Что такое постквантовая криптография?

Постквантовая криптография (англ. post-quantum cryptography) — наиболее эффективный метод защиты ценных данных с длинным жизненным циклом от кибератак с применением как классических, так и квантовых компьютеров.

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

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

и другие, более специализированные криптографические методы.

Для того, чтобы разобраться в том, что такое «постквантовая криптография», давайте вначале разберемся в термине «криптосхема».

Криптосхема — это алгоритм или протокол, который путем применения заданных математических преобразований к цифровым данным решает те или иные задачи защиты информации.

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

Для обоснования стойкости криптосхемы задачу ее взлома сводят к решению некоторой сложной математической задачи. Установить строгую эквивалентность взлома криптосхемы «Y» и математической задачи «X» не всегда возможно, поэтому криптосхема «Y» считается стойкой, если:

• умеем эффективно решать математическую задачу «X» — следовательно, взламываем криптосхему «Y»;
• много ученых думали много лет, но не придумали вычислительно эффективного способа решения задачи «X»;
• много ученых думали много лет, но не придумали иного способа взлома криптосхемы «Y», кроме решения задачи «X».

Криптосхемы разделяются на:

• симметричные — такие, что ключи зашифрования и расшифрования совпадают;
• асимметричные — такие, что ключи зашифрования и расшифрования различаются, но связаны между собой некоторой математической функцией.

Наиболее распространенные современные асимметричные криптосхемы основываются на таких сложных задачах, как:

• факторизация (разложение на множители) больших натуральных чисел (например алгоритм RSA);
• дискретное логарифмирование в конечных полях (алгоритмы: DSA, DH, ГОСТ Р 34.10-94);
• дискретное логарифмирование в группе точек эллиптических кривых (алгоритмы: ECDSA, ECDH, ГОСТ Р 34.10-2012).

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

Возьмем для примера пользовательский трафик в сети Интернет. Почти весь такой трафик защищается с использованием протокола TLS — комбинации симметричных, например, AES и асимметричных, например, RSA криптосхем. Для дешифрования трафика злоумышленнику достаточно определить секретный сеансовый ключ, полученный при помощи асимметричной криптосхемы. Именно этот класс криптосхем подвержен так называемой квантовой угрозе, поскольку уже сейчас известны эффективные квантовые алгоритмы (например метод Шора для факторизации и дискретного логарифмирования) для их взлома, и дело только за созданием квантового компьютера достаточной мощности. Появление такого квантового компьютера, который смог бы взломать криптосхему RSA с рекомендуемой для использования в настоящее время длиной ключа 3072 бита, прогнозируется по наиболее оптимистичными исследователями, на 2030й год.

В то же время симметричным криптографическим алгоритмам, таким, как блочные шифры ГОСТ Р 34.12-2015, AES и хэш-функции ГОСТ Р 34.10-2012, SHA-3, квантовый компьютер угрожает в меньшей степени, поскольку, хотя известные квантовые алгоритмы (метод Гровера и другие) и снижают вычислительную трудоемкость их взлома, он по-прежнему нереализуем в обозримое время.

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

Основные направления синтеза квантово-устойчивых, или постквантовых, криптосхем включают:

• использование теории целочисленных решеток (lattice-based cryptography): задача поиска кратчайшего вектора решетки и ее варианты, задача обучения с ошибкой;
• использование кодов, исправляющих ошибки (code-based cryptography): задача декодирования случайного кода;
• использование многочленов от многих переменных (multivariate cryptography): задача решения нелинейной системы уравнений над конечным полем;
• использование криптографических хэш-функций (hash-based cryptography): задачи поиска коллизии, прообраза, второго прообраза для криптографических хэш-функций;
• использование изогений суперсингулярных эллиптических кривых (supersingular isogeny-based cryprography): задача поиска пути в графе изогений;
• «экзотика»: проблемы сопряженного поиска (search problem), операции в группах кос (braid groups), алгебра октонионов, многочлены Чебышёва и т.д.

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

Начиная с 2017 года, процессы исследования в области синтеза и анализа квантово-устойчивых криптосхем получили новый импульс благодаря усилиям Национального института стандартов и технологий США (National Institute of Standards and Technology, NIST), организовавшего открытую международную площадку-конкурс для подачи предложений по стандартизации и обсуждению постквантовых криптосхем. Эксперты NIST и представители международного криптографического сообщества за прошедшие два раунда конкурса проанализировали более 80 криптосхем-кандидатов, отобрав 15 финалистов. Ожидается, что к 2024 году процесс стандартизации американских (и де-факто международных) постквантовых криптосхем будет завершен.

Собственный конкурс по выбору оптимального набора квантово-устойчивых криптосхем провели и в Китае силами Китайской ассоциации криптологических исследований (CACR) в 2018-2019 годах. На конкурс было представлено 36 алгоритмов, также закрывающих весь спектр классов сложных задач постквантовой криптографии.

В России усилиями рабочей группы РГ 2.5 «Постквантовые криптографические механизмы» при техническом комитете Росстандарта «Криптографическая защита информации» (ТК 26) c 2020 года ведется разработка собственного набора квантово-устойчивых криптосхем, которые в ближайшем будущем дополнят семейство национальных стандартов в области криптографии.

Таким образом, международное криптографическое сообщество активно ищет пути противодействия квантовой угрозе. В условиях стремительного развития квантовых компьютеров и квантовых вычислений актуальным становится сценарий атаки «Сохранение данных сейчас — взлом потом» (backup now — decrypt later), в котором злоумышленник сегодня сохраняет зашифрованные традиционными методами данные, а с появлением у него доступа к квантовому компьютеру дешифрует их. Защищать ценные данные с длинным жизненным циклом от квантовой угрозы требуется уже сегодня, и постквантовая криптография предоставляет для этого эффективные средства.