---

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

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

M(R, S)|| text.

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

Перевірювач має необхідні елементи даних, які потрібні для процесу перевіряння.

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

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

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

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

А.2.1.4.3 Відновлення доповнення

Цей етап ідентичний А.2.1.3,5. Входи для функції призначення складаються зі свідоцтва R з А.2.1.4.2 і М₂ з А.2.1.4.1. Повторно обчислене призначення Т=(7і, Т₂) — вихід функції призначення А.2.1.3.5.А.2.1.4.4 Повторне обчислювання попереднього підпису

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

pj _ q-A^-1 С mod Q у A"¹ S mod Q

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

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

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

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

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

ПРИКЛАДИ ЦИФРОВИХ ПІДПИСІВ З ДОПОВНЕННЯМ
НА ОСНОВІ СЕРТИФІКАТІВ, ЩО БАЗУЮТЬСЯ НА ФАКТОРИЗАЦІЇ

Наведені приклади механізмів підписування — цифрові підписи з перемішуванням, що базують­ся на ISO/IEC 9796 (детермінований) і ESIGN (рандомізований). Ці схеми описані нижче.

В.1 Цифрові підписи з перемішуванням, що базовані на ISO/IEC 9796

Механізм цифрового підписування, описаний в ISO/IEC 9796, —детермінований підпис, що ба­зується на факторизації. Будучи детермінованим, він не використовує рандомізатор чи попередній підпис. У ключ підпису, який визначено в розділі 7, входять два секретних простих множники Р_ъР₂.

В. 1.1 Генерування параметрів проблемної області

Параметри проблемної області Z можуть містити значення показника степеня для перевіряння v Серед параметрів проблемної області можуть бути й інші параметри, такі, наприклад, як геш-функція.

В.1.2 Генерування ключа підпису і перевіркового ключа

Якщо показник степеня для перевіряння не зазначений в наборі параметрів проблемної області, підписувач обирає додатне ціле число ц де v < N (модулі).

Підписувач обирає сукупність {Р-і, Р₂} двох випадково чи псевдовипадково вибраних і різних про­стих цілих чисел Р,; які задовольняють такі умови:

• якщо V непарне, то Р, -1 повинно бути взаємно простим з v;

• якщо V парне, то (Р,- - 1) /2 повинно бути взаємно простим з v і Р- - Р₂ не повинно ділитись на 8.

Щоб гарантувати, що факторизація N = Р-Р₂щоро обчислювння неможлива, можливі додаткові обмеження на Р,.

Підписувач обчислює відкритий модуль N = РіР₂, показник степеня для підпису, s, ціле число по модулю N (0 < s < N) таким чином, що:

sv = 1 mod Icm (Р₁ -1, Рг-1), якщо v—непарне;

sv = 1 mod y₂ Icm (P_} -1, P₂ -1), якщо v — парне.

Ключ підпису X — це сукупність чисел ({Р-і, Р₂}, s).

Перевірковий ключ У— це пара чисел (Л/, v).

В.1.3 Процес підписування

Процес підписування є процесом детермінованого механізму підписування і тому не виробляє попередній підпис.

В. 1.3.1 Гзтування повідомлення для підписування

Вхідні дані: М- = М (повідомлення), М₂ порожня.

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

Детерміноване свідоцтво — це ціле число Н mod N, визначене геш-атрибутом повідомлення. Геш- атрибут складається із доповненого геш-коду, пов’язаного з допоміжним контрольним полем, яке вміщує ідентифікатор геш-функції, як визначено в ISO/IEC 10118. Якщо геш-функція не визначена параметром проблемної області, контрольне поле обов’язкове. Якщо перевірковий ключ — парне число, то кінце­вий геш-атрибут ділять на 2 (за потреби), щоб його символ Jacobi дорівнював 1 по модулю N.

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

Підписом є S = H^s mod N.

В. 1.3.4 Побудова доповнення

Доповнення будується з підпису і допоміжного текстового поля text. Текстове поле може включати сертифікат, який криптографічно ув’язує відкритий перевірковий ключ з даними ідентифікації підпису­вана.

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

Підписане повідомлення утворюється за допомогою конкатенації повідомлення М і доповнення:

М И (S, text).

В.1.4 Процес перевіряння

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

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

Свідоцтво Н відновлюється з вхідних даних М- згідно із В.1.3.2.

Використовуючи ціле число V, отримане або з параметрів проблемної області Z, або з перебірко­вого ключа У, і ціле число N з перевіркового ключа У, перевірювач обчислює:

Н = S^V mod N.

Якщо показник степеня для перевіряння парний, то Н змінений згідно з модулем відповідності 8.

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

В.2 ESIGN

ESIGN — механізм цифрового підписування, який використовує як модулі ціле число N = Р²О, де Р> Q — прості цілі числа, показник степеня для підпису s дорівнює показнику степеня для перевіряння V— цілому числу, більшому чи такому, що дорівнює 4. Цей загальний показник може бути включений в параметри проблемної області або отриманий із сертифіката в додатковому тексті, який входить у доповнення. Серед параметрів проблемної області може знаходитись ціле число п, яке визначає розмір цілих простих чисел у бітах. Приблизно п — це 1/3 від кількості бітів для подання N. Розмір геш- атрибута не перевищує п-1 бітів (тобто, 0 < Н < 2^л~¹).

