«Страшный сон криптографа»: как квантовый компьютер меняет правила цифровой безопасности

Когда в 2006 году я защищал диплом по постквантовой криптографии, многие смотрели на меня с недоумением: зачем это нужно? Казалось, я занимаюсь чем-то далеким и от практики, и от востребованной теории. Но меня всегда интересовала математика — именно та специфическая, которая связана с векторами, матрицами и сейчас используется в постквантовой криптографии. Я не бросил исследовать эту тему и спустя почти двадцать лет могу констатировать: она актуальна как никогда.

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

К примеру, когда мы вбиваем https в строке браузера, запускается целый криптографический процесс: установка ключей, создание защищенного соединения, шифрование между сайтом и нашим компьютером. Когда мы звоним по мобильному телефону, даже не используя IP-телефонию, мы также задействуем криптографию.

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

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

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

Кажется, без хай-тека и технологических наворотов в данном случае не обойтись. На самом же деле защита от подделки применяется даже в примитивных кассовых аппаратах. Каждый чек получает уникальную криптографическую метку, созданную с помощью секретного ключа устройства, — ФПД или фискальный признак документа. Эта метка зависит от содержимого чека и не позволяет поменять в нём хотя бы один символ бесследно. Это своего рода электронная подпись. По ней также можно определить, напечатан чек на самом аппарате или подделан в другой системе.

Тот же принцип — только на другом уровне сложности — защищает банковские переводы, электронные паспорта, доступ к госуслугам, обновления ПО.

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

Криптографии в данном случае не повезло: в основе всей современной цифровой защиты лежат именно те две задачи, которые лучше всего умеет решать квантовый компьютер:

• То самое разложение на множители — факторизация. На ней построен алгоритм RSA, который защищает ваши банковские переводы, электронную почту или подключение к удаленному серверу.
• Дискретное логарифмирование — основа протокола Диффи-Хеллмана для безопасного обмена ключами через открытые каналы. Именно этот протокол применяется, когда вы открываете сайт по https: браузер и сервер обмениваются ключами шифрования. Та же технология защищает переписку в мессенджерах.

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

Но квантовый компьютер использует в вычислениях два принципа квантовой механики: запутанности и суперпозиции. А основу квантовых вычислений составляет квантовое дискретное преобразование Фурье, с помощью которого можно одновременно «просветить» огромное количество вариантов и обнаружить скрытые закономерности.

Такие возможности при появлении высокопроизводительного квантового компьютера ставят под угрозу привычные системы шифрования: они перестают быть надежным барьером.

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

Теперь переведем это на язык математики. Каждому предмету присваивается свой номер и объём. Сообщение превращается в двоичную маску — последовательность из нулей и единиц.

Если бит равен 1 — берем, если 0 — пропускаем. Тогда шифр-текстом будет сумма объемов всех выбранных предметов.

Например, у нас есть предметы с объемами: 15, 2, 7, 9, 10, 4.

А сообщение такое: 0 1 1 0 1 0.

Тогда для шифрования берём предметы под номерами 2, 3 и 5. Их объемы — 2, 7 и 10. Сумма этих чисел — и есть зашифрованное значение:

Казалось бы, для таких задач и создается квантовый компьютер — чтобы разом просчитать все комбинации. Но нет: он «упаковывает рюкзак» почти так же долго, как и классическая машина. Задача станет еще сложнее, если вместо числового «рюкзака» использовать алгебраический, где меняется сам смысл «упаковки». В обычном рюкзаке совокупный объем — это сумма объемов всех предметов. Но если вместо сложения использовать побитовую сумму объемов по модулю 2 (XOR), даже квантовому компьютеру будет крайне сложно.

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

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

Главный минус сегодняшнего ИИ в том, что для оценки его работы нужна квалификация. А уровень этой квалификации зависит от сложности задачи. Постквантовая криптография требует высочайшего уровня знаний в разных областях математики. Часто ИИ выдает результат, который на первый взгляд кажется верным, даже подтверждается экспериментами. Но при внимательном разборе замечаешь логические ошибки именно в математике, лежащей в основе подхода. А что будет, если вы ее пропустите?!

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

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

Итак, привычные алгоритмы, такие как RSA или протокол Диффи‑Хеллмана, уходят в прошлое — они уязвимы перед квантовыми компьютерами. Им на смену приходят другие: декодирование алгебраической решетки и линейного кода или задача обучения с ошибками.

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

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

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

У России в этом процессе есть свой вес: отечественные школы по теории кодирования и алгебраическим решеткам сейчас одни из лучших в мире.

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

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

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