---

У цьому підрозділі описаний процес підписування для певного класу механізмів підписування. У межах цього класу функція підписування для використовуваного механізму отримується заміною (А, В, С) на (S, Ті Т₂), яку визначають коефіцієнти рівняння підпису:

АК+ ВХ + С = 0 (mod Q).

Ця заміна буде визначена чи погоджена під час установлення системи підписування.

Процес підписування і формування підписаного повідомлення складається з восьми етапів (див. рис. 1):

• Рисунок 1 — Процес підписування з рандомізованим свідоцтвомстворювання рандомізатора;

• створювання попереднього підпису;

• готування повідомлення для підписування;

• обчислювання свідоцтва (перша частина підпису);

• обчислювання призначення;

• обчислювання другої частини підпису;

• побудова доповнення;

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

У цьому процесі підписувач використовує особистий ключ підпису X і параметри проблемної об­ласті Е, G і Q.

Підписувач створює секретний рандомізатор, що є цілим числом К, таким, що 0 < К < Q і gcd (К, Q) = 1. Виходом цього етапу є значення К, що підписувач тримає в секреті.

Примітка. Допускається вилучення з розгляду ряду цілих чисел як можливих значень К.

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

Виходом цього етапу є попередній підпис П.

Повідомлення розбивається на дві частини, що будуть називатися вхідними даними і М₂. Одна з цих частин може бути порожня і дві частини не обов’язково повинні бути різними (більш докладно в ISO/IEC 14888-1).

Змінні на цьому етапі — це попередній підпис П із 6.2.2 і М- з 6.2.3. Значення цих змінних вважа­ються входами функції свідоцтва. Виходом функції свідоцтва є свідоцтво R.

Входами для функції призначення є перша частина підпису (свідоцтво) R з 6.2.4 І М₂ з 6.2.3. Вихід для функції призначення — призначення Т = (Т_ьТ₂), де і Т₂— цілі числа такі, що

0 <Т_У І < Q, 0 < |Т₂| < Q.

Входи для цього етапу — рандомізатор К з 6.2.1, ключ підпису X, призначення Т= (Ті, Т₂) з 6.2.5, заміна (А, В, С) на (S, T_1t Г₂) ■ параметр проблемної області Q, визначений у 6.1.1. Підписувач фор­мує рівняння підпису

(АК + ВХ + С) = 0 (mod Q)

і розв’язує його відносно S, другої частини підпису, де 0 < S < Q. Пара (R, S) буде називатися під­писом Е.

Доповнення будується з підпису і додаткового текстового поля text у такий спосіб: ((/?, S), text). Це текстове поле могло б включати сертифікат, що криптографічно ув’язує відкритий перевірковий ключ з даними ідентифікації підписувана.

Примітка. Як зазначалося в ISO/IEC 14888-1, залежно від застосовання існують різні шляхи формування допов­нення І додавання його в кінець повідомлення. Загальна вимога полягає в тому, щоб перевірювач мав можливість ус­тановити правильний підпис до повідомлення. Для успішного перевіряння також важливо, щоб до процесу перевірян­ня перевірювач мав змогу ув'язати правильний перевірковий ключ Із цим підписом.

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

6.3 Процес перевіряння

Процес перевіряння складається з чотирьох етапів (рис. 2):

1. ) готування повідомлення для перевіряння;

) відновлення свідоцтва;

2. ) обчислювання функції перевіряння:

• відновлювання призначення;

• повторне обчислювання попереднього підпису;

• повторне обчислювання свідоцтва;

3. ) підтвердження свідоцтва.

У цьому процесі перевірювач користується перевірковим ключем підписувача У і параметрами проблемної області: кінцева група Е, елемент G в Е і його порядок Q.

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

Перевірювач відновлює М з підписаного повідомлення і поділяє повідомлення на дві частини: Ц і М₂.

5. .3.2 Відновлення свідоцтва

Перевірювач відшукує підпис (R, S) у доповненні і поділяє його на свідоцтво R і другу частину підпису S.

6. .3.3 Обчислювання функції перевіряння

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

Цей етап ідентичний етапу 6.2.5. Входи функції призначення складають свідоцтво R з 6.3.2 і М₂ з 6.3.1. Повторно обчислене призначення Т = (Т_ьТ₂) є виходом функції призначення.

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

П =У^тGⁿ, де m = -А^-1В mod Q і n = -А^-1 С mod Q.

Обчислювання на цьому етапі ті самі, що й на етапі 6.2.4. Перевірювач обчислює функцію свідоцтва, де входи — П з 6.3.3.2 і М- з 6.3.1, а вихід — повторно обчислене свідоцтво R.

7. .3.4 Підтвердження свідоцтва

