Развенчан слух, что Китай взломал современную криптографию с помощью квантового компьютера

В октябре 2024 года мировые СМИ стали распространять пугающие новости о том, что китайским учёным якобы удалось взломать современные криптографические шифры военного применения с помощью квантового компьютера D-Wave Advantage (на фото вверху).

Эти новости основаны не на пустых словах, а на научной статье от группы исследователей под руководством д-ра Ван Чао (Wang Chao) из Шанхайского университета. Статья опубликована в сентябре 2024 года в журнале Chinese Journal of Computers. Авторы использовали D-Wave Advantage для успешной атаки на три алгоритма — Present, Gift-64 и Rectangle, которые являются критически важными для расширенного стандарта шифрования (AES), используемого для защиты данных в правительственном, военном и финансовом секторах.

Западные эксперты по криптографии изучили статью и оценили достижения китайских коллег.

Авторы научной статьи отмечают, что их успех впервые выявил «реальную и существенную угрозу» взлома вышеперечисленных шифров.

Угроза может распространиться и на AES-256 — шифр, который считался абсолютно безопасным. Исследователи заявили, что им не удалось взломать AES-256, но они подошли к этому «ближе, чем когда-либо прежде».

Квантовый отжиг

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

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

Пример расписания отжига двух функций, источник

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

128-кубитный сверхпроводящий адиабатический процессор D-Wave Systems для квантового отжига, источник

Криптография в безопасности

Алгоритмы Present, Gift-64 и Rectangle используют структуру SP-сети (Substitution-Permutation Network, SPN), которая является частью стандарта AES. Но все три — легковесные блочные шифры с ограниченной сферой применения во встроенных системах с ограниченными вычислительными возможностями.

Исследователи из Шанхайского университета предложили новую вычислительную архитектуру для симметричного криптоанализа: Quantum Annealing-Classical Mixed Cryptanalysis (QuCMC), которая сочетает алгоритм квантового отжига с традиционными математическими методами.

Цитата из научной статьи:

«Используя архитектуру QuCMC, мы сначала применили свойство деления для описания правил распространения линейных и нелинейных слоёв в алгоритмах симметричных шифров со структурой SPN.

Затем задачи поиска отличителя структуры SPN были преобразованы в задачи смешанного целочисленного линейного программирования (MILP). Эти MILP-модели были преобразованы в D-Wave ограниченные квадратичные модели (CQM), использующие эффект квантового туннелирования, вызванный квантовыми флуктуациями, для выхода из локальных минимумов и достижения оптимального решения, соответствующего интегральному отличителю (integral distinguisher) для атакуемых алгоритмов шифрования. Эксперименты, провед`нные с использованием квантового компьютера D-Wave Advantage, позволили успешно осуществить атаки на три репрезентативных алгоритма структуры SPN: PRESENT, GIFT-64 и RECTANGLE, и успешно проведён поиск интегральных отличителей до 9 раунда. Результаты экспериментов показывают, что алгоритм квантового отжига превосходит традиционные эвристические алгоритмы глобальной оптимизации, такие как имитационный отжиг, по способности избегать локальных минимумов и по времени решения. Это первая практическая атака на несколько полномасштабных алгоритмов симметричных шифров со структурой SPN с использованием реального квантового компьютера.

Кроме того, это первый случай, когда атаки квантовых вычислений на несколько алгоритмов симметричного шифра со структурой SPN достигли производительности традиционных математических методов».

Реферат научной статьи (abstract) на английском

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

«Это интригующее исследование, но оно не вызовет квантовый апокалипсис прямо сейчас, — считает Авеста Ходжати (Avesta Hojjati), глава отдела исследований и разработок компании DigiCert. — Хотя здесь демонстрируется потенциальная угроза квантовых вычислений для классического шифрования, но атака проведена на 22-битные ключи».

22-битные ключи представляют собой строку символов с 2²² (4 194 304) возможных комбинаций, что намного меньше, чем в 2048- и 4096-битных ключах, широко используемых сегодня.

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