НОУ ІНТУІТ, Лекція, Електронний цифровий підпис

Мета лекції: ознайомитися з деякими алгоритмами формування та перевірки електронного цифрового підпису (ЕЦП, ЕП).

Електронний підпис на основі алгоритму RSA

Розглянута нами у Лекції 11 схема використання алгоритму RSA при великому модулі N практично не дозволяє зловмиснику отримати закритий ключ і прочитати зашифроване повідомлення. Однак вона дає можливість зловмиснику підмінити повідомлення від абонента А до абонента Б, оскільки абонент А шифрує своє повідомлення відкритим ключем, отриманим від Б на відкритому каналі зв'язку. А якщо відкритий ключ передається відкритим каналом, будь-хто може отримати його і використовувати для заміни повідомлення. Уникнути цього можна, використовуючи складніші протоколи, наприклад, наступний.

Нехай, як і раніше, користувач А хоче передати користувачеві Б повідомлення, що складається з декількох блоків mi . Перед початком сеансу зв'язку абоненти генерують відкриті та закриті ключі, що позначаються, як зазначено в таблиці:

Відкритий ключ Закритий ключ
Користувач АNA, dAeA
Користувач БNБ, dБeБ

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

Основна частина протоколу складається з наступних кроків.

  1. Спочатку користувач А обчислює числа, тобто шифрує повідомлення своїм закритим ключем. Внаслідок цих дій користувач А підписує повідомлення.
  2. Потім користувач А обчислює числа , тобто шифрує те, що вийшло на кроці 1 відкритим ключем користувача Б. На цьому етапіповідомлення шифрується, щоб ніхто сторонній не міг його прочитати.
  3. Послідовність чисел gi передається користувачу Б.
  4. Користувач Б отримує gi і спочатку послідовно обчислює числа , використовуючи свій закритий ключ. При цьому повідомлення розшифровується.
  5. Потім Б визначає числа, використовуючи відкритий ключ користувача А. За рахунок виконання цього етапу проводиться перевірка підпису користувача А.

В результаті абонент Б отримує вихідне повідомлення та переконується в тому, що його відправив саме абонент А. Дана схема дозволяє захиститися від кількох видів можливих порушень, а саме:

  • користувач А не може відмовитись від свого повідомлення, якщо він визнає, що секретний ключ відомий тільки йому;
  • порушник без знання секретного ключа не може ні сформувати, ні зробити осмислену зміну повідомлення, що передається лінією зв'язку.

Ця схема дозволяє уникнути багатьох конфліктних ситуацій. Іноді немає необхідності зашифровувати повідомлення, що передається, але потрібно його скріпити електронним підписом. У цьому випадку з наведеного вище протоколу виключаються кроки 2 і 4, тобто текст шифрується закритим ключем відправника і отримана послідовність приєднується до документа. Отримувач за допомогою відкритого ключа відправника розшифровує прикріплений підпис, який є зашифрованим повторенням основного повідомлення. Якщо розшифрований підпис збігається з основним текстом, то підпис вірний.

Існують і інші варіанти застосування алгоритму RSA для формування ЕЦП. Наприклад, можна шифрувати (тобто підписувати) відкритим ключем не саме повідомлення, а хеш від нього.

Можливість застосування алгоритму RSA для отримання електронного підпису пов'язана зтим, що секретний та відкритий ключі у цій системі рівноправні. Кожен із ключів, d або e можуть використовуватися як для шифрування, так і для розшифрування. Ця властивість виконується не у всіх криптосистемах із відкритим ключем.

Алгоритм RSA можна використовувати також обміну ключами.

Цифровий підпис на основі алгоритму Ель-Гамалю

Принцип створення та перевірки підпису

Алгоритм Ель-Гамалю також можна використовувати для формування цифрового підпису. Група користувачів вибирає загальні параметри Р та А . Потім кожен абонент групи вибирає своє секретне число Хi, 1 і обчислює відповідне йому відкрите число . Таким чином, кожен користувач отримує пару (закритий ключ; відкритий ключ) = (Хi, Yi). Відкриті ключі користувачів можуть зберігатися у загальній базі системи розподілу ключів та за необхідності надаватися всім абонентам системи.

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

Нехай користувач 1 хоче підписати повідомлення цифровим підписом і передати його користувачеві 2. У цьому випадку алгоритм дій наступний.

  1. Перший користувач вибирає випадкове секретне число k , взаємно просте з Р-1 і обчислює число
  2. Потім за допомогою розширеного алгоритму Евкліда необхідно знайти значення b у наступному рівнянні:

Підписи, створені з використанням алгоритму Ель-Гамалю, називаютьсярандомізованими, так як для одного і того ж повідомлення з використанням одного ітого ж закритого ключа щоразу будуть створюватися різні підписи (a, b), оскільки кожного разу використовуватиметься нове значення k. Підписи, створені із застосуванням алгоритму RSA, називаютьсядетермінованими, так як для одного і того ж повідомлення з використанням одного і того ж закритого ключа щоразу буде створюватися один і той самий підпис.

Приклад обчислення та перевірки цифрового підпису

Нехай абоненти, які обмінюються через Інтернет зашифрованими повідомленнями, мають такі параметри: Р = 11, А = 7 .

Один із користувачів цієї системи зв'язку хоче підписати своє повідомлення m=5 цифровим підписом, сформованим за алгоритмом Ель-Гамалю. Спочатку він повинен вибрати собі закритий ключ, наприклад, Х1 = 3 і сформувати відкритий ключ Y1 = 73 mod 11 = 2 . Відкритий ключ може бути переданий усім зацікавленим абонентам або поміщений до бази даних відкритих ключів системи зв'язку.

Потім користувач вибирає випадкове секретне число k взаємно просте з Р-1 . Нехай k = 9 (9 немає спільних дільників з 10). Далі необхідно обчислити число

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

Рішенням останнього рівняння буде значення b=9.

Таким чином, пара чисел (8, 9) буде цифровим підписом повідомлення m=5.

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

Оскільки с1 = с2 , то цифровий підпис першого користувача повідомлення m=5 правильна.