Перебірковий ключ — це пара цілих чисел Y= (N, v), де Л/ є добуток Л/ = Р-іР₂Р₃= а у — ціле число, яке задовольняє умову v = з > 4.

Процес підписування ESIGN витікає Із загальної моделі, описаної в розділі 8 ISO/IEC 14888-1. Це рандомізований механізм підписування, який використовує детерміноване свідоцтво і виробляє підпис, який складається з однієї частини.

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

ПІдписувач секретно створює рандомізатор, який є випадковим чи псевдовипадковим додатнім цілим числом К по модулю PQ, так що 0 < К < PQ. Вихід цього етапу — значення К, яке підписувач тримає в секреті.

Входами для цього етапу є рандомізатор К і ключ підпису X. Підписувач обчислює попередній підпис як П = (І/, V), де U = K^s mod N і V = (s№^-1)^-1 mod P. Друга частина попереднього підпису V по­винна зберігатися в секреті.

Повне повідомлення М береться як вхід для обчислювання свідоцтва, тобто М^-М,аМ₂— порожня (див. 8.2 ISO/IEC 14888-1).

Детерміноване свідоцтво — геш-атрибут повідомлення, яке позначається як Н, де Н повинно бути менше ніж 2^П“¹.

Входами для цього етапу є Р і Q з ключа підпису X, рандомізатор К, обчислений у В.2.3.1.1, по­передній підпис П = (U,V), обчислений у В.2.3.1.2, і свідоцтво /7, обчислене у В.2.3.3.

Підпис S обчислюється за формулою:

S = К + (Г (2^2п/7 - U) /PQ' V mod P)PQ mod N.

Вихід цього етапу — підпис S - S.

Доповнення відновлюється з підпису та додаткового текстового поля text. Текстове поле може включати свідоцтво, яке криптографічно ув'язує відкритий перевірковий ключ з даними ідентифікації підписувана.

Підписане повідомлення отримується конкатенацією повідомлення М та доповнення М || (S, text).

Перевірювач володіє необхідними елементами даних, які потрібні для процесу перевіряння.

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

Свідоцтво /7 утворюється з вхідних даних

Використовуючи ціле число и, отримане чи з параметрів проблемної області Z, чи з ключа пере­віряння Y, перевірювач обчислює Н , яке дорівнює п старшим бітам значення

S" mod N.

Підпис має силу, якщо значення відновленого свідоцтва /7 збігається зі значенням повторно об­численого свідоцтва Н .ДОДАТОК С
(довідковий)

ГЕНЕРУВАННЯ ПРОСТИХ ЧИСЕЛ Р

ТА Q ЗГІДНО ІЗ FIPS PUB 186

Щоб побудувати просте число Q в діапазоні 2¹⁵⁹ < Q < 2^1S0, схема генерування простого числа роз­починає роботу з використання SHA-1 і визначеного користувачем значення SEED. У подальшому те значення SEED використовується, щоб утворити х в діапазоні 2^L-1 < х < 2^L. Просте число Р формується далі округленням х до числа конгруентно 1 за модулем 2Q, як це описано нижче.

Ціле число х в діапазоні 0 < х < 2⁹ може бути перетворене в послідовність з g бітів, за допомо­гою його розкладення по основі 2, як це показано нижче:

х = х₁ ■ 2^9-1 + х₂ • 2^9-2 + ... + х_д_! • 2 + х_д {х₁ Хд}.

Та навпаки, послідовність з д бітів {x-f,..., х_д} перетворюється в ціле число згідно з правилом
{Х1 Хд} -> X' ■ 2⁹“¹+ Х₂ ■ 2⁹“² +...+ Хд_-| • 2 + Хд.

Треба звернути увагу, що перший біт послідовності — це найбільш значущий біт відповідного ціло­го числа, а останній біт — найменш значущий.

Нехай L-1 = п ■ 160 + Ь, де b та п — цілі числа і 0 < b < 160.

Крок 1. Виберіть довільну послідовність, в крайньому разі з 160 бітів, та назвіть її SEED. Нехай g — довжина SEED в бітах.

Крок 2. Обчисліть U = SHA [SEED] XOR SHA [(SEED + 1) mod 2⁹].

Крок 3. Перетворіть Q з U так, щоб його найстарший (2¹⁵⁹ біт) і наймолодший біти дорівнювали 1. У термінах Бульових операцій Q = U OR 2¹⁵⁹ OR 1. Відзначимо, що 2¹⁵⁹ < Q < 2¹⁶⁰.

Крок 4. Використайте сильний алгоритм тестування на простоту числа Q. (Сильний тест на про­стоту — це коли імовірність того, що не просте число пройшло тест, найбільш дорівнює 2^-80).

Крок 5. Якщо Q не просте, тоді перейдіть на крок 1.

Крок 6. Нехай counter = 0 та offset = 2.

Крок 7. Для к = 0, ..., п нехай V_k = SHA [(SEED + offset + к) mod 2⁹].

Крок 8. Нехай W є ціле число, тоді:

W= V_o+ V₁• 2¹⁶⁰ + ... + V_n_₁■ 2^(n-1)'¹⁶⁰ + (V_n mod 2^b) • 2ⁿ'¹⁶⁰ та нехай x = И/+ 2^L~¹. Відзначимо, що 0 < H/< 2^L-1, тоді як наслідок 2^L-1 < х < 2^L.