Российские криптографы взломали схему постквантовой подписи pqsigRM

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

Исследователи из лаборатории криптографии компании «Криптонит» (входит в «ИКС Холдинг») первыми провели структурную атаку, которая ставит под сомнение стойкость как оригинальной схемы pqsigRM, так и её улучшенного варианта Enhanced pqsigRM.

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

Разработчики Enhanced pqsigRM попытались обойти этот риск: они модифицировали конструкцию, комбинируя коды Рида — Маллера особым способом, чтобы скрыть их структуру. Но, как выяснилось, скрыть не получилось — российские криптографы смогли восстановить структуру кода и показать, как его можно взломать.

В атаке применяются разные методы, включая произведение кодов Шура — Адамара и алгоритмы для декодирования самих кодов Рида — Маллера. Атака работает для широкого диапазона параметров — в частности, когда выполняется условие: 2r < m – 2. При этом, как отмечают исследователи, на практике часто используют именно такие параметры.

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

Результаты работы были представлены на симпозиуме CTCrypt 2025 в докладе под названием «Эффективная структурная атака на схему постквантовой подписи pqsigRM».