> mod n = 4545
Алгоритм Ель-Гамаля
Схема Ель-Гамаля (Elgamal) - криптосистема, запропонована в 1984 році. Схема Ель-Гамаля лежить в основі стандартів електронного цифрового підпису в США та Росії. p> Генерація ключів
Генерується випадкове просте число p довжини n.
Вибирається довільне ціле число g, що є первісним коренем за модулем p.
Вибирається випадкове число x з інтервалу (1, p), взаємно просте з p-1.
Обчислюється
Відкритим ключем є трійка (p, g, y), закритим ключем - число x.
Робота в режимі шифрування виглядає наступним чином:
шифрується повідомлення М
Вибирається випадкове секретне число k, взаємно просте з p - 1. p> Обчислюється a = G k ( mod p), b = y k M (mod p), де M - вихідне повідомлення. p> Пара чисел (a, b) є шифротекст.
Довжина шіфротекста у схемі Ель-Гамаля довше вихідного повідомлення M вдвічі.
Розшифрування повідомлення здійснюється наступним чином
Знаючи закритий ключ x, вихідне повідомлення можна обчислити з шіфротекста (a, b) за формулою:
В
і
Режим підпису повідомлення
При роботі в режимі підпису передбачається наявність фіксованою хеш-функції h, значення якої лежать в інтервалі (1, p - 1). br/>
Підпис повідомлень
Для підпису повідомлення M виконуються наступні операції:
Обчислюється дайджест повідомлення M: m = h (M).
Вибирається випадкове число 1
За допомогою розширеного алгоритму Евкліда обчислюється число s, яке задовольняє порівнянні:
В
Підписом повідомлення M є пара (r, s).
Перевірка підпису
Знаючи відкритий ключ (p, g, y), підпис (r, s) повідомлення M перевіряється наступним чином:
Перевіряється здійснимість умов: 0
Обчислюється дайджест m = h (M).
Підпис вважається вірною, якщо виконується порівняння:
.
DSS (Digital Signature Standard) цифровий підпис
Алгоритм:
вибирається просте число q приблизно в 160 біт (для цього використовуються генератор випадкових чисел і тест на простату)
вибирається інше просте число р, порівнянне з 1 по модулю q розміром приблизно в 512 біт
вибирається породжує елемент, для цього обчислюється для випадкового цілого g 0 , якщо g в‰ 1, то він і буде породжує елементом
вибирається секретний ключ як випадкове ціле число х з діапазону 0
Приклад. Нехай А хоче підписати повідомлення. Спочатку А приймає своєму ВІД хеш функцію і отримує ціле число h з діапазону 0 k спочатку обчислюється за модулем р, а результат приводитися по меншому простому модулю q. Нарешті, А знаходить таке ціле s, що. Пара (r, s) відрахувань по модулю q є її підписом. p> Щоб перевірити підпис, одержувач У обчислює і. Потім він обчислює. Якщо результат порівнянний з r за модулем q, то підпис вважається справжньою.
Література
1. Дж. Андерсон, Дискретна математика і комбінаторика, М.: Вільямс - 2003. p> 2. Н. Коблиц, Курс теорії чисел і криптографії, М.: наукове вид-во ТВП, 2001. p> 3.
