2015-05-10
506
Рассмотрим кривую
E 7(2,6): Y2 = Х3 + 2Х + 6 (mod 7). (11)
Проверим условие (10):
4 • 23 + 27 • 62 = 4 • 1 + 6 • 1 = 3 ≠ 0 (mod 7).
Данная кривая несингулярна.
Найдем какую-нибудь (случайную) точку. Пусть x = 5. Тогда
Y 2 = 5 3 + 2 • 5 + 6 = 6 + 3 + 6 = 1 (mod 7)
и у = 1 (mod 7) или у = - 1 = 6 (mod 7). Мы нашли сразу две точки: (5,1) и (5,6). Найдем еще пару точек путем вычисления композиции. Вначале найдем [2](5,1). Используя (8), (6) и (7), вычисляем
Мы получили [2](5,1) = (4,6) (можно убедиться, что полученная точка лежит на кривой, подставив ее координаты в уравнение (10)). Найдем еще одну точку [3](5,1) = (5,1) + (4,6). Используя (5),(6) и (7), вычисляем
х 3 = 22 – 5 – 4 = 2 (mod 7),
у 3 = 2 · (5 – 2) – 1 = 2 · 3 – 1 = 5 (mod 7).
Мы получили [3](5,1) = (2,5). Итак, мы нашли четыре точки.
Цифровая подпись на эллиптической кривой (ГОСТ Р34.10‑2001)
Данный метод полностью аналогичен описанному ранее методу ГОСТ Р34.10-94, но возведение в степень заменяется операцией композиции на кривой.
Для сообщества пользователей выбирается общая эллиптическая кривая Ep (a, b) и точка G на ней, такая, что G, [2]G, [3]G,..., [ q ]G суть все различные точки множества Ep (a, b), и q = #Ер (а, b), причем [ q ]G = О.
Число точек на кривой, при надлежащем выборе параметров р, а и b, может быть простым числом, #Ер (а, b)= q. В этом случае любая точка (кроме О)является генератором всего множества точек. Длина числа q берется равной 256 бит.
Каждый пользователь U выбирает случайное число хU (секретный ключ), 0 < хU < q, и вычисляет точку на кривой YU = [ хU ]G (открытый ключ). Параметры кривой и список открытых ключей передаются всем пользователям.
Чтобы подписать сообщение m пользователь А делает следующее:
1) вычисляет значение хеш-функции сообщения h = h(m);
2) выбирает случайно число k, 0 < k < q;
3) вычисляет P = [k]G = (x, у);
4) вычисляет r = х mod q (при r = 0 возвращается к шагу 2);
5) вычисляет s = (k h + r xА) mod q (при s = 0 возвращается к шагу 2);
6) подписывает сообщение парой чисел (r, s).
Для проверки подписанного сообщения (m; r, s) любой пользователь, знающий открытый ключ YA, делает следующее:
1) вычисляет h = h(m);
2) убеждается, что 0 < r, s < q;
3) вычисляет u1 = s · h-1 mod q и u2 = -r · h-l mod q;
4) вычисляет композицию точек на кривой P = [u1]G + [u2]YA = (х, у) и если Р = О, отвергает подпись;
5) если х mod q = r, принимает подпись, в противном случае отвергает ее.
