---

Ця властивість теж дає змогу легко побудувати ефективний алгоритм перевірки примітивності многочленів.

В алгоритмі з 6.11 обидва ці алгоритми використовуються сумісно. Розклади на прості множ­ники чисел вигляду 2^т-1, необхідні для перевірки примітивності многочленів, наведено в табли­цях [13].

Незвідний над полем GF(2) многочлен f(t) має т різних коренів у полі GF(2^m). Знайти один із цих коренів можна наступним чином.

Нехай deg() позначає степінь многочлена, що міститься в дужках.

1. Приймають g(t) = f(t).

2. Доки deg(g)> 1, виконують наступні дії:

   1. Обирають одночлен d(t) = ut з випадковим коефіцієнтом иє GF(2^m);

   2. Виконують т-1 раз обчислення d(t) <- (d(t)²+ ut) mod g (f).

   3. Обчислюють найбільший спільний дільник h(t) многочленів g(f) і d(t). Якщо deg (ft) = 0 або deg (ft) = deg (g), то переходять до кроку 2.1. Якщо 2deg(ft) > deg(g), то g(t) <- g(t)/h(t}, інакше приймають g(f) = ft(f). Переходять до кроку 2.1.

3. Маємо двочлен вигляду g-t + g_Q. Тоді шуканий корінь дорівнює g_og"J •

Основне поле можна задавати поліноміальними базисами з різними примітивними многочле­нами або оптимальним нормальним базисом. Тому при реалізації цього стандарту може виникнути потреба переходити від одного базису до іншого.

Нехай скінченне поле задано базисом В₁₍ якому відповідає многочлен p^(t) (примітивний много­член у разі поліноміального базису або нормальний многочлен у разі оптимального нормального базису) та базисом В₂, якому відповідає многочлен р₂(0 (примітивний многочлен у разі поліно­міального базису або нормальний многочлен у разі оптимального нормального базису). Для пере­ходу від базису до базису В₂ обчислюють корінь и многочлена p-i(f) в базисі В₂, а потім в базисі В₂ обчислюють елементи и_к= и^к, 0 < к < т- 1, якщо базис В₁ поліноміальний, або елементи и_к= и², 0 < к < т- 1, якщо базис В_д оптимальний нормальний. З цих елементів будують матрицю U. що складається з їх розкладів у базисі В₂:

Ця матриця є матриця переходу від базису В_} до базису В₂, а обернена матриця LT¹ є мат­риця переходу від базису В₂ до базису В_1; тобто елемент поля в базисі В_} (позначимо його х) та базисі В₂ (позначимо його у) пов’язані співвідношенням

у= xU, x = yU~

Еліптична крива над скінченним полем GF(2^m) є множина пар (х,у) елементів цього скінчен­ного поля, що задовольняють афінне рівняння еліптичної кривої в нормальній формі Вейєршт- расса

у² + ху = х³ + Ах²+ В,

де A, Be GF(2^m), В* 0, разом із приєднаною нескінченно віддаленою точкою О. Пара (х, у) еле­ментів основного поля називається афінними координатами точки еліптичної кривої. Нескінченно віддалена точка О не має афінних координат. Елементи (А, В) основного поля називаються коефі­цієнтами рівняння еліптичної кривої. Координати точки Р еліптичної кривої позначають (х_Р, у_Р). Число точок еліптичної кривої (враховуючи і нескінченно віддалену точку) називається порядком еліптичної кривої.

Поряд з афінним зображенням еліптичних кривих і точок на них відомі проективні зображення еліптичних кривих і точок на них декількох типів. Класичне проективне рівняння Вейєрштрасса має вигляд:

y²z + xyz = х³ + A x²z + Bz³,

а точками проективної еліптичної кривої є трійки елементів основного поля (x:y:z), що задо­вольняють це рівняння, причому хоча б одна з цих координат відмінна від нуля. Використання двокрапки у запису проективних координат позначає, що трійки координат, отримані одна з Іншої множенням на ненульовий елемент основного поля, відповідають тій самій проективній точці еліп­тичної кривої (і також задовольняють проективне рівняння Вейєрштрасса). У проективному зобра­женні нескінченно віддалена точка має координати (0:1:0). Для переходу від афінних координат до проективних використовуються співвідношення:

(х,у)^ (х:у: 1);

О ->(0:1:0).

Для переходу від проективних координат до афінних використовуються співвідношення:

якщо z = 0, то (x:y:z)—> О;

якщо z* 0, то (x:y:z) -> (xz^-1,yz^-1).

Перехід до проективних координат часто дає змогу підвищити ефективність обчислень у групі точок еліптичної кривої [14].

Точки еліптичної кривої утворюють скінченну абелеву групу відносно операції додавання точок. Правила виконання цієї операції наведено в наступному розділі. Сума точок Р і Q еліптич­ної кривої позначається P + Q, при цьому Р + Q = Q + Р. Нейтральним (або нульовим) елементом цієї групи є нескінченно віддалена точка О: для будь-якої точки Р еліптичної кривої виконується Р+О =О + Р. Точка (-Р), така, що (-Р) + Р = Р + (-Р) = О, називається точкою, протилежною для точки Р, її координати виражаються через координати точки Р таким чином: х__Р= х_Р, у__Р= х_Р+ у_Р. Точка 2Р-Р+ Р називається подвоєнням точки Р. Існує єдина точка порядку два, Р = (0,>/в). Сума k точок Р, k — натуральне число, позначається кР, операція обчислення цієї суми називається