Підпис засвідчений, якщо повторно обчислене свідоцтво R з 6.3.3.3 дорівнює R з 6.3.2. Можуть знадобитися додаткові перевіряння (як приклад інших перевірянь див. А. 1.2.4.6).

7 МЕХАНІЗМИ ЦИФРОВОГО ПІДПИСУВАННЯ, ЗАСНОВАНІ НА ФАКТОРИЗАЦЇЇ

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

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

Ключ підпису для підписувача — таємно згенерована сукупність X = ({P-і, P₂,...,P_r}, s), що скла­дається з набору випадково чи псевдовипадково обраних, але не обов’язково різних, простих цілих чи­сел Pj і цілого числа s. Мінімальна кількість різних простих чисел дорівнює двом.

Перевірковий ключ У — це пара цілих чисел (А/, и), де N — добуток П Р_{, всі Р_{— прості числа, av— ціле число, що задовольняє умову, яка залежить від ключа підпису.

Якщо v визначають як параметр проблемної області, то на ключ підпису могли би бути накладені додаткові обмеження так, щоб v задовольняло відповідну умову.

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

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

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

Повідомлення використовують, щоб побудувати вхідні дані Л4| і М₂. Друга частина, М₂, може ви­явитися порожньою, дві частини не обов’язково повинні бути різними.

Вхід для цього етапу — вхідні дані Мр Вихід — геш-атрибут Н, визначений для Відзначимо, що геш-атрибут інтерпретують як ціле число по mod N таке, що 0 < Н < N.

Входи для цього етапу — свідоцтво, обчислене в 7.2.3, ключ підпису з 7.1.2.1 і, можливо, М₂ (див. ISO/IEC 14888-1, рис. 2). Для рандомізованого механізму входами також є рандомізатор К і попередній підпис П. Вихід — підпис, що складається з однієї частини І = S.

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

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

M||(S, text).

Перевірювач відновлює М з підписаного повідомлення і визначає дві частини вхідних даних М, і /W₂, як визначено в 7.2.2.

Перевірювач відновлює значення свідоцтва Н як деяку функцію вхідних даних що відповідає функції свідоцтва, визначеній у 7.2.3.

Використовуючи ціле число у, отримане або з множини параметрів проблемної області Z, або як перевірковий ключ Y, перевірювач використовує функцію перевіряння, щоб одержати повторно обчис­лене СВІДОЦТВО Н.

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

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

Нижче наведені приклади таких механізмів підписування, а саме: алгоритм цифрового підпису (Digital Signature Algorithm, DSA) U.S. NIST, алгоритм Pointcheval/Vaudenay та механізми підписування, що базуються на еліптичних кривих.

Групи, які використовуються для таких механізмів підписування, включають мультиплікативну гру­пу Z*_P, де Р — просте число (DSA і Pointcheval/Vaudenay), та адитивну групу, яка утворена точками еліптичної кривої над кінцевим полем (Elliptic Curve DSA).

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

А.1.0 Символи та система позначання

Р — просте ціле число;

Z_P — множина цілих чисел U, таких, що 0 < U < Р;

Z*_P — множина цілих чисел U, таких, що 0 < U < Р

А.1.1 Американський алгоритм цифрового підпису (DSA)

Цей приклад взятий з публикацїі Федеральних стандартів з питань обробки інформації Американсь­кого національного інституту стандартів та технології (U.S. National Institute of Standards and Technology, NIST) (FIPS PUB 186, від 19 травня 1994). Основні параметри, визначені в пункті 6, повинні бути по­дані у відповідній формі. Познаки частково змінені щодо FIPS PUB 186, щоб відповідати познакам, які використано у цьому стандарті.

DSA — механізм підписування, коли Е = Z*_P, де Р — просте число, a Q — простий дільник Р-1. Повідомлення розбивається таким чином, що M-_t порожня, а М₂= М.

Функція свідоцтва визначається виразом

Р = П mod Q, а функція призначення — виразом

_(Гі,Т₂) = (-Р, -Н), де Н = h (М) — геш-атрибут повідомлення М, перетворений в ціле число згідно з правилом перетво­рення, наведеним у додатку С. Геш-функція h — це алгоритм безпечного перемішування (Secure Hash Algorithm, SHA), прийнятий у США (NIST) як стандарт безпечного перемішування (Secure Hash Standard, SHS) (FIPS PUB 180-1, від 17 квітня 1995).

Алгоритм SHA описаний також в ISO/IEC DIS 10118-3. (Відзначимо, що контрольне поле з ідентифікатором геш-функції в DSA не потрібне, так що геш-атрибут — це h(/W), див. ISO/IEC 14888-1).

Коефіцієнти (А, В, С) рівняння підпису в DSA визначаються в такий спосіб:

(А,В,С) = (5,Т_йТ₂).

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