Читателю предлагается обзор основных направлений и перспектив стандартизации криптографических механизмов защиты информации, стойких как относительно классических, так и квантовых методов анализа (так называемых постквантовых криптографических алгоритмов), прежде всего на основе материалов мероприятий, проводимых американским Национальным институтом стандартов и технологий (NIST). Обозначен ряд проблем, возникающих перед отечественным криптографическим сообществом ввиду перспективы создания квантового вычислителя.
В настоящее время как за рубежом, так и в Российской Федерации ведутся активные исследования в области квантовых вычислений. Создание компьютера, реализующего квантовую модель вычислений (квантового компьютера) повлечет негативные последствия для ряда криптографических механизмов. В частности, на квантовом компьютере можно реализовать с полиномиальной сложностью алгоритмы факторизации и дискретного логарифмирования в произвольной группе (метод Шора), что в перспективе может привести к компрометации всех асимметричных криптографических схем, стойкость которых обосновывается предположением о сложности решения указанных задач, в том числе схем RSA, Диффи – Хеллмана и цифровых подписей ECDSA и ГОСТ Р 34.10–2012. При этом прорыва в области криптоанализа симметричных криптосхем не ожидается, поскольку известные в настоящее время квантовые алгоритмы анализа хэш-функций и блочных шифров (метод Амбайниса для поиска коллизий и метод Гровера для поиска прообраза) по-прежнему имеют экспоненциальную сложность, хотя и меньшую, чем классические.
При этом специалисты по-разному оценивают перспективы создания действующих образцов квантового вычислителя с характеристиками, достаточными для решения задач практического криптоанализа. Прогнозные оценки сроков создания таких квантовых компьютеров составляют от 10 до 40 лет , некоторые особо пессимистично настроенные ученые считают физические препятствия на пути создания квантовых вычислителей непреодолимыми.
Основной характеристикой мощности квантового вычислителя является количество кубитов – элементарных блоков. Задавая условие задачи как начальное состояние системы кубитов, составляющих квантовый вычислитель, и производя над ними серию предписанных квантовым алгоритмом преобразований, в результате финального измерения состояния системы кубитов получают решение задачи. При этом однако возникают значительные трудности инженерно-физического характера, связанные с необходимостью противодействия физической деградации кубитов в процессе вычислений и проведения точных измерений их состояния.
Для успешной факторизации числа N, являющегося секретным ключом криптографической системы RSA, метод Шора требует приблизительно 4/3logN кубитов и полиномиальное количество операций. В настоящее время нормативно-методические документы, регулирующие применение системы RSA, рекомендуют использование чисел длиной 2048 и более битов, таким образом, провести практически успешный криптоанализ можно будет на квантовом вычислителе мощностью не менее 2730 кубитов.
Существующие коммерческие прототипы квантовых компьютеров, в том числе разрабатываемые фирмами IBM и D-Wave, в основном предназначены для решения оптимизационных задач и не подходят для целей криптоанализа. Отметим, что в январе текущего года фирма IBM представила "персональный" 20-кубитовый квантовый вычислитель, смонтированный в корпусе объемом около 9 м3. Квантовые вычислители фирмы D-Wave, используемые в том числе Google и NASA, имеют, по утверждениям фирмы-производителя, до 1152 кубитов, сгруппированных в несколько кластеров, однако характер их внутренних топологических связей позволяет утверждать о наличии значительных ограничений в реализованной в данных устройствах модели квантовых вычислений.
Направления синтеза криптографических схем, стойких относительно анализа как с использованием классических, так и квантовых вычислений, получили общее название “постквантовая криптография”. Первая международная конференция PQCrypto, посвященная этим направлениям, состоялась в 2006 г. и с тех пор проводится каждые 1–2 года.
В последнее время проводимые международным криптографическим сообществом исследования в области синтеза постквантовых криптоалгоритмов интенсифицировались благодаря усилиям Национального института стандартов и технологий США (NIST), организовавшего площадку для подачи предложений по стандартизации и обсуждения постквантовых криптографических схем. (Отметим, что данное мероприятие формально не является конкурсом, поскольку предусматривает не выдвижение и награждение победителя, а лишь определение набора оптимальных синтезных решений для дальнейшего исследования и перспективной стандартизации, но носит все его черты, поэтому далее будем употреблять выражение “конкурс NIST”.) Прием заявок на участие в конкурсе NIST завершен 30 ноября 2017 г. Всего поданы описания 69 криптографических механизмов, разработанных авторскими коллективами из различных стран, в том числе международными. В апреле 2018 г. состоялся симпозиум, подводящий итог этапу приема заявок.
Решения, поданные для участия в конкурсе NIST, реализуют следующие механизмы: цифровую подпись, шифрование, инкапсуляцию ключей и выработку общего ключа. Учитывая опыт ранее проводимых NIST конкурсов на создание блочного шифра (AES) и хэш-функции (SHA-3), комплекс работ по анализу предложений и созданию новых стандартов может занять до пяти лет.
NIST предъявляет требования по стойкости к участникам конкурса как формальные (строго доказуемые на основе предположения о сложности решений некоторой задачи), так и практические. Рассмотрим сначала первые.
Асимметричные системы шифрования
Для асимметричных систем шифрования (перечислены от слабых требований к сильным):
Электронная подпись
Для схем подписи интерес представляют следующие понятия стойкости (перечисленные от слабых требований к сильным):
Практическая стойкость
Определения практической стойкости, заданные требованиями NIST, предусматривают пять уровней стойкости.
Для каждой заявки должно быть предоставлено формальное доказательство стойкости, предложены наборы параметров для некоторых (необязательно всех) уровней стойкости.
Всего на конкурс подано 69 заявок, 14 из них уже отозваны авторами или взломаны, на 13 схем опубликованы атаки (не всегда приводящие к их компрометации или отзыву).
Одна из заявок, поданная Д. Бернштейном с соавторами, носит явно сатирический характер, в ней предлагается использовать RSA с экспоненциальным размером ключей; так, для пятого уровня стойкости предполагается использовать ключи размером более 1 Гбайт.
Перечислим теперь основные синтезные решения, применяемые конкурсантами NIST:
Криптосхемы на основе теории решеток (см. пример соответствующей схемы выработки общего ключа на рис. 1) основаны на ряде сложных задач, в их числе NP-задачи поиска кратчайшего вектора (SVP) и поиска ближайшего вектора (CVP); задача обучения с ошибками (LWE; RLWE) и задача поиска наименьшего целочисленного решения системы линейных алгебраических уравнений (SIS).
¹ Здесь перечеркнуты названия отозванных или взломанных схем, символ (*) после названия схемы обозначает наличие атаки (не обязательно полностью компрометирующей схему) на нее (см. M.-J. Saarinen, (Most) Post-Quantum Bugs are just Plain Old Bugs, CTCrypt 2018 Rump Session).
Задачи теории кодирования рассматривались в криптографии с конца 1970-х гг., так, схема МакЭлиса хотя и взломана для ряда частных случаев российскими специалистами², при условии использования кодов Гоппы остается стойкой.
² 1994 год, В.М. Сидельников (1940--2008).
Схема приведена на рис. 2.
К числу основанных на задачах теории кодирования конкурсантов NIST относятся: BIG QUAKE, BIKE, Classic McEliece, DAGS (*), Edon-K (*), HQC, LAKE, LEDAkem, LEDApkc, Lepton, LOCKER, McNie, NTS-KEM, Ouroboros-R, QC-MDPC KEM, Ramstake, RLCE-KEM (*), RQC, pqsigRM, RaCoSS (*), RankSign (*).
Следующая идея – использование NP-полной задачи решения системы многочленов от многих переменных – исследуется с точки зрения синтеза криптосхем с середины 1980-х гг. (см. пример на рис. 3). В то же время разработаны различные практически эффективные методы для решения этой задачи (XL-метод, F4, F5 и др.), многие из криптосхем, построенных на данной задаче, были успешно атакованы (вспомним системы HFE, Мацумото – Имаи).
К числу основанных на этой задаче конкурсантов NIST относятся: CFPKM, Giophantus (*), DualModeMS, GeMSS, Gui, HiMQ-3, LUOV, MQDSS, Rainbow, SRTPI (*), DME.
Основанные на хэшировании схемы подписи используют разработанные еще в конце 1970-х гг. идеи одноразовой подписи Лампорта и Винтерница, адаптируя их для построения многоразовой схемы подписи на основе древовидной структуры хэш-значений специального вида. Эту идею в том или ином виде применяют следующие конкурсанты NIST: SPHINCS+, GravitySPHINCS.
На сложной задаче поиска пути в графе изогений между суперсингулярными эллиптическими кривыми основана схема SIKE.
К прочим примитивам относятся WalnutDSA (*) (группы кос³), pqRSA (юмор), Guess Again (*), HK17 (*), Mersenne-756839, RVB (*), Picnic.
³ Несостоятельность использования групп кос для построения стойких криптосхем была показана в 2014 г. российским специалистом М.М. Глуховым (1930--2018).
30 января 2019 г. NIST опубликовал перечень кандидатов, прошедщих на второй этап конкурса. В их число вошли следующие схемы:
Можно отметить, что эксперты NIST не высказали явного предпочтения при выборе базовых синтезных решений, исключив лишь наиболее экзотические (на которые и пришлась большая часть атак).
Следующим этапом будет внесение правок и улучшений в прошедшие на второй этап схемы, для этого отводится срок до 15 марта 2019 г.
Важным вопросом является эффективность предлагаемых на конкурс NIST схем. Необходимо отметить, что все без исключения схемы имеют размер параметров, длину ключей и, как правило, длину шифртекста (подписи, общего ключа) большую, чем у традиционных криптографических схем (RSA, ECDH, ECDSA) при равном (относительно классического вычислителя) уровне стойкости. Как правило, вычислительных ресурсов (процессорного времени, памяти) также требуется больше.
Таким образом, переход к постквантовой криптографии потребует для сохранения функциональности защищенных сетей обработки информации значительного увеличения выделяемых на криптографические преобразования вычислительных ресурсов.
Область постквантовой криптографии охвачена и в деятельности Международной организации по стандартизации/Международной электротехнической комиссии. Так, профильным техническом комитетом, отвечающим за стандартизацию механизмов обеспечения информационной безопасности, инициировано проведение работ по созданию установочного документа, в котором будут отражены основные направления создания постквантовых криптографических схем.
Заключение
Таким образом, международное сообщество активно готовится к наступлению постквантовой эры. Очевидна также необходимость подготовки отечественной информационной инфраструктуры к появлению квантовых криптоаналитических вычислителей, для чего потребуется разработка семейства постквантовых стандартов в области криптографической защиты информации, учитывая, разумеется, и международный опыт. При этом, однако, надо принимать во внимание ряд следующих соображений.
Таким образом, необходимость разработки семейства постквантовых криптографических механизмов является важной, хотя на данный момент и не первоочередной задачей, которую предстоит решать не только в рамках Технического комитета "Криптографическая защита информации" (ТК 26), но и силами всего российского криптографического сообщества.