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

ЕЦП накладається за допомогою особистого ключа і перевіряється за допомогою відкритого ключа.

Загальна схема

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

• алгоритм генерації ключових пар користувача;
• функцію обчислення підпису;
• функцію перевірки підпису.

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

Стійкість

У наш час детерміновані схеми практично не використовуються. Навіть у ті алгоритми, які спочатку були детерміновані, зараз внесено модифікації, що обертають їх у імовірнісні. Саме так до схеми підпису RSA, у другій версії стандарту PKCS#1 додане попереднє перетворення даних, що має у собі, серед іншого, зашумлення. Після внесення змін алгоритм RSA був перейменований у RSA-OAEP.
Функція перевірки підпису перевіряє, чи має відповідність цей підпис до даного документа та відкритого ключа користувача. Відкритий ключ користувача доступний усім, таким чином, будь-хто може перевірити підпис під даним документом.
Оскільки довжина документів, що підписуються, змінна (і досить велика), в схемах ЕЦП найчастіше підпис ставлять не на сам документ, а на його геш-образ. Для обчислення геш-образу використовують криптографічні геш-функції, що гарантує виявлення змін, внесених до документу, при перевірці підпису. Геш-функції не є частиною алгоритму ЕЦП, тому в схемі може бути використана будь-яка надійна Геш-функція.

Алгоритми ЕЦП поділяють на два великих класи:

• звичайні цифрові підписи;
• цифрові підписи з відновленням документа.

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

Захищеність

Цифровий підпис забезпечує:

• Посвідчення джерела документа. У залежності від деталей визначення документа можуть бути підписані такі поля, як «автор», «внесені зміни», «мітка часу» і т. д.;
• Захист від внесення змін до документу. У разі внесення будь-яких випадкових або навмисних змін до документу (або підпису) зміниться геш, отже, підпис стане недійсним;
• Неможливість відмови від авторства. Враховуючи, що створити коректний підпис можна лише, знаючи закритий ключ (а він відомий тільки власникові), власник не може відмовитися від свого підпису під документом.

Можливі наступні загрози щодо цифрового підпису:

• Зловмисник може спробувати підробити підпис для обраного документа;
• Зловмисник може спробувати підібрати документ відповідно даному підпису, щоб підпис до нього підходив;
• Зловмисник може спробувати підробити підпис для будь-якого документа.

У разі використання надійної геш-функції, важко створити підроблений документ з таким самим геш-образом, як у справжнього. Однак ці загрози можуть реалізуватися внаслідок слабкості конкретних алгоритмів гешування, підпису, або помилок в їх реалізаціях.

Тим не менш, можливі ще такі загрози щодо систем цифрового підпису:

• Зловмисник, який вкрав закритий ключ, може підписати будь-який документ від імені власника ключа;
• Зловмисник може обманним шляхом змусити власника підписати будь-який документ, наприклад, використовуючи протокол сліпого підпису;
• Зловмисник може підмінити відкритий ключ власника (див. управління ключами) на свій власний, видаючи себе за нього.

Стандарти та алгоритми ЕЦП:

• Міжнародний стандарт IEEE P 1363-2000. Алгоритми: DSA, ECDSA.
• Міжнародний стандарт: ISO / IEC 15946-2:2002. Алгоритми: ECDSA, ECGDSA, ECKDSA.
• Міжнародний стандарт: ISO / IEC 14888-2. Алгоритми: RSA.
• Міжнародний стандарт: PKCS # 1. Алгоритм: RSA.
• Американський стандарт: X9.62-1998. Алгоритм: ECDSA.
• Російські стандарти: ГОСТ Р 34.10-94, ГОСТ Р 34.10-2001.
• Український стандарт: ДСТУ 4145-2002.

Управління ключами

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

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

Схема RSA

Розглянемо процес накладення ЕЦП відповідно до алгоритму RSA (див. розділ «Направлене шифрування» - дати лінк - для довідки). Припустимо, Кореспондент 1 хоче послати Кореспонденту 2 повідомлення M, причому таким чином, щоб Кореспондент 2 був упевнений, що повідомлення не було модифіковано і що автором повідомлення дійсно є Кореспондент 1. Кореспондент 1 створює цифровий підпис S, зводячи M в ступінь d і помножуючи на модуль n:

S = M^d (mod n), де d і n - приватний секретний ключ Кореспондента 1. Він посилає M і S Кореспонденту 2.

Щоб перевірити підпис, Кореспондент 2 зводить S в ступінь E і помножує на модуль N: M = S^e (mod n), де e і n - відкритий (Public) ключ Кореспондента 1.

Таким чином, забезпечення цілісності та автентифікація автора повідомлення здійснюється без передачі секретних (Private) ключів: обидва кореспонденти використовують тільки відкритий (Public) ключ свого опонента або власний особистий (Private) ключ. Надіслати зашифроване повідомлення і перевірити підписане повідомлення може будь-хто, але розшифрувати або підписати повідомлення може тільки власник відповідного особистого (Private) ключа.

Схема Ель-Гамаль

У 1991 р. в США був опублікований проект федерального стандарту цифрового підпису - DSS (Digital Signature Standard), що описує систему цифрового підпису DSA (Digital Signature Algorithm). Одним з основних критеріїв при створенні проекту була його патентна чистота. Алгоритм DSA заснований на криптографічній системі Ель-Гамаль і має, як і RSA, теоретико-числовий характер. Його надійність основана на практичній нерозв'язності певного часткового випадку задачі обчислення дискретного логарифму. Сучасні методи вирішення цієї проблеми мають приблизно таку саму ефективність, що й методи вирішення задачі факторізаціі. Довжина підпису у схемі DSA менша за RSA в декілька разів.

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

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

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

• загальні параметри;
• секретний ключ;
• відкритий ключ.

Загальні параметри необхідні для функціонування системи в цілому. Секретний ключ використовується для формування ЕЦП, а відкритий - для перевірки ЕЦП. Загальними параметрами системи є прості цілі числа p, q, g, де q - простий дільник числа (p - 1), g - так званий генератор, що задовольняє рівності g = h ^ ((p - 1) /q) mod p> 1 . Параметри p, q, g публікуються для всіх учасників обміну. Секретний ключ X випадково вибирається з діапазону [1, q] і тримається в секреті.
Відкритий ключ обчислюється як: y= g ^ x mod p. При описанні цієї схеми будуть використовуватися наступні позначення та додаткові параметри: m - вхідне повідомлення користувача для схеми з ЕЦП; k - випадкове число, яке задовольняє умовою 0

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

• обчислюється геш-код повідомлення m h = h (m);
• з діапазону [1, q] випадковим чином вибирається значення k і обчислюється r = (g ^ k mod p) mod q;
• обчислюється s = (k ^ -1 (h + xr)) mod q, де k ^ -1 задовольняє умовою (k ^ -1 * k) mod q = 1.

Значення r, s є ЕЦП повідомлення m і передаються разом з ним по каналах зв'язку.
Нехай прийнято повідомлення m1 і його підпис s1, r1. Перевірка ЕЦП відбувається наступним чином:

• перевіряє виконання умов 0
• обчислюється w = s1 ^ -1 mod q;
• обчислюється u1 = (h (m1) w) mod q;
• обчислюється u2 = ((r1 / w) mod q;
• обчислюється v = ((g ^ u1 * y ^ u2) mod p) mod q;
• перевіряється рівність v = r1.

Якщо остання  рівність виконується, то підпис приймається. У даному стандарті специфікується також процедура створення основних параметрів системи і проводиться доказ того, що у разі v = r1, то m1 = m, r1 = r, s1 = s.