Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що грунтується на еліптичних кривих. Формування та перевіряння

Вхідні дані алгоритму: стиснене зображення Рє GF(2^m} точки еліптичної кривої, коефіцієн­ти еліптичної кривої (Д, В).

Результат виконання алгоритму — точка еліптичної кривої Р з координатами (х_Р, у_Р).

Алгоритм відновлення точки еліптичної кривої:

1. Якщо Р = 0 , то приймають х_Р= 0, у_р= В²" = 4в та переходять до кроку 7.

2. Виділяють крайній правий двійковий розряд k стисненого зображення точки Р = (Р_т і,... ,Р₀): k = P_Q. _

3. Координату х_Р точки Р еліптичної кривої приймають рівною х_Р= (х_{Р т}^,...,х_Р^,х_Р0) = Р, далі крайній правий розряд приймають рівним Хр_і0 = 0. Якщо слід отриманої координати tr(x_P)*A, то крайній правий розряд приймають рівним х_Р0 = 1.

4. ОбЧИСЛЮЮТЬ елемент W~Xp+AXp+B основного поля.

5. Розв’язують квадратне рівняння z²+ z = v, v = wXp², згідно з 6.7.

6. Якщо слід tr(z) розв’язку z = (z_m_₁,..., z₀) квадратного рівняння дорівнює к, то приймають y_P-zx_P, інакше приймають y_P~(z+ 1)х_Р.

7. Результат виконання алгоритму — точка еліптичної кривої Р = (х_р, у_Р).

У цьому підрозділі встановлено алгоритм перевіряння примітивності многочлена f(t) степеня т над скінченним полем GF(2).

Вхідні дані алгоритму: многочлен f(t) = t^m+ + ...+ f₀, коефіцієнти якого належать до поля

GF(2), т — непарне число.

Результат виконання алгоритму — повідомлення «многочлен примітивний» або повідом­лення «многочлен не примітивний».

А

2.1

2.2

2.3

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




Для / від 1 до




виконують кроки 2.1—2.3:



лгоритм перевіряння примітивності многочлена:

Обчислюють многочлен g(t)<-g(t)² mod f(t).

Обчислюють найбільший спільний дільник d(f) многочленів f(t) і g(f) + t.

Якщо d(f) 1, то видають повідомлення «многочлен не примітивний» і припиняють

виконання алгоритму.

З таблиць або за допомогою факторизації визначають прості дільники р, р_к числа 2^т-1.

Для і від 1 до k виконують кроки 4.1 і 4.2:

2*-1

1. Обчислюють многочлен = t ^Рі mod f(f).

2. Якщо d/(t) = 1, то видають повідомлення «многочлен не примітивний» і припиняють виконання алгоритму.

5. . Видають повідомлення «многочлен примітивний».

6. .12 Перевіряння простоти порядку базової точки еліптичної кривої

У цьому підрозділі встановлено алгоритм перевіряння простоти порядку базової точки еліп­тичної кривої.

Вхідні дані алгоритму: порядок базової точки еліптичної кривої п.

Результат виконання алгоритму— повідомлення «порядок базової точки еліптичної кривої п просте число» або «порядок базової точки еліптичної кривої п складене число».

Алгоритм перевіряння простоти порядку базової точки еліптичної кривої п:

1. Обчислюють зображення числа п-1 вигляду n-1 =J2^k, де / — непарне число.

2. Для і від 1 до 50 виконують кроки 2.1 — 2.3:

   1. Обчислюють випадкове натуральне число а, 1 < а < п. Для цього:

      1. Обчислюють випадкове ціле число згідно з 6.3.

      2. Якщо а = 0 або <7=1, то переходять до кроку 2.1.1, інакше переходять до кроку 2.2.

   2. Обчислюють ціле число b = a^! mod n;

   3. Якщо dr 1 і b * n — 1, то виконують кроки 2.3.1 — 2.3.3:

      1. Приймають/= 1.

      2. Доки /<к-1 і Ь*п— 1, виконують кроки 2.3.2.1 — 2.3.2.3:

         1. Обчислюють b <- b² mod п.

         2. Якщо Ь= 1, то видають повідомлення «порядок базової точки еліптичної кривої п скла­дене число» і припиняють виконання алгоритму.

         3. Обчислюють/<—/+1.

      3. Якщо b * п - 1, то видають повідомлення «порядок базової точки еліптичної кривої п складене число» і припиняють виконання алгоритму.

