Схеми цифрового підпису
Призначення
1)Справжність, яка переконує, що саме ця особа підписала документ.
2)Унікальність, так як і ручний підпис - частина документа, яку не можна перемістити на інші документи. Тобто будь-який окремий документ матиме свій унікальний цифровий підпис.
3)Цілісністьдокумента, що підписується, тобто неможливість зміни підписаного документа.
Симетричні схеми
Симетричні схеми мають такі переваги:
- Стійкість симетричних схем випливає із стійкості використовуваних блокових шифрів, надійність яких добре вивчена.
- Якщо стійкість шифру виявиться недостатньою, його можна буде замінити більш стійкий з мінімальними змінами у реалізації.
Недоліки симетричних схем:
- Потрібно підписувати окремо кожен біт інформації, що передається, що призводить до значного збільшення підпису. Підпис може перевищувати повідомлення за розміром на два порядки.
- Згенеровані для підпису ключі можуть бути використані лише один раз, оскільки після підписування розкривається половина секретного ключа.
Протокол цифрового підпису з достовірним посередником
Користувач А хоче підписати цифрове повідомлення та відправити його користувачеві B. Існує посередник, у якого є ключ k_1 для секретного зв'язку з A та ключ k_2 для секретного зв'язку з B. Ці ключі встановлені до початку протоколу і можуть бути використані багаторазово. Шифрування відбувається з допомогою симетричного шифру E.
2. Посередник розшифровує криптограму b, використовуючи ключ k_1.
3. Посередник формує блок інформації I = [a, b, pa], де a – розшифроване повідомлення, b – копія криптограми, pa – ідентифікатор абонентаA. Зашифровує блок інформації I ключі k_2 і відправляє криптограмму c користувачу B.
4. B розшифровує блок I інформації, використовуючи ключ k_2. B отримав повідомлення a та сертифікат посередника pa, що засвідчує, що повідомлення надійшло саме від A.
1. Тільки посередник та відправник A мають секретний ключ k_1, тому тільки A може надіслати посереднику повідомлення, зашифроване на ключі k_1. (захист ЦП від підробки)
2. Підпис не тиражується і підписаний документ незмінний.
3. Від цього підпису не можна зректися (невідмовність).
Асиметричні схеми
Визначення схеми цифрового підпису
Схема цифрового підпису - це сукупність ймовірнісних поліноміальних алгоритмів (Gen;Sign;Vrfy>), що задовольняють наступному:
1) Алгоритм генерації ключаGenприймає на вхід секретний параметр і на виході видає (pk; sk; s0) - відкритий ключ, секретний ключ та початковий стан відповідно. Припустимо, що і що може бути обчислено з pk.
2) Алгоритм ПідписанняSignприймає на вхід секретний ключ sk, величину та повідомленняm. На виході виходить підпис разом із величиною , і записано, як Sign.
3) Детермінований алгоритм перевірки підписуVrfyприймає як вхідні дані відкритий ключ pk, повідомленняmта підпис . Як вихідні дані виступає бітb, і записується, якVrfy.
Першою і найвідомішою у всьому світі конкретною системою ЕЦП стала система RSA, математична схема якої була розроблена в 1977 р. в Массачусетському технологічному інституті США.
значення функції f(N) = (p - 1)(q - 1).
Далі відправникобчислює число Е із умов:
Алгоритм виробітку параметрів
Алгоритми підпису та перевірки використовують дві функції хешування. Перша функція, яка називаєтьсякомпресором:
Друга функція, яка називаєтьсягенератором:
(N, e, d, G, H, k_0, k_1) - параметри цифрового підпису, де
(N, e, d) – параметри ключа RSA, причому (N, e) – відкриті, а d = e^(-1)(mod φ(N)) – закрито.
Алгоритм генерації підпису
Візуально генерацію підпису можна представити так:
Алгоритм перевірки підпису
2. Представимо y у вигляді рядка біт b w r* γ;
3. r = r * XOR G_1 (w);
4. Якщо H(M r) = w і
то цифровий підпискоректний
Схема підпису Рабіна
Підпис Рабіна базується на криптографічній системі з відкритим ключем. Ця система заснована на складності обчислення квадратних коренів за модулем n. При цьому модуль n є добутком двох великих простих чисел. Параметри криптографічної схеми Рабіна:
p - просте число, p ≡ 3 mod 4, p - секретний ключ;
q – просте число, секретний ключ
n = pq - Відкритий ключ криптографічної системи.
Формування підпису
1. Генерується випадкова послідовність R довжиною t біт
r(i) ∈ , i = 0, 1, …, t-1.
2. Повідомлення M поєднується з послідовністю R
3. Послідовність бітів MR ставиться відповідно до числа a Перевірка підпису
1. Обчислюється значення a´a´ ≡ Z^2 mod n. 2. Якщо a=a´, то підпис приймається, інакше відкидається.
Схеми, засновані на еліптичних кривих
Група точок еліптичної кривої (див. еліптична крива), будучи спочатку абстрактним алгебраїчнимоб'єктом, що використовується для побудови алгоритмів цифрового підпису.
Можна накласти обмеження на безліч значень змінних х, y коефіцієнтів a, b, c. Обмежуючи область визначення рівняння значущим додатків числовим безліччю (полем) ми отримаємо еліптичну криву, задану над полем.
Еліптична крива над кінцевим простим полем GF(p) визначається як безліч пар (x,y), таких що x,y ≡ GF(p), що задовольняють рівняння:
y^2 = x^3 + ax + b mod p, a, b ≡ GF(p)
Пари (x,y) називають точками. Крапки еліптичної кривої можна складати. Сума двох точок, у свою чергу, також лежить на еліптичній кривій.
Крім точок, що лежать на еліптичній кривій, розглядається також нульова точка. Вважається, що сума двох точок – A з координатами (x', y') та B з координатами (x*, y*) – дорівнює 0, якщо x' = x*, y' = –y* (mod p). Нульова точка не лежить на еліптичній кривій, але проте бере участь у обчисленнях. Її можна розглядати як нескінченно віддалену точку.
Безліч точок еліптичної кривої разом з нульовою точкою і з введеною операцією додавання називатимемо «групою». Для кожної еліптичної кривої число точок у групі звичайно, але досить велике. Оцінка порядку (числа елементів) групи точок еліптичної кривої m така: p + 1 – 2√p ≤ m ≤ p + 1 + 2√p, де р – порядок поля, над яким визначено криву. Якщо у схемі Ель-Гамалю рекомендується використовувати число р порядку 2^512, то у разі еліптичної кривої достатньо взяти p> 2^255.
Важливу роль алгоритмах підписи з допомогою еліптичних кривих грають «кратні» точки. Точка Q називається точкою кратності k, якщо для деякої точки P k разів виконано рівність:
P = Q + Q + Q + … + Q =kQ Якщо для певної точки P існує таке число k, що kP = 0, це число називають порядком точки P. Кратні точки еліптичної кривої є аналогом ступенів чисел у простому полі. Завдання обчислення кратності точки еквівалентна задачі обчислення дискретного логарифму. Власне, на складності обчислення «кратності» точки еліптичної кривої і ґрунтується надійність цифрового підпису. Хоча еквівалентність задачі дискретного логарифмування та завдання обчислення кратності та доведена, друга має велику складність. Секретним ключем, як і раніше, покладемо деяке випадкове число x. Відкритим ключем вважатимемо координати точки на еліптичній кривій P, що визначається як P = xQ, де Q — спеціальним чином обрана точка еліптичної кривої («базова точка»). Координати точки Q разом з коефіцієнтами рівняння, що задає криву, є параметрами схеми підпису та мають бути відомі всім учасникам обміну повідомленнями. Вибір точки Q залежить від алгоритмів і дуже непростий. Так, стандарт ГОСТ 34.10-2001 визначає, що точка Q повинна мати порядок q, де q - просте число з «хорошими властивостями алгебри». Число q досить велике (2254 ГОСТ Р 34.10-2012
Параметри цифрового підпису
Параметрами схеми цифрового підпису є:
- Просте числоp- модуль еліптичної кривої;
- еліптична крива E, що задається своїм інваріантом J(Е) або коефіцієнтами a, b;
- ціле число m - порядок групи точок еліптичної кривої E;
– просте число q – порядок циклічної підгрупи групи точок еліптичної кривої E, для якого виконані такі умови:
- Точка P O еліптичної кривої Е, з координатами , що задовольняє рівності qP = O.
- хеш-функція , що відображає повідомлення,представлені у вигляді двійкових векторів довільної кінцевої довжини, двійкові вектора довжиниlбіт. Хеш-функція визначена у ГОСТ Р 34.11. Якщо ,2^254 Двійкові вектори
Для визначення процесів формування та перевірки цифрового підпису необхідно встановити відповідність між цілими числами та двійковими векторами довжиниlбіт.
Розглянемо наступний двійковий вектор довжиноюlбіт, у якому молодші біти розташовані праворуч, а старші – зліва:
де , i = 0.l- 1 одно або 1, або 0.
Число відповідає двійковому вектору, якщо виконано рівність
Для двох двійкових векторів
відповідних цілим числам і операція конкатенації (об'єднання) визначається наступним чином:
Об'єднання являє собою двійковий вектор довжиною 2lбіт, складений з коефіцієнтів векторів.
Формули (*) і (**) визначають спосіб розбиття двійкового вектора довжиною 2lбіт на два двійкових вектори довжиноюlбіт, конкатенацією яких є.
У цьому розділі визначено процеси формування та перевірки цифрового підпису під повідомленням користувача.
Для реалізації цих процесів необхідно, щоб всім користувачам були відомі параметри цифрового підпису, відповідні параметрам схеми цифрового підпису.
Крім того, кожен користувач повинен мати ключ підпису d і ключ перевірки підпису , які повинні відповідати параметрам схеми цифрового підпису.