де М-вихідне повідомлення;

(а, b) –шифротекст;

р- випадкове просте число;

х- закритий ключ;

Можно перевірити, за формулою (2.1.6)

, (2.1.6)

де М-вихідне повідомлення;

а – шифротекст;

р, - відкриті ключі;

х- закритий ключ;

k - випадкове ціле число.

Тому за формулою (2.1.7)

, , (2.1.7)

де, М-вихідне повідомлення

(а, b) – шифротекст;

р, - відкриті ключі;

х- закритий ключ;

k- випадкове ціле число.

2.2 Електронний цифровий підпис по Ель-Гамалю

Формування і перевірка підпису відбувається за етапами.

1.Генерується випадкове просте число p довжини n бітів.

2. Вибирається випадковий примітивний елемент поля Z_p.

3. Вибирається випадкове ціле число x таке, що 1< x < p-1

4. Обчислюється y, за формулою (2.2.1)

(2.2.1)

- випадковий примітив поля;

k- випадкове ціле число;

p- випадкове просте число довжини n бітів;

5. Відкритим ключем є трійка (p, , y ), закритим ключем – число x.

Цифровий підпис небхідний для того щоб можна було встановити зміни даних, і встановити справжність підписанта. Одержувач підписаного повідомлення може використовувати цифровий підпис для підтвердження третій стороні того, що підпис дійсно зроблено відправленою стороною. При роботі в режимі підпису передбачається наявність фіксованої хеш-функції h, значення якої лежать в інтервалі (1, p-1). Схема підпису представлена на рис. 2.2.1

Рисунок 2.2.1– Цифровий підпис за схемою Ель-Гамаля

Для підпису повідомлення M виконуються наступні операції:

1. Обчислюється хеш повідомлення за формулою (2.2.2)

M: m = h (M) (2.2.2)

2. Обирається випадкове число k, в інтервалі 1 <k <p-1, взаємна просте з p-1 і обчислюється за формулою (2.2.3)

(2.2.3)

3. Знаходимоо число s з рівняння (2.2.4)

, (2.2.4)

Тобто, s за формулою (2.2.5)

(2.2.5)

де m-хеш сума повідомлення;

х- закритий ключ;

r- підпис;

k- випадкове число;

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

4. Підписом повідомлення М є пара (r, s). Адресату відправляється трійка (M, r, s)

Перевірка підпису

Знаючи відкритий ключ (p, , y), підпис (r, s) повідомлення M перевіряється наступним чином:

1. Перевіряється здійснимість умов: 0 <r <p та 0 <s <p-1 .Якщо хоча б одне з них не виконується, то підпис вважається неправильною.

2. Обчислюється хеш повідомлення за формулою (2.2.6)

(2.2.6)

3. Розраховується ,

4. Підпис вважається вірним, якщо виконується порівняння:

, (2.2.7.)

де m-дайджест повідомлення;

r- підпис;

k- випадкове число;

р, - відкриті ключ;

s- число.

2.3 Стандарт dss

У 1991 р NIST (National Institute of Standards and Technology) запропонував для обговорення проект стандарту ЕЦП DSS (Digital Signature Standard), який використовує алгоритм DSA (Digital Signature Algorithm). Стійкість даного алгоритму заснована на складності рішення задачі дискретного логарифмування в мультиплікативної групі простого поля.

Підхід DSS використовує алгоритм, який розроблявся для використання тільки в якості цифрового підпису. На відміну від RSA, його не можна використовувати для шифрування або обміну ключами. Проте, це технологія відкритого ключа. Нижче приведено схему створення підпис за допомогою DSS, рисунок 2.3.1

Рисунок 2.3.1 – Схема створення підпису за допомогою DSS

Підхід DSS використовує сильну хеш-функцію. Хеш-код є входом функції підпису разом з випадковим числом k, створеного для цього підпису. Функція підпису також залежить від закритого ключа відправника KR_a і параметрів, відомих всім учасникам. Параметри складаються з глобального відкритого ключа KU_G. Результатом є підпис, що складається з двох компонент, позначених як s і r.

Для перевірки підпису одержувач також створює хеш-код отриманого повідомлення Який з підписом є входом в функцію верифікації. Функція верифікації залежить від глобального відкритого ключа KU_G і від відкритого ключа відправника KU_a. Виходом функції верифікації є значення, яке має дорівнювати компоненті r підписи, якщо підпис коректна. Функція підпису така, що тільки відправник, що знає закритий ключ, може створити коректний підпис.

2.3 Алгоритм DSA

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

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

Разом з проектом DSS опублікований проект стандарту SHS що описує односпрямований хеш-функцію SHA, рекомендовану для використання разом з DSA. Хеш-функція SHA є модифікацією алгоритму MD4 (Message Digest 4), добре відомого в криптографічного літературі.

Формування та перевірка підпису DSА здійснюється за етапами.

1. Відправник А повідомлення Μ надає широкому колу абонентів (одержувачів його повідомлень) доступ до таких опцій:

• p - модуль, який є простим числом 2L-1 <p <2L, де L є бітової довжиною p;

• q - простий дільник числа p-1, де 2N-1 <q <2N, а N є бітової довгою q;

• - генератор підгрупи порядку q mod p, такий, що б 1 < <p;

• x - секретний ключ 0 <x <q

• y - відкритий ключ, який обчислюється за формулою (2.3.1)

(2.3.1)

• k - секретне число, яке є унікальним для кожного повідомлення

2. Вироблення електронного цифрового підпису

Підпис повідомлення М складається з пари чисел r і s, які обчислюються за формулою (2.3.2)

, (2.3.2)

де, r, s- пара чисел, k - секретне число, яке є унікальним для кожного повідомлення, p - модуль, який є простим числом, - генератор підгрупи порядку q mod p.

(2.3.3)

Підпис (r, s) передається разом з повідомленням М одержувачу

3. Верифікація ЕЦП:

Верифікація- перевірка достовірності даних користувача. Процес верифікації описується наступним чином:

• одержувач перевіряє виконання умов 0 <r '<q і 0 <s' <q; в разі невиконання умов підпис відкидається

• якщо дві умови першого кроку задовольняються, виробляються такі обчислення за формулою (2.3.4), (2.3.5), (2.3.6)

, (2.3.4)

де, s'- число зворотне до s, q - простий дільник числа p-1.

(2.3.5)

, (2.3.6)

де ;

Якщо v = r ', тоді підпис приймається, якщо v ≠ r ', це означає або підміну інформації в процесі передачі, або не знання відправником секретного ключа

2.4 Програмна реалізація

2.5 Висновок

Програмно DES (Data Encryption Standard) приблизно в 100 разів швидше RSA . Ці числа можуть незначно змінюватися зі зміною параметрів, але RSA ніколи не досягне швидкості DES (Data Encryption Standard).

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

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

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

Пропонований алгоритм DSA заснований на криптографічного системі Ель-Гамаля. Його надійність основана на практичній нерозв'язності завдання обчислення дискретного логарифма. Одним з головних аргументів проти DSA є те, що, на відміну від загальної задачі обчислення дискретного логарифма , її окремий випадок, використаний у даній схемі, мало вивчений і, можливо, має істотно меншу складність розкриття.

3.Криптографія на еліпттичних кривих