САНКТ - Петербурзького державного технічного університету

Факультет технічної кібернетики

Кафедра інформаційних і керуючих систем

Реферат

«Цифровий підпис»

Студент Барташевич О.Є.

Викладач Чистяков І.В.

Санкт-Петербург

2001

Зміст

1. асиметричні алгоритми шифрування. 3

1.1. Стандарт ассімметрічного шифрування RSA .. 4

1.1.1. Генерація ключів. 4

1.1.2. Шифрування/розшифрування. 5

1.2. Алгоритм ЕльГамаля. 6

1.2.1. Загальні відомості. 6

1.2.2. Шифрування повідомлень. 6

1.2.3. Підтвердження автентичності відправника. 6

1.3. Алгоритм Шаміра. 7

1.3.1. Загальний опис. 7

1.3.2. Передача повідомлень. 7

1.3.3. Приклад використання. 8

1.4. Кpіптосістеми на основі еліптичних уpавненій. 8

2. Електронно-цифровий підпис. 9

2.1. Загальні положення. 9

3. Алгоритм DSA .. 10

3.1. Генерація ЕЦП .. 11

3.2. Перевірка ЕЦП .. 12

4. Стандарт на процедури ЕЦП ГОСТ Р 34.10-94. 12

4.1. Генерація ЕЦП .. 13

4.2. Перевірка ЕЦП .. 13

5. Цифрові підписи, засновані на симетричних криптосистемах. 13

6. Атаки на ЕЦП .. 22

7. Деякі засоби роботи з ЕЦП .. 23

7.1. PGP. 23

7.2. GNU Privacy Guard (GnuPG) 24

7.3. Криптон. 24

7.4. ВербаО .. 24

8. Література та посилання. 25 1. Асиметричні алгоритми шифрування

Розвиток основних типів криптографічних протоколів (ключовий обмін, електронно-цифровий підпис (ЕЦП), аутентифікація та ін) було б неможливо без створення відкритих ключів і побудованих на їх основі асиметричних протоколів шифрування.

Основна ідея асиметричних криптоалгоритмів полягає в тому, що для шифрування повідомлення використовується один ключ, а при дешифрування - інший. Крім того, процедура шифрування підготовлений так, що вона необоротна навіть за відомим ключа шифрування - це друга необхідна умова асиметричної криптографії. Тобто, знаючи ключ шифрування і зашифрований текст, неможливо відновити вихідне повідомлення - прочитати його можна тільки за допомогою другого ключа - ключа дешифрування. А раз так, то ключ шифрування для відправлення листів будь-якій особі можна взагалі не приховувати - знаючи його все одно неможливо прочитати зашифроване повідомлення. Тому, ключ шифрування називають в асиметричних системах "відкритим ключем", а от ключ дешифрування одержувачу повідомлення, потрібно тримати в секреті - він називається "закритим ключем".

Таким чином, ми "забрали від необхідності вирішувати складне завдання обміну секретними ключами.

Напрошується питання: "Чому, знаючи відкритий ключ, не можна обчислити закритий ключ?" - Це третя необхідна умова асиметричною криптографії - алгоритми шифрування і дешифрування створюються так, щоб знаючи відкритий ключ, неможливо вирахувати закритий ключ.

У цілому система листування при використанні асиметричного шифрування виглядає наступним чином. Для кожного з N абонентів, які ведуть листування, обрана своя пара ключів: "відкритий" Ej і "закритий" Dj, де j - номер абонента. Всі відкриті ключі відомі всім користувачам мережі, кожен закритий ключ, навпаки, зберігається тільки у того абонента, якого він належить. Якщо абонент, скажімо під номером 7, має намір передати інформацію абоненту під номером 9, він шифрує дані ключем шифрування E9 і відправляє її абоненту 9. Незважаючи на те, що всі користувачі мережі знають ключ E9 і, можливо, мають доступ до каналу, по якому йде зашифроване послання, вони не можуть прочитати вихідний текст, так як процедура шифрування необоротна з відкритого ключа. І лише абонент № 9, отримавши послання, виробляє над ним перетворення з допомогою відомого тільки йому ключа D9 і відновлює текст послання. Зауважте, що якщо повідомлення потрібно відправити у протилежному напрямку (від абонента 9 до абонента 7), то потрібно буде використовувати вже іншу пару ключів (для шифрування ключ E7, а для дешифрування - ключ D7).

Як ми бачимо, по-перше, в асиметричних системах кількість існуючих ключів пов'язано з кількістю абонентів лінійно (у системі з N користувачів використовуються 2 * N ключів), а не квадратичного, як у симетричних системах. По-друге, при порушенні конфіденційності k-ої робочої станції зловмисник дізнається тільки ключ Dk: це дозволяє йому читати всі повідомлення, що приходять абоненту k, але не дозволяє вивадавать себе за нього при відправленні листів. 1.1. Стандарт ассімметрічного шифрування RSA

Найпоширенішим алгоритмом асиметричного шифрування є алгоритм RSA. Він був запропонований трьома ісседователямі-математиками Рональдом Рівестом (R. Rivest), Аді Шамір (A. Shamir) та Леонардом Адльманом (L. Adleman) в 1977-78 роках. Розробникам даного алгоритму вдалося ефективно втілити ідею односторонніх функцій з секретом. Стійкість RSA базується на складності факторизації великих цілих чисел. У 1993 році метод RSA був оприлюднений і прийнятий як стандарт (PKCS # 1: RSA Encryption standart). RSA можна застосовувати як для шифрування/розшифрування, так і для генерації/перевірки електронно-цифрового підпису. 1.1.1. Генерація ключів

Першим етапом будь-якого асиметричного алгоритму є створення пари ключів: відкритого і закритого і поширення відкритого ключа "по всьому світу". Для алгоритму RSA етап створення ключів складається з наступних операцій:

Вибираються два простих (!) числа p і q

обчислюється їх добуток n (= p * q)

Вибирається довільне число e (e

Методом Евкліда вирішується в цілих числах (!) рівняння e * d + (p-1) (q-1) * y = 1. Тут невідомими є змінні d і y - метод Евкліда як раз і знаходить безліч пар (d, y), кожна з яких є рішенням рівняння в цілих числах.

Два числа (e, n) - публікуються як відкритий ключ.

Число d зберігається в таємниці - це і є закритий ключ, який дозволить читати всі послання, зашифровані за допомогою пари чисел (e, n). 1.1.2. Шифрування/розшифрування

Як же проводиться власне шифрування за допомогою цих чисел:

Відправник розбиває своє повідомлення на блоки, рівні k = [log2 (n)] біт, де квадратні дужки позначають взяття цілої частини від дрібного числа.

Подібний блок, як Ви знаєте, може бути інтерпретовано як число з діапазону (0; 2k-1). Для кожного такого числа (назвемо його mi) обчислюється вираз ci = ((mi) e) mod n. Блоки ci і є зашифроване повідомлення, і

їх можна спокійно передавати по відкритому каналу, оскільки операція піднесення до степеня за модулем простого числа, є незворотною математичної завданням. Зворотній їй завдання має назву "логарифмуванню в кінцевому полі" і є на кілька порядків складнішим завданням. Тобто навіть якщо зловмисник знає числа e і n, то за ci прочитати вихідні повідомлення mi він не може ніяк, окрім як повним перебором mi.

А ось на приймальній стороні процес дешифрування все ж можливий, і допоможе нам у цьому збережене в секреті число d. Досить давно була доведена теорема Ейлера, окремий випадок якій стверджує, що якщо число n представимо у вигляді двох простих чисел p і q, то для будь-якого x має місце рівність (x (p-1) (q-1)) mod n = 1. Для дешифрування RSA-повідомлень скористаємося цією формулою.

зведемо обидві її частини в ступінь (-y): (x (-y) (p-1) (q-1)) mod n = 1 (-y) = 1.

Тепер помножимо обидві її частини на x: (x (-y) (p-1) (q-1) +1) mod n = 1 * x = x.

А тепер згадаємо як ми створювали відкритий і закритий ключі. Ми підбирали за допомогою алгоритму Евкліда d таке, що e * d + (p-1) (q-1) * y = 1, тобто e * d = (-y) (p-1) (q-1) +1 . А отже в останньому виразі попереднього абзацу ми можемо замінити показник ступеня на число (e * d). Отримуємо (xe * d) mod n = x. Тобто для того, щоб прочитати повідомлення ci = ((mi) e) mod n достатньо звести його до степеня d за модулем m:

((ci) d) mod n = ((mi) e * d) mod n = mi.

Насправді операції зведення в ступінь великих чисел досить трудомісткі для сучасних процесорів, навіть якщо вони виробляються за оптимізованим за часом алгоритмами. Тому зазвичай весь текст повідомлення кодується звичайним блоковим шифром (набагато більш швидким), але з використанням ключа сеансу, а от сам ключ сеансу шифрується як раз асиметричним алгоритмом за допомогою відкритого ключа одержувача і поміщається в початок файлу. 1.2. Алгоритм ЕльГамаля 1.2.1. Загальні відомості

Криптографія зі свого боку вели пошуки більш ефективних систем відкритого шифрування і в 1985 році Т.Ель-Гамаль (США) запропонував наступну схему на основі піднесення до степеня за модулем великого простого числа P .
Здається велике просте число P і ціле число A , 1

. Повідомлення представляються цілими числами M з інтервалу 1

. 1.2.2. Шифрування повідомлень

Протокол передачі повідомлення M виглядає наступним чином.

абоненти знають числа A і P ;

абоненти генерують незалежно один від одного випадкові числа:

Ka, Kb

задовольняють умові:

1

одержувач обчислює і передає відправнику число B, яке визначається послідовністю:

В = AKbmоd (P)

відправник шифрує повідомлення M і відправляє отриману послідовність одержувачу

C = M * BKamоd (P)

одержувач розшифровує отримане повідомлення

D = (AKa)-Kbmоd (P)

M = C * Dmоd (P)

У цій системі відкритого шифрування та ж ступінь захисту, що для алгоритму RSA з модулем N з 200 знаків, досягається вже при модулі < b> P з 150 знаків. Це дозволяє в 5-7 разів збільшити швидкість обробки інформації. Однак, у такому варіанті відкритого шифрування немає підтвердження автентичності повідомлень. 1.2.3. Підтвердження достовірності відправника

Для того, щоб забезпечити при відкритому шифруванні по модулю простого числа P також і процедуру підтвердження автентичності відправника Т. ЕльГамаль запропонував такий протокол передачі підписаного повідомлення M :

абоненти знають числа A і P ;

відправник генерує випадкове число і зберігає його в секреті:

Ka

що задовольняє умові:

1

обчислює і передає одержувачу число B, обумовлене последователньостью:

В = AKamоd (P)

Для повідомлення M (1

):

вибирає випадкове число L (1

) , що задовольняє умові

(L, P-1) = 1

обчислює число

R = ALmоd (P)

вирішує щодо S

M = Ka * R + L * Sm оd (P )

передає підписане повідомлення

[M , R , S ]

одержувач перевіряє правильність підпису

AM = (BR) * (RS) mоd (P)

У цій системі секретним ключем для підпису повідомлень є число X, а відкритим ключем для перевірки достовірності підпису число B. Процедура перевірки підпису служить також і для перевірки правильності розшифрування, якщо повідомлення шифруються. 1.3. Алгоритм Шаміра 1.3.1. Загальний опис

Ще один цікавий приклад використання піднесення до степеня за модулем великого простого числа P для відкритого шифрування запропонував А. Shamir (один з авторів RSA). Як і в системі ЕльГамаля повідомлення M представляються цілими числами з інтервалу 1 1.3.2. Передача повідомлень

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

абоненти знають числа P;

абоненти генерують незалежно один від одного випадкові числа:

Ka, Kb

задовольняють умові:

1

відправник обчислює значення і передає одержувачу:

C = MKamоd (P)

одержувач обчислює і передає відправнику число B, яке визначається послідовністю:

D = CKbmоd (P)

відправник анулює свій шифр і відправляє отриману послідовність одержувачу

E = D (X-1) mоd (P) E = DFamоd (P)

де:

Fa = Ka-1

одержувач розшифровує отримане повідомлення

M = EFbmоd (P)

де:

Fb = Kb-1 1.3.3. Приклад використання

Ця процедура ОШ може бути використана, наприклад, для таких "екзотичних" цілей як гра в карти по телефону.
Дійсно, якщо гравець A бажає "здати" гравцеві B, скажімо, 5 карт з 52 як при грі в покер, він зашифровує позначення всіх карт і передає їх гравцеві B:

Ca = MaKamоd (P)

де

I = 1,2, .., 52

Гравець B вибирає з них 5, зашифровує своїм ключем 22 і повертає гравцеві А:

Da = CaKbmоd (P)

де

I = 1,2 ..., 5

Гравець A знімає з цих 5 карт свій шифр і видає їх гравцеві B.
Гравець B розшифровує отримані карти:

Ma = EaFbmоd (P)

При цьому решта колоди C (6) ... C (52) тепер знаходиться у гравця B, але він не може розкрити ці карти, тому що вони зашифровані на ключі його партнера A. Інші процедури ігор робляться аналогічно. 1.4. Кpіптосістеми на основі еліптичних уpавненій

Еліптичні кpивий - математичний об'єкт, яке може опpеделен над будь-яким полем (кінцевим, дійсним, pаціональним або комплексним). У кpіптогpафіі зазвичай використовуються кінцеві поля. Еліптична кpивий є безліч точок (x, y), удовлетвоpяющее наступного уpавненію:

y2 = x3 + ax + b,

а також нескінченно віддалена точка. Для точок на кpивий досить легко вводиться опеpація складання, якому ігpает ту ж pоль, що і опеpація множення в кpіптосістемах RSA і Ель-Гамаля.

У pеальних кpіптосістемах на базі еліптичних уpавненій використовується уpавненіе

y2 = x3 + ax + b mod p,

де p - пpосто.

пpоблеми діскpетного логаpіфма на еліптичній кpивий полягає в наступному: дана точка G на еліптичній кpивий поpядка r (кількість точок на кpивий) і дpугих точка Y на цій же кpивий. Потрібно знайти єдину точку x таку, що Y = xG, тобто Y є х-я ступінь G. 2. Електронно-цифровий підпис 2.1. Загальні положення

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

- Гарантування істинності листа шляхом звірення підпису з наявним зразком;

- Гарантування авторства документа (з юридичної точки зору)

Виконання даних вимог грунтується на наступних властивостях підпису:

- підпис автентичними, тобто з її допомогою одержувачу документа можна довести, що вона належить підписує;

- підпис неподделиваема; тобто є доказом, що тільки та людина, чий автограф стоїть на документі, міг підписати цей документ, і ніхто інший.

- Підпис нестерпними, тобто є частиною документа і тому перенести її на інший документ неможливо.

- Документ з підписом є незмінним.

- Підпис незаперечна.

- Будь-яка особа, що володіє зразком підпису може упевнитися, що документ підписаний вледельцем підпису.

Розвиток сучасних засобів безпаперового документообігу, засобів електронних платежів немислимо без розвитку засобів докази автентичності та цілісності документа. Таким засобом є електронно-цифровий підпис (ЕЦП), яка зберегла основні властивості звичайного підпису.

Існує кілька методів посторенія ЕЦП, а саме:

- шифрування електронного документа (ЕД) на основі симетричних алгоритмів. Дана схема передбачає наявність у системі третьої особи - арбітра, що користується довірою обох сторін. Авторизацією документа в даній схемі є сам факт зашифрування ЕД секретним ключем і передача його арбітра.

- Використання асиметричних алгоритмів шифрування. Фактом підписання документа є зашифрування його на таємному ключі відправника.

- Розвитком попередньої ідеї стала найбільш распространенния схема ЕЦП - зашифрування остаточного результату обробки ЕД хеш-функцією за допомогою асиметричного алгоритму.

Крім перерахованих, існують й інші методи побудови схем ЕЦП

- групова підпис, неспірній підпис, довірена підпис і ін Поява цих різновидів обумовлено різноманітністю завдань, що вирішуються за допомогою електронних технологій передачі й обробки електронних документів. 3. Алгоритм DSA

У 1991 р. в США був опублікований проект федерального стандарту цифрового підпису - DSS (Digital Signature Standard, [DSS91], описує систему цифрового підпису DSA (Digital Signature Algorithm). Одним з основних критеріїв при створенні проекту була його патентна чистота.

Пропонований алгоритм DSA, має, як і RSA, теоретико-числовий характер, і заснований на криптографічного системі Ель-Гамаля у варіанті Шнорр. Його надійність заснована на практичній нерозв'язності певного окремого випадку завдання обчислення дискретного логарифма. Сучасні методи вирішення цього завдання мають приблизно ту ж ефективність, що і методи розв'язання задачі факторизації; в зв'язку з цим пропонується використовувати ключі довжиною від 512 до 1024 біт з тими ж характеристиками надійності, що і в с?? стеми RSA. Довжина підпису в системі DSA менше, ніж у RSA, і становить 320 біт.

З моменту опублікування проект отримав багато критичних відгуків, багато з яких були враховані при його доопрацюванні. Одним з головних аргументів проти DSA є те, що, в відміну від загальної задачі обчислення дискретного логарифма, її окремий випадок, використаний у даній схемі, мало вивчений і, можливо, має істотно меншу складність розтину. Крім того, стандарт не специфікує спосіб отримання псевдовипадкових чисел, що використовуються при формуванні цифрової підпису, і не вказує на те, що цей елемент алгоритму є одним з найбільш критичних з криптографічного стійкості.

Опції DSA обмежені тільки цифровим підписом, система принципово не призначена для шифрування даних. По швидкодії система DSA порівнянна з RSA при формуванні підпису, але істотно (в 10-40 разів) поступається їй при перевірці підпису.

Разом з проектом DSS опублікований проект стандарту SHS (Secure Hash Standard), що описує односпрямований хеш-функцію SHA (Secure Hash Algorithm), рекомендовану для використання разом з DSA. Хеш-функція SHA є модифікацією алгоритму MD4, добре відомого в криптографічного літературі. 3.1. Генерація ЕЦП

При генерації ЕЦП використовуються параметри трьох груп:

- загальні параметри

- секретний ключ

- відкритий ключ

Загальні параметри необхідні для функціонування системи в цілому. Секретний ключ використовується для формування ЕЦП, а відкритий - для перевірки ЕЦП. Спільними параметрами системи є прості цілі числа p , q , g , що задовольняють наступним умовам:

p : 2 ^ 511

<2 ^ 512

q: простий дільник числа (p-1), який задовольняє умові

2 ^ 159 <2 ^ 160

g: так званий генератор, що задовольняє

рівності g = h ^ ((p -1)/q ) mod p > 1 .

Парараметри p , q , g публікуються для всіх учасників обміну ЕД з ЕЦП.

Секретний ключ x випадково вибирається з діапазону [1, q] і тримається в секреті.

Відкритий ключ обчислюється: y = g ^ x mod p .

Також при описі даної схеми будуть використовуватися наступні позначення та доролнітельние параметри: m - вхідна повідомлення користувача для схеми з ЕЦП; k - випадкове число, що задовольняє умові 0

Процес створення ЕЦП складається з декількох етапів:

1.Вичісляется хеш-код повідомлення m h = H (m )

2.Із діапазону [1, q] випадковим чином вибирається значення k і обчислюється r = (g ^ k mod p ) mod q

3. Обчислюється S = (k ^ -1 (h + xr )) mod q , де k ^ -1 задовольняє умові

(k ^ -1 * k) mod q = 1

Значення r, s є ЕЦП повідомлення m та передаються разом з ним по каналах зв'язку. 3.2. Перевірка ЕЦП

Нехай прийнято повідомлення m1 і його підпис s1, r1.

Перевірка ЕЦП відбувається наступним чином:

- перевіряється виконань умов 0 < r 1 , 0 1 < q , і якщо хоча б одне з них порушений, підпис відкидається.

- обчислювати значення:

w = s1 ^ -1 mod q

u1 = (H (m1) w) mod q

u2 = ((r1/w) mod q

v = ((g ^ u1y ^ u2) mod p) mod q

- перевіряється рівність v = r1

Якщо останнє рівність виконується, то підпис приймається. У даному стандарті специфікується також процедура створення основних параметрів системи і проводиться доказ того, що якщо v = r1, то m1 = m, r1 = r, s1 = s. 4. Стандарт на процедури ЕЦП ГОСТ Р 34.10-94

Вітчизняним стандартом на процедури вироблення і перевірки ЕЦП є ГОСТ Р 34.10-94. Схема ЕЦП, запропонована в даному стандарті, багато в чому нагадує підпис у DSA.

Цифровий підпис є цілих два великих простих числа. Загальнодоступні параметри схеми ЕЦП (p, q, a) повинні задовольняти таким умовам:

p : 2 ^ 501

<2 ^ 512 або 2 ^ 1020 < p <2 ^ 1020

q: простий дільник числа (p-1), який задовольняє

умові 2 ^ 254 < q <2 ^ 256

a: 1

Секретний ключ x випадково вибирається з діапазону [1, q] і тримається в секреті.

Відкритий ключ обчислюється: y = a ^ x mod p. 4.1. Генерація ЕЦП

Процес створення ЕЦП складається з декількох етапів:

1.Вичісляется хеш-код повідомлення mh = H (m)

(хеш-функція, яка використовується в даному стандарті відповідно до

ГОСТ Р 34.10-94), якщо h (m) (mod p) = 0, то h (m) прісваевается значення 0 ... 02551

2.Із діапазону [1, q] випадковим чином вибирається значення k

3. обчислюється r = ( a ^ k mod p ) , r 1 = r (mod p ); якщо r1 = 0, слід повернутися до попереднього етапу і виробити інше значення k.

3. Обчислюється s = (xr 1 + kh (m )) (mod < b> p ) ; якщо s = 0, то необхідно виробити інше значення k.

Значення r1, s1 є ЕЦП повідомлення m та передаються разом з ним по каналах зв'язку. 4.2. Перевірка ЕЦП

Перевірка ЕЦП відбувається наступним чином:

- перевіряється виконань умов 0 < r , 0 < q , і якщо хоча б одне з них порушений, підпис відкидається.

- Обчислюється хеш-код даного повідомлення h = H (m); Якщо h (m) (mod p) = 0, то бітове подання h (m): 0 ... 02551

- Обчислюється значення v = (h (m )) ^ q -2 ( mod p ).

- Обчислюється значення z 1 = sv (mod p ); z 2 = (q -r 1) v (mod p ).

- Обчислюється значення u = (a ^ z1y ^ z2 (mod p)) (mod q )

- перевіряється рівність u = r 1

Якщо останнє раенство виконується, то підпис приймається. 5. Цифрові підписи, засновані на симетричних криптосистемах

На перший погляд, сама ця ідея може здатися абсурдом. Дійсно, загальновідомо, що так звана «сучасна», вона ж двухключевую криптографія виникла і почала швидко розвиватися в останні десятиліття саме тому, що ряд нових криптографічних протоколів типу протоколу цифрового підпису не вдалося ефективно реалізувати на базі традиційних криптографічних алгоритмів, широко відомих і добре вивчених на той час. Тим не менше, це можливо. І першими, хто звернув на це увагу, були родоначальники криптографії з відкритим ключем У. Діффі і М. Хеллман, що опублікували опис підходу, що дозволяє виконувати процедуру цифрового підпису одного біта за допомогою блочного шифру. Перш ніж викласти цю ідею, зробимо кілька зауважень про суть і реалізаціях цифрового підпису.

Стійкість будь-якої схеми підпису доводиться зазвичай встановленням Рівносильність відповідного завдання розкриття схеми якої-небудь іншого, про яку відомо, що вона обчислювально нерозв'язна. Практично всі сучасні алгоритми ЕЦП засновані на так званих «складних математичних завданнях »типу факторизації великих чисел або логарифмування в дискретних полях.

Однак, доказ неможливості ефективного обчислювального вирішення цих завдань відсутній, і немає жодних гарантій, що вони не будуть вирішені в найближчому майбутньому, а відповідні схеми зламані - як це сталося з «ранцевий» схемою цифровий підпису. Більше того, з бурхливим прогресом засобів обчислювальних техніки «межі надійності» методів відсуваються в область все більших розмірів блоку.

Лише кілька десятиліть тому, на зорі криптографії з відкритим ключем вважалося, що для реалізації схеми підпису 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. Одержувачу відомі всі використовувані при цьому величини.

Таким чином, функція перевірки підпису буде наступною:

.

Покажемо, що дана схема працездатна, для чого перевіримо виконання необхідних властивостей схеми цифрової підпису:

1. Неможливість підписати біт t, якщо невідомий ключ підпису. Дійсно, для виконання цього зловмиснику потрібно було б розв'язати рівняння Es (Xt) = Ct щодо s, що еквівалентно визначення ключа для відомих блоків шифрованого і відповідного йому відкритого тексту, що обчислювально неможливо через використання стійкого шифру.

2. Неможливість підібрати інше значення біта t, яке підходило б під задану підпис, очевидна: число можливих значень біта всього два і ймовірність виконання двох наступних умов одночасно пренебрежимо мала в просто в силу використання криптостійкості алгоритму:

E s ( X 0) = C 0,
E s ( X 1) = C 1.

Таким чином, запропонована Діффі і Хеллманом схема цифрового підпису на основі класичного блочного шифру володіє такою ж стійкістю, що і лежить в її основі блочний шифр, і при цьому дуже проста. Проте, у неї є два істотні недоліки.

Перший недолік полягає в тому, що дана схема дозволяє підписати лише один біт інформації. У блоці більшого розміру доведеться окремо підписувати кожен біт, тому навіть з урахуванням хешування повідомлення всі компоненти підпису - секретний ключ, перевірочна комбінація і власне підпис виходять досить великими за розміром і більш ніж на два порядки перевершують розмір підписуваного блоку. Припустимо, що в схемі використовується криптографічний алгоритм 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 -бітових блоків даних у n K-бітові Y = Pn ® nK (X), | X | = n, | Y | = nK. Визначимо рекурсивну функцію Rk «Односторонньої прокрутки» блоку даних T розміром n біт k раз (k і 0) за допомогою наступної формули:

де X - довільний несекретних n-бітовий блок даних, що є параметром процедури прокручування.

По своїй ідеї функція односторонньої прокручування надзвичайно проста, треба всього лише потрібне кількість разів (k) виконати наступні дії: розширити n-бітовий блок даних T до розміру ключа використаного алгоритму шифрування (nK), на отриманому розширеному блоці як на ключі зашифрувати блок даних X, результат зашифрування занести на місце вихідного блоку даних (T). За визначенням операція Rk (T) володіє двома важливими для нас властивостями:

1. Адитивність і комутативність за кількістю прокручування:

Rk + k '(T) = Rk' (Rk (T)) = Rk (Rk '(T )).

2. Однобічність або незворотність прокрутки: якщо відомо тільки деяке значення функції 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, навіть не володіючи ключем підпису:

(a) якщо T

(b) якщо 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-бітова група. Тоді розміри ключів підпису/перевірки і самої підписи збігаються і дорівнюють такій величині:

біт,