Роль отечественной математической школы в развитии мировой криптографии

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

Автор: Иван Чижов, заместитель руководителя лаборатории криптографии по научной работе компании “Криптонит”, к. ф.-м. н., доцент кафедры ИБ факультета ВМК МГУ им. М.В. Ломоносова

Русский след в американском стандарте

В этом году Национальный институт стандартов и технологий США (NIST) утвердил алгоритм HQC (Hamming Quasi-Cyclic) для защиты данных от атак с использованием квантовых компьютеров. Мало кто знает, что в его основе лежит исследование русского математика. HQC представляет собой механизм инкапсуляции ключей (KEM). Он построен на задаче отличения зашумленного кодового слова от случайного вектора. Именно основу этой задачи заложил российский математик Михаил Алехнович, который сформулировал ее как вычислительно сложную проблему, для которой пока не существует эффективных алгоритмов решения даже с использованием квантового компьютера [1]. Его работа, опубликованная в журнале Theoretical Computer Science, стала отправной точкой для HQC.

Коды Гоппы и постквантовая криптография

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

Например, криптосистема Classic McEliece (1978) основана на кодах, разработанных советским математиком Валерием Денисовичем Гоппой. Этот вклад отмечают и за рубежом. Например, "бабушка" современной теории кодирования Флоренс Джесси Мак-Вильямс [2] в предисловии к русскому изданию "библии" теории кодирования пишет: "Издание русского перевода книги "Теория кодов, исправляющих ошибки" является для нас большой честью. Это вполне понятно, если учесть значительный вклад, сделанный советскими учеными в теорию кодирования".

На базе криптосистемы МакЭлиса созданы многие современные криптографические алгоритмы, включая постквантовые. Среди них большие надежды связывают с NTRU-McEliece Hybrid, BIKE (Bit Flipping Key Encapsulation) и уже упоминавшимся HQC. Один или несколько из них могут войти в новые постквантовые криптографические стандарты, так как прошли многоэтапный отбор. Как вообще получилось так, что в новейшем американском стандарте (который де-факто станет международным) используются труды российских математиков? Основная причина в том, что разработка постквантовых алгоритмов – наукоемкий процесс, который лежит на стыке большого количества областей математики и криптографии. Он требует привлечения специалистов научных школ разных стран.

Так исторически сложилось, что теория помехоустойчивого кодирования, как и в целом общая теория информации, всегда привлекала внимание советских ученых. Вспомним, что в 1961 г. в СССР был создан целый Институт проблем передачи информации (в настоящее время он носит имя своего основателя Александра Александровича Харкевича), поэтому не удивительно, что в области теории кодирования советской школой было получено большое количество фундаментальных результатов, оказавшихся нужными в постквантовой криптографии. Упомянутый конкурс NIST проходил с 2016 г., а отдельные алгоритмы начали разрабатывать еще раньше и только сейчас довели до статуса финальных кандидатов на включение в будущий стандарт. Около сотни других разработок не прошли этот жесточайший отбор, а вот алгоритмы на базе идей русских математиков доказали свою надежность.

Дискретное логарифмирование и алгоритм Гельфонда-Шенкса

Готовясь к постквантовой эре, все продолжают использовать классическую криптографию. Каждый день вы пользуетесь этими механизмами при совершении банковских транзакций, общаясь через мессенджеры и просто подключаясь к сайтам по HTTPS. В основном это американские алгоритмы, но и в них просматривается русский след. Если вы интересовались, как все это устроено, то хотя бы раз слышали про протокол Диффи-Хеллмана, криптосистему Эль-Гамаля или схемы цифровой подписи DSA и ECDSA. Все они построены на сложности дискретного логарифмирования.

В 1962 г. советский математик Александр Осипович Гельфонд разработал алгоритм решения сложной задачи (дискретного логарифмирования в мультипликативной группе кольца вычетов по простому модулю). Этот же алгоритм спустя десять лет опубликовал Дэниел Шенкс, поэтому сейчас его называют алгоритмом Гельфонда – Шенкса.

Александр Гельфонд не только заложил теоретическую базу, но и показал практическую применимость своих идей, что подтверждается материалами из архивов Математического института им. В. А. Стеклова РАН. Его вклад в понимании реальной трудоемкости задачи дискретного логарифмирования остается ключевым для современной криптографии.

Российские стандарты в международной практике Российские разработки в области криптографии становятся частью международных стандартов ИСО/МЭК. Например, механизмы формирования и проверки цифровой подписи ГОСТ 34.10-2012, вошли в ISO/IEC 14888-3 (часть 3: механизмы на дискретных логарифмах) [3].

Кроме того, российские хэшфункции ГОСТ 34.11-2012 (известные как семейство хэшфункций "Стрибог") стали частью международного стандарта ISO/IEC 10118-3:2018 [4]. Редактором этого стандарта был Василий Шишкин, руководитель лаборатории криптографии компании "Криптонит". Также отмечу, что российский алгоритм шифрования "Магма" (RFC 8891 [5]) и многие другие отечественные разработки в области криптографии опубликованы как RFC [6]. Наиболее примечательные из них RFC 9189 [7] и RFC 9367 [8], описывающие использование алгоритмов ГОСТ в разных версиях протокола TLS. Именно он позволяет сегодня выполнять защищенное подключение к сайтам. Другой отечественный режим шифрования (MGM) был утвержден IETF как RFC 9058 [9]. Он предотвращает атаки с подменой IP и MAC в VPN.

Криптоанализ с точки зрения математики

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

В том числе оно помогает вычислять верхние границы вероятностей успеха в атаках по побочным каналам (SideChannel Attacks), таких как анализ энергопотребления или времени выполнения операций. Именно этот тип атак крайне опасен для постквантовых криптографических механизмов и стандартов.

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

Заключение

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

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