Квантовая ложь

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

Математики

Хотя уважаемый американский математик Питер Шор не поднимал ни хайпа, ни паники, именно он в 1994 году предложил целое семейство алгоритмов, пригодных для решения вычислительно сложных математических задач на квантовом компьютере. В первую очередь — это задача разложения на простые множители. Для достаточно больших чисел классический компьютер будет искать решения столетиями — на чем и основаны криптографические алгоритмы вроде RSA. Но мощный квантовый компьютер при помощи алгоритма Шора справится с этой проблемой за короткий срок. Хотя в 1994 году даже намеков на такие компьютеры не было, проблема захватила умы хакеров, физиков и, конечно, журналистов. Шор вспоминает, что когда он впервые выступил со своей идеей на конференции в 1994 году, он еще не решил проблему разложения на множители окончательно — финальная версия его научной работы вышла лишь в 1995 году. Но уже через 5 дней после выступления люди уверенно рассказывали друг другу, что проблема факторизации разрешена.

Стартапы

Многие годы о квантовой угрозе говорили как о крайне отдаленном сценарии, поскольку число квантовых битов (кубитов), необходимых для взлома криптографии, исчисляется тысячами и миллионами, а в экспериментальных квантовых компьютерах их были единицы. Ситуация изменилась в 2007 году, когда канадская компания D-Wave Systems продемонстрировала «первый коммерческий квантовый компьютер» с 28 кубитами и пообещала уже к концу 2008 года масштабировать свою разработку до 1024 кубитов. Компания прогнозировала, что в 2009 году можно будет арендовать квантовый компьютер для вычислений через облако, применяя его для анализа рисков в страховом деле, для моделирования в химии и материаловедении, а также для «правительственных и военных нужд». К 2009 году D-Wave планировала и достичь «квантового превосходства», когда квантовый компьютер решает задачу быстрее классического.

Разбираться с заявлениями компании экспертному сообществу пришлось много лет. Принцип квантового отжига (Quantum Annealing), применяемый в системах D-Wave, даже отказывались считать квантовым эффектом, и его наличие, с большими оговорками, удалось доказать только в 2013 году. А величину (и вообще наличие) квантового превосходства обсуждали и опровергали еще дольше. В любом случае, системы D-Wave не могут выполнять алгоритмы Шора и Гровера, для решения задач криптоанализа они непригодны. Компания по сей день строит компьютеры (вернее, «квантовые отжигатели») со все большим числом кубитов, но их практическое применение очень ограничено.

Киберагентства

Если Агентство национальной безопасности США выпускает предупреждения и советы по какой-то проблеме, значит, проблема эта серьезная. Именно поэтому рекомендация АНБ, выпущенная в 2015 году и мотивирующая компании и госучреждения начать переход на квантово-устойчивое шифрование, была воспринята как сигнал, что до появления практически применимых квантовых компьютеров осталось мало времени. Это стало сюрпризом — на тот момент самым большим числом, которое удалось разложить на множители при помощи алгоритма Шора было число 21. Поэтому предупреждение АНБ породило ряд спекуляций на тему того, что известно агентству про квантовые компьютеры и чего не знают все остальные.

Сейчас, почти десять лет спустя, можно с достаточной уверенностью сказать, что сотрудники АНБ в своих пояснениях, выпущенных на полгода позже, были вполне искренни — они просто хотели получить запас времени. Ведь закупленное для госорганов оборудование служит десятилетиями. Тогда же было объявлено о начале конкурса для создания стандартизованного набора новых алгоритмов, устойчивых к квантовому взлому. Уже в 2024 году стандарт на такие алгоритмы был принят.

Интернет-гиганты

Квантовыми вычислениями интересуются (и инвестируют в них) многие крупные IT-компании, в том числе Google и IBM. В лабораториях IBM на исходе XX века создали первый работоспособный квантовый компьютер с двумя кубитами, но уже исследователи Google в 2019 году объявили, что смогли достичь квантового превосходства. Их экспериментальный компьютер Sycamore с 53 кубитами смог за 200 секунд решить задачу, которую классический суперкомпьютер решал бы 10 тысяч лет. Впрочем, конкуренты из IBM не согласились с данным заявлением. Во-первых, решить удалось чисто синтетическую задачу, специально созданную для квантового компьютера и не имеющую ни аналогов для классического компьютера, ни практического применения. На суперкомпьютере пришлось бы просто имитировать квантовый, что не очень полезно и, конечно, очень медленно. Также в IBM заявили, что при достаточном дисковом пространстве классический компьютер способен решить данную задачу с большей точностью и за достаточно короткий срок: максимум за 2,5 дня.

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

