Гонка за квантово-безопасную криптографию продолжается

В 2016 году Лили Чен начала конкурс по переписыванию строительных блоков шифрования.

Вместе со своей командой математиков из Национального института стандартов и технологий США Чен обратилась к академическим и отраслевым криптографам по всему миру, чтобы найти алгоритмы, которые могли бы противостоять новым угрозам, исходящим от квантовых компьютеров. Спустя пять лет проект почти завершен. После трех раундов выбывания Чен и ее команда сократили количество заявок с 69 до семи финальных алгоритмов, при этом несколько победителей будут названы в конце года. Если все пойдет по плану, результатом станет новый набор алгоритмов, сертифицированных NIST, и новая мера защиты от хаоса полностью работоспособного квантового компьютера.

«Криптосистемы в устройствах и системах связи перестанут быть безопасными», когда эти компьютеры достигнут своего потенциала, - говорит Чен. «Пришло время подготовиться к квантовым угрозам».

У Чен есть технические причины для беспокойства. Существующие системы шифрования полагаются на определенные математические уравнения, которые классические компьютеры не очень хорошо решают, но квантовые компьютеры могут легко справиться с ними. Как исследователь безопасности, Чен особенно заинтересована в способности квантовых вычислений решать два типа математических задач: разложение больших чисел на множители и решение дискретных логарифмов (по сути, решение проблемы bx = a для x). Практически вся интернет-безопасность полагается на эту математику для шифрования информации или аутентификации пользователей в таких протоколах, как Transport Layer Security. Эти математические задачи просты для решения в одном направлении, но трудны в обратном, и поэтому идеально подходят для криптографической схемы.

«С точки зрения классического компьютера это сложные проблемы, - говорит Чен. «Однако они не слишком сложны для квантовых компьютеров».

В 1994 году математик Питер Шор в своей статье обрисовал, как будущий квантовый компьютер может решать проблемы факторизации и дискретного логарифмирования, но инженеры все еще пытаются заставить квантовые системы работать на практике. Хотя несколько компаний, таких как Google и IBM, а также такие стартапы, как IonQ и Xanadu, создали небольшие прототипы, эти устройства не могут работать стабильно, и они не смогли окончательно выполнить какие-либо полезные задачи, помимо того, что могут выполнить лучшие обычные компьютеры. В 2019 году Google сообщил, что его квантовый компьютер решил проблему быстрее, чем лучшие из существующих суперкомпьютеров, но это была надуманная задача, не имеющая практического применения. А в 2020 году академические исследователи в Китае также сообщили, что их квантовый компьютер превзошел обычные вычисления в выполнении алгоритма, который может быть полезен для специализированных задач оптимизации. Но пока квантовым компьютерам удавалось разложить на множители только крошечные числа, такие как 15 и 21, - полезное доказательство принципа, но отнюдь не практическая угроза.

Это не помешало исследователям оставаться на шаг впереди квантовой проблемы. Питер Швабе, математик из Института безопасности и конфиденциальности Макса Планка, вместе с коллегами разработал несколько схем криптографии, которые победили в третьем раунде конкурса NIST. Одна из его работ квалифицируется как протокол на основе решетки, класс квантово-устойчивых алгоритмов, которые включают геометрическую головоломку в сетке точек, расположенных в сотнях или даже тысячах измерений. Чтобы взломать код, компьютер должен использовать заданные отрезки линии для решения головоломки, например, найти наиболее компактный способ соединить линии в сетке один за другим.

«Криптография на основе решеток в настоящее время считается наиболее реалистичной заменой существующих сегодня протоколов», - говорит Швабе.

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

«Мы должны попытаться подготовить эти криптосистемы задолго до появления квантовых компьютеров», - говорит математик NIST Дастин Муди, член команды Чена.

До введения стандартов NIST некоторые компании уже начали экспериментировать с этими новыми схемами криптографии. В 2019 году Google и компания по безопасности Cloudflare начали тестирование скорости и безопасности двух протоколов, устойчивых к квантовым вычислениям. «Мы надеемся, что этот эксперимент поможет выбрать алгоритм с лучшими характеристиками для будущего Интернета», - написал криптограф Крис Квятковски из Cloudflare в своем блоге после проведения тестов.

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

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

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