Страница 5: ДСТУ ISO/IEC 14888-3-2002. Інформаційні технології. Методи захисту. Цифрові підписи з доповненням. Частина 3. Механізми на основі сертифікатів (61478)

Крок 9. Нехай с = х mod 2Q і припустимо Р = х - (с-1). Відзначаємо, що Р конгруентно 1 за мо­дулем 2Q.

Крок 10. Якщо Р < 2 ^L-1, то переходимо на крок 13.

Крок 11. Виконуємо сильне тестування на простоту числа Р.

Крок 12. Якщо Р пройшов тест, виконаний на кроці 11, переходимо на крок 15.

Крок 13. Нехай counter = counter + 1 та offset = offset + п + 1.

Крок 14. Якщо counter > 2¹² = 4096, переходимо на крок 1, інакше (тобто, якщо counter < 4096), пе­реходимо на крок 7.

Крок 15. Збережемо значення SEED і значення counter, щоб використати під час підвтерджуван- ня правильності генерування Р і Q.ДОДАТОК D
(довідковий)

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

Текст у цьому довідковому додатку взятий безпосередньо з ANSI Х9.62-1998, Public Key Cryptography For the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). Цей текст включено для ознайомлення користувачів з додатковими математичними основами еліптичних кривих на доповнення до того, що наведено в нормативних розділах цього стандарту. Для глибшого ознайомлення з предметом див. Menezes A. «Elliptic Curve Public Key Cryptosystems».

Національна примітка

Див. також ДСТУ 4145.

Відзначимо, що частина познак у цьому додатку трохи відмінна від тих, що використовуються в цьому стандарті. Наприклад, цей додаток описує арифметику в адитивних познаках, в той час як у розділі А.2 використані мультиплікативні познаки. Як приклад, дх перетворюється в xG, a ab перетво­рюється в А + В.

D.1 Еліптичні криві та точки

Еліптична крива Е, визначена над F_q, — це множина точок Р = (х_р, у_р), де х_р і у_р — елементи F_q, які задовольняють деяке рівняння, разом з точкою на нескінченності, що позначається через О. F_q інко­ли називають базисним полем.

Якщо q~p — просте непарне число (базисне поле — F_p) та р > 3, то а, b повинні задовольняти 4а³ + 27b² = 0 (mod р), і кожна точка Р = (х_р, у_р) на Е (відмінна від точки О) повинна задовольняти в F_p наступне рівняння:

Ур² + х_р³+ах_р +Ь.

Якщо q = 2^т— степінь 2 (базисне поле — Г₂т), то b повинно бути відмінним від нуля в F?_m , і кож­на точка Р = (х_р, у_р) на Е (відмінна від точки О) повинна задовольняти таке рівняння в Е,_т:

Ур² + Хр у_р = х_р³+ ахр² +Ь.

Будь-яка точка еліптичної кривої Р (яка не є точкою О на нескінченності) подається двома еле­ментами поля, координатами Р по х і у: Р = (х_р, у_Р).

D.1.1 Правила додавання для еліптичних кривих над F_p

Множина точок Е (F_p} перетворює групу з послідовними правилами складання:

1. О + 0= О

2. (х, у) + О = О + (х, у) = (х, у) для всіх (х, у) є Е (F_p}

3. (х, у) + (х, -у) = О для всіх (х, у) є Е (F_p} (тобто від’ємною для точки (х, у) є точка мінус (х, у) = (х, -у))

4. Правило для додавання двох різних точок, які не є інверсією одна для одної

Нехай (х_ъ Уі) є Е (F_p} І (х₂, у₂) є Е (F_p} такі дві точки, що Хї * х₂ Тоді (х_1э у^ + (х₂, у₂) = (х₃, у₃), де:

х₃- 13 - X! - х₂, Уз = X (X! - х₃) - у₁ та

_х=Уг-У1.

х₂-х,

V) Правило для подвоєння точки

Нехай (x_1t у-]) є Е (F_p} є такою точкою, що у! * 0. Тоді 2 (x_1f y-f) = (х₃, у₃), де x₃ = /?-2x_1f у₃ = X (х-і - х₃)-у! та

Зх² + а

2Уі

Група Е (F_p} — абелева, а це означає, що Рі + Р₂ = ?2 ⁺ Рі для всіх точок р! та Р₂ в Е (F_p). Ка­жуть, що крива суперсингулярна, якщо # Е (F_p) = р + 1, інакше вона не суперсингулярна.D.1.2 Правила додавання для еліптичних кривих над F_2m

Множина точок Е (Р_2т) перетворює групу за такими правилами додавання:

1. О + О - О

2. (х, у) + О = О + (х, у) = (х, у) для всіх (х, у) є Е (Р₂п,)

3. (х, у) + (х, х + у) = О для всіх (х, у) є E(F₂J (тобто від’ємною для точки (х, у) є точка — (X, у) = (X, X + у))

4. Правило додавання двох різних точок, які не є інверсією одна для одної Нехай (х_ъ у-і) є Е (F_zm) та (х₂, у₂) є Е (Е,_т) — дві точки, такі, що Xj * х₂. Тоді (х_1; ут) + (х₂, у₂) = (х₃, Уз), Де

х₃ = А,² + X + х-і + х₂ + а, уз - А (х-і + х₃) + х₃ + ут та

Z - ^у1“^у2 А — —■— •

Хі~Х₂

5. Правило для подвоєння точки

Нехай (x_1f уі) є Е (Р₂п)є такою точкою, що х-, * 0

Тоді 2 (x_1t у-і) = (х₃, уз), де

х₃ = А² + А + а, уз = х-і² + (А + 1) х₃ та

7 - х + ^Уі А — X 4 Ч »

Хі

Група Е (Р₂п ) — абелева, це означає що р! + Р₂ = Р₂ + Рі для всіх точок Р-і та Р₂ в Е (Р₂™).

ДОДАТОК Е
(довідковий)

ЧИСЛОВІ ПРИКЛАДИ ЦИФРОВОГО ПІДПИСУ
НА ОСНОВІ СЕРТИФІКАТІВ З ДОПОВНЕННЯМ

У цьому прикладі наведені числа в шістнадцятковій системі числення, отримані згідно з алгорит­мом, наведеним у додатку 5 FIB PUB 186.

L = 200 (512₁₀)

Е.2 Алгоритм підпису Pointcheval/Vaudenay

Значення всіх величин представлено в шістнадцятковій системі числення.

У наступних прикладах SHA-1 використовуються виключно як геш-функції, тому геш-атрибут — це просто значення SHA-1, перетворене згідно з додатком С у відповідні елементи даних.

Примітка. З погляду вимог безпеки важливо уникати криптографічних слабких кривих (наприклад, потрібно пере­конатися, що кожна крива не вразлива для атак на спеціальних прикладах обчислювання дискретного логарифма для цієї еліптичної кривої).

Національна примітка

E.3.1.1 Параметри алгоритму

Поле F₂w подано у вигляді поліномів по модулю нескороченого поліному х¹⁹¹ + х⁹ + 1.

Крива Е: Y² + XY = X³ + аХ² + Ь над Е_21Э1, де (в шістнадцятковій системі числення)