множенням точки Р на натуральне число к. За означенням 0Р=О, (-к)Р = к(-Р), тому можна го­ворити про множення точки на довільне ціле число. Множення точки на ціле число — основна криптографічна операція, яка використовується у цьому стандарті. Еліптична крива з даним коефі­цієнтом В*0 ізоморфна у полі непарного степеня т або еліптичній кривій з коефіцієнтами (0, В), або еліптичній кривій з коефіцієнтами (1,В). Тому в стандарті прийнято, що коефіцієнті дорівнює або 0, або 1

Нехай п — просте непарне число, що ділить порядок еліптичної кривої. Точка Р * 0 еліптич­ної кривої називається базовою, якщо її порядок дорівнює п, тобто пР = О і кР* О, 0 < к< п. Просте число п називається порядком базової точки. Порядок базової точки повинен задовольняти умову Менезеса-Окамото-Венстона [16,17], а саме, 2^т**1 mod п для к=1 L_M0V, де L_MOV—деяке гра­

ничне значення. Для скінченних полів, наведених у таблицях 1 і 2, достатньо прийняти L_WOy = 32. Виконання цієї умови забезпечує високу криптографічну стійкість алгоритму обчислення й пере­вірки цифрового підпису, визначеного цим стандартом. Точки еліптичної кривої вигляду кР, к - 0 л-1, утворюють циклічну підгрупу групи точок еліптичної кривої. Ця циклічна підгрупа

є основною математичною структурою, в якій діють криптографічні алгоритми, встановлені в цьому стандарті.

Зображення точки Р еліптичної кривої парою координат (х_Р, у_Р) є надмірним, оскільки коорди­ната у_Р є один з двох розв’язків квадратного рівняння у + х_Ру - х_р+ Ах_р+ В . Якщо точка Р має простий порядок, а степінь поля — непарне число, то наймолодший розряд координати х_Р також надмірний, оскільки у цьому випадку tr(A) = tr(x_P) [15] і наймолодший розряд х_Р легко відновлюється за значенням сліду коефіцієнта А. Ці дві властивості дають змогу зображати точку еліптичної кривої у вигляді одного елемента основного поля. Таке зображення точок еліптичної кривої називається стиском точки.

Нехай Р = (х_р, ур), РїО і Q = (x₀, y_Q), Q*O, P*Q — дві точки еліптичної кривої в афінних координатах. Сума цих точок R~P + Q обчислюється за такими правилами.

Якщо Q = — P, то R = O. Якщо Q*-P, то координати (x_ft, y_R) точки R обчислюються за форму­

лами:

Я

'Ур+Уо^ .Xp + Xq _>

Ур + Уо

Х_Р+ Xq

+ Хр + Xq + А,

Ур⁺Уо ^Xp + XQ

ч

(хр +X_R)+X_R +Ур.

кщо Хр = 0, то 2Р=О. Якщо х_р^0, то координати (x_R,y_R) подвоєної точки R = 2P обчислюють ся за формулами:

2 S

*r =Хр +~г>

Хр

Ун = х²

+ Хр

+ — x_R

+ Xr.

Для множення точки Р*О на велике ціле число можна використовувати способи, цілком анало­гічні тим, що застосуються для піднесення цілого числа до степеня к. Наприклад, якщо t 1

/с = ^/(;2' — двійкове зображення числа к, то точку Q = kP можна обчислити наступним чином: /=о

1. Приймають Q *- О.

2. Для і від t- 1 до 0 обчислюють Q<- 2Q; якщо fc, = 1, то додатково обчислюють Q<— Q + Р.

Як було відзначено вище, підвищити ефективність обчислень у групі точок еліптичної кривої можна за рахунок переходу до проективних координат. Це пов’язане з тим, що при додаванні й подвоєнні точок у проективних координатах не використовується операція обчислення оберне­ного елемента основного поля — найпрацемісткіша операція в скінченному полі.

3. 9 Доведення правильності алгоритму перевіряння цифрового підпису

Основне криптографічне перетворення при обчисленні цифрового підпису виконується над елементом h основного поля, який обчислюється за результатом обчислення функції гешування. Якщо отримане повідомлення ідентичне оригінальному, то під час перевіряння підпису буде обчис­лено точно той самий елемент основного поля. Якщо цифровий підпис прийнято без спотворень, то для перевіряння цифрового підпису буде використана та сама пара цілих чисел (r, s), яка була отримана під час обчислення цифрового підпису. Під час перевіряння цифрового підпису обчис­люють точку еліптичної кривої R = sP + rQ, де Р — базова точка еліптичної кривої, Q=-dP — відкри­тий ключ цифрового підпису, обчислений за базовою точкою Р з використанням особистого ключа цифрового підпису d. Крім того, s = e + rd, де е — одноразовий таємний параметр, який було вико­ристано для обчислення передпідпису (е, Р_в). Тому

R = sP+ rQ = (е + rd)P- rdP = eP + rdP-rdP = eP.

Таким чином, координата x_R точки R = (x_r, y_R) дорівнює F_e, тому у = hx_R= hF_g і після перетво­рення елемента у на ціле число f отримаємо ціле число г, тобто r ~ г, що й доводить правильність алгоритму перевіряння цифрового підпису.

Криптографічна стійкість цифрового підпису базується на дуже великій складності задачі дискретного логарифмування R = eP, Q--dP в циклічній підгрупі групи точок еліптичної кривої, що використовується в цьому стандарті.

ДОДАТОК Г
(рекомендований)

РЕКОМЕНДОВАНІ ЕЛІПТИЧНІ КРИВІ

Для реалізації цього стандарту можна використовувати еліптичні криві, наведені в таблицях Г.1 і Г.2. В поліноміальному базисі зображення коефіцієнта В відповідає рекомендованому при­мітивному многочлену. Символ «/» означає, що написання коефіцієнта В еліптичної кривої або її порядку п розділено на два рядки.

Таблиця Г.1 — Рекомендовані еліптичні криві в поліноміальному базисі

Закінчення таблиці Г.1