Правительства

Эксперты по информационной безопасности, включая тех же сотрудников АНБ, неоднократно повторяли, что даже в отсутствие практически применимого квантового компьютера существует квантовая угроза. Обеспеченные ресурсами противники могут сохранять зашифрованную копию всего интересующего их трафика, чтобы расшифровать его потом, когда квантовый компьютер появится. Такая атака, имеющая название Store Now, Decrypt Later (SNDL), часто упоминается в контексте квантовой гонки, но в 2022 году правительство США создало определенный ажиотаж, заявив, что против США уже ведутся атаки SDNL. Эксперты из компании QuSecure, занимающейся вопросами «постквантовой» безопасности, также называли это «распространенной практикой» в статье, озаглавленной «Квантовый апокалипсис».

Тем временем в Белом доме придумали аббревиатуру CRQC (Cryptanalytically Relevant Quantum Computer) и велели американским ведомствам перейти на постквантовые алгоритмы шифрования не позже 2035 года.

Энтузиасты

Квантовые компьютеры — сложные и штучные физические приборы, часто требующие экстремального охлаждения. Поэтому небольшие фирмы и одиночки мало что могут сделать в квантовой гонке. Но некоторые все же хотят. В 2023 году определенную шумиху создали заявления исследователя по имени Эд Герк, основавшего компанию Planalto Research. Она, по заявлению учредителя, смогла провести квантовые вычисления «на коммерческом Linux-десктопе» с капитальными затратами менее тысячи долларов и без применения криогеники. При этом автор якобы смог взломать 2048-битный ключ алгоритма RSA. Что интересно, для этого якобы использовался собственный алгоритм, а не алгоритм Шора. Криптографы и разработчики квантовых компьютеров неоднократно требовали предоставить доказательства этого достижения, но получили только несколько отговорок. Научная работа Герка, впрочем, была опубликована, но, по оценкам экспертов, в ней есть серьезные методические проблемы и даже домыслы.

И конечно, пресса

Исследование ученых Шанхайского университета, которое напрямую увязывает квантовые компьютеры и взлом шифров, было опубликовано в Китае в сентябре 2024 года, однако обрело мировую известность после ноябрьской публикации в South China Morning Post. В исполнении этого издания ученые уже успешно взломали «шифрование военного уровня», и этот заголовок бездумно растиражировали другие СМИ.

Авторы исследования действительно нацелились конкретно на шифрование, но решили на практике гораздо более скромную задачу — взломали 50-битные шифры, родственные AES (Present, Gift-64 и Rectangle). Что интересно, они воспользовались при этом одной из свежих моделей уже знакомого нам D-Wave, но компенсировали его ограничения по сравнению с полноценным квантовым компьютером при помощи классических алгоритмов. В этом исследовании есть научная новизна, но его практическая применимость для взлома реальных шифров — под большим вопросом. Кроме дефицита кубитов препятствием будет невероятно долгий период подготовительных «классических» вычислений для реальных 128- и 256-битных ключей.

Это был не первый случай, когда китайские исследователи заявляли об успехах во взломе шифрования, но первое такое заявление в 2022 году не получило широкой известности.

Интернет-гиганты (да, опять)

Новый раунд спекуляций запустил недавний анонс Google, посвященный чипу Willow. Авторы утверждают, что в чипе удалось решить одну из ключевых проблем масштабирования квантовых вычислений — коррекцию ошибок. Дело в том, что считать состояние кубита без ошибок и не нарушив квантовой сцепленности с другими кубитами очень сложно, поэтому вычисления часто запускают по многу раз, а также соединяют многочисленные «шумные» физические кубиты в один «идеальный» логический. Несмотря на все это, при увеличении числа кубитов ошибки экспоненциально нарастают, делая систему все более хрупкой. Новый чип демонстрирует обратное поведение — с увеличением числа кубитов ошибок становится меньше.

У Willow 105 физических кубитов. Разумеется, этого совершенно недостаточно для взлома современных шифров. По оценке самих сотрудников Google, их компьютеру потребовались бы миллионы кубитов, чтобы стать CRQC.

Но такие мелочи не помешали другим исследователям начать обратный отсчет до смерти современной криптографии. Так, в университете Кента подсчитали, что успехи квантовых вычислений потребуют остановить сеть Bitcoin на 300 дней, чтобы обновить ее алгоритмы для квантовой устойчивости.

Добро пожаловать в реальность

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