dxdt.ru: занимательный интернет-журнал

Где именно в криптосистеме электронной подписи ECDSA “работает” эллиптическая кривая?

Посмотрим, для начала, на значение подписи, которое состоит из двух параметров – (R, S). Здесь R – это координата X точки на используемой эллиптической кривой, а именно, X-координата точки k∘G, где G – точка кривой, называемая генератором (зафиксированный параметр криптосистемы), а k – секретное уникальное значение (ECDSA nonce). Запись k∘G, – “умножение на скаляр”, – означает повторное сложение точек: G⊕G⊕G⊕…⊕G, где G встречается k раз, а “⊕” – обозначает операцию в группе точек кривой, то есть, сложение точек. (Умножение тут лучше было бы записать [k]G, например, но это детали.)

На значение k накладываются различные ограничения, но это всего лишь натуральное число (конечно, так можно сказать про всё, что встречается “в компьютерах”). Структура кривой такова, что есть пары точек с совпадающими X-координатами, но различными Y-координатами. Этот момент нередко используется в атаках на реализации ECDSA. В данном случае – R это именно X-координата.

Эллиптическая кривая непосредственно использована для вычисления одного параметра подписи – R, который, впрочем, сразу “превращается” из точки, как кортежа значений, задаваемых дополнительной структурой уравнения кривой, в единственное число.

Нетрудно заметить, что здесь, в процессе вычисления R, не использовано никаких значений, связанных с подписываемым сообщением или с секретным ключом – эти элементы пока что даже не упоминались. Параметр R служит в качестве опорного значения, необходимого для проверки подписи – к R должно сойтись значение после “невидимых сокращений”, заложенных в уравнение проверки подписи.

Это основная математическая идея ECDSA: базовое уравнение так устроено, что части структуры преобразования, вынесенные наружу в составе публичных значений, сокращаются, если ключ проверки соответствует подписи (и параметрам), но не сокращаются в почих случаях.

Сокращающиеся структуры не видны, а вычислить их, – то есть, обратить, – по открытым значениям и параметрам, сложно. Концептуально это напоминает, например, RSA, где внутри открытого ключа всегда содержится структура, связанная с разложением на простые множители, благодаря которой криптосистема работает. Тут необходимо обратить внимание на то, что, во многих практических реализациях, значение k может вычисляться с использованием и подписываемого сообщения, и секретного ключа – например, так делается в схеме детерминированной ECDSA. Но “классическая” ECDSA такого, вообще говоря, не требует. Это, впрочем, один из самых проблемных моментов реализаций данной криптосистемы – так, если третья сторона знает параметры генератора псевдослучайных чисел, который использовался для получения k, то эта третья сторона без особых трудностей может вычислить секретный ключ по значению подписи и подписанного сообщения (см. ниже).

Итак, эллиптическая кривая, заданная для ECDSA, использовалась для вычисления R. Где ещё встречаются операции с точками? Прежде всего – вычисление открытого ключа. Открытый ключ в ECDSA это точка на кривой, а получается он из секретного значения d путём умножения генератора: Q == d∘G. То есть, d – целое число. Принцип эквивалентен вычислению r. Однако, в отличие от r, открытый ключ Q повсеместно записывают как пару координат (X,Y), но это только способ записи, потому что достаточно сохранять X и один “бит знака” для Y.

Вторая часть подписи ECDSA – параметр s. И значение этого параметра вычисляется уже без использования операций с точками кривой. Уравнение для s следующее:

S == k^(-1)*(H + Rd)

– здесь, кроме уже определённых k, R и d (d – секретный ключ), используется значение H – это и есть подписываемое сообщение (технически, это значение хеш-функции от сообщения).

Все значения в данной формуле – это натуральные числа (даже k^(-1)), а не точки. Поэтому тут использованы другие значки для обозначения операций: “+”, “*”, “^(-1)” – это “обычные” операции сложения, умножения и взятия обратного по умножению. “Обычные” в кавычках по той причине, что вычисления проводятся по модулю некоторого числа. То есть, это привычная арифметика остатков. Положительное число, по модулю которого проводятся операции, это так называемый порядок группы точек кривой. Можно считать, что порядок – это количество доступных для вычислений точек кривой. Порядок обозначают, например, P, а тот факт, что это арифметика остатков “по P” записывают как (mod P). Так что свойства кривой тут участвуют только косвенно. Взятие обратного по умножению – k^(-1) – это нахождение такого числа, которое даст 1 (mod P) при умножении на k. Так как вычисления выполняются (mod q), то k^(-1) тоже будет целым числом. Пример: 4*2 == 1 (mod 7) – так как 8/7 – даст остаток 1. Обратите внимание, что все вычисления дальше – тоже (mod P), но отдельно этот момент упоминаться не будет, так как, для практических целей ECDSA и для простого P, свойства вычислений совпадают с привычными операциями в рациональных числах (кроме сложения точек кривой).

Раз это обычная арифметика, то и по формуле для S нетрудно увидеть, что если известны k, H, R, S, то легко вычислить секретный ключ d – просто перепишем уравнение относительно неизвестной переменной d. Значения H, R, S – публично доступны: первое из них это подписанное сообщение, а два других – сама подпись. Никаких “хитростей” эллиптической кривой тут уже не задействовано, поэтому и никакие особенности арифметики эллиптических кривых конкретно на этом направлении криптосистему не защищают. (Более того, если известно не точное значение, но какие-то дополнительные свойства k, то уравнение S можно превратить в неравенство, составить набор “приближений”, который позволит найти приближённое значение для секретного ключа, чтобы потом быстро подобрать его точно по значению открытого. Но это тема для другой записки.) Итак, при вычислении S операции на эллиптической кривой не используются.

Проверка подписи в ECDSA использует следующее уравнение:

C == (H*S^(-1))∘G ⊕ (R*S^(-1))∘Q

– обратите внимание, что тут разные обозначения операций, чтобы можно было различить операции с точками и операции с числами; а значение Q, – открытый ключ, – это d∘G. Работает вся эта схема потому, что, из-за свойств сложения в группе точек кривой, можно операцию сложения точек ⊕ спустить в натуральные числа, вот как: 3∘G ⊕ 5∘G == (G⊕G⊕G)⊕(G⊕G⊕G⊕G⊕G) == 8∘G. При этом, если подставить вместо S формулу вычисления S (см. выше), то в правой части сократится всё, кроме k. Получим, что C == k∘G, а X-координата C должна совпасть с R, если, конечно, подпись верна и вычисления верны. И здесь эллиптическая кривая используется непосредственно для вычисления итогового значения, а именно – умножение на скаляры точек G (генератор) и Q (открытый ключ), сложение получившихся точек.

Адрес записки: https://dxdt.ru/2024/04/25/12884/