s2-1 mod q;
обчислює u1=f(M) s' mod q;
обчислює u2 =s'si mod q
обчислює t = (hu1bu2 mod p)mod q;
якщо t = S1, то підпис є справжнім.
Коректність процедури підписування ґрунтується на тому, що hr=(hu1bu2 mod p). Справді, оскільки b =ha mod p, то початкове порівняння рівносильне такому: hr=hu1+au2 (mod p). У цьому разі h є порядку q в Zp*, а тоді досить перевірити, що r = (u1+au2)mod q. Останнє рівносильне перевірянню правильності порівняння l = r' (u1+au2)mod q. Підставивши вирази для u1 та и2, отримаємо r'(u1+аиг) = r'(f(M)) s' + as1 s') = r’(f(M)) + as1) s' = s2s' = l(mod q).
Зазначимо, що завдяки застосуванню числа q довжиною у 160 бітів пара чисел, які утворюють цифровий підпис, потребує лише 320 бітів. Безпосередня атака з метою відшукання таємного ключа а потребує обчислення дискретного логарифма за модулем р, де р є порівняно великим числом. Завдяки рівності ha = ha mod q mod p показники сте-пенів h можуть бути зведені за модулем q. Це спрощує обчислення й приводить до пев-ної зміни тесту автентичності підписів.
Протоколи, пов'язані з підписами
Сліпі підписи
Для генерування сліпих цифрових підписів (документ у цьому разі не оприлюд-нюють) дуже добре підходить алгоритм RSA. Наведений далі протокол відповідає ситу-ації, у якій особа А хоче отримати сліпий підпис нотаріуса під повідомленням М. Нота-ріус використовує публічний ключ (e, п) і приватний ключ (d, n) алгоритму шифрування RSA. Протокол передбачає такі кроки:
сторона А закриває повідомлення М. З цією метою вона вибирає випадкове
число k < п, взаємно просте з п, і обчислює t = Mke mod n;
А пересилає число t нотаріусові;
нотаріус шифрує t за допомогою свого приватного ключа s = t mod n;
нотаріус пересилає стороні А число s;
оскільки s = td = (Mke)d = Md-ked = (Mdk)mod n, то особа А може легко об-
числити Md = s*k-1 (mod n), де Md mod n є підписаним повідомленням М.
У наведеному протоколі нотаріус не бачить тексту М. Щоб отримати М з числа t, йому необхідно знайти ке mod я.
Підпороговий канал з використанням підпису Ель-Гамаля
Кожен цифровий підпис повинен використовувати випадкові компоненти. Це га-рантує, що кожний підпис є іншим, та робить можливим багаторазове підписування того самого документа (хоча б для перевірки). З іншого боку, ці випадкові компоненти можна використати для пересилання повідомлення так, що ніякий невтаємничений спостерігач не в стані його підписати. Такий спосіб передавання інформації називають підпороговим каналом. Можливість реалізації підпорогового каналу пов'язана з ситуа-цією, коли криптограми не можна відрізнити від випадкових послідовностей. Єдина проблема полягає в тому, як отримати ці "випадкові" послідовності з цифрових під-писів. Для цього є відповідні методи з використанням, наприклад, алгоритмів DSA і Ель-Гамаля.
Припустимо, що абонент В хоче переслати абоненту А важливу інформацію, при-ховуючи її в цифровому підписі. З цією метою В пересилає невинні листи, підписані згідно з методом Ель-Гамаля. Попередньо особи А і В узгодили таємний ключ, який потім особа А використовує для отримання таємних даних, прихованих у цифрових підписах.
Хід протоколу. Для формування цифрових підписів В вибирає просте число р і випадкові числа g,x < р. Обчислює у = g x mod p, публікує у, g, p та повідомляє А число х.
Щоб у підписі певного повідомлення М' заховати текст М, В діє так:
обчислює F = gM mod p;
знаходить таке G, що виконується конгруенція М'= (x*F + M*G)mod (p- 1).
Одночасно знаходить таке Т, що М*Т= l mod (р - 1);
обчислює G = (M'-xF)-Tmod (р - 1). У цьому разі обов'язково, щоб G і р - 1
були взаємно простими. Якщо це не так, то В модифікує текст М;
пересилає А підпис (F, G) (підпис типу Ель-Гамаля).
Під час перевірки, що підпис автентичний за схемою Ель-Гамаля, А обчислює М: М =(М' - xF)G-1 mod (p - 1).
Зазначимо, що під час формування підпису потрібне виконання таких умов:
0<М<р-1;
числа М і р-1 повинні бути взаємно простими (якщо це не виконується, то В
незначно модифікує текст М, наприклад, додаванням пропуску між словами
тощо).
Незаперечні підписи
У випадку, який розглядаємо, потрібно таке:
верифікація підпису є можливою лише за участю автора підпису;
у випадку підробленого підпису справжній автор має змогу довести фальшування.
Цифровий підпис, який задовольняє ці умови, називають незаперечним підписом.
Початкові умови. Нехай р - просте число. Крім того, нехай р має вигляд 2q + 1, де q є простим числом. Нехай G - множина таких чисел т< р, що тq 1 mod p. До G належать усі числа вигляду g2i mod р, де g є твірною для Zp* та і < q. Легко перевірити, що (g2i+1i)q g2qi+q (gp-1)igqgq?1modp. Тоді множина G має саме q елементів. Нехай а твірна в G (наприклад, g2 mod p є такою твірною; насправді кожний елемент G, відмінний від 1, є твірною).
З метою генерування ключа вибирають випадково х < q і обчислюють Р = ах mod p. Значення р, a, b публікують. Число х є таємним ключем.
Підписувати можна числа з множини G.
Утворення підпису. Підписом під М є G є число yMx mod p.
Верифікація підпису. З метою перевіряння особою А підпису у, утвореного осо-бою В під документом М, сторони А і В виконують такі кроки:
А вибирає два випадкові натуральні
