Обчислюється хеш-код даного повідомлення h = H (m); Якщо h (m) (mod p) = 0, то бітове подання h (m): 0 ... 02551
Обчислюється значення v = (h (m)) ^ q-2 (mod p).
Обчислюється значення z1 = sv (mod p); z2 = (q-r1) v (mod p).
Обчислюється значення u = (a ^ z1y ^ z2 (mod p)) (mod q)
перевіряється рівність u = r1
Якщо останнє раенство виконується, то підпис
приймається.
Цифрові підписи, засновані на симетричних криптосистемах
На перший погляд, сама ця ідея може здатися
абсурдом. Дійсно, загальновідомо, що так звана «сучасна», вона ж
двухключевую криптографія виникла і почала швидко розвиватися в останні
десятиліття саме тому, що ряд нових криптографічних протоколів типу
протоколу цифрового підпису не вдалося ефективно реалізувати на базі
традиційних криптографічних алгоритмів, широко відомих і добре вивчених
на той час. Тим не менше, це можливо. І першими, хто звернув на це
увагу, були родоначальники криптографії з відкритим ключем У. Діффі і М.
Хеллман, що опублікували опис підходу, що дозволяє виконувати процедуру
цифрового підпису одного біта за допомогою блочного шифру. Перш ніж викласти цю
ідею, зробимо кілька зауважень про суть і реалізаціях цифрового підпису.
Стійкість будь-якої схеми підпису доводиться
звичайно встановленням Рівносильність відповідного завдання розкриття схеми
який-небудь інший, про яку відомо, що вона обчислювально нерозв'язна.
Практично всі сучасні алгоритми ЕЦП засновані на так званих «складних
математичних завданнях »типу факторизації великих чисел або логарифмування в
дискретних полях.
Однак, доказ неможливості ефективного
обчислювального вирішення цих завдань відсутній, і немає жодних гарантій, що вони
не будуть вирішені в найближчому майбутньому, а відповідні схеми зламані - як це
сталося з «ранцевий» схемою цифрового підпису. Більше того, з бурхливим прогресом
засобів обчислювальних техніки «межі надійності» методів відсуваються в
область все більших розмірів блоку.
Лише кілька десятиліть тому, на зорі криптографії
з відкритим ключем вважалося, що для реалізації схеми підпису RSA достатньо навіть
128-бітових чисел. Зараз ця межа відсунута до 1024-бітових чисел --
практично на порядок, - і це ще далеко не межа. Це призводить до
необхідності переписувати реалізують схему програми, і часто
перепроектувати апаратуру.
Нічого подібного не спостерігається в області
класичних блокових шифрів, якщо не рахувати спочатку збиткового і незрозумілого
рішення комітету за стандартами США обмежити розмір ключа алгоритму DES 56-ма бітами, тоді
як ще під час обговорення алгоритму пропонувалося використовувати ключ більшого
розміру. Схеми підписи, засновані на класичних блокових шифри, вільні від
зазначених недоліків:
по-перше, їх стійкість до спроб злому випливає
з стійкості використаного блочного шифру, оскільки класичні методи
шифрування вивчені набагато більше, а їх надійність обгрунтована набагато краще,
ніж надійність асиметричних криптографічних систем;
по-друге, навіть якщо стійкість використаного в
схемою підпису шифру виявиться недостатньою в світлі прогресу обчислювальної
техніки, його легко можна буде замінити на інший, більш стійкий, з тим же
розміром блоку даних і ключа, без необхідності міняти основні характеристики
всієї схеми - це зажадає тільки мінімальної модифікації програмного
забезпечення;
Отже, повернемося до схеми Діффі і Хеллмана підпису
одного біта повідомлення за допомогою алгоритму, що базується на будь-якому класичному
блоковому шифрі. Припустимо, у нашому розпорядженні є алгоритм зашифрування EK,
оперує блоками даних X розміру n і використовує ключ розміром nK: | X | = n, | K | = nK. Структура ключової інформації в схемі наступна:
секретний ключ підпису kS вибирається як довільна
(випадкова) пара ключів k0,
k1 використовуваного блочного
шифру:
kS = (k0, k1);
Таким чином, розмір ключа підпису дорівнює
подвоєному розміром ключа використаного блочного шифру:
| KS | = 2 | K | = 2nK.
Ключ перевірки являє собою результат
шифрування двох блоків тексту X0 і X1 з
ключами k0 і k1 відповідно:
kV = (C0, C1)
= 
де є параметром схеми блоки даних
несекретних і відомі перевіряє підпис стороні. Таким чином, розмір ключа
перевірки підпису дорівнює подвоєному розміром блоку використаного блочного шифру:
| kV | = 2 | X | = 2n.
Алгоритм Sig вироблення цифрового підпису для біта t (t О (0,1)) полягає просто у виборі відповідної
половини з пари, що становить секретний ключ підпису:
s = S (t)
= Kt.
Алгоритм Ver перевірки підпису полягає у перевірці рівняння Ekt (Xt) = Ct, яке, очевидно, має виконуватися для нашого t. Одержувачу відомі
всі використовувані при цьому величини.
Таким чином, функція перевірки підпису буде
наступною:
.
Покажемо, що дана схема працездатна, для чого
перевіримо виконання необхідних властивостей схеми цифрового підпису:
Неможливість підписати біт t, якщо невідомий
ключ підпису. Дійсно, для виконання цього зловмиснику потрібно було
б розв'язати рівняння Es (Xt) = Ct щодо s, що еквівалентно визначення ключа для відомих
блоків шифрованого і відповідного йому відкритого тексту, що обчислювально
неможливо через використання стійкого шифру.
Неможливість підібрати інше значення біта t, яке підходило
б під задану підпис, очевидна: число можливих значень біта всього два і
ймовірність виконання двох наступних умов одночасно пренебрежимо мала в
просто в силу використання криптостійкості алгоритму:
Es (X0) = C0,
Es (X1) = C1.
Таким чином, запропонована Діффі і Хеллманом
схема цифрового підпису на основі класичного блочного шифру має таку саму
стійкістю, що і лежить в її основі блочний шифр, і при цьому дуже проста.
Проте, у неї є два істотні недоліки.
Перший недолік полягає в тому, що дана
схема дозволяє підписати лише один біт інформації. У блоці більшого розміру
доведеться окремо підписувати кожен біт, тому навіть з урахуванням хешування
повідомлення всі компоненти підпису - секретний ключ, перевірочна комбінація і
власне підпис виходять досить великими за розміром і більш ніж на два
порядку перевершують розмір підписуваного блоку. Припустимо, що в схемі
використовується криптографічний алгоритм EK з розміром блоку та ключа, відповідно n і nK.
Припустимо також, що використовується функція хешування з розміром вихідного
блоку nH. Тоді розміри основних робочих блоків будуть
наступними:
розмір ключа підпису: nkS = 2nHЧnK.
розмір ключа перевірки підпису: nС = 2nHn.
розмір підпису: nS = nHЧnK.
Якщо, наприклад, як основу в даній схемі
буде використаний шифр ГОСТ28147-89 з розміром блоку n = 64 біта
і розміром ключа nK = 256 біт, і для вироблення
хеш-блоків буде використаний той же самий шифр в режимі вироблення імітовставки,
що дасть розмір хеш-блоку nH = 64 то
розміри робочих блоків будуть наступними:
розмір ключа підпису: nkS = 2nHЧnK = 2Ч64Ч256біт = 4096 байт;
розмір ключа перевірки підпису: nС = 2nHn = 2Ч64Ч64 біт =
1024 байти.
розмір підпису: nS = nHЧnK = 64Ч256 біт
= 2048 байт.
Другий недолік даної схеми, може, менше
помітний, але настільки ж серйозна. Справа в тому, що пара ключів вироблення підпису та
перевірки підпису можуть бути використані тільки один раз. Дійсно,
виконання процедури підпису біта повідомлення призводить до розкриття половини
секретного ключа, після чого він вже не є повністю секретних і не може
бути використаний повторно. Тому для кожного підписується повідомлення
необхідний свій комплект ключів підпису і перевірки. Це практично виключає
можливість використання розглянутої схеми Діффі-Хеллмана в спочатку
запропонованому варіанті в реальних системах ЕЦП.
Однак, кілька років тому Березін і Дорошкевич
запропонували модифікацію схеми Діффі-Хеллмана, фактично знімає її
недоліки.
Центральним у цьому підході є алгоритм
«Односторонньої криптографічного прокрутки», який до певної міри може
служити аналогом операції піднесення до степеня. Як завжди, припустимо, що в
нашому розпорядженні є криптографічний алгоритм EK з
розміром блоку даних і ключа відповідно n і nK біт, причому nЈnK.
Нехай у нашому розпорядженні також є деяка
функція відображення n-бітових блоків даних у nK-бітові Y = Pn ® nK (X), | X | = n, | Y | = nK. Визначимо рекурсивну функцію Rk
«Односторонньої прокрутки» блоку даних T розміром n біт k раз (k і 0) за допомогою наступної формули:
де X - довільний несекретних n-бітовий
блок даних, що є параметром процедури прокручування.
По своїй ідеї функція односторонньої прокручування
надзвичайно проста, треба всього лише потрібну кількість разів (k) виконати
наступні дії: розширити n-бітовий блок даних T до розміру
ключа використаного алгоритму шифрування (nK), на
отриманому розширеному блоці як на ключі зашифрувати блок даних X,
результат зашифрування занести на місце вихідного блоку даних (T). За визначенням операція Rk (T) володіє двома важливими для нас
властивостями:
аддитивного і комутативність за кількістю
прокручування:
Rk + k '(T) = Rk' (Rk (T)) = Rk (Rk '(T )).
Однобічність або незворотність прокрутки: якщо
відомо тільки деяке значення функції Rk (T), то обчислювально
неможливо знайти значення Rk '(T) для будь-якого k'
Тепер покажемо, як вказану операцію можна
використовувати для підпису блоку T, що складається з nT бітів.
Секретний ключ підпису kS вибирається як довільна пара блоків k0, k1,
мають розмір блоку даних використовуваного блочного шифру, тобто розмір ключа
вироблення підпису дорівнює подвоєному розміром блоку даних використаного
блочного шифру: | kS | = 2n;
Ключ перевірки підпису обчислюється як пара блоків,
мають розмір блоків даних використаного алгоритму за наступними формулами:
kC = (C0, C1)
= (R2nT-1 (K0), R2nT-1 (K1 )).
У цих обчисленнях також використовуються несекретні
блоки даних X0 і X1, що є
параметрами функції «односторонньої прокрутки», вони обов'язково повинні бути
різними. Таким чином, розмір ключа перевірки підпису також дорівнює подвоєному
розміром блоку даних використаного блочного шифру: | kC | = 2n.
Обчислення і перевірка ЕЦП будуть виглядати
наступним чином:
Алгоритм SignT вироблення
цифрового підпису для nT-бітового блоку T полягає в
виконання «односторонньої прокрутки» обох половин ключа підпису T і 2nT-1-T
разів відповідно:
s = SignT (T) = (s0, s1) = 
.
Алгоритм VernT
перевірки підпису полягає в перевірці істинності співвідношень 
, які,
очевидно, повинні виконуватися для справжнього блоку даних T:
R2nT-1-T (s0) = R2nT-1-T (RT (k0)) = R2nT-1-T + T (k0) = R2nT-1 (k0) = C0,
RT (s1) = RT (R2nT-1-T (k1)) = RT +2 nT-1-T (k1) = R2nT-1 (k1) = C1.
Таким чином, функція перевірки підпису буде
наступною:
Покажемо, що для даної схеми виконуються
необхідні умови працездатності схеми підпису:
Припустимо, що в розпорядженні зловмисника
є nT-бітовий блок T, його підпис s = (s0, s1),
і ключ перевірки kC = (C0, C1). Користуючись цією інформацією, зловмисник
намагається знайти правильну підпис s '= (s'0, s'1)
для іншого nT-бітового блоку T '.
Для цього йому треба вирішити наступні рівняння щодо s'0 і s'1:
R2nT-1-T '(s'0) = C0,
RT '(s'1) = C1.
У розпорядженні зловмисника є блок даних T з підписом s = (s0, s1),
що дозволяє йому обчислити одне з значень s'0, s'1,
навіть не володіючи ключем підпису:
якщо T
якщо T> T ', то s'1 = R2nT-1-T' (k1) = RT-T '(R2nT-1-T (k1)) = RT-T' (s1).
Однак для знаходження другої половини підпису (s'1 і s'0
у випадках (a)
та (b)
відповідно) йому необхідно виконати перейдіть у зворотний бік, тобто
знайти Rk (X), маючи в своєму розпорядженні тільки
значенням для більшого k, що є обчислювально неможливим. Таким
чином, зловмисник не може підробити підпис під повідомленням, якщо не
має в своєму розпорядженні секретним ключем підпису.
Друга вимога також виконується: вірогідність
підібрати блок даних T ',
відмінний від блоку T, але що володіє такою ж цифровим підписом,
надзвичайно мала і може не прийматися до уваги. Дійсно, нехай
цифровий підпис блоків T і T '
збігається. Тоді підписи обох блоків будуть рівні відповідно:
s = SnT (T) = (s0, s1) = (RT (k0), R2nT-1-T (k1)),
s '= SnT (T') = (s'0, s'1) = (RT '(k0), R2nT-1-T' (k1 )),
але s = s ', отже:
RT (k0) = RT '(k0) і R2nT-1-T (k1) = R2nT-1-T' (k1).
Покладемо для визначеності TЈT ', тоді справедливо наступне:
RT'-T (k0 *) = k0 *, RT'-T (k1 *) = k1 *, де
k0 *= RT (k0), k1 *= R2nT-1-T '(k1)
Остання умова означає, що прокручування двох
різних блоків даних одне і те ж число раз залишає їх значення
незмінними. Вірогідність такої події надзвичайно мала і може не прийматися
до уваги.
Таким чином розглянута модифікація схеми
Діффі -Хеллмана робить можливим підпис не одного біта, а цілої бітової групи.
Це дозволяє в кілька разів зменшити розмір підпису і ключів
підпису/перевірки даної схеми. Однак треба розуміти, що збільшення розміру
підписуються бітових груп призводить до експоненціальним росту обсягу
необхідних обчислень і починаючи з деякого значення робить роботу схеми
також неефективною. Кордон «розумного розміру» підписує групи знаходиться
десь близько десяти біт, і блоки більшого розміру все одно необхідно
підписувати «по частинах».
Тепер знайдемо розміри ключів і підпису, а також
обсяг необхідних для реалізації схеми розрахунків. Нехай розмір хеш-блоку і
блоку використовуваного шифру однакові і рівні n, а розмір підписуються бітових груп дорівнює nT.
Припустимо також, що якщо остання група містить меншу кількість бітів, обробляється
вона все одно як повна nT-бітова група. Тоді розміри ключів
підпису/перевірки і самої підписи збігаються і дорівнюють такій величині:
біт,
де йxщ позначає округлення числа x до
найближчого цілого в бік зростання. Число операцій шифрування EK (X), необхідний для реалізації процедур
схеми, визначаються нижченаведеними співвідношеннями:
при виробленні ключової інформації воно дорівнює:
,
при виробленні та перевірці підпису воно вдвічі менше:
.
Розмір ключа підпису та перевірки підпису можна
додатково зменшити наступними прийомами:
Немає необхідності зберігати ключі підпису окремих
бітових груп, їх можна динамічно виробляти в потрібний момент часу з
допомогою генератора криптостійкості гами. Ключем підпису в цьому випадку буде
бути звичайний ключ використаного в схемі підпису блочного шифру. Наприклад,
якщо схема підпису буде побудована на алгоритмі ГОСТ 28147-89, то розмір ключа
підпису буде дорівнює 256 бітам.
Аналогічно, немає необхідності зберігати масив
ключів перевірки підпису окремих бітових груп блоку, достатньо зберігати його
значення хеш-функції цього масиву. При цьому алгоритм вироблення ключа підпису та
алгоритм перевірки підписи будуть доповнені ще одним кроком - обчисленням
хеш-функції масиву перевірочних комбінацій окремих бітових груп.
Таким чином, проблема розміру ключів та підписи
вирішена, однак, другий недолік схеми - одноразовість ключів - не подолана,
оскільки це неможливо в рамках підходу Діффі-Хеллмана.
Для практичного використання такої схеми,
розрахованої на підпис N повідомлень, відправнику необхідно зберігати N ключів підпису, а
одержувачу - N ключів перевірки, що досить незручно. Ця проблема може бути вирішена в
точності так само, як була вирішена проблема ключів для множинних бітових
груп - генерацією ключів підписи для всіх N повідомлень з одного майстер-ключа і згортання
всіх перевірочних комбінацій в одну контрольну комбінацію за допомогою алгоритму
обчислення хеш-функції.
Такий підхід вирішив би проблему розміру збережених
ключів, але привів би до необхідності разом підписом каж
