---

ДОДАТОК А
(обов’язковий)

ГЕНЕРАТОР ВИПАДКОВИХ ДВІЙКОВИХ
ПОСЛІДОВНОСТЕЙ

У цьому додатку встановлено алгоритм обчислення випадкових двійкових рядків, що надалі названо генератором випадкових послідовностей. Цей генератор треба використовувати для отри­мання випадкових цілих чисел, випадкових елементів основного поля і випадкових точок еліптич­них кривих. Генератор за одне звернення до нього видає випадковий рядок довжини t= 1. Як крипто­графічне перетворення в генераторі застосовується алгоритм криптографічного перетворення згідно з ГОСТ 28147 у режимі простої заміни. Таблиця заміни і особистий ключ цього перетворення по­винні відповідати ГОСТ 28147. Умови отримання й використання особистого ключа повинні унемож­ливлювати доступ до нього або його частини, модифікацію, підміну або знищення. Особистий ключ криптографічного перетворення згідно з ГОСТ 28147, що використовується в генераторі випадкових послідовностей, не можна використовувати для іншої мети.

Позначимо через Е_к() шифрування двійкового рядка довжиною 64 двійкові розряди алгоритмом ГОСТ 28147 в режимі простої заміни на ключі к довжиною 256 двійкових розрядів. Нехай з, D, і, х — двійкові рядки довжиною 64 двійкові розряди. Перед застосуванням задають початковий стан генератора випадкових послідовностей.

Встановлення початкового стану генератора випадкових послідовностей:

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

• Задають значення двійкового рядка D. Для цього використовують поточне значення дати і часу з точністю 64 двійкові розряди.

• Обчислюють двійковий рядок / = Е_к(О).

Використання генератора випадкових послідовностей

При кожному зверненні до генератора випадкових послідовностей виконують такі обчислення (символ Ф позначає порозрядне додавання за модулем 2 двійкових рядків довжиною 64 двійкові розряди):

• х = E_k(/® s);

• s = Е_к(х®Г);

Випадковий двійковий рядок є двійковий рядок довжини 1, який складається з крайнього правого розряду х₀ двійкового рядка х = (х₆₃,..., х₀).

ДОДАТОК Б

(довідковий)

ПРИКЛАДИ ОБЧИСЛЕНЬ ЦИФРОВОГО ПІДПИСУ

У цьому додатку наведено приклади обчислення й перевіряння цифрового підпису з викорис­танням поліноміального та оптимального нормального базисів. У прикладах обчислень двійкові рядки наведено у вигляді рядків шістнадцяткових цифр: двійковий рядок у разі потреби доповнюють зліва нулями так, щоб довжина рядка стала кратною чотирьом, потім рядок ділять на групи по 4 двійкових розряди, кожну таку групу заміняють на шістнадцяткову цифру, що відповідає цій групі двійкових символів.

Б.1 Обчислення й перевіряння цифрового підпису в поліноміальному базисі

Вибір загальних параметрів

Як основне поле використовують скінченне поле GF(2¹⁶³). Елементи цього поля зображають у поліноміальному базисі, що відповідає примітивному многочлену х¹⁶³ + х⁷ + х⁶ + х³ + 1 (див. таб­лицю 1).

Використовується еліптична крива над полем GF(2¹⁶³) (перша еліптична крива з таблиці Г.1): у² + ху = х³ + х² + 5FF6108462A2DC8210AB403925E638A19C1455D21.

Порядок цієї еліптичної кривої ділиться на просте число

n = 400000000000000000002BEC12BE2262D39BCF14D, яке є порядком базової точки.

Обчислення базової точки еліптичної кривої здійснюють наступним чином: обчислюємо випад­кову точку еліптичної кривої

Р= (Хр, Ур) = (72D867F93A93AC27DF9FF01AFFE74885C8C540420, 0224A9C3947852B97C5599D5F4AB81122ADC3FD9B).

Оскільки пР = О, то точка Р — шукана базова точка еліптичної кривої.

Як особистий ключ цифрового підпису візьмемо ціле число

d= 183F60FDF7951FF47D67193F8D073790C1C9B5A3E.

Обчислимо відкритий ключ цифрового підпису, що відповідає обраному особистому ключу:

