Алгоритм MOV

Алгоритм MOV — это метод сведения задачи дискретного логарифмирования в эллиптической криптографии (ECC) к задаче дискретного логарифмирования в конечном поле, что позволяет использовать для её решения субэкспоненциальные алгоритмы (например, индекс-калькуляции). Алгоритм назван по фамилиям авторов — Альфреда Менезеса, Тацуаки Окамото и Скотта Ванстоуна, опубликовавших работу в 1993 году. Основная идея MOV заключается в использовании спаривания Вейля или спаривания Тейта для переноса задачи из группы точек эллиптической кривой в мультипликативную группу расширенного конечного поля.

История и предпосылки

До появления алгоритма MOV эллиптическая криптография считалась устойчивой к субэкспоненциальным атакам, поскольку для стандартных эллиптических кривых (например, определённых над простыми полями) не было известно эффективных методов решения задачи дискретного логарифмирования (ECDLP). В 1993 году Менезес, Окамото и Ванстоун показали, что для некоторых классов кривых — так называемых суперсингулярных эллиптических кривых — существует редукция к задаче дискретного логарифмирования в конечном поле (DLP), для которой известны субэкспоненциальные алгоритмы (например, решето числового поля). Это открытие существенно повлияло на выбор параметров в криптосистемах на основе эллиптических кривых.

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

Спаривание Вейля

Спаривание Вейля — это билинейное отображение \( e: E[n] \times E[n] \to \mu_n \), где \( E[n] \) — группа точек кручения порядка \( n \) на эллиптической кривой, а \( \mu_n \) — группа корней \( n \)-й степени из единицы в некотором расширении конечного поля. Спаривание обладает следующими свойствами:

• Билинейность: \( e(P+Q, R) = e(P,R) \cdot e(Q,R) \) и \( e(P, Q+R) = e(P,Q) \cdot e(P,R) \).
• Невырожденность: если \( e(P,Q)=1 \) для всех \( Q \in E[n] \), то \( P = \mathcal{O} \) (точка на бесконечности).
• Альтернирование: \( e(P,P)=1 \).

Сведение задачи

Пусть дана эллиптическая кривая \( E \) над конечным полем \( \mathbb{F}_q \) и точки \( P, Q \in E(\mathbb{F}_q) \), где \( Q = kP \). Задача ECDLP заключается в нахождении \( k \). Алгоритм MOV использует спаривание Вейля для отображения этой задачи в мультипликативную группу поля \( \mathbb{F}_{q^m} \), где \( m \) — степень вложения (embedding degree). Для суперсингулярных кривых \( m \) мало (обычно 2, 3, 4 или 6), что делает поле \( \mathbb{F}_{q^m} \) достаточно малым для применения субэкспоненциальных алгоритмов.

Шаги алгоритма:

1. Выбрать случайную точку \( R \in E[n] \), не равную \( \mathcal{O} \).
2. Вычислить \( \alpha = e(P, R) \) и \( \beta = e(Q, R) = e(kP, R) = e(P, R)^k \).
3. Решить задачу дискретного логарифмирования \( \log_{\alpha}(\beta) \) в поле \( \mathbb{F}_{q^m} \) с помощью алгоритма индекс-калькуляции или решета числового поля.
4. Полученное значение \( k \) является решением исходной задачи ECDLP.

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

Алгоритм MOV эффективен только для эллиптических кривых с малым значением степени вложения \( m \). Степень вложения — это наименьшее целое число \( m \), такое что \( n \) делит \( q^m - 1 \), где \( n \) — порядок подгруппы, в которой решается задача. Для суперсингулярных кривых \( m \leq 6 \), что позволяет свести задачу к полю размера \( q^m \), где субэкспоненциальные алгоритмы работают за приемлемое время. Для обычных (не суперсингулярных) кривых, используемых в современных стандартах (например, кривые NIST P-256, Curve25519), степень вложения \( m \) очень велика (порядка \( n \)), что делает редукцию неэффективной.

Классификация кривых по устойчивости к MOV

• Суперсингулярные кривые: степень вложения мала (1, 2, 3, 4, 6). Уязвимы к атаке MOV. Не рекомендуются для использования в криптографии, если не требуется билинейное спаривание (например, в схемах на основе спариваний).
• Обычные кривые с малым m: некоторые кривые с комплексным умножением могут иметь малую степень вложения. Требуют проверки при выборе параметров.
• Кривые с большим m: современные стандартные кривые (например, secp256k1, Curve25519, P-256) имеют степень вложения, равную порядку подгруппы, что делает атаку MOV неосуществимой.

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

Криптоанализ

Алгоритм MOV показал, что не все эллиптические кривые одинаково безопасны. После его публикации стандарты (например, ANSI X9.62, IEEE P1363, ГОСТ Р 34.10-2012) начали включать требования к выбору кривых, исключающие суперсингулярные и кривые с малой степенью вложения. В частности, в ГОСТ Р 34.10-2012 используются кривые, определённые над простыми полями с большим порядком подгруппы, что гарантирует устойчивость к MOV.

Положительное применение

Спаривания, лежащие в основе алгоритма MOV, нашли применение в криптографии на основе спариваний (pairing-based cryptography). Они используются в:

• Схемах идентификации и аутентификации (например, протокол Боне-Франклина).
• Цифровых подписях (например, BLS-подпись).
• Криптосистемах с открытым ключом (например, IBE — шифрование на основе идентификации).

Таким образом, MOV стал не только инструментом атаки, но и фундаментом для новых криптографических примитивов.

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

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

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

• Алгоритм MOV был опубликован в 1993 году на конференции CRYPTO, и его появление вызвало временный скепсис относительно безопасности ECC, однако быстро выяснилось, что большинство практических кривых не подвержены атаке.
• Степень вложения \( m \) для кривой secp256k1 (используемой в биткойне) равна порядку подгруппы, что делает MOV-атаку невозможной.
• В 2000-х годах были найдены кривые с малым \( m \), специально сконструированные для криптографии на основе спариваний (например, кривые Баррето-Наэрига), которые, наоборот, требуют малой степени вложения для эффективной работы.

Источники

• Menezes, A., Okamoto, T., Vanstone, S. A. (1993). "Reducing elliptic curve logarithms to logarithms in a finite field". IEEE Transactions on Information Theory, 39(5), 1639–1646.
• Frey, G., Rück, H. G. (1994). "A remark concerning m-divisibility and the discrete logarithm in the divisor class group of curves". Mathematics of Computation, 62(206), 865–874.
• Koblitz, N., Menezes, A., Vanstone, S. (2000). "The state of elliptic curve cryptography". Designs, Codes and Cryptography, 19(2-3), 173–193.
• Hankerson, D., Menezes, A., Vanstone, S. (2004). "Guide to Elliptic Curve Cryptography". Springer.