Скалярное умножение точки

Скалярное умножение точки — это операция в эллиптической криптографии, заключающаяся в многократном сложении одной и той же точки эллиптической кривой с самой собой. Результатом операции является другая точка на той же кривой. Скалярное умножение является ключевым вычислительным примитивом, лежащим в основе таких криптографических схем, как алгоритм Диффи — Хеллмана на эллиптических кривых (ECDH) и алгоритм цифровой подписи на эллиптических кривых (ECDSA). Операция определяется как \( k \cdot P = P + P + \dots + P \) (k раз), где \( k \) — целое число (скаляр), а \( P \) — точка на кривой.

Математическое определение

Пусть \( E \) — эллиптическая кривая, заданная над конечным полем \( \mathbb{F}_q \), и \( P \in E(\mathbb{F}_q) \) — точка на этой кривой. Скалярное умножение точки \( P \) на целое число \( k \) (скаляр) определяется следующим образом:

• Если \( k = 0 \), то \( 0 \cdot P = \mathcal{O} \), где \( \mathcal{O} \) — точка на бесконечности (нейтральный элемент группы).
• Если \( k > 0 \), то \( k \cdot P = \underbrace{P + P + \dots + P}_{k \text{ раз}} \).
• Если \( k < 0 \), то \( k \cdot P = (-k) \cdot (-P) \), где \( -P \) — точка, обратная к \( P \) относительно сложения.

Операция сложения точек на эллиптической кривой является групповой операцией, поэтому скалярное умножение является аналогом возведения в степень в мультипликативной группе конечного поля. В криптографии скаляр \( k \) обычно является секретным ключом, а точка \( P \) — базовой точкой (генератором) циклической подгруппы.

Алгоритмы вычисления

Прямое вычисление скалярного умножения путём последовательного сложения \( k \) раз является неэффективным при больших \( k \) (например, порядка \( 2^{256} \)). Для практического применения используются алгоритмы, основанные на двоичном представлении скаляра.

Метод «двойного и сложения» (Double-and-Add)

Этот алгоритм является аналогом бинарного возведения в степень. Он обрабатывает биты скаляра \( k \) от старшего к младшему (или наоборот) и использует две операции: удвоение точки (2·P) и сложение точек (P + Q).

Пример для \( k = 13 \) (двоичное представление: 1101):

1. Начальное значение: \( Q = \mathcal{O} \).
2. Бит 1 (старший): \( Q = 2 \cdot Q = \mathcal{O} \), затем \( Q = Q + P = P \).
3. Бит 1: \( Q = 2 \cdot Q = 2P \), затем \( Q = Q + P = 3P \).
4. Бит 0: \( Q = 2 \cdot Q = 6P \).
5. Бит 1: \( Q = 2 \cdot Q = 12P \), затем \( Q = Q + P = 13P \).

Алгоритм выполняет \( \log_2(k) \) удвоений и в среднем \( \frac{1}{2} \log_2(k) \) сложений. Для 256-битного скаляра требуется около 256 удвоений и 128 сложений, что значительно быстрее, чем \( 2^{256} \) операций.

Метод Монтгомери (Montgomery Ladder)

Этот метод, предложенный Питером Монтгомери в 1987 году, устойчив к атакам по побочным каналам (SPA — Simple Power Analysis). В отличие от метода «двойного и сложения», который выполняет разные операции в зависимости от бита (сложение или только удвоение), лестница Монтгомери выполняет одинаковое количество операций для каждого бита: одно удвоение и одно сложение. Это делает время выполнения и потребляемую мощность независимыми от значения скаляра.

Алгоритм использует две переменные \( R_0 \) и \( R_1 \), которые всегда удовлетворяют соотношению \( R_1 = R_0 + P \). На каждом шаге в зависимости от бита \( k_i \) выполняется:

• Если \( k_i = 0 \): \( R_0 = 2 \cdot R_0 \), \( R_1 = R_0 + R_1 \).
• Если \( k_i = 1 \): \( R_1 = 2 \cdot R_1 \), \( R_0 = R_0 + R_1 \).

После обработки всех битов \( R_0 = k \cdot P \).

Алгоритм с окном (Window Method)

Для ускорения вычислений используется предварительное вычисление таблицы небольших кратных точек. Например, для окна шириной \( w \) бит предварительно вычисляются \( 2^w \) значений: \( 0, P, 2P, \dots, (2^w - 1)P \). Затем скаляр разбивается на блоки по \( w \) бит, и для каждого блока выполняется умножение на соответствующее значение из таблицы. Этот метод сокращает количество сложений, но увеличивает требования к памяти.