Q = - dP = (х_о, у₀) = (057DE7FDE023FF929CB6AC785CE4B79CF64ABDC2DA, 3E85444324BCF06AD85ABF6AD7B5F34770532B9AA).

Нехай використовується довжина цифрового підпису L_D= 512.

Припустимо, що функцію гешування вибрано згідно з ГОСТ 34.311 (//-/= 1) і її використовують за промовчанням. У цьому випадку L_w = 256. За лромовчанням приймемо також, що ІН не пере­дається.

Обчислення цифрового підпису

Вважаємо, що всі перевірки згідно з розділом 12 підтверджують правильність відповід­них даних. Обчислимо геш-функцію за повідомленням Т. Нехай результат гешування дорівнює Н(Т) = 09C9C44277910C9AAEE486883A2EB95B7180166DDF73532EEB76EDAEF52247FF.

Перетворимо результат обчислення функції гешування Н(Т) на елемент основного поля згідно з 5.9. Перетворення цього рядка на елемент основного поля полягає у виділенні з цього рядка min(m, L_H)= 163 молодших розрядів. У результаті перетворення отримаємо елемент основного поля /7 = 03A2EB95B7180166DDF73532EEB76EDAEF52247FF.

Обчислимо передпідпис F_e згідно з розділом 11. Нехай ціле число е дорівнює

е= 1025E40BD97DB012B7A1D79DE8E12932D247F61C6.

Обчислимо точку еР:

еР = (х_ер, у_ер) = (42A7D756D70E1C9BA62D2CB43707C35204EF3C67C, 5310AE5E560464A95DC80286F17EB762EC544B15B).

Тоді F_g дорівнює координаті х_вР цієї точки:

F_e = 42A7D756D70E1C9BA62D2CB43707C35204EF3C67C.

Обчислимо добуток елементів основного поля

У= hF_e= 274EA2C0CAA014A0D80A424F59ADE7A93068D08A7.

Перетворимо елемент основного поля у на ціле число г згідно з 5.8:

r= 274EA2C0CAA014A0D80A424F59ADE7A93068D08A7.

Обчислимо ціле число

з = е + dr mod n = 2100D86957331832B8E8C230F5BD6A332B3615АСА.

Перетворимо пару цілих чисел (г, з) на цифровий підпис D згідно з 5.10:

D =000000000000000000000002100D86957331832B8E8C230F5BD6A332B3615ACA

00000000000000000000000274EA2C0CAA014A0D80A424F59ADE7A93068D08A7.

Підписане повідомлення довжини L-L_T+L_D має вигляд ТІЇ О.

Перевіряння цифрового підпису

Перевіримо цифровий підпис, обчислений вище. Під час перевіряння цифрового підпису використовують ті самі загальні параметри, обчислений вище відкритий ключ та геш-функцію за промовчанням (ІН = 1, L_H = 256, іН не передається). Вважаємо, що всі перевірки згідно з розді­лом 13 підтверджують правильність відповідних даних.

Перевіряємо цифровий підпис:

D = 000000000000000000000002100086957331832B8E8C230F5BD6A332B3615ACA

00000000000000000000000274EA2C0CAA014A0D80A424F59ADE7A93068D08A7.

Перевіримо довжину цифрового підпису: L_D=512, тобто чи це число кратне 16 і більше подвоєної довжини двійкового зображення порядку базової точки п.

Обчислюємо L_T= L - L_d. Вважаємо, що підписаний текст прийнято без спотворень, тому L_T>0.

Обчислюємо Н(Т). Підписаний текст прийнято без спотворень, тому результат обчислення функції гешування є, як і при обчисленні цифрового підпису,

H(T) = 09C9C44277910C9AAEE486883A2EB95B7180166DDF73532EEB76EDAEF52247FF.

Перетворюємо результат обчислення функції гешування на елемент основного поля згідно з 5.9: ft = 03A2EB95B7180166DDF73532EEB76EDAEF52247FF.

Перетворюємо цифровий підпис на пару цілих чисел (г, з) згідно з 5.11:

r= 274EA2C0CAA014A0D80A424F59ADE7A93068D08A7,

s = 2100D86957331832B8E8C230F5BD6A332B3615ACA.

Переконуємося, що 0 < г< п.

Переконуємося, що 0 < s < п.

Обчислюємо точку еліптичної кривої

R = sP + rQ = (x_R, y_R) = (42A7D756D70E1C9BA62D2CB43707C35204EF3C67C, 5310AE5E560464A95DC80286F17EB762EC544B15B).

Обчислюємо елемент основного поля

y=hx_p=274EA2C0CAA014A0D80A424F59ADE7A93068D08A7.

Перетворюємо елемент основного поля у на ціле число г згідно з 5.8:

г == 274EA2C0CAA014A0D80A424F59ADE7A93068D08A7.

Оскільки г = г, то підпис дійсний.

Б.2 Обчислення й перевіряння цифрового підпису в оптимальному нормальному базисі

Загальні параметри цифрового підпису

Як основне поле візьмемо поле GF(2¹⁷³) в оптимальному нормальному базисі (див. табли­цю 2). Нехай еліптична крива визначена рівнянням (перша еліптична крива з таблиці Г.2):

/+ ху=х³+ 043D7E139319F43BA00944915740E1Е6651В06Е278С7.

Порядок базової точки дорівнює

n = 800000000000000000000189В4Е67606Е3825ВВ2831.

Як базову точку візьмемо точку

Р= (х_Рі у_Р) = (1D26E5282C2647E1B0327CB4F6087932A0A1F006A89F, 0322218E4551CF8F6E3345644A10B2408F5DF19EC2C7).

Особистий і відкритий ключі цифрового підпису оберемо наступним чином: особистий ключ

d=49FF09C848613AEA23699F78C960D5174617311ADCC,

відкритий ключ

Q = -dP=(x_Q, y_o) = (16C1FF796B32D6D2FC83CA9530B368B322F7874B2D01, 1F253334197826B6ADAE44EDEAA7EA281D1C5E597A37).

Нехай функція гешування обчислена за промовчанням згідно з ГОСТ 34.311 (ІН= 1 ,L_H= 256) та при цьому прийнято, що іН передається. Нехай результат обчислення є

Н(Т) = 2А681ЕСЕ118389В27А108137187ЕА862117EF1484289470ECAC802C5A651FDA8.

Припустимо, що довжина цифрового підпису дорівнює найменшому припустимому значенню L_O = 352.

Обчислення цифрового підпису

Вважаємо, що всі перевірки згідно з розділом 12 підтверджують правильність відповідних даних.

Обчислимо Н(Т) і перетворимо результат обчислення на елемент основного поля h згідно з 5.9. В результаті перетворення отримаємо елемент основного поля

h = 0137187EA862117EF1484289470ECAC802C5A651FDA8

Обчислимо передпідпис F_e згідно з розділом 11. Нехай ціле число е дорівнює

е = 70516411E5D9886B8486ECE54A30E9403D103B95F90.

Обчислимо точку еР:

еР=(х_еР, у_еР) = (028886ЕА28А7С2951FA6473EB3EBC861D3EDB1FBB031, 19059E90F7C7725079CFFE312A389B265140F5BDA493).

Тоді F_e дорівнює координаті х_еР цієї точки:

F_e= 028886ЕА28А7С2951FA6473EB3EBC861D3EDB1FBB031.

Обчислимо добуток елементів основного поля

у— hF_e = 0477ECC260F390FB6D0AE4AE3B7A78120F8EC458EF9A.

Перетворимо елемент основного поля у на ціле число г згідно з 5.8:

r=477ECC260F390FB6D0AE4AE3B7A78120F8EC458EF9A.

Обчислимо ціле число

s= е + drmod n = 472EA56AE478F95F1EC9F628FF43857E168B50FB819

Перетворимо пару цілих чисел (r, s) на цифровий підпис D згідно з 5.10:

D = 0472EA56AE478F95F1EC9F628FF43857E168B50FB819

0477ECC260F390FB6D0AE4AE3B7A78120F8EC458EF9A.

Підписане повідомлення довжини L-8 + L_T+ L_D має вигляд ІН || ТIID, де іН — двійковий рядок виду 00000001.

Перевіряння цифрового підпису.

Перевіримо цифровий підпис, обчислений вище. Під час перевіряння цифрового підпису ви­користовують ті самі загальні параметри, обчислений вище відкритий ключ та геш-функцію за про­мовчанням (/77=1, L_H=256, іН передається). Вважаємо, що всі перевірки згідно з розділом 13 підтверджують правильність відповідних даних.

Перевіряється цифровий підпис

D = 0472EA56AE478F95F1EC9F628FF43857E168B50FB819 0477ECC260F390FB6D0AE4AE3B7A78120F8EC458EF9A.

За промовчанням, перші 8 бітів повідомпення задають іН. Перевіряємо, чи геш-функція з но­мером 00000001 діє на даний час, та визначаємо відповідну довжину геш-коду L_H=256.

Перевіряємо довжину цифрового підпису: L_D= 352, тобто чи це число кратне 16 і більше под­воєної довжини двійкового зображення порядку базової точки п.

Обчислюємо L_T= L-L_D-L(iH). Вважаємо, що підписаний текст прийнято без спотворень, тому L_T>Q.

Обчислюємо Н(Т). Підписаний текст прийнято без спотворень, тому результат обчислення функції гешування є, як і при обчисленні цифрового підпису,

H(7) = 2A681ECE118389B27A108137187EA862117EF1484289470ECAC802C5A651FDA8.

Перетворюємо результат обчислення на елемент h основного поля згідно з 5.9: h = 0137187EA862117EF1484289470ECAC802C5A651FDA8.

Перетворюємо цифровий підпис на пару цілих чисел (r, s) згідно з 5.11: r=477ECC260F390FB6D0AE4AE3B7A78120F8EC458EF9A, s = 472EA56AE478F95F1EC9F628FF43857E168B50FB819.

Переконуємося, що 0<г<п.

Переконуємося, що 0<s<n.

Обчислюємо точку еліптичної кривої

R = sP + rQ = (x_R, y_R) = (028886EA28A7C2951FA6473EB3EBC861D3EDB1FBB031, 19059E90F7C7725079CFFE312A389B265140F5BDA493).

Обчислюємо елемент основного поля

у = hx_R = 0477ECC260F390FB6D0AE4AE3B7A78120F8EC458EF9A.

Перетворюємо елемент основного поля у на ціле число f згідно з 5.8: r =477ECC260F390FB6D0AE4AE3B7A78120F8EC458EF9A.

Оскільки г = г, то підпис дійсний.

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

ОСНОВНІ МАТЕМАТИЧНІ ПОНЯТТЯ,
ЯКІ ВИКОРИСТАНО У СТАНДАРТІ

Основними математичними об’єктами, які використовуються в цьому стандарті, є скінченні поля й еліптичні криві, визначені над цими полями. У цьому додатку наведено основні відомості про ці об’єкти, необхідні для реалізації алгоритмів, описаних у цьому стандарті. Детальний виклад теорії скінченних полів подано в монографії [1]. Уперше використовувати еліптичні криві в криптографічних цілях було запропоновано в [2] і [3]. Найкращим посібником з теорії еліптичних кривих є книги Дж.Сільвермана [4] і [5]. Простіший виклад цієї теорії з описом криптографічних застосувань міс­титься у книгах [6] і [7]. У статті [8] пояснено принципи побудови криптографічних алгоритмів на еліптичних кривих.

Скінченна абелева група є скінченною множиною G, на якій визначено одну операцію, що співвідносить кожній парі елементів (а, Ь) множини G деякий елемент с цієї самої множини. Ця операція може записуватися адитивно, і тоді групова операція називається додаванням, а еле­мент с називається сумою елементів а і Ь, с = а + Ь, або мультиплікативно, і тоді групова операція називається множенням, а елемент с називається добутком елементів а і Ь, c = ab.

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

• ab = ba (а + Ь = Ь + а) (комутативність);

• a(bc) = (ab)c (а + (Ь + с) = (а + Ь) + с) (асоціативність);

• існує єдиний елемент групи, що позначається 1 у мультиплікативному запису і 0 в адитив­ному запису, такий що

• 1о = б/1=а (0 + а = а + 0 = а).