Цифровий підпис Ель Гамаля (EGSA. Інші з Інші. Робота № 516434

Цифровий підпис Ель Гамаля (EGSA

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Кафедра СКС

Інформація про роботу

Рік:

2011

Тип роботи:

Інші

Предмет:

Інші

Група:

СКС

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти та науки України Національний університет „Львівська політехніка” Кафедра СКС Доповідь №2 на тему: «Цифровий підпис Ель Гамаля (EGSA)» 1. Забезпечення аутентифікації даних. При обміні електронними документами каналами зв'язку виникає проблема аутентифікації як автора документа, так і самого документа. Це означає, що отримувач має бути впевненим, по-перше, в істинності автора, а по-друге, у відсутності змін в самому документі. У звичайних паперових документах ці проблема вирішується за рахунок того, що зміст документу та рукописний підпис автора жорстко пов'язані фізичним носієм даних (папером). В електронних документах на машинних носіях такого зв'язку немає. Метою аутентифікації електронних документів є їх захист від можливих видів зловмисних дій, до яких належать: •активне перехоплення - зловмисник, під'єднавшись до каналу зв'язку, перехоплює файли документів і змінює їх; •маскарад - абонент C надсилає документ абоненту B від імені абонента A; ренегатство - абонент A стверджує, що не надсилав документ абоненту B, хоч насправді надсилав; підміна - абонент B змінює отриманий або формує новий документ, після чого стверджує, що отримав його від абонента A; повтор - абонент C повторює від свого імені раніше переданий документ, який абонент A надсилав абоненту B. Один із найпростіших способів аутентифікації (підписування) електронних документів -використання шифрування. При цьому відправник А шифрує документ своїм секретним ключем і відправляє отримувачу Б. Отримувач Б дешифрує документ за допомогою відкритого ключа відправника А. Якщо це йому вдається, то документ вважається істинним. Якщо отримувач Б не зможе дешифрувати документ, то документ істинним не вважається. Такий спосіб має надзвичайно серйозний недолік, пов'язаний з тим, що він є неефективним для підписування документів значного обсягу. Саме тому для аутентифікації електронних документів, що передаються телекомунікаційними каналами зв'язку, використовується спеціально створюваний електронний цифровий підпис (ЕЦП). Функціонально ЕЦП аналогічний звичайному рукописному підпису і має такі властивості: •засвідчує, що підписаний документ отримано від особи, яка поставила свій підпис; •не дає можливості особі, яка поставила свій пидпис, відмовитись від підписаного документу; •є невід'ємною частиною даного документу і не може бути використаний для підписання іншого документу; •гарантує цілісність підписаного документу. Електронний цифровий підпис являє собою відносно невелику кількість додаткових цифрових даних, які передаються разом із підписаним текстом. Застосування ЕЦП має вигляд наступного кріптографічного протоколу: 1)для того документу M, який має бути підписаним, відправник А обчислює значення, так званої, односторонньої хеш-функції H = h(M); 2)хеш-значення H відправник А шифрує своїм особистим секретним ключем і отримуєчисло, яке вважається підписом документу; 3)зашифроване хеш-значення разом із документом M відправник А направляєотримувачу Б; 4)отримувач Б спочатку сам обчислює хеш-значення H отриманого документу, далі дешифрує отримане хеш-значення з використанням відкритого ключа відправника А, після чого порівнює обидва значення. Якщо два отриманих хеш-значення співпадають, то підпис відправника А вважається вірним, а сам документ M - істинним. Отже, учасники кріптографічного протоколу ЕЦП мають попередньо домовитись про використання певної кріптографічної системи, а також хеш-функції. 2. Односторонні хеш-функції. Хеш-функція h, яка використовується у протоколі ЕЦП, призначена для того, щоб стиснути підписуваний документ M довільної довжини до двійкового хеш-значення H = h(M) фіксованої довжини (декілька десятків біт). Завдяки цьому підписується не сам довгий документ, а його коротке хеш-значення, а довжина підпису стає фіксованою. Основні властивості хеш-функції: 1)хеш-значення H залежить від усього документу M надзвичайно складним способом, завдяки чому за значенням H неможливо відновити документ M; 2)хеш-значення H є чутливим до будь-яких, навіть незначних, змін у документі M (вставки, вилучення, перестановки тощо); 3)хеш-функція h(M) є необоротною, тобто підбір деякого фіктивного документу M' з тим же самим хеш-значенням H є задачею практично нерозв'язуваною; 4)ймовірність того, що хеш-значення двох різних документів співпадуть, є надзвичайно малою. Переважна більшість використовуваних хеш-функцій мають вигляд Hi= h(Mi, Hi-1) і працюють за наступним принципом: вони утворюють одне хеш-значення довжиною n біт із двох вхідних значень, кожне з яких теж має довжину n біт. Для застосування такої хеш-функції документ M має бути попередньо представлений у двійковій формі і розбитий на окремі блоки M, довжиною n біт кожний. Зміст указаних вхідних значень хеш-функції наступний: 1)перше вхідне значення являє собою черговий блок документу Mi ; 2)друге вхідне значення являє собою хеш-значення Hi.1 усіх попередніх блоків документу. При обчисленні хеш-значення для першого блоку Mi документу використовується деяке початкове хеш-значення H0, яке можна вибрати випадковим або фіксованим (наприклад, H0 = 0 - у найпростішому випадку). При цьому хеш-значення, обчислене при використанні останнього блоку документу, вважається хеш-значенням усього документу M. Правило утворення одного хеш-значення із двох вхідних залежить від типу хеш-функції. У найпростішому випадку тут може використовуватись додавання за модулем 2, тобто Hi = Mi Hi-1. Визначення кількості біт n для хеш-значення може здійснюватись на підставі значення модуля системи ЕЦП, а саме: кількість біт хеш-значення має бути на одиницю меншою кількості біт значення модуля системи ЕЦП. Розглянемо приклад. Відомо, що модуль системи ЕЦП 1910 = 100112. Кількість біт цього значення рівна 5. Виберемо кількість біт хеш-значення n = 4. Припустимо, що необхідно підписати наступний документ M: 29, 7, 11, 3, 20, 36. Необхідно знайти найпростіше хеш-значення для цього документу. Утворюємо двійковий образ документу: 11101, 111, 1011, 11, 10100, 100100. Суцільна послідовність біт має вигляд: 1110111110111110100100100. Доповнюємо кількість біт цієї послідовності до числа, кратного n = 4, за рахунок початку цієї ж послідовності і отримуємо: 1110 1111 1011 1110 1001 0010 0111. Таким чином, даний документ розбито на сім блоків довжиною 4 біт кожний. Тепер утворюємо послідовність хеш-значень: Остаточно, хеш-значенням усього документу M вважається значення H = 10002 = 810. 3. Алгоритм електронного цифрового підпису Ель Гамаля (EGSA). Надійний та зручний для реалізації на персональних комп'ютерах алгоритм цифрового підпису був розроблений у 1984 році американцем арабського походження Тахером Ель Гамалем. У 1991 році Національний інститут стандартів (НІСТ) США обґрунтував перед комісією Конгресу США вибір цього алгоритму як бази для відповідного національного стандарту. Найменування EGSA має походження від слів El Gamal Signature Algorithm (алгоритм цифрового підпису Ель Гамаля). Ідея EGSA базується на тому, що для практичної неможливості фальсифікації ЕЦП може бути використана практично нерозв'язувана задача дискретного логарифмування. Послідовно розглянемо алгоритм електронного цифрового підпису Ель Гамаля: 1)Відправник, який має підписати свій документ, вибирає деяке велике просте ціле число P. Це число є відкритим і передається усім отримувачам документів відправника. Реальні значення близькі до 21024 (=1038) Приклад. Відправник вибирає число P = 11. 2). Відправник вибирає також велике ціле число G, яке має задовольняти умовам 1 < G < P. Це число також є відкритим і передається усім отримувачам документів відправника. Реальні значення близькі до 2512 (=10154). Приклад. Відправник вибирає число G = 2. 3). Відправник вибирає ціле число X, яке має задовольняти умовам 1 < X< P. Це число є секретним ключем відправника для підписування документів. Приклад. Відправник вибирає секретний ключ X = 8. 4). Відправник обчислює число Y = GX mod P. Це число є відкритим ключем відправника, яке використовується отримувачами для перевірки його підпису. Це число також передається усім отримувачам документів відправника. Приклад. Відправник обчислює число Y = GX mod P = 28 mod 11 = 3. 5). Відправник обчислює хеш-значення H свого документу M. Кількість біт хеш-значення має бути на одиницю меншою кількості біт значення P -1. У загальному випадку хеш-значення H документу M відправника має задовольняти умовам 1 < H < (P - 1). Приклад. Відправник обчислює хеш-значення H свого документу M і отримує H = 5. Згадані умови стосовно кількості біт виконуються. Дійсно, значення H = 5 має 3 біта, а значення P - 1 = 10 має 4 біта. 6). Відправник вибирає випадкове ціле число K, яке має задовольняти умовам 1 < K < (P - 1). Крім того, числа K і P - 1 мають бути взаємно простими, тобто їх найбільший спільний дільник НСД (К, P -1) = 1. Це число також є секретним числом відправника для підписування його документу M. Приклад. Відправник вибирає випадкове ціле число K = 9. 7). Відправник обчислює ціле число a = GK modP. Це число є першою складовою електронного цифрового підпису його документу. 4.Робота в режимі підпису Ель-Гамаля Цифровий підпис служить для того щоб можна було встановити зміни даних і щоб встановити справжність сторони, яка підписалась. Одержувач підписаного повідомлення може використовувати цифровий підпис для доказу третій стороні того, що підпис дійсно зроблений відправляючою стороною. При роботі в режимі підпису передбачається наявність фіксованої хеш-функції h(.), значення якої лежить в інтервалі (1, р-1). Підпис повідомлень Для підписання повідомлення виконуються такі операції: а).Обчислюється дайджест повідомлення М:m=h(M): б)Вибирається випадкове число 1<до<р-1 взаємно просте с р-1 і обчислюється r=gK mod р. в)За допомогою розширеного алгоритму Евкліда обчислюється число s,яке задовольняє порівняння: m=хr+ks(mod р-1). г)Підписом повідомлення M є пара (r,s). Перевірка підпису Знаючи відкритий ключ (р, g, у), підпис (r, s) повідомлення M перевіряється наступним чином: а)Перевіряється здійснимість умов: 0 <r <р і 0 <s <р-1. Якщо хоча б одна з них не виконується, то підпис вважається невірним. б).Обчислюється дайджест m=h(M). в)Підпис вважається вірним, якщо виконується порівняння: yrrs=gm (mod p). Головною перевагою схеми цифрового підпису Ель-Гамаля є можливість виробляти цифрові підписи для великого числа повідомлень з використанням тільки одного секретного ключа. Щоб зловмисникові підробити підпис, йому потрібно вирішити складні математичні завдання з перебуванням логарифма в полі Zp. Коментарі: • Випадкове число k має одразу після обчислення підпису знищуватися, тому що якщо зловмисник знає випадкове число k і сам підпис, то він легко може знайти секретний ключ за формулою: x=(m-ks)r-1 mod (p-1) і повністю підробити підпис. Число k повинно бути випадковим і не повинно дублюватися для різних підписів, отриманих при однаковому значенні секретного ключа. • Використання згортки m = h (M) пояснюється тим, що це захищає підпис від перебору повідомлень по відомим зловмисникові значенням підпису. • Цифровий підпис Ель-Гамаля став прикладом побудови інших підписів, схожих за своїми властивостями. В їх основі лежить виконання порівняння: yA*rB=gC(modp), в якому трійка (A, B, C,) приймає значення однієї з перестановок ± r, ± s і ± m при якомусь виборі знаків. Наприклад, вихідна схема Ель-Гамаля виходить при A = r, B = s, C = m. На такому принципі побудови підпису зроблені стандарти цифрового підпису США і Росії. В американському стандарті DSS (Digital Signature Standard), використовується значення А = r, В =-s, C = m, а в Російському стандарті: А =-х, В =-m, C = s. 5. Висновок Порівняння деяких алгоритмів: Алгоритм Ключ Назва Криптостійкість, MIPS Примітки RSA До 4096 бит Шифрування і підпис 2,7'1028 для ключа 1300 біт Заснований на складності задачи факторизації великих чисел; один з перших асиметричних алгоритмів. Включений до багатьох стандартів ElGamal До 4096 бит Шифрування і підпис При одинаковій довжині ключа криптостойкість рівна RSA, тобто 2,7'1028 для ключа 1300 біт Заснований на складності задачи обрахунку дискретних логарифмів в кінцевому полі; дозволяє швидко згенерувати ключи без зниження стійкості. Використовується в алгоритмі цифрового підпису DSA-стандарту DSS DSA До 1024 бит Тільки підпис Заснований на складності задачи дискретного логарифмування в кінцевому полі; прийнятий в якості держ. стандарту США; застосовується для секретних і несекретних комунікацій; розробником є АНБ. ECDSA До 4096 бит Шифрування і підпис Криптостойкість і швидкість роботи вище, чим у RSA Сучасний напрямок. Розробляється багатьма математиками Забезпечення аутентифікації даних. Односторонні хеш-функції. Алгоритм електронного цифрового підпису Ель Гамаля (EGSA). Робота в режимі підпису Ель Гамаля Висновок Список використаної літератури Список використаної літератури 1. Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В Основы криптографии. 2. Б. А. Фороузан Схема цифровой подписи Эль-Гамаля (http://www. intuit.ru/department/security/ manencryptk/3/4.html#sect22) // Управление ключами шифрования и безопасность сети (http://www. intuit.ru/department/security/manencryptk/) / Пер. А. Н. Берлин. — Курс лекций. 3. Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone 11.5.2 The ElGamal signature scheme (http://www. cacr. math.uwaterloo.ca/hac/about/chap11.pdf) // Handbook of applied cryptography (http://www. cacr. math.uwaterloo. ca/hac/). 4. Схема Эль-Гамаля Источник: http://ru.wikipedia.org/w/index.php?oldid=33208732 Редакторы: A5b, Alt-sysrq, Andrew89, Atr2006, Dj of Realiry, Gdn, Gistereziz, Insider, Koliz, LeX4051, Lonelind, MarLex, Maxal, Mothlike, Netch, Nibumbum, Obersachse, Oort, SysoevIY, Velikodniy, Vlad2000Plus, Vlsergey, 43 анонимных правок

Інші Інші

12.02.2012 18:02-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись