Атака MOV

Атака MOV — это метод криптоанализа, применяемый для атак на эллиптические кривые, основанный на сведении задачи дискретного логарифмирования в группе точек эллиптической кривой (ECDLP) к задаче дискретного логарифмирования в мультипликативной группе конечного поля, что позволяет использовать для её решения субэкспоненциальные алгоритмы, такие как индекс-калькулус (index calculus). Атака названа по первым буквам фамилий её авторов — Альфреда Менезеса (Alfred Menezes), Т-Ен Окамото (Tatsuaki Okamoto) и Скотта Ванстоуна (Scott Vanstone), которые впервые описали её в 1993 году.

История

До появления атаки MOV криптосистемы на основе эллиптических кривых (ECC) считались устойчивыми к субэкспоненциальным атакам, поскольку для решения ECDLP в общем случае требовались экспоненциальные алгоритмы, такие как ρ-метод Полларда (Pollard's rho). В 1993 году Менезес, Окамото и Ванстоун опубликовали работу, в которой показали, что для некоторых классов эллиптических кривых (так называемых «суперсингулярных» кривых) ECDLP может быть сведена к задаче дискретного логарифмирования в конечном поле, где существуют субэкспоненциальные методы решения. Это открытие существенно повлияло на стандартизацию и практическое применение ECC, заставив разработчиков избегать уязвимых кривых.

Суть атаки

Математическая основа

Атака MOV использует спаривание Вейля (Weil pairing) или спаривание Тейта (Tate pairing) — билинейные отображения, которые ставят в соответствие паре точек на эллиптической кривой элемент мультипликативной группы конечного поля. Для эллиптической кривой \(E\) над конечным полем \(\mathbb{F}_q\) и простого числа \(n\), делящего порядок группы точек кривой, спаривание Вейля \(e_n: E[n] \times E[n] \to \mu_n\) отображает пару точек \(n\)-кручения в корень \(n\)-й степени из единицы в расширении поля \(\mathbb{F}_{q^k}\), где \(k\) — степень вложения (embedding degree).

Алгоритм атаки

Пусть даны две точки \(P\) и \(Q = xP\) на эллиптической кривой, и требуется найти \(x\) (дискретный логарифм). Атака MOV состоит из следующих шагов:

1. Вычисляется спаривание Вейля \(e_n(P, Q) = e_n(P, P)^x\).
2. Вычисляется \(g = e_n(P, P)\).
3. Задача сводится к нахождению \(x\) из уравнения \(g^x = e_n(P, Q)\) в мультипликативной группе поля \(\mathbb{F}_{q^k}\).
4. Для решения полученной задачи дискретного логарифмирования в конечном поле применяются субэкспоненциальные алгоритмы, например, индекс-калькулус.

Условия применимости

Атака MOV эффективна только в том случае, если степень вложения \(k\) достаточно мала (обычно \(k \leq 6\)), чтобы задача дискретного логарифмирования в \(\mathbb{F}_{q^k}\) решалась за приемлемое время. Для суперсингулярных кривых \(k \leq 6\), что делает их уязвимыми. Для обычных (несуперсингулярных) кривых, используемых в современных стандартах, \(k\) велико (например, для кривой secp256k1 \(k \approx 2^{128}\)), что делает атаку MOV непрактичной.

Классификация уязвимых кривых

Суперсингулярные кривые

Эллиптическая кривая над полем \(\mathbb{F}_q\) называется суперсингулярной, если её след Фробениуса \(t\) делится на характеристику поля \(p\) (то есть \(t \equiv 0 \pmod{p}\)). Для таких кривых степень вложения \(k\) мала (обычно \(k \leq 6\)), что позволяет эффективно применять атаку MOV. Суперсингулярные кривые часто использовались в ранних реализациях ECC, но после открытия атаки MOV их применение было ограничено.

Кривые с малым значением степени вложения

Некоторые несуперсингулярные кривые также могут иметь малую степень вложения \(k\), если их порядок делит \(q^k - 1\) для небольшого \(k\). Такие кривые встречаются редко, но их существование учитывается при выборе параметров для криптосистем.

Применение и последствия

Влияние на криптографию

Атака MOV привела к пересмотру критериев выбора эллиптических кривых для криптографических целей. В современных стандартах (например, ГОСТ Р 34.10-2012, NIST P-256, Curve25519) используются кривые с большим значением степени вложения \(k\), что делает атаку MOV неэффективной. Суперсингулярные кривые, напротив, нашли применение в криптографии на спариваниях (pairing-based cryptography), где малая степень вложения является преимуществом для вычисления спариваний.

Примеры уязвимых кривых

• Кривые над полями характеристики 2: многие суперсингулярные кривые над \(\mathbb{F}_{2^m}\) имеют \(k \leq 4\).
• Кривые над полями малой характеристики: например, кривые над \(\mathbb{F}_{3^m}\).
• Кривые с малым порядком группы: некоторые кривые, используемые в учебных примерах или устаревших протоколах.

Критика и ограничения

Атака MOV не является универсальным методом взлома ECC. Её применение ограничено узким классом кривых с малой степенью вложения. Для большинства кривых, используемых в современных криптосистемах, атака MOV требует вычисления спариваний в полях огромного размера, что делает её вычислительно нереализуемой. Кроме того, существуют модификации атаки, такие как атака Фрея-Рюка (Frey-Rück attack), которая использует спаривание Тейта и может быть более эффективной в некоторых случаях.

Интересные факты

• Атака MOV была независимо переоткрыта в 1994 году Герхардом Фреем (Gerhard Frey) и Хансом-Георгом Рюком (Hans-Georg Rück), что привело к появлению термина «атака Фрея-Рюка» как синонима.
• Спаривания, используемые в атаке MOV, легли в основу современной криптографии на спариваниях, которая применяется в протоколах идентификации, шифрования с поиском (searchable encryption) и в системах на основе блокчейна (например, в криптовалюте Ethereum для проверки zk-SNARKs).
• В России стандарт ГОСТ Р 34.10-2012 использует эллиптические кривые, устойчивые к атаке MOV, что подтверждается соответствующими криптографическими сертификациями.

Источники

• Menezes A., Okamoto T., Vanstone S. Reducing elliptic curve logarithms to logarithms in a finite field // IEEE Transactions on Information Theory. — 1993. — Vol. 39, № 5. — P. 1639–1646.
• Frey G., Rück H.-G. A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves // Mathematics of Computation. — 1994. — Vol. 62, № 206. — P. 865–874.
• Hankerson D., Menezes A., Vanstone S. Guide to Elliptic Curve Cryptography. — Springer, 2004. — 311 p.
• ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.