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

У цьому підрозділі встановлено алгоритм перетворення елемента основного поля хє GF(2^m) на ціле число а.

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

Результат виконання алгоритму — ціле число a = а₀), що задовольняє умову

L = Ца)< Цп).

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

1. Якщо елемент х основного поля дорівнює 0, то ««-0 L = L(«)<-1, кінець алгоритму.

2. Обчислюють ціле число k=L(n)-1.

3. Приймають сі,= х_/ для / = 0 /с-1 та знаходять j, що дорівнює найбільшому Індексу і,

при якому а,= 1. Якщо такого індексу нема, то приймають 0 та закінчують виконання алгоритму.

4. Двійковий рядок («_;,...,д₀) довжини L = L(tf)=y+1 зображує ціле число а, яке є результат виконання алгоритму.

У цьому підрозділі встановлено алгоритм перетворення результату обчислення функції гешу­вання Ло) ^на елемент основного поля хє GF(2^m), x = (x_m_₁,..., х₀).

Вхідні дані алгоритму: геш-код (h_Lif__b..., h₀).

Результат виконання алгоритму— елемент основного поля хє GF(2^m), x = (x_m_₁ х₀).

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

1. Обчислюють ціле число k = min(m, L_H).

2. Приймають Xj = h, для і = 0 k - 1.

3. Якщо k < т, то приймають х, = 0 для І= к,..., т - 1.

4. Двійковий рядок х₀) зображує елемент х основного поля, який є результат вико­

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

У цьому підрозділі встановлено алгоритм перетворення пари цілих чисел (r, s), які задоволь­няють умови 0<г< п, 0<s<n, на цифровий підпис D = D_o).

Вхідні дані алгоритму: пара цілих чисел (r, s) у двійковому зображенні: г = г₀),

s = (s_L(_S)_i s₀), 0<r<n, 0<s<n, довжина цифрового підпису L_D: L_D> 2Цп), L_D кратне 16.

Результат виконання алгоритму — цифровий підпис D = (Df. -і,..., D_o) довжини L_D.

Алгоритм перетворення пари цілих чисел на цифровий підпис:

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

2. Утворюють двійковий рядок R за правилом:

   1. Приймають R_(:= r_t для / = L(r)-1.

   2. Приймають = 0 для і-Цг),..., І- 1.

3. Утворюють двійковий рядок S за правилом:

   1. Приймають S, = s, для /=0,..., L(s)-1.

   2. Приймають S, = 0 для /= L(s),..., І - 1.

4. Рядок D є конкатенація двох рядків S||R.

5. Двійковий рядок D = (D_t D_o) довжини L_D є результат виконання алгоритму.

Цей підрозділ встановлює алгоритм перетворення двійкового рядка D парної довжини L_D на пару цілих чисел r= (г_Цгу__ь..., r₀), s = з₀).

Вхідні дані алгоритму: двійковий рядок D = парної довжини L_D.

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

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

1. Обчислюють ціле число І - L_d/2 .

2. Приймають r, = D, для /= 0,1.

3. Визначають j як найбільше і, і=0,..., /-1, для якого г, = 1.

4. Якщо такого індексу нема, то г<-О,у = О та переходять до кроку 6.

5. Двійковий рядок (Гцг}_r₀), L(r)=/+1, зображає ціле число г.

6. Приймають s,= Dj і _t для і- 0,..., ї-1.

7. Визначають індекс / як найбільше і, i=Q Z-1, для якого з,= 1.

8. Якщо такого індексу нема, то s«-0, j=0 та переходять до кроку 10.

9. Двійковий рядок (sq_S)_i,..., s₀), L(s)=j+ 1, зображає ціле число s.

10. Пара цілих чисел rise результат виконання алгоритму.

5. ОБЧИСЛЮВАЛЬНІ АЛГОРИТМИ

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

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

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

У цьому стандарті функцію гешування використовують для обчислення й перевіряння цифро­вого підпису. Функція гешування Н перетворює текст Т довільної довжини L_T на двійковий рядок Н(Т) фіксованої довжини L_H.

У цьому стандарті треба використовувати функцію гешування, встановлену в ГОСТ 34.311, або будь-яку іншу функцію гешування, рекомендовану уповноваженим органом державної влади у сфері криптографічного захисту інформації. Значення параметра L_H однозначно визначається ідентифікатором ІН конкретної функції гешування, яка використовується сумісно з цим стандартом. Параметр іН належить до загальних параметрів цифрового підпису. Таких параметрів у групі корис­тувачів може бути декілька. При цьому L_H>160 , Z_(/H)<64. Значення ІН=1, L(iH} = 8 відповідають функції гешування, встановленій в ГОСТ 34.311. Дозволено використовувати геш-функцію за про- мовчанням. При цьому ІН можна випускати.

Якщо використовувана функція гешування накладає обмеження на довжину L_T повідомлення, то ці обмеження мають силу і для цього стандарту.

У цьому підрозділі встановлено алгоритм обчислення випадкового цілого числа а, такого що Ца}<Цп}. Як генератор випадкових послідовностей треба використовувати генератор випадкових послідовностей, визначений у 6.1.

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

Результат виконання алгоритму — випадкове ціле число a. L(<z)<L(n).

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

1. Обчислюють довжину Цп} двійкового зображення цілого числа л.

2. Обчислюють мінімальне значення к, для якого kt > Цп}- 1.

3. За к звернень до генератора випадкових послідовностей формують випадковий двійко­вий рядок довжини kt. Перші L(n)-1 елементи цієї послідовності формують випадковий ДВІЙКОВИЙ рядок Рц_п)-2 довжини Цп)- 1.

4. Приймають «у = R, для /=0,..., L(n)-2.

5. Знаходять індекс /як найбільше /, для якого д,- = 1; якщо такого індексу нема, то приймають «<—0 та припиняють виконання алгоритму.

6. Випадковий рядок Яцп}-2>---> знищують.

Двійковий рядок зображує випадкове ціле число а, яке є результат виконання алго­

ритму.

У цьому підрозділі встановлено алгоритм обчислення випадкового елемента х основного поля GF(2^m). Як генератор випадкових послідовностей треба використовувати генератор випадкових послідовностей, визначений у 6.1.

Вхідні дані алгоритму: степінь т основного поля, довжина t випадкової послідовності, що ви­дається генератором випадкових послідовностей за одне звернення до нього.

Результат виконання алгоритму — випадковий елемент х основного поля.

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

1. За k звернень до генератора випадкових послідовностей формують випадковий двійковий рядок довжини kt > m, де k — мінімальне число з такою властивістю.

2. Перші т елементів цього рядка формують випадковий двійковий рядок (R_m_i, .., R_o)-

3. Приймають Х/=/?/Для / = 0,..., т-1.

4. Випадковий двійковий рядок (R_m_^,..., R_o) знищують.

5. Двійковий рядок (х^,..., х₀) зображує випадковий елемент х основного поля.

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

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

Результат виконання алгоритму — слід tr(x) елемента х.

Алгоритм обчислення сліду:

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

2. Для і від 1 до т - 1 обчислюють t 1² + х.

3. Результат обчислення сліду tr(x) = t.

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

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

Результат виконання алгоритму — напівслід htr(x) елемента х.

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

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

п ■ и m-1 _с* *4

2. Для t від 1 до —обчислюють t <- Г + х.

3. Результат обчислення напівсліду: htr(x) = t.

У цьому підрозділі встановлено алгоритм розв’язування квадратного рівняння z²+ uz = w в основному полі.

Вхідні дані алгоритму: квадратне рівняння z²+ uz = w; и, we GF(2^m); m — непарне число.

Результат виконання алгоритму — кількість розв’язків k квадратного рівняння й один з роз­в’язків цього рівняння, якщо к> 0.

Алгоритм розв’язування квадратного рівняння:

1. Якщо и = 0, то приймають z= w²= , k = 1 і переходять до кроку 8.

2. Якщо w = 0, то приймають z = 0, k = 2, і переходять до кроку 8.

3. Обчислюють елемент основного поля v=wu~².

4. Обчислюють слід елемента tr(y) згідно з 6.5.

5. Якщо ґг(у)=1, то приймають /с = 0, z = 0, і переходять до кроку 8.

6. Обчислюють напівслід елемента v, згідно з 6.6.

7. Обчислюють елемент основного поля z = tu, приймають к =2.

8. Результат виконання алгоритму: кількість розв’язків квадратного рівняння к та один з роз­в’язків z, якщо к> 0.

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

Вхідні дані алгоритму: еліптична крива у²+ ху = х³+ Ах²+ В над полем GF(2^m), т — непарне число, А є {0,1}, В* 0.

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

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

1. Обчислюють випадковий елемент и основного поля згідно з 6.4.

2. Обчислюють елемент ОСНОВНОГО ПОЛЯ IV = и³+ Аи²+ В.

3. Розв’язують квадратне рівняння z²+ uz= w згідно з 6.7.

4. Якщо кількість розв'язків квадратного рівняння дорівнює 0, то переходять до кроку 1, інакше переходять до кроку 5.

5. Приймають х_Р= и, y_P=z, z — розв'язок квадратного рівняння, отриманий на кроці 3.

6. Результат виконання алгоритму — випадкова точка еліптичної кривої Р з координатами (*Р.Ур)-

У цьому підрозділі встановлено алгоритм перетворення точки Р непарного простого порядку еліптичної кривої над GF(2^m) з координатами (х_Р, у_Р) у стиснене зображення Рє GF(2^m), т — непарне число.

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

Результат виконання алгоритму — стиснене зображення PeGF(2^m) точки Р еліптичної кривої.

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

1. Якщо хр = 0, то приймають Р=0 та переходять до кроку 3.

2. Якщо Хр^О, ТО обчислюють елемент ОСНОВНОГО ПОЛЯ У = УрХр¹ =(Ут-1>" > Уо), обчислюють слід елемента у, /=Гг(у) та приймають Р = (Р_т_₁₁ ... , Ро) = (^р._т-і тобто крайній

правий двійковий розряд координати х_Р замінюють на значення сліду елемента у.

3. Результат виконання алгоритму: Рє GF(2^m) — стиснене зображення точки Р еліптичної кривої.

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