Евгений Крук: «В кодовой криптографии к прорыву мы находимся ближе всех»

Научный руководитель МИЭМ — о том, как будет устроена защита информации в будущем

В 2015 году в разговоре с академиком Жоресом Ивановичем Алферовым я как-то упомянул, что в свете скорого появления квантового компьютера нам нужно бы активизировать свои усилия в области постквантовой криптографии. Академик отмахнулся: «Какой квантовый компьютер, до него еще лет сорок…»

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

Компетенции в этом направлении у России есть, хотя сосредоточены они в нескольких небольших научных группах, оставшихся от большого научного сообщества, существовавшего в 70–80-е годы. В советское время теория кодирования была очень развитой наукой. Да, наверное, первое место в мире по этим разработкам занимал Массачусетский технологический институт, но на втором стоял Институт проблем передачи информации (сейчас — ИППИ РАН им. А.А. Харкевича). Институт не из самых больших, но из шести советских лауреатов Филдсовской премии трое работали в нем. Партнером этого института по разработкам в области теории кодирования была кафедра технической кибернетики Ленинградского института авиационного приборостроения (ныне ГУАП). Я начал работать на этой кафедре еще в ранней юности, закончил работать в ГУАП в должности проректора четыре года назад, и, когда в 90-е годы к нам в институт стали приходить крупные иностранные корпорации (Samsung, Huawei), они приходили именно за этим — за новыми решениями в области теории кодирования.

Современная криптография началась в середине 70-х годов XX века. Началась она со знаменитого протокола Диффи — Хеллмана, который позволял, используя незащищенный канал связи, тем не менее передавать защищенную информацию. Это был своего рода контрапункт в развитии сетей передачи информации. В традиционной криптографии рассматривалась ситуация, в которой легальные пользователи могли секретно обменяться ключом (например, при встрече) и использовать его для обмена информацией. В распределенных сетях с их миллионами пользователей такой обмен стал невозможным. На смену традиционной криптографии должна была прийти новая, свободная от необходимости использовать секретный обмен ключами. Такой новой криптографией и стала «криптография с открытым ключом», стартовавшая с работы Диффи и Хеллмана. Они предложили новое понятие — «функция с закрытыми дверями». Это такая функция шифрования информации, которая вычисляется достаточно просто, но обратная к ней функция, то есть функция расшифрования, вычисляется с помощью специального секретного ключа. Для тех, кому секретный ключ неизвестен, расшифрование становится вычислительно не реализуемой задачей.

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

Таким образом, Диффи и Хеллман сформулировали задачу поиска функции с закрытыми дверями. Первыми решениями этой задачи были две такие функции. Обе назывались по имени создателей. Одна, более известная, — это система RSA (Ривест — Шамир — Адлеман). Вторая — система McElice, разработанная профессором Калифорнийского технологического института Робертом Мак-Элисом.

Эти системы имели разную судьбу.

Система McElice была основана на использовании кодов, «исправляющих ошибки». У этого метода были свои объективные сложности, которые со временем решались, но Роберт Мак-Элис придумал эту систему скорее как умственное упражнение, решение головоломки. Никаких действий по продвижению этой системы он не предпринимал, и система имела исключительно академическую судьбу: по ней писались статьи, защищались диссертации, велись дискуссии. Практические разработки почти не проводились.

Рональд Ривест, Ади Шамир и Леонард Адлеман на тот момент были молодыми энергичными людьми, которые взялись активно продвигать свою систему. Через некоторое время после публикации научного открытия они создают корпорацию RSA Data Security и очень активно пропагандируют эту систему. Они судятся со спецслужбами, которые пытаются помешать публикации системы, выигрывают суд, при этом известный популяризатор науки Мартин Гарднер публикует систему в журнале Scientific American.

Паблисити было настолько большим, что со временем практически все мировые платежные системы стали использовать RSA.

Чтобы вскрыть систему RSA, надо разложить на множители некое огромное число, являющееся произведением двух простых чисел. Это трудная (вычислительно сложная) задача. Определенные успехи в ее решении были, однако казалось, что запаса прочности RSA хватит надолго. Но в 1994 году появляется работа американского ученого Питера Шора, посвященная полиномиальному алгоритму разложения чисел на множители на квантовом компьютере. Квантовый компьютер не существует, есть только красивая идея, сформулированная в 1980 году Ричардом Фейнманом, но если и когда квантовый компьютер нужной мощности будет создан, то алгоритм, который грозит обрушить все платежные системы, уже есть. Если говорить конкретнее, пока длина регистра компьютера порядка 50 кубитов, криптосистема с длиной ключа 2048 знаков еще устойчива. Но когда у вас 70–80 кубитов — эта система уже вскрывается.

В начале нулевых годов в разработках квантового компьютера был сделан огромный рывок, и начались поиски альтернативных систем с открытым ключом. В связи с «угрозой» квантового компьютера появилось понятие постквантовой криптографии — криптографии, которая устойчива к атакам с помощью квантового компьютера. Сейчас в мире проводятся десятки конференций по постквантовой криптографии.

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

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

Недавно мы составили дорожную карту развития МИЭМ на ближайшие годы, и постквантовая криптография включена в нее в качестве прорывного направления. Кроме того, это входит в один из стратегических проектов Вышки в рамках «Приоритета-2030». В условиях ковида, конечно, загадывать трудно: многие наши проекты он сильно затормозил, но мы с коллегами, с аспирантами и студентами МИЭМ будем продолжать исследования. Надеюсь, получится, должно получиться.