---

(SK-RX-H) = 0 (mod Q).

А.1.1.1 Параметри DSA

L — 512 + 64 /, для цілого числа І, 0 < І < 8

Р — просте число, таке, що 2 ^/-"¹< Р < 2^L

Q — простий дільник Р-1, де 2¹⁵⁹ < Q < 2¹⁶⁰

F — ціле число, таке, що 1 < F < Р-"І і F^(P-1)/Q mod Р > 1

G — р(^р-іуо _mocj р елемент порядку Q в Е = Z*_P.

Цілі числа Р, Q та G можуть бути відкритими і можуть бути спільними для групи користувачів. Щоб досягти відповідності FIPS, параметри Рта О визначаються, як це зазначено в FIPS PUB 186, дода­ток 2. (Подробиці можна знайти в додатку С).

Примітка 1. Розмір Р в цьому прикладі такий, як його визначено в алгоритмі цифрового підпису (DSA). Зверніть увагу, що розмір Р не повинен перевищувати 1024 біти. 3 19 травня 1994 цей розмір Р забезпечує достатню надійність безпеки. Визнається одночасно, що внаслідок прогресу в розробленні теоретико-числових алгоритмів може статися так, що розмір Р в 1024 бітів є недостатнім

.Примітка 2. Рекомендується, щоб усі користувачі перевіряли належну генерацію відкритих параметрів DSA.

Примітка 3. Відомо, що DSA має негативну особливість, за якої атака може бути встановлена, якщо колізія на ос­новній геш-функції може бути знайдена зі складністю 2⁷⁴ порівняно з 2⁸⁰ в найбільш безпечному випадку. Хоча ця ата­ка легко виявляється, користувачам, які хочуть уникнути цієї особливості, краще використовувати механізм, наведений в А.1.2.

А. 1.1.2 Гэнерування ключа підпису та перебіркового ключа в DSA

Ключ підпису — секретно згенероване випадкове чи псевдовипадкове ціле число X, таке, що 0 < X < Q. Відповідний відкритий перевірковий ключ У це

Y=G^X.

Секретний ключ підпису користувача X та відкритий перевірковий ключ У звичайно встановлюються на певний проміжок часу. Ключ підпису X повинен зберігатись у секреті.

А.1.1.3 Процес підписування в DSA

А.1.1.3.1 Створювання рандомізатора

Підписувач обчислює випадкове чи псевдовипадкове ціле число /(таке, що 0 < К< Q. Параметр К треба обчислювати для кожного підпису та таємно зберігати.

А.1.1.3.2 Створювання попереднього підпису

Маючи значення рандомізатора К на вході цього етапу, підписувач обчислює

n = G^KmodR

А.1.1.3.3 Готування повідомлення для підписування

Повідомлення разбивается так, що Мі є порожньою, а М₂= М.

А.1.1.3.4 Обчислювання свідоцтва

Підписувач обчислює R = П mod Q, де свідоцтво — це функція попереднього підпису. Таким чином, R = (G^K mod Р) mod Q.

А.1.1.3.5 Обчислювання призначення

Підписувач обчислює призначення (Ті, Т₂) = (-R, -Н), де Н = h(M) — геш-атрибут повідомлення М, та М = М₂.

А.1.1.3.6 Обчислювання другої частини підпису

Підпис — це (R, S). Таким чином:

R = (G^K mod Р) mod Q,
S = (К^-1(h (M) + XR)) mod Q.

Значення h (M) — це 160-бітовий вихідний рядок алгоритму безпечного перемішування (SHA). Щоб використати цей рядок під час обчислення S, його треба перетворити в ціле число. Правило перетво­рення наведено в додатку С. За бажанням, можна здійснити перевіряння R = 0 або S = 0. Якщо R = 0 або S = 0, створюється нове значення К і підпис треба обчислити повторно. (Досить малоймовірно, щоб R = 0 або S = 0, якщо підписи виробляються належним чином).

А.1.1.3.7 Побудова доповнення

Доповнення — це конкатенація підпису (R,S) та додаткового текстового поля

text, (R,S)text.

А.1.1.3.8 Побудова підписаного повідомлення

Підписане повідомлення — це конкатенація повідомлення М та доповнення

М И (R, S) ||/ех/.

А.1.1.4 Процес перевіряння в DSA

До перевіряння підпису в підписаному повідомленні потрібно, щоб перевірювач мав достовірні копії Р, Q і G.

Перевірювач також має необхідні елементи даних для процесу перевіряння. Наприклад, перевірко­вий ключ (з питань додаткових необхідних елементів даних див. розділ 9 ISO/IEC 14888-1).

А.1.1.4.1 Готування повідомлення для перевіряння

Перевірювач відновлює М = М₂ з підписаного повідомлення. Мі є порожньою.

А.1.1.4.2 Відновлення свідоцтва

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

А.1.1.4.3 Відновлення призначення

Цей етап ідентичний А.1.1.3.5. Входи для функції призначення складають свідоцтво R з А.1.1.4.2 і М₂ з А. 1.1.4.1. Призначення Т = (Ті,Т₂) повторно одержують як вихід функції призначення А. 1.1.3.5.

А.1.1.4.4 Повторне обчислювання попереднього підпису

Входи для цього етапу — параметри проблемної області, ключ перевіряння У, призначення Т = (Ті,Т₂) з А. 1.1.4.3 та друга частина підпису S з А. 1.1.4.2. Перевірювач призначає коефіцієнтам (А, В, С) значення (S, 7Ї , Т₂) (як це визначено функцією підписування) та одержує повторно обчисле­не значення попереднього підпису, використовуючи в Е співвідношення:

П = y-^A'’^em^odQ(5-A-¹Cm^odQ _т0(-| р _в£

А.1.1.4.5 Повторне обчислювання свідоцтва

Обчислювання на цьому етапі — таке саме, як в А.1.1.3.4. Перевірювач обчислює функцію свідоцтва. Вхід — П з А.1.1.4.4. Треба зазначити, що є порожньою. Вихід — повторно обчислене свідоцтво R.

А. 1.1.4.6 Підтвердження свідоцтва

Нехай значення М₂ згідно з А. 1.1.4.1, а значення R і S згідно з А. 1.1.4.2. У— відкритий перебірко­вий ключ підписувача. Щоб перевірити підпис, перевірювач спочатку перевіряє умови 0 < R < Q і 0 < S < Q. Якщо будь-яка з цих умов порушується, то підпис відхиляється. Якщо ці дві умови вико­нуються, то перевірювач порівнює повторно обчислене свідоцтво R із А.1.1.4.5 зі значенням R із А. 1.1.4.2. Якщо R = R, то підпис має силу.

А. 1.2 Підписи Pointcheval/Vaudenay

Механізм Pointcheval/Vaudenay — варіант алгоритму DSA, де Е = Z*_P, Р— просте число і Q — простий дільник Р-1. Повідомлення розбите таким чином, що є порожньою, а М₂= М. Свідоцтво ви­значається виразом:

R = П mod Q, а функція призначення — співвідношенням:

(Т_ЬТ₂) = (-R, -Н),

де Н = h (R||M) — геш-атрибут конкатенації свідоцтва R та повідомлення М. Геш-функція h — алгоритм безпечного перемішування (SHA-1). Зверніть увагу, що обчислення Т₂ потребує перетворення геш- атрибута в ціле число. Для цього етапу потрібен певний узгоджений метод для перетворення (див. приклад в ISO/IEC DIS 10118-4).

Коефіцієнти (А,В,С) рівняння підпису Pointcheval/Vaudenay встановлюються таким чином:

(A, В, С) = (S, Т_ьТ₂).

Таким чином, рівняння підпису набуває вигляду:

SK-RX-H = 0 (mod Q).

А. 1.2.1 Параметри Pointcheval/Vaudenay

Р просте число

Q простий дільник Р-1

F ціле число, таке, що 1 < F < Р-1 і p(^p_1)^/Q mod Р > 1

G f^(P"^i;/q mod Р.

Примітка. Особливу увагу треба приділити генеруванню Р, Q і F. Наприклад, можна використати процедури з А.1.1.1.

А. 1.2.2 Гэнерування ключа підпису та перебіркового ключа Pointcheval/Vaudenay

Ключ підпису — секретно вироблене випадкове чи псевдовипадкове ціле число X, таке, що 0 < X < Q. Відповідний відкритий перевірковий ключ Y— це

Y=G^X.

Секретний ключ підпису користувача Xта відкритий перевірковий ключ Y зазвичай встановлюють­ся на деякий проміжок часу. Ключ підпису X повинен зберігатися в секреті.

А. 1.2.3 Процес підписування Pointcheval/Vaudenay

А.1.2.3.1 Створювання рандомізатора

Підписувач обчислює випадкове чи псевдовипадкове ціле число К, таке, що 0 < К < Q та gcd (К, Q) = 1.

А.1.2.3.2 Створювання попередного підпису

Вхід для цього етапу — рандомізатор, а підписувач обчислює:

П = G^K mod Р.

А.1.2.3.З Готування повідомлення для підписування

Повідомлення ділять так, що є порожньою, аМ₂ = М.

А.1.2.3.4 Обчислювання свідоцтва

Підписувач обчислює R - П mod Q, де свідоцтво — просто функція попередного підпису. Таким чином:

R = (G^K mod Р) mod Q.

А.1.2.3.5 Обчислювання призначення

Підписувач обчислює призначення (Т|, Т₂) = (-Я -Н), де Н = h — геш-атрибут конкатенації свідоцтва і повідомлення М (і М ~ М₂).

А.1.2.3.6 Обчислювання підпису

Підпис — (R, S). Таким чином:

R = (G^mod R) mod Q,
S=/C¹(h (RM} + XR) mod Q.

A.1.2.3.7 Побудова доповнення

Доповнення буде конкатенацією (R, S) та додаткового текстового поля text,(R, S) ]| text.

А.1.2.3.8 Побудова підписаного повідомлення

Підписане повідомлення — конкатенація повідомлення Мта доповнення:

jW[|(R, S) Ц text.

А.1.2.4 Процес перевіряння Pointcheval/Vaudenay

До перевіряння підпису підписаного повідомлення треба, щоб перевірювач мав достовірні копії Р, Q і G та інші необхідні елементи даних.

А.1.2.4.1 Готування повідомлення для перевіряння

Перевірювач відновлює М₂- М з підписаного повідомлення. Л4і — порожня.

А.1.2.4.2 Відновлення свідоцтва

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

А.1.2.4.3 Відновлення призначення

Цей етап ідентичний А.1.2.3.5. Входи функції призначення складають зі свідоцтва R з А.1.2.4.2 та М₂ з А, 1.2.4.1. Призначення Т~ (Т_ь Т₂) повторно обчислюється як вихід функції призначення А. 1.2.3.5.

А.1.2.4.4 Повторне обчислювання попереднього підпису

Входи для цього етапу — параметри проблемної області, ключ перевіряння У, призначення Т- (T_1t Т₂) з А.1.2.4.3 та друга частина підпису S3 А.1.2.4.2. Перевірювач призначає коефіцієнтам (А, В, С) зна- ченння (S, Т₂) (як це визначено функцією підписування) та отримує повторно обчислене значення

попереднього підпису П, використовуючи формулу:

П ₌ В mod Q _g-A-¹ с mod Q _mod p ₃

A.1.2.4.5 Повторне обчислювання свідоцтва

Обчислювання на цьому етапі такі самі, як в А.1.2.3.4. Перевірювач обчислює функцію свідоцтва. Входи— П з А.1.2,4.4 і Mf з А. 1.2.4.1. Вихід — повторно обчислене свідоцтво R.

А.1.2.4.6 Підтвердження свідоцтва

Нехай М₂ набуває значення, отримане в А.1.2.4.1, a R і S — в А.1.2.4.2. Перевірювач виконує пе­ревіряння умов O<R<Q1O<S< Q. Якщо будь-яка з цих умов порушена, підпис відхиляється.

Якщо ці дві умови виконуються, перевірювач порівнює повторно обчислене значення свідоцтва R з А. 1.2.4.5 зі значенням R з А.1.2.4.2. Якщо R = R, то підпис має силу.

А.2 Приклад механізму, що базується на еліптичних кривих

А.2.1 DSA, що базується на еліптичних кривих

Нижче наведена схема — аналог алгоритму DSA, що базується на еліптичних кривих. (Додаткові математичні дані про еліптичні криві наведені в додатку D). Таким чином, це механізм підписування, де Е є циклічною групою точок на еліптичній кривій. Ми приймаємо

(А, В, С) = (S, Т_ьТ₂), де (Т_ьТ₂) = (-R, /-/), а Н— геш-атрибут повідомлення М.

Таким чином, рівняння підпису набуває вигляду:

SK-RX + Н = 0 (mod Q).

A.2.1.1 Параметри DSA, що базуються на еліптичних кривих

F — кінцеве поле;

Е — група точок на еліптичній кривій над полем F;

#Е — потужність Е;

Q — простий дільник #Е;

G — точка на еліптичній кривій порядка Q.

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

А.2.1.2 Генерування ключа підпису і перевіркового ключа в DSA, що базується на еліптичних кривих

Ключ підпису — секретно згенероване випадкове чи псевдовипадкове ціле число X, таке, що 0 < Х< Q. Відповідний відкритий перевірковий ключ Y— це

Y = G^x.

Секретний ключ підпису користувача Хта відкритий перевірковий ключ /звичайно встановлюють­ся на деякий проміжок часу. Ключ підпису X повинен зберігатись у секреті.

А.2.1.3 Процес підписування в DSA, що базується на еліптичних кривих

А.2.1.3.1 Створювання рандомізатора

Обирається секретне випадкове ціле число К, таке, що 0 < К < Q.

А.2.1.3.2 Створювання попереднього підпису

Вхід для цього етапу — рандомізатор К, за допомогою якого підписувач обчислює

n = G^K.

А.2.1.3.3 Готування повідомлення до підписування

Повідомлення розбивається таким чином, що є порожня, а М₂= М.

А.2.1.3.4 Обчислювання свідоцтва

Підписувач обчислює R = П_х mod Q, де П_х — координата х точки П, яка інтерпретується як ціле число в діапазоні [1, Q-1] (див. 5.2 ISO/IEC 14888-1).

А.2.1.3.5 Обчислювання призначення

Підписувач обчислює призначення (7і, Т₂) = (-R, Н), де Н— геш-атрибут повідомлення М.

А.2.1.3.6 Обчислювання другої частини підпису

Підпис — (R, S). Оскільки

R = П_х mod Q,
S = (К~' (XR-НУ) mod Q,

то

(R, S) = ((П_х) mod Q, K^XR-H)) mod Q).

A.2.1.3.7 Побудова доповнення

Доповнення буде конкатенацією (R, S) і додаткового текстового поля text, (R, S) || text.