3. Видають повідомлення «порядок базової точки еліптичної кривої п просте число».

Додатково дозволено використовувати будь-який метод, який дає строге математичне дове­дення простоти порядку базової точки еліптичної кривої л, наприклад, метод сум Якобі або метод еліптичних кривих.

4. 13 Перевіряння виконання умови Менезеса-Окамото-Венстона

У цьому підрозділі встановлено алгоритм перевіряння виконання умови Менезеса-Окамото- Венстона для порядку п базової точки еліптичної кривої.

Вхідні дані алгоритму: порядок п базової точки еліптичної кривої, визначеної над скінченним полем GF(2^m).

Результат виконання алгоритму — повідомлення «умова Менезеса-Окамото-Венстона виконана» або повідомлення «умова Менезеса-Окамото-Венстона не виконана».

Алгоритм перевіряння виконання умови Менезеса-Окамото-Венстона:

1. . Обчислюють ціле число k = 2^m mod п.

2. . Приймають j= 1.

3. . Для і від 1 до 32 виконують кроки 3.1 —3.2:

   1. Обчислюють нове значення цілого числа j: j jk mod n.

   2. Якщо j=1, то видають повідомлення «умова Менезеса-Окамото-Венстона не виконана» і припиняють виконання алгоритму.

4. . Видають повідомлення «умова Менезеса-Окамото-Венстона виконана».

7. ОБЧИСЛЕННЯ ЗАГАЛЬНИХ ПАРАМЕТРІВ ЦИФРОВОГО ПІДПИСУ

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

1. Вибір основного поля

Дозволено задавати основне поле поліноміальним або оптимальним нормальним базисом.

Якщо використовують поліноміальний базис, то основне поле треба вибирати серед полів GF(2^m), степені яких наведено в таблиці 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(2^m), степені яких наведено в таблиці 2.

Таблиця 2 — Допустимі основні поля з оптимальним нормальним базисом

Степінь поля т	173	179	191	233	239	251	281
Степінь поля т	293	359	419	431	443	491	509

2. Вибір еліптичної кривої і порядку базової точки

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

3. Обчислення базової точки еліптичної кривої

У цьому підрозділі встановлено алгоритм обчислення базової точки еліптичної кривої над основ­ним полем.

Вхідні дані алгоритму: коефіцієнти еліптичної кривої А, В і порядок базової точки п, обрані згідно з 7.1 і 7.2.

Результат виконання алгоритму — базова точка Р еліптичної кривої.

Алгоритм обчислення базової точки:

1. Обчислюють випадкову точку Р згідно з 6.8.

2. Обчислюють точку еліптичної кривої R = nP.

3. Якщо R*Q, то переходять до кроку 1, інакше переходять до кроку 4.

4. Результат виконання алгоритму — базова точка Р еліптичної кривої.

Базову точку задають її координатами. Допускається зберігання й передача базової точки у стисненому вигляді. Стискання базової точки виконують згідно з 6.9, відновлення базової точки виконують згідно з 6.10.

7. ПЕРЕВІРЯННЯ ПРАВИЛЬНОСТІ ЗАГАЛЬНИХ ПАРАМЕТРІВ ЦИФРОВОГО ПІДПИСУ

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

У цьому розділі встановлено правила та умови перевіряння правильності загальних параметрів цифрового підпису.

1. Перевіряння правильності вибору основного поля

Якщо основне поле задане поліноміальним базисом, то перевіряється виконання наступних умов: