11. Вычисление кратного kQ заданной точки q

Поскольку, арифметика эллиптических кривых не содержит прямых

формул для вычисления кратного kQ для заданной точки Q( , ), то эту

операцию выполняют с использованием операций сложения, вычитания и

удвоения точки. Для этого надо представить число k в двоичной системе

исчисления k = ... , ∈ {0, 1}, потом вычислить все точки 2Q, 4Q,

... , · Q и подсчитать сумму тех точек · Q, для которых = 1.

Пример. Пусть k = 13. В двоичной системе k = , тогда,

13Q = 8Q + 4Q + Q. Эту же точку можно вычислить как 16Q − 2Q − Q.

Приведем здесь фрагмент процедуры вычисления кратного kP точки

P , предполагая что процедуры удвоения Double(P) и сложения точек Add-

Points(P,Q) уже определены:

long Mult_k(Point P, long k) {

Point B = P ;

while (k) {

if (k%2 == 0)

{ k/ = 2; B = Double(B);}

else

{ k − −; B = AddPoints(B, P);}

}

return B;

}

12. Шифрование сообщений с использованием эллиптических кривых

Рассмотрим самый простой подход к шифрованию/дешифрованию

секретных сообщений с использованием эллиптических кривых. Задача

состоит в том, чтобы зашифровать сообщение М, которое может быть

представлено в виде точки на эллиптической кривой (x, y). Как и в

случае обмена ключом, в системе шифрования/дешифрования в качестве

параметров рассматривается эллиптическая кривая (a, b) и базовая точка

G на ней. Участник B выбирает закрытый ключ , представляющий собой

целое число от 2 до n, где n–порядок точки G и вычисляет открытый ключ

= ·G, являющийся точкой на кривой. Участник А выбирает случайное

целое положительное число k и вычисляет зашифрованное сообщение ,

являющееся парой точек на эллиптической кривой:

= {k · G, Pm + k · PB}.

Чтобы дешифровать сообщение, участник В вычитает из второй точки

произведение первой точки на свой закрытый ключ:

+ k · − · (k · G) = + k · ( · G) − · (k · G) = .

Участник А зашифровал сообщение добавлением к нему k .

Никто не знает значения k , поэтому, хотя и является открытым ключом,

никто не знает k · . Противнику для восстановления сообщения придется

вычислить k , зная G и k · G. Сделать это будет нелегко, т.к. надо

вычислить дискретный логарифм. Получатель также не знает k , но ему

в качестве подсказки посылается k · G. Умножив k · G на свой закрытый

ключ, получатель получит значение, которое было добавлено отправителем

к незашифрованному сообщению. Тем самым получатель, не зная k , но имея

свой закрытый ключ, может восстановить незашифрованное сообщение.

Замечание. Здесь надо еще сказать, как кодировать текстовое

сообщение точками кривой. Для этого сообщение разбивается на отдельные

символы, и каждый символ заменяется его числовым кодом. Можно

использовать какую-нибудь стандартную кодировку типа ASCII или

WIN1251 либо просто перенумеровать все буквы последовательными

цифрами.

Далее надо каждому коду сопоставить какую-нибудь точку на кривой.

Самый простой вариант – это составить таблицу, сопоставив символу с кодом

k координату x точки kG. Однако, лишь половина значений x является,в

среднем, координатами точки ЭК. Поэтому, можно выбрать какое-нибудь

натуральное число k ≥ 2 и выбрать кодом для x любую точку ЭК P(u, v),

для которой x = ⌊u/k⌋ (таких точек будет, в среднем, ⌊k/2⌋).

Тогда, зная координаты (u, v) любой из возможных точек P , можно

восстановить x, вычисляя целую часть от u/k.

Другой вариант состоит в том, чтобы использовать эллиптические

кривые специального вида, например, кривые вида = + a (mod p),

где p ≡ 2(mod 3). Для таких кривых полином z = + a(mod p) является

перестановкой, поэтому каждый элемент 0 ≤ u < p имеет кубический корень

в поле . Тогда, кодовую точку для числа y можно взять равной точке

(x, y), имеющей y в качестве своей ординаты, а x, найденном из уравнения = - a .

Построение электронной цифровой подписи с использованием ЭК

Алгоритм ECDSA (Elliptic Curve Digest Signature Algorithm) принят в

качестве стандартов ANSI X9F1 и IEEE P1363.

Создание ключей:

1. Выбирается эллиптическая кривая (a, b). Число точек на ней должно

делиться на большое простое число n.

2. Выбирается базовая точка G ∈ (a, b) порядка n, n · G = ∞.

3. Выбирается случайное число d ∈ (1, n).

4. Вычисляется Q = d · G.

5. Закрытым ключом является d, открытым ключом - кортеж <

a, b, G, n,Q >.

Создание подписи:

1. Выбирается случайное число k ∈ (1, n).

2. Вычисляется k · G = ( , ) и r = (mod n).

3. Проверяется условие r 0, так как иначе подпись не будет зависеть от

закрытого ключа. Если r = 0, то выбирается другое случайное число

k .

4. Вычисляется (mod n).

5. Вычисляется s = · (Н(M) + d·r) (mod n).

H(M) – хэш-функция от сообщения М.

6. Проверяется условие s 0, так как в этом случае необходимого для

проверки подписи числа (mod n) не существует. Если s = 0, то

выбирается другое случайное число k .

Подписью для сообщения М является пара чисел (r, s).

Проверка подписи:

1. Проверим, что числа r и s принадлежат диапазону чисел (1, n).

В противном случае результат проверки отрицательный, и подпись

отвергается.

2. Вычислить w = (mod n), и H(M),

3. Вычислить = H(M) ·w (mod n), и = r·w (mod n)

4. Вычислить · P + · Q = ( , ), v = (mod n)

Спаривание Вейля-Тейта 112

5. Подпись верна в том и только том случае, когда v = r .

Определение. Полем называется кольцо с единицей, в котором каждый ненулевой элемент обладает обратным . Другими словами, кольцо с единицей является полем, если множество ненулевых элементов образует группу по умножению. Эту группу называют мультипликативной группой поля F и обозначают символом F*.

Пример 1. Полями являются множества рациональных чисел Q, действительных чисел R, комплексных чисел C относительно операций сложения и вычитания.

Пример 2. Кольцо вычетов Z_N по модулю числа N является полем, если N – простое число. Число N называется характеристикой поля.

Пусть K – поле, а f(x) – многочлен, неразложимый в K в произведение многочленов меньшей степени. Такой многочлен называется неприводимым над полем K. Свойство неприводимости существенно зависит от свойств поля K, поскольку если в качестве K взять поле комплексных чисел, то любой многочлен является разложимым в произведение линейных многочленов. Подобно кольцу классу вычетов Z_N можно рассматривать классы эквивалентности по модулю многочлена f(x).

Пример 3. Кольцо вычетов многочленов по модулю неприводимого многочлена f(x) с коэффициентами из поля K образует поле.

Если K – конечное поле, содержащее p элементов (p – простое число), а f(x) – многочлен степени m, то поле вычетов содержит элементов. Такие поля называются полями Галуа в честь выдающегося французского математика Эвариста Галуа, погибшего на дуэли в 20-летнем возрасте, и обозначают символом . В курсе алгебры доказывается, что любое конечное поле является полем Галуа для некоторого основания p и степени m. Еще один важный факт, касающийся полей Галуа, состоит в том, что мультипликативная группа конечного поля K всегда является циклической, т.е. существует порождающий элемент x такой, что любой ненулевой элемент y поля K является степенью x