Вхідні дані алгоритму: стиснене зображення Рє GF(2m} точки еліптичної кривої, коефіцієнти еліптичної кривої (Д, В).
Результат виконання алгоритму — точка еліптичної кривої Р з координатами (хР, уР).
Алгоритм відновлення точки еліптичної кривої:
Якщо Р = 0 , то приймають хР= 0, ур= В2" = 4в та переходять до кроку 7.
Виділяють крайній правий двійковий розряд k стисненого зображення точки Р = (Рт і,... ,Р0): k = PQ. _
Координату хР точки Р еліптичної кривої приймають рівною хР= (хР т^,...,хР^,хР0) = Р, далі крайній правий розряд приймають рівним Хрі0 = 0. Якщо слід отриманої координати tr(xP)*A, то крайній правий розряд приймають рівним хР0 = 1.
ОбЧИСЛЮЮТЬ елемент W~Xp+AXp+B основного поля.
Розв’язують квадратне рівняння z2+ z = v, v = wXp2, згідно з 6.7.
Якщо слід tr(z) розв’язку z = (zm_1,..., z0) квадратного рівняння дорівнює к, то приймають yP-zxP, інакше приймають yP~(z+ 1)хР.
Результат виконання алгоритму — точка еліптичної кривої Р = (хр, уР).
Перевіряння примітивності многочлена
У цьому підрозділі встановлено алгоритм перевіряння примітивності многочлена f(t) степеня т над скінченним полем GF(2).
Вхідні дані алгоритму: многочлен f(t) = tm+ + ...+ f0, коефіцієнти якого належать до поля
GF(2), т — непарне число.
Результат виконання алгоритму — повідомлення «многочлен примітивний» або повідомлення «многочлен не примітивний».
А
2.1
2.2
2.3
Приймають g(f) = t.
Для / від 1 до
виконують кроки 2.1—2.3:
Обчислюють многочлен g(t)<-g(t)2 mod f(t).
Обчислюють найбільший спільний дільник d(f) многочленів f(t) і g(f) + t.
Якщо d(f) 1, то видають повідомлення «многочлен не примітивний» і припиняють
виконання алгоритму.
З таблиць або за допомогою факторизації визначають прості дільники р, рк числа 2т-1.
Для і від 1 до k виконують кроки 4.1 і 4.2:
2*-1
Обчислюють многочлен = t Рі mod f(f).
Якщо d/(t) = 1, то видають повідомлення «многочлен не примітивний» і припиняють виконання алгоритму.
. Видають повідомлення «многочлен примітивний».
.12 Перевіряння простоти порядку базової точки еліптичної кривої
У цьому підрозділі встановлено алгоритм перевіряння простоти порядку базової точки еліптичної кривої.
Вхідні дані алгоритму: порядок базової точки еліптичної кривої п.
Результат виконання алгоритму— повідомлення «порядок базової точки еліптичної кривої п просте число» або «порядок базової точки еліптичної кривої п складене число».
Алгоритм перевіряння простоти порядку базової точки еліптичної кривої п:
Обчислюють зображення числа п-1 вигляду n-1 =J2k, де / — непарне число.
Для і від 1 до 50 виконують кроки 2.1 — 2.3:
Обчислюють випадкове натуральне число а, 1 < а < п. Для цього:
Обчислюють випадкове ціле число згідно з 6.3.
Якщо а = 0 або <7=1, то переходять до кроку 2.1.1, інакше переходять до кроку 2.2.
Обчислюють ціле число b = a! mod n;
Якщо dr 1 і b * n — 1, то виконують кроки 2.3.1 — 2.3.3:
Приймають/= 1.
Доки /<к-1 і Ь*п— 1, виконують кроки 2.3.2.1 — 2.3.2.3:
Обчислюють b <- b2 mod п.
Якщо Ь= 1, то видають повідомлення «порядок базової точки еліптичної кривої п складене число» і припиняють виконання алгоритму.
Обчислюють/<—/+1.
Якщо b * п - 1, то видають повідомлення «порядок базової точки еліптичної кривої п складене число» і припиняють виконання алгоритму.
Видають повідомлення «порядок базової точки еліптичної кривої п просте число».
Додатково дозволено використовувати будь-який метод, який дає строге математичне доведення простоти порядку базової точки еліптичної кривої л, наприклад, метод сум Якобі або метод еліптичних кривих.
13 Перевіряння виконання умови Менезеса-Окамото-Венстона
У цьому підрозділі встановлено алгоритм перевіряння виконання умови Менезеса-Окамото- Венстона для порядку п базової точки еліптичної кривої.
Вхідні дані алгоритму: порядок п базової точки еліптичної кривої, визначеної над скінченним полем GF(2m).
Результат виконання алгоритму — повідомлення «умова Менезеса-Окамото-Венстона виконана» або повідомлення «умова Менезеса-Окамото-Венстона не виконана».
Алгоритм перевіряння виконання умови Менезеса-Окамото-Венстона:
. Обчислюють ціле число k = 2m mod п.
. Приймають j= 1.
. Для і від 1 до 32 виконують кроки 3.1 —3.2:
Обчислюють нове значення цілого числа j: j jk mod n.
Якщо j=1, то видають повідомлення «умова Менезеса-Окамото-Венстона не виконана» і припиняють виконання алгоритму.
. Видають повідомлення «умова Менезеса-Окамото-Венстона виконана».
ОБЧИСЛЕННЯ ЗАГАЛЬНИХ ПАРАМЕТРІВ ЦИФРОВОГО ПІДПИСУ
Загальні параметри цифрового підпису можуть бути однаковими для довільного числа користувачів цифрового підпису. Цей розділ встановлює правила обчислення загальних параметрів цифрового підпису.
Вибір основного поля
Дозволено задавати основне поле поліноміальним або оптимальним нормальним базисом.
Якщо використовують поліноміальний базис, то основне поле треба вибирати серед полів GF(2m), степені яких наведено в таблиці 1. Поліноміальний базис задають примітивними тричленами або примітивними п'ятичленами. Використання примітивних многочленів, наведених у таблиці 1, не є обов’язковим.
Таблиця 1 — Допустимі основні поля з поліноміальним базисом і рекомендовані примітивні многочлени
№ ч/ч |
Степінь поля т |
Примітивний многочлен |
№ ч/ч |
Степінь поля т |
Примітивний многочлен |
1 |
163 |
х163+х7+х6+х3+1 |
31 |
337 |
х337+х10+х6+х+1 |
2 |
167 |
х167+х6+1 |
32 |
347 |
х347+х17+хб+х+1 |
3 |
173 |
х173+х,0+х2+х+1 |
33 |
349 |
х349+х6+х5+хг+1 |
4 |
179 |
х179+х4+х2+х+1 |
34 |
353 |
х353+х2б+х7+х3+1 |
5 |
181 |
х181+х7+х6+х+1 |
35 |
359 |
х359+х1в+х4+х2+1 |
6 |
191 |
х191+х9+1 |
36 |
367 |
х367+х21+1 |
7 |
193 |
х193+х,5+1 |
37 |
373 |
х373+хэ+хь+х+1 |
8 |
197 |
х197+х21+х2+х+1 |
38 |
379 |
Х379+Х17+Хб+Х+1 |
9 |
199 |
х^+х^+х^+х+І |
39 |
383 |
хзвз+хэ+хь+х+1 |
10 |
211 |
хг11+х1г+х6+х+1 |
40 |
389 |
хЗВ9+х17+х10+Х+1 |
11 |
223 |
х223+х,2+х2+х+1 |
41 |
397 |
x397+xzz+x3+x+1 |
12 |
227 |
Хгг7+хгі+хг+х+1 |
42 |
401 |
х401+хг9+х4+х+1 |
13 |
229 |
х229+х21+х2+х+1 |
43 |
409 |
х409+х,ь+хб+х+1 |
14 |
233 |
хгзз+х9+х4+х+1 |
44 |
419 |
х419+хгі+х14+х+1 |
15 |
239 |
х239+х,5+х2+х+1 |
45 |
421 |
х421+х7+х4+х+1 |
16 |
241 |
Хг41+х15+х4+х+1 |
46 |
431 |
Х431+Х5+Х3+Х+1 |
17 |
251 |
х2Ь1+х,4+х4+х+1 |
47 |
433 |
х433+х,5+х5+х+1 |
18 |
257 |
х2Ь7+Х,2+1 |
48 |
439 |
х439+хв+х3+х2+1 |
19 |
263 |
х2ЬЗ+х27+х2+х+1 |
49 |
443 |
х443+х2В+х3+х+1 |
20 |
269 |
x2b9+x7+xb+x+1 |
50 |
449 |
x^W+Z+i |
21 |
271 |
x271+x’fi+x3+x+1 |
51 |
457 |
х4В7+х16+1 |
22 |
277 |
х27/+х23+х3+х2+1 |
52 |
461 |
x4ti1+x23+x4+x+1 |
23 |
281 |
х2В1+Х9+х4+х+1 |
53 |
463 |
X4ti3+X24+X3+X+1 |
24 |
283 |
х2ВЗ+Х2Ь+х9+х+1 |
54 |
467 |
х4В/+х2В+Х3+Х+1 |
25 |
293 |
x^+x'W+x+l |
55 |
479 |
Х473+Х25+ХЬ+Х+1 |
26 |
307 |
хзо/+хв+х4+х2+1 |
56 |
487 |
х^Чх’ЧАх+і |
27 |
311 |
хзі1+х29+х4+х+1 |
57 |
491 |
Х491+Х17+ХЬ+Х2+1 |
28 |
313 |
х3,3+х7+х3+х+1 |
58 |
499 |
х499+х2У+Хь+Х2+1 |
29 |
317 |
хзі7+х9+х5+х2+1 |
59 |
503 |
х593+х3+1 |
ЗО |
331 |
x^+x'^+xW+l |
60 |
509 |
хЬ9У+х23+Х3+Х2+1 |
Якщо використовують оптимальний нормальний базис, то основне поле треба вибирати серед полів GF(2m), степені яких наведено в таблиці 2.
Таблиця 2 — Допустимі основні поля з оптимальним нормальним базисом
Степінь поля т |
173 |
179 |
191 |
233 |
239 |
251 |
281 |
Степінь поля т |
293 |
359 |
419 |
431 |
443 |
491 |
509 |
Вибір еліптичної кривої і порядку базової точки
Еліптичні криві для будь-якого з наведених у таблицях 1 і 2 основних полів і порядки базових точок, що їм відповідають, надає в установленому порядку уповноважений орган державної влади у сфері криптографічного захисту інформації. Дозволено використовувати еліптичні криві, наведені в додатку Г.
Обчислення базової точки еліптичної кривої
У цьому підрозділі встановлено алгоритм обчислення базової точки еліптичної кривої над основним полем.
Вхідні дані алгоритму: коефіцієнти еліптичної кривої А, В і порядок базової точки п, обрані згідно з 7.1 і 7.2.
Результат виконання алгоритму — базова точка Р еліптичної кривої.
Алгоритм обчислення базової точки:
Обчислюють випадкову точку Р згідно з 6.8.
Обчислюють точку еліптичної кривої R = nP.
Якщо R*Q, то переходять до кроку 1, інакше переходять до кроку 4.
Результат виконання алгоритму — базова точка Р еліптичної кривої.
Базову точку задають її координатами. Допускається зберігання й передача базової точки у стисненому вигляді. Стискання базової точки виконують згідно з 6.9, відновлення базової точки виконують згідно з 6.10.
ПЕРЕВІРЯННЯ ПРАВИЛЬНОСТІ ЗАГАЛЬНИХ ПАРАМЕТРІВ ЦИФРОВОГО ПІДПИСУ
Висока криптографічна стійкість цифрового підпису, який встановлено цим стандартом, гарантується тільки в тому випадку, якщо загальні параметри цифрового підпису обчислені правильно, тобто строго відповідно до цього стандарту.
У цьому розділі встановлено правила та умови перевіряння правильності загальних параметрів цифрового підпису.
Перевіряння правильності вибору основного поля
Якщо основне поле задане поліноміальним базисом, то перевіряється виконання наступних умов: