| Головна » Статті » Інформатика | [ Додати статтю ] |
Цифрові підписи
|
Цифрові підписи Цифрові підписи є електронними відповідниками традиційних підписів. Власти-вості, що їх повинні задовольняти цифрові підписи, такі: 1. лише особа А може створити підпис особи А (підробка підпису не може бути реалізованою); 2. можливість однозначно ствердити, що цифровий підпис зроблений саме під конкретним документом (копіювання підпису з одного документа на інший не може бути реалізованим). Звідси випливає, що цифрові підписи можуть гарантувати набагато вищий рівень безпеки, ніж традиційні. Найпростіший спосіб реалізації цифрових підписів полягає у дотриманні такого протоколу. Нехай kD - приватний ключ особи А. Одночасно є відомими відповідний до ключа kD публічний ключ kЕ і асиметричний алгоритм, до якого належать ці ключі. Підписують документ М так: особа А утворює криптограму з документа М за допомогою ключа kD. Отри- ману криптограму особа А публікує як підпис; оригінальний документ пересилається разом з підписом; абонент, який хоче перевірити підпис особи А, перетворює криптограму за до-помогою ключа kЕ. У такий спосіб він отримує текст, який підписала особа А. Схема має ту ваду, що цифровий підпис є надто довгим. Проте маємо гарантію, що підпис не може бути перенесений на інші документи. У розглянутому способі можна виділити три окремі етапи. Початковий етап. Визначають усі необхідні параметри, за допомогою яких бу-дуть утворюватися підписи. Утворення підпису. Виконуються обчислення, під час яких утворюється послі-довність, що є підписом конкретного документа. Верифікація підпису. Перевіряють як автентичність підпису автора, так і автен-тичність підписаного документа. Верифікація має вигляд тесту, який витримує лише справжній підпис. Приклад 6.1. Нехай р = 59 і q = 71. Тоді п = 4189 і ф(п) = 4060. Вибираємо є = 1229. Обчислюємо за допомогою алгоритму Евкліда НСД (1229, 4060) = 1. Одночасно обчислюємо d= 1229-1 mod 4060 = 849. Згенеровано ключі алгоритму RSA: 1229, 4189 - публічний ключ, 849 - приватний ключ. Що робить користувач А, коли хоче надіслати особі В повідомлення Перерахуйте сто тисяч ТОВ Роги і копита і додати до нього цифровий підпис? (Цифрове зобра-ження цього повідомлення, ігноруючи пропуски між словами, має вигляд 19062006200025231322062122182210213227220918022018031011141819102200). Розбиває повідомлення на блоки по чотири цифри з огляду на значення модуля п: 1906 2006 2000 2523 1322 0621 2218 2210 2132 2722 0918 0220 1803 1011 1418 1910 2200. Використовуючи свій приватний ключ d і число п, обчислює: сторона А пересилає стороні В разом з повідомленням:* Для перевірки цифрового підпису абонент В використовує публічний ключ є = 1229 абонента А: Як бачимо, після застосування до прийнятого цифрового підпису публічного ключа абонента А абонент В отримав повідомлення, що збігається з прийнятим пові-домленням. Тому абонент В робить висновок, що отримані повідомлення й цифровий підпис справді належать абоненту А. Хешувальні функції Хешувальною (вкорочувальною) функцією (hash-function) називають процедуру перетворення інформації, що відображає початкову послідовність бітів довільної дов-жини, в послідовність бітів фіксованої довжини. Нагадаємо (див. 1.2.4), що Л є однонапрямленою хешувальною функцією, якщо виконуються такі умови: для кожного тексту X легко обчислити значення h(X); h(X) має однакову довжину для всіх текстів X (тому довжина h(X) не дає жодної інформації про текст X); 3) практично неможливо для заданого У знайти таке X, що h(X) = Y. Послідовність h{X) повинна бути досить довгою для того, щоб систематичний пошук X був практично неможливим. Коли значення хешувальної функції складається з 128 бітів, то маємо 2128 можливих варіантів. Зазначимо, що суттєво меншого вкорочення досягти неможливо, оскільки для до-вільної хешувальної функції, що вкорочує вхідну послідовність до 64 бітів, цілком реально знайти колізію методом дня народження. Хешувальні функції повинні задовольняти три головні вимоги: за відомим значенням функції h(X) повинно бути неможливо (дуже складно в обчислювальному сенсі) знайти її аргумент X. Таку функцію називають стій-кою в сенсі обернення; для заданого аргументу X повинно бути неможливим знайти такий інший ар-гумент Х1, що h{X) - h(X1). Таку функцію називають стійкою в сенсі обчислення колізій; з погляду практичного застосування алгоритми обчислення хешувальних функцій повинні бути швидкими, а ще ліпше - бути оптимізованими під кон-кретне апаратне обчислювальне середовище. У контексті криптографічних застосувань ці функції можна використати у разі зберігання паролів (гасел); цифрових підписів; засвідчення документів. Пункти стосовно цифрових підписів та засвідчення документів буде розглянуто в розділах 6, 7, а тут розглянемо пункт, що стосується зберігання паролів. Одна із широко вживаних у такому випадку технік є зберігання не паролів, а зна-чень певної хешувальної функції h на паролях: користувач А подає свій пароль х; операційна система обчислює h(x) і порівнює зі значенням, записаним у від- повідній області для А; саме значення х в той же час усувається з пам'яті процесора;* якщо значення збігаються, то відкривається сесія користувача А. Словникова атака є найпростішим методом розкриття паролів в операційних сис-темах. Атака має на меті не відшукання пароля певного користувача, а якогось пароля, використаного в цій системі. Це є так звані слабкі паролі (дати народжень, імена тощо). Атака відбувається так: спочатку обчислюють значення функції А для слів з великого словника, який охоплює слова з різних мов, географічні й власні назви. Крім того, добре увес-ти в словник слова, записані з невеликими змінами або помилками. Список цих значень можна заготувати наперед; копіюють область, яка містить значення функції h для паролів користувачів (у багатьох системах вона доступна для читання); на власному комп'ютері порівнюють зчитані та обчислені значення. Відшукавши відповідну пару, можна ідентифікувати пароль одного користувача. З метою захисту паролів від атаки діють так. Для кожного користувача А утво-рюють запис, який складається з компонентів: випадково вибраної послідовності rА сталої довжини (зокрема, для операцій- ної системи UNIX ця довжина дорівнює 12 бітів); значення хешувальної функції для тексту, утвореного з пароля користувача А та послідовності rА. Наприклад, якщо послідовність rА має 12 бітів, то відповідний словник повинен мати список 212 додаткових значень для кожного пароля. Варіант хешувальної функції з ключем називають кодом достовірності. Як-що h - хешувальна функція з ключем К, то код достовірності повідомлення X дорівнює h(XK), де ХК- об'єднання текстів X і К. Той факт, що h(XK) отримано справді з X, може перевірити лише той, хто має ключ К. Код достовірності в криптографії аналогічний до поняття контрольної суми, яке вводять під час розгляду проблем завадостійкого коду-вання. Контрольну суму і код достовірності долучають до повідомлення в разі його пе-ресилання: суму - для того, щоб перевірити, чи повідомлення не було спотворене внаслідок фізичних завад у каналі зв'язку, а код, - щоб перевірити, чи повідомлення на шляху до адресата не було змінене зловмисником. Практичні хешувальні алгоритми Прикладом хешувальної функції може бути функція h, збудована на базі системи RSA. Якщо довжина тексту X не перевищує довжини повідомлень, які можна шифру-вати цією системою, то h(X) - RSA(X). Довші повідомлення спочатку розбивають на блоки X = X1.. Хl-1Xl відповідної довжини, а тоді обчислюють значення хешувальної функції: На практиці, проте, використовують швидші з погляду обчислення хешувальні функції, які вважають безколізійними. Усі такі функції вкорочують вхідний текст до 128 або до 160 біт. Узагальнена схема обчислення хешувальної функції показана на рис. 5.1. У зображеній схемі початкове повідомлення завжди доповнюється до довжини, кратної кількості бітів V значення хешувальної функції, яку обчислюють. З доповненого повідомлення послідовно беруть V-бітові блоки і для кожного з них виконують певне перетворення, результати яких накопичуються й дають бажану хешувальну функцію. Алгоритм MD5 Сім'я алгоритмів обчислення хешувальної функції MD (Massage Digest Algorithm; кроковий узагальнений алгоритм) була розроблена Р.Райвестом. Вона охоплює алгоритми MD2, MD4, MD5, які незначно відрізняються один від одного. Найширше використовують сьогодні алгоритм MD5, запропонований 1991 р. Його детально опи-сано далі. Алгоритм перетворює вхідне повідомлення довільної довжини в стиснутий образ довжиною 128 бітів. На початку вхідні тексти завжди перетворюються в послідовності, довжина яких кратна 512 бітам. Для цього до двійкового зображення вхідних даних додають біт, що дорівнює одиниці, й таку кількість нульових бітів, щоб загальна кількість бітів була на 64 менша від числа, кратного 512. Потім дописують 64 біти, які відповідають довжині вхідного повідомлення в двійковому зображенні. У випадку, коли довжина повідомлен-ня понад 2м, використовують лише 64 молодші біти довжини. Для обчислення хешувальної функції вхідне повідомлення розбивають на блоки по 512 бітів кожний. Кожен блок М, відповідно, розбивають на шістнадцять 32-бітових блоків Mj, (j = 0, 1, ..., 15). Опрацювання одного блока М відбувається за чотири цикли, кожен з яких охоплює 16 кроків. Кожен цикл використовує такі побітові операції: сума за модулем 2 (по-значають знаком ), диз'юнкція (знак v), кон'юнкція (позначають крапкою або відсут-ністю знака між змінними), інверсія (позначають рискою зверху над змінною). Ці операції виконують над відповідними бітами 32-бітових блоків X, Y, Z і визна-чають функції: За допомогою функції F визначають процедуру FF: де Mj означає j 32-бітовий блок вхідної послідовності; "+" - додавання за модулем 232 відповідних 32-бітових чисел; Shs - операцію циклічного зсуву праворуч на s позицій; ti, дорівнює цілій частині числа 232 |sin і|, наведеного у двійковому розвиненні. Для задания процедур GG, НН, II функцію F заміняють, відповідно, на функції G, Н,І. З метою накопичення значень хешувальної функції алгоритм використовує регістри а, b, с, d, які зберігають 32-бітові числа, їхні початкові значення, наведені в шістнадцятковій системі числення, є такими: а = 67452301, b = efcdab89, с = 98badcfe, d = 10325476. Цикл 1. Послідовно виконують такі 16 кроків: Кожен раз порядок регістрів a, b, c, d зсувається циклічно на одну позицію пра-воруч. Крім того, аргументи .у (кількість позицій циклічного зсуву) утворюють таку послідовність: 7, 12, 17, 22, 7, 12,... Цикл 2. Відбувається подібно до циклу 1. Однак замість процедури FF виконують процедуру GG; замість послідовності 7,12,17,22 використовують послідовність 5, 9, 14, 20. Крім того, i-й виклик 0=1,2, ..., 16) процедури GG використовує t16+,- за-мість ti, та М1+5i mod 16 замість Mi. Цикл 3. Відбувається з аналогічними змінами: використовують процедуру НН; послідовність 4, 11, 16, 23, а також t32+i та M5+3i mod 16 під час і-го (і - 1, 2,..., 16) виклику процедури НН. Цикл 4. Використовують процедуру //; послідовність 6, 10, 15, 21, а також f48+i та M3+7imod16 під час i-го (і =1,2,..., 16) виклику процедури //. Остаточним значенням хешувальної функції є послідовність із 128 бітів, яку отримують об'єднанням (конкатенацією) вмісту регістрів a b c d. Алгоритм SHA-1 Алгоритм SHA-1 (Secure Hash Algorithm; безпечний хешувальний алгоритм) прийнятий 1992 р. як стандарт у США. Він ґрунтується на тих самих принципах, що й сім'я алгоритмів MD. Алгоритм SHA-1 перетворює послідовності довжини, кратної 512 бітам, у стиснуту 160-бітову послідовність. У цьому разі вхідні тексти перетворюються в послідовності, довжина яких кратна 512 бітам. Це виконується так само, як і в алгоритмі MD5, додаванням одиниці, потрібної кількості нулів та 64-бітової довжини повідомлення. Вхідний текст має вигляд M = M1,M2, ...,МN (N 512-бітових блоків), де кожен блок Mi, має шістнадцять (Wo, W1 ..., Wl5) 32-бітових слів. Алгоритм використовує регістри a, b, c, d, є, які зберігають 32-бітові числа. їхні початкові значення в шістнадцятковій системі такі: а, b, с, d такі ж, як і в алгоритмі MD5, а є = c3d2elf0. Один цикл (на вхідному блоці довжини 512) описують так: де значенняКi, наведені в шістнадцятковій системі, такі: Функція ft, визначає32-бітове значення: та У кінці одного циклу отримують значення а, b, с, d, e, які додають до відповідних їм початкових значень, і переходять до опрацювання наступного блока Мi. Значення хешувальної функції є послідовністю бітів конкатенації остаточних зна-чень у регістрах a b с d e (160 бітів). Алгоритм RIPEMD-160 Алгоритм RIPEMD-160 (і його модифікації RIPEMD-128 і RIPEMD-160) створений за європейським проектом RIPE (Race Integrity Primitives Evaluation; швидке визна-чення примітивів цілісності) для використання поза США. Основою для цього алгорит-му взято алгоритм MD4. RIPEMD-160 перетворює послідовності довільної довжини в стиснуті 160-бітові послідовності. Головні операції в цьому алгоритмі: додавання за модулем 232, циклічний зсув, а також побітові операції: сума за модулем 2, диз'юнкція, кон'юнкція, інверсія. У табл. 5.1 наведено порівняльні характеристики швидкостей програмної реаліза-ції різних алгоритмів хешування. Генерування коротких підписів Ідеєю, яка дає змогу генерувати короткі підписи, є підписування замість самого документа М деякого значення Н(М), де Н є однонапрямленою хешувальною функцією. У цьому разі досягається додатковий ефект: підпис можна наводити, не оприлюднюючи самого змісту документа. Підписи, утворені за допомогою алгоритму RSA Сьогодні підписування за допомогою алгоритму RSA є одним із найпопулярніших методів генерування коротких підписів. Це підписування виконують так. Для документа М обчислюють значення Н(М), де Я є фіксованою хешувальною функцією. Сторона Л шифрує Н(М) за допомогою свого приватного ключа, викорис-товуючи алгоритм RSA. Отримана криптограма - це цифровий підпис сторони А під до-кументом М. Перевірка підпису сторони А потребує дешифрування цього підпису публічним ключем сторони А. Після дешифрування перевіряють, чи в результаті отримано Н(М). Цифровий підпис Епь-Гамаля Початкові умови. Вибирають просте число р та велике число g : 1 < g < р - 1. В ідеальному випадку g є твірною в Zp*. Кожен користувач А вибирає випадкове число а<р- 1, обчислює h = g mod p та виставляє g,p,h як публічний ключ. У цьому разі число а є приватним ключем особи А. Генерування підпису. Особа А виконує підписування конкретного документа М так: вибирає число r, яке взаємно просте з р - 1; обчислює S1 =gr mod p; обчислює r’ = r-1 mod (p - 1) (оскільки НСД(r, р - 1) = 1, то існує таке r’, що r- r'=1 mod(p- 1)); обчислює s2 = (М – as1)- r' mod (p - 1), оскільки виконується порівняння М = (as1 + rs2) mod (p - 1); подає (s1, s2) як підпис для документа М. Верифікація підпису. Особа В перевіряє виконання порівняння gM = hs1gs2 (mod p). Зазначимо, що на підставі малої теореми Ферма Цифровий підпис Ель-Гамаля має той недолік, що складається з двох чисел тієї ж величини, що й число р. Оскільки розкриття таких підписів ґрунтується на розв'язу-ванні задачі дискретного логарифмування за модулем р, то необхідне використання ве-ликих чисел р, наприклад з 1024 бітами у двійковому зображенні. У цьому випадку цифровий підпис Ель-Гамаля складатиметься із 2048 бітів. Цифровий підпис Шнорра Початкові умови. Вибирають велике просте число р таке, що р-1 має досить великий простий дільник q (рекомендованими є р > 2512, q > 2140). Також вибирають таке число h 1, що hq = l(mod p). Параметри р, q, h виставляють публічно. Кожен користувач А вибирає випадкове число 1 < а < р - 1 та обчислює число v =(hq)-1 mod p. Зазначимо, що в цьому разі виконується порівняння ha v = 1(mod p). Сторона А виставляє число v як публічний ключ, а число а є її приватним ключем. Генерування підпису. Особа А виконує підписування конкретного документа М так: вибирає випадкове число 1 < r < q-1 обчислює X = hr mod p; обчислює S1 =f(MX), де f є деякою хешувальною функцією, MX означає конкатенацію М і X в один текст; обчислює s2 = (r + as1 )mod q подає (s1, s2) як підпис для документа М. Верифікація підпису. З метою перевіряння підпису особа В виконує такі дії: обчислює Z = hs2vs1 modр; якщо s1 =f(MZ), то підпис є справжнім. Коректність підписування ґрунтується на тому факті, що Z-X. Справді, вико-нуються такі рівності: Алгоритм цифрового підпису DSA Розглянемо алгоритм цифрового підпису DSA. (Digital Signature Algorithm). О Початкові умови. Вибирають такі числа: просте число р з L бітами в двійковому зображенні, де 512<L<1024 і 64IL; число q, яке є дільником числа р - 1 зі щонайменше 160 бітами у двійковому зображенні; елемент h з множини Zp*, який має порядок q; випадкове число а, де а < q число b = ha(mod p). Число а є приватним ключем алгоритму DSA, який слугує для утворення під-писів. Число b є публічним ключем, який відповідає числу а. Параметри р, q, h ви-ставляють публічно. Генерування підпису. Власник ключа а підписує документ М в такий спосіб: вибирає випадкове число 1 < r < q — 1; обчислює r' = r-1 mod q; обчислює s1 = (hr mod p) mod q; обчислює s2 =r’ (f(M)) + as1) mod q; подає пару (s1, s2) як підпис для документа М. Зазначимо, що алгоритм DSA використовує хешувальну функцію SHA: ДМ) = SHA(M), що перетворює вхідну послідовність у послідовність довжини 160 бітів. Верифікація підпису. З метою перевіряння підпису особа В виконує такі обчис-лення: обчислює s' = 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. Верифікація підпису. З метою перевіряння особою А підпису у, утвореного осо-бою В під документом М, сторони А і В виконують такі кроки: А вибирає два випадкові натуральні числа 0 < е1, е2 < q А обчислює с (уe1 be2 )mod p і надсилає число с особі В; В обчислює z х-1 mod q та d сz mod p і надсилає число d особі A; А перевіряє, чи виконується порівняння d(Мe1аe2)mod p. Зазначимо таке: якщо особа В справді створила підпис, то | |
| Переглядів: 1164 | |
| Всього коментарів: 0 | |