Применение в криптографии

Алгоритм Диффи — Хеллмана на эллиптических кривых (ECDH)

ECDH используется для установления общего секретного ключа между двумя сторонами по незащищённому каналу. Протокол основан на вычислительной сложности задачи дискретного логарифмирования на эллиптической кривой (ECDLP).

1. Стороны договариваются о параметрах кривой и базовой точке \( G \).
2. Алиса генерирует секретный скаляр \( a \) и вычисляет открытый ключ \( A = a \cdot G \).
3. Боб генерирует секретный скаляр \( b \) и вычисляет открытый ключ \( B = b \cdot G \).
4. Алиса вычисляет общий секрет \( S = a \cdot B = a \cdot (b \cdot G) = (ab) \cdot G \).
5. Боб вычисляет общий секрет \( S = b \cdot A = b \cdot (a \cdot G) = (ab) \cdot G \).

Без знания \( a \) или \( b \) злоумышленник не может вычислить \( S \), так как для этого требуется решить ECDLP.

Алгоритм цифровой подписи на эллиптических кривых (ECDSA)

ECDSA используется для аутентификации и обеспечения целостности данных. Подпись создаётся с использованием секретного ключа, а проверяется с помощью открытого.

1. Генерация ключей: Выбирается секретный скаляр \( d \), открытый ключ \( Q = d \cdot G \).
2. Создание подписи: Для сообщения \( m \) выбирается случайное число \( k \). Вычисляется точка \( (x_1, y_1) = k \cdot G \). Значение \( r = x_1 \mod n \) (где \( n \) — порядок подгруппы). Вычисляется \( s = k^{-1} \cdot (H(m) + d \cdot r) \mod n \). Подпись — пара \( (r, s) \).
3. Проверка подписи: Вычисляется \( w = s^{-1} \mod n \), \( u_1 = H(m) \cdot w \mod n \), \( u_2 = r \cdot w \mod n \). Вычисляется точка \( (x_1, y_1) = u_1 \cdot G + u_2 \cdot Q \). Подпись считается верной, если \( x_1 \equiv r \pmod{n} \).

Другие применения

• Схемы шифрования на эллиптических кривых (ECIES): Гибридная схема шифрования, использующая ECDH для генерации ключа и симметричное шифрование для данных.
• Слепые подписи (Blind Signatures): Используются в системах электронного голосования и анонимных платежах.
• Подписи с нулевым разглашением (Zero-Knowledge Proofs): Например, в протоколах доказательства знания дискретного логарифма.

Криптостойкость и безопасность

Безопасность скалярного умножения основана на сложности задачи дискретного логарифмирования на эллиптической кривой (ECDLP). Для кривой с порядком примерно \( 2^{256} \) лучшие известные атаки (например, метод Полларда — Ро) требуют около \( 2^{128} \) операций, что считается вычислительно неосуществимым.

Однако практическая безопасность зависит от корректной реализации:

• Атаки по побочным каналам (Side-Channel Attacks): Измерение времени выполнения, потребляемой мощности или электромагнитного излучения может раскрыть биты скаляра. Для защиты используются методы, такие как лестница Монтгомери, постоянное время выполнения и маскирование.
• Атаки с внедрением ошибок (Fault Attacks): Внесение временных сбоев в вычисления может привести к получению неверного результата, который может раскрыть секретный ключ.
• Кривые с низкой криптостойкостью: Использование кривых с небольшим порядком или с аномальными свойствами (например, supersingular curves) может сделать ECDLP тривиальной. Поэтому в стандартах (ГОСТ Р 34.10-2012, NIST P-256, Curve25519) используются строго определённые кривые.

Особенности в российских стандартах

В Российской Федерации криптографические алгоритмы на эллиптических кривых регламентируются стандартом ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи». Стандарт определяет использование эллиптических кривых над полем характеристики \( p \) (простые поля) и двоичные поля. В стандарте заданы конкретные параметры кривых (например, кривая с параметрами, определёнными в приложении А), и скалярное умножение является основной операцией при вычислении открытого ключа и проверке подписи.

Источники

1. ГОСТ Р 34.10-2012 «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».
2. Hankerson, D., Menezes, A., Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer.
3. Montgomery, P. L. (1987). «Speeding the Pollard and Elliptic Curve Methods of Factorization». Mathematics of Computation, 48(177), 243–264.
4. Koblitz, N. (1987). «Elliptic curve cryptosystems». Mathematics of Computation, 48(177), 203–209.
5. Miller, V. S. (1985). «Use of Elliptic Curves in Cryptography». Advances in Cryptology — CRYPTO '85.