ChSTU repository
ChSTU repository preserves and enables easy and open access to all types of digital content including text, images, moving images, mpegs and data sets
Learn More
Please use this identifier to cite or link to this item:
https://er.chdtu.edu.ua/handle/ChSTU/7732| Title: | Модифікація алгоритму цифрового підпису |
| Authors: | Байрак, Анатолій Володимирович Мандрус, Антон Євгенійович |
| Keywords: | алгоритм цифрового підпису;хеш-алгоритм;galois field;digital signature algorithm;digital signature;підпис повідомлення |
| Issue Date: | 2022 |
| Abstract: | Створення програмного засобу, що демонструє роботу модифікованої схеми електронного цифрового підпису (генерація ключів, підписування та перевірка підпису). |
| URI: | https://er.chdtu.edu.ua/handle/ChSTU/7732 |
| Appears in Collections: | 125 Кібербезпека та захист інформації (Безпека інформаційних і комунікаційних систем) |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Б_125_Мандрус_Байрак.pdf Restricted Access | 1.04 MB | Adobe PDF | View/Open Request a copy |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
Extracted text
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
ФАКУЛЬТЕТ ЕЛЕКТРОННИХ ТЕХНОЛОГІЙ І РОБОТОТЕХНІКИ
КАФЕДРА РОБОТОТЕХНІЧНИХ І ТЕЛЕКОМУНІКАЦІЙНИХ СИСТЕМ ТА
КІБЕРБЕЗПЕКИ
До захисту допущено
завідувач кафедри РТСК
д.т.н., професор
_______________ В.В. Палагін
"_____" _____________ 2022 року
Пояснювальна записка
до дипломного проекту (роботи)
бакалавра
(освітньо-кваліфікаційний рівень)
на тему «Модифікація алгоритму цифрового підпису»
Виконав: студент 4 курсу, групи БІ-81
Спеціальності 125 – «Кібербезпека» ,
(шифр і назва спеціальності)
освітньої програми «Безпека інформаційних і
комунікаційних систем»
(назва освітньої програми)
Мандрус А.Є.
(прізвище та ініціали)
Керівник Байрак А.В.
(прізвище та ініціали)
Рецензент Сагун А.В.
(прізвище та ініціали)
Черкаси – 2022 року
Форма № Н-9.01
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
Факультет електронних технологій і робототехніки
Кафедра робототехнічних і телекомунікаційних систем та кібербезпеки
Освітньо-кваліфікаційний рівень бакалавр
Спеціальність 125 – Кібербезпека
Освітня програма – Безпека інформаційних і комунікаційних систем
ЗАТВЕРДЖУЮ
Завідувач кафедри В.В. Палагін
“_____” ___________________ 2022 року
ЗАВДАННЯ
НА ВИПУСКНУ РОБОТУ СТУДЕНТУ
Мандруса Антона Євгенійовича ___________________
(прізвище, ім’я, по батькові)
1. Тема проекту (роботи) Модифікація алгоритму цифрового підпису
керівник проекту (роботи) Байрак Анатолій Володимирович
(прізвище, ім’я, по батькові, науковий ступінь, вчене звання)
затверджені наказом вищого навчального закладу від «18» лютого 2022 року № 58/04
2. Термін здачі студентом закінченої роботи “ 25 ” травня 2022 року _________
3. Вихідні дані до роботи: наукові та навчальні джерела з галузі Cryptography та
Information Security; відомості про принципи роботи Digital Signature та сучасні схеми
електронного цифрового підпису; алгоритм цифрового підпису Digital Signature
Algorithm; криптографічні Cryptographic Hash Function та їх використання у схемах
цифрового підпису; хеш-алгоритм MD5; математичний апарат скінченних полів Galois
Field GF(2); програмні засоби реалізації криптографічних алгоритмів мовами
програмування.
4. Зміст розрахунково-пояснювальної записки (перелік питань, що їх належить розробити)
визначення поняття електронного цифрового підпису; аналіз функцій та призначення
ЕЦП; огляд існуючих алгоритмів та схем цифрового підпису; принципи застосування хеш-
функцій у схемах цифрового підпису; аналіз базових алгоритмів хешування; дослідження
алгоритму DSA та процесу формування електронного підпису; демонстрація прикладу
роботи алгоритму DSA; розробка модифікації алгоритму цифрового підпису на основі
використання нової хеш-функції; аналіз ефективності модифікованої схеми.
5. Перелік графічного матеріалу (з точним зазначенням обов’язкових креслень, плакатів)
1. Структурна схема системи електронного цифрового підпису на основі алгоритму
Digital Signature Algorithm.; 2. Схема алгоритму формування та перевірки електронного
цифрового підпису; 3. Блок-схема модифікованого алгоритму цифрового підпису з
використанням хеш-функції, що працює у полі Galois Field GF(2); 4. Охорона праці.
.6. Консультанти з проекту (роботи) із зазначенням розділів проекту, що їх стосуються
Підпис, дата
Прізвище, ініціали та посада
Розділ завдання завдання
консультанта
видав прийняв
Охорона праці Кожем’якін О.С.
старший викладач кафедри
безпеки життєдіяльності
7. Дата видачі завдання 18 лютого 2022 року
КАЛЕНДАРНИЙ ПЛАН
Термін
№ Назва етапів дипломного проекту
виконання етапів Примітка
з/п (роботи)
проекту (роботи)
1. Аналіз технічного завдання та пошук
18.02.22 – 09.03.22
літератури
2. Аналіз принципів роботи електронного
цифрового підпису, його функцій, призначення 10.03.22 – 24.03.22
та огляд існуючих схем ЕЦП.
3. Дослідження хеш-функцій та їх застосування
в алгоритмах цифрового підпису, зокрема 25.03.22 – 10.04.22
аналіз алгоритму Digital Signature Algorithm.
4. Розробка модифікації алгоритму цифрового
підпису DSA із використанням
11.04.22 – 25.04.22
криптографічної хеш-функції, що працює у
полі Galois Field GF(2).
5. Створення програмного засобу, що
демонструє роботу модифікованої схеми
26.04.22 – 10.05.22
електронного цифрового підпису (генерація
ключів, підписування та перевірка підпису).
7. Виконання розділу охорони праці 11.05.22 – 26.05.22
8. Оформлення пояснювальної записки 27.05.22 – 01.06.22
9. Оформлення презентації 02.06.22 – 09.06.22
Студент Мандрус А.С.
( підпис ) (прізвище та ініціали)
Керівник проекту (роботи) Байрак А.В.
( підпис ) (прізвище та ініціали)
ВСТУП
Сьогодні умови існування окремих бізнесів, людей і країн тісно залежать
від технологій забезпечення безпеки. Така постановка питання пов’язана з
необхідністю забезпечити надійні і захищені канали передавання різного типу
електронних даних, документів. Збільшення мобільності бізнесу, цифрова
трансформація суспільства збільшує потребу в різного роду електронних та
комп’ютерних технологіях захисту інформації. Одною з таких технологій є
електронний цифровий підпис. На даний момент ця технологія дуже
розвинена, існує багато механізмів та заходів для її реалізації в електронному
вигляді в різного типу інформаційних систем. Часто такі ІС мають розподілену
або хмарну інфраструктуру. І хоча сам по собі алгоритм ЕЦП не вважається
секретною інформацією, проблеми модифікації подібних програмних засобів
періодично виникають. Відомо, що не всі існуючі схеми ЕЦП підлягають
модифікації.
Актуальність. В зв’язку зі швидким зростанням продуктивності
комп’ютерних систем з’являється необхідність у пошуку більш стійких
алгоритмів ЕЦП. В даному контексті деякі з них близькі до вичерпання
закладених резервів, а деякі можуть гарантувати необхідний рівень стійкості
лише за умови збільшення довжини ключа, що підвищує вимоги до
комп’ютерних платформ при обчисленні ключових пар. В зв’язку з чим постає
задача пошуку прийнятних модифікацій алгоритму цифрового підпису.
Об’єктом роботи є система цифрового підпису на базі алгоритму DSA,
який використовує криптографічну хеш-функцію.
Предметом роботи алгоритм цифрового підпису DSA на базі
криптографічної хеш-функція по типу згортки, яка оперує значеннями в кільці
числових полів GF(2).
Метою роботи є модифікація схеми електронного цифрового підпису на
базі за рахунок використання нової криптографічної хеш-функція по типу
6
згортки, яка оперує значеннями в кільці числових полів GF(2) з подальшим
створенням програмного засобу, який ілюструє роботу модифікованої схеми
ЕЦП.
Для досягнення мети необхідно вирішити такі задачі:
− проаналізувати існуючі схеми електронного цифрового підпису та
технології їх використання;
− дослідити основні недоліки та переваги існуючих схем ЕЦП та
обрати варіант одної з таких схем для подальшої модифікації;
− розробити криптографічну хеш-функцію по типу згортки, яка
оперує значеннями в кільці числових полів GF(2);
− створити програмний засіб, який ілюструє роботу модифікованої
схеми ЕЦП та містить всі етапи даної схеми (формування ключової пари,
підписування та перевірки ЕЦП повідомлення).
Структура та обсяг роботи. Робота складається із вступу, 4 розділів,
загальних висновків, переліку використаних джерел, що містить 17
найменувань на 3 сторінках, 9 рисунків та 4 таблиці та 1 додаток на 4
сторінках.
Загальний обсяг роботи – 69 сторінок, з них 65 сторінки основного
тексту.
7
РОЗДІЛ 1
ЕЛЕКТРОННИЙ ЦИФРОВИЙ ПІДПИС ТА ЙОГО СХЕМИ
1.1 ЕЦП. Функції та призначення ЕЦП
Як відомо, електронний цифровий підпис – реквізит електронного
документа, що служить для визначення джерела даних та захисту документа
від підробки. Практично в такому вигляді таке означення зустрічається і в
Законі України «Про електронні довірчі послуги» [1].
Для отримання ЕЦП виконується криптографічний перетворення
електронного документа, яке потім приєднується до документа або логічно
поєднується з ним. Це дає можливість підтвердити його цілісність та
ідентифікувати того, хто підписав.
Основним призначенням ЕЦП є захист цілісності інформації. Більш
конкретними завдання застосування цифрового підпису є:
1. Автентифікація особи, яка підписала електронний документ.
2. Контроль цілісності документа: при будь-якій зміні документа підпис
стане недійсним, бо обчислюється на підставі вихідного стану документа і
відповідає йому.
3. Захист від змін (підробки) документа.
4. Неможливість відмовитися від авторства (створити підпис може лише
власник закритого ключа, тому він потім не може відмовитися від свого
підпису під документом).
5. Доказове підтвердження авторства документа.
Галузей використання ЕЦП на сьогодні багато. А потенційна сфера
постійно розширюється:
- електронна торгівля;
8
- митні декларації;
- реєстрація угод у банках;
- контроль за виконанням державного бюджету;
- системи звернення до органів влади;
- електронний документообіг;
- завірення та перевірка нотаріальних угод тощо.
Поняття ЕЦП було введено ще у 1976 році Діффі і Хеллманом, які
висловили припущення про її існування [2].
У 1977 Рівест, Шамір і Адлеман розробили криптосистему RSA, яку
можна було використовувати для створення примітивних ЕЦП [3].
Незабаром після RSA розроблено алгоритми цифрового підпису Рабіна,
Меркле.
Формулювання вимоги до безпеки алгоритмів ЕЦП та опис можливих
атак на алгоритми ЕЦП було зроблено у 1984 році Гольдвассером, Мікалі та
Рівестом [4].
1.2 Огляд відомих схем та алгоритмів ЕЦП
В Україні ЕЦП обчислюється за криптографічними алгоритмами,
визначеними у ДСТУ 4145-2002 «Інформаційна технологія. Криптографічний
захист інформації. Електронний цифровий підпис, що ґрунтується на
еліптичних кривих», затвердженому наказом Державного комітету України з
питань технічного регулювання та споживчої політики від 28 грудня 2002 року
№ 31 (далі - ДСТУ 4145-2002) [5].
В даному випадку, слід говорити, що використання схем ЕЦП,
заснованих на асиметричних алгоритмах з використанням геш-функцій є
загальносвітовим трендом.
Існуючі алгоритми ЕЦП діляться на два великі класи:
9
1) звичайні цифрові підписи, які необхідно пов'язувати з повідомленням,
що підписується;
2) цифрові підписи з відновленням повідомлення, що містять у собі
підписуваний документ: у процесі перевірки підпису автоматично
обчислюється і тіло документа.
1.2.1 Закордонні стандарти ЕЦП
Стандарт США
США є законодавцем стандартів ЕЦП. Перший у світі стандарт
шифрування даних було прийнято США. DSS (Digital Signature Standard) —
американський стандарт, що описує Digital Signature Algorithm (DSA), який
може бути використаний для створення цифрового підпису [6]. Цифровий
підпис служить для встановлення змін даних і для встановлення справжності
сторони, що підписалася. DSA включає два алгоритми (S, V):
для створення підпису повідомлення (S) та для її перевірки (V).
Обидва алгоритми спочатку обчислюють хеш повідомлення,
використовуючи криптографічну хеш-функцію. Алгоритм S використовує
хеш та секретний ключ для створення підпису, алгоритм V використовує хеш
повідомлення, підпис та відкритий ключ для перевірки підпису.
Стандарт РФ
В 1994 Головним управлінням безпеки зв'язку Федерального агентства
урядового зв'язку та інформації при Президентові Росії був розроблений
перший російський стандарт ЕЦП - ГОСТ Р 34.10-94. В 2002 році існуючий на
той момент стандарт змінено на стандарт ГОСТ Р 34.10-2001, заснований на
обчисленнях в групі точок еліптичної кривої [7] цього не вимагають.
1.2.2 Вітчизняна схема ЕЦП
10
На момент написання даної роботи, відповідно до згаданого стандарту
України ДСТУ 4145-2002 [8] при використанні функції гешування за ДСТУ
7564-2014 в операціях формування та перевіряння електронного цифрового
підпису режим обчислення геш-значення визначається відповідно до вимог до
формату посиленого сертифіката відкритого ключа [9], затверджених наказом
Міністерства юстиції України, Адміністрації Державної служби спеціального
зв’язку та захисту інформації України від 20 серпня 2012 року № 1236/5/453,
зареєстрованих у Міністерстві юстиції України 20 серпня 2012 року за №
1398/21710.
В усіх інших операціях обчислення значення геш-функції згідно з ДСТУ
7564-2014 рекомендується використовувати режим хешуванням з
формуванням геш-значення завдовжки 256 бітів».
Українcький стандарт ЕЦП описаний в нормативному документі ДСТУ
4145-2002. Він ґрунтується на групах точок еліптичної кривої. Схема
електронного підпису включає в себе наступні складові:
- алгоритм генерації ключової пари користувача, який випадково
вибирає закритий ключ та обчислює відповідний йому відкритий ключ;
- формування підпису – для електронного документа за допомогою
закритого ключа обчислюється підпис;
- перевірку (верифікацію) підпису – для документа та підпису за
допомогою відкритого ключа визначається дійсність підпису.
Залежно від алгоритму функція, що формує підпис, може бути
детермінованою або ймовірною. Детерміновані функції завжди знаходять
однаковий підпис для одного й того самого документа.
Ймовірнісні функції вносять до ЕЦП елемент випадковості, що посилює
криптостійкість алгоритмів ЕЦП. Але для функціонування ймовірнісних схем
необхідні або апаратний генератор шуму, або криптографічно надійний
генератор псевдовипадкових бітів, що ускладнює їхнє практичне
використання.
11
Розрізняють одноразові схеми ЕЦП, у яких після перевірки підпису
треба провести заміну ключів, та багаторазові схеми, які
1.3 Існуючи схеми побудови ЕЦП
На сьогодні існують дві основні схеми побудови ЕЦП, які мають
практичне застосування для захисту цілісності інформації – симетрична та
асиметрична.
1.3.1 Симетрична схема ЕЦП будується на основі алгоритмів
симетричного шифрування.
Дана схема передбачає наявність в системі третьої особи – арбітра, який
має довіру обох сторін. Під автентифікацією документу визнається факт його
шифрування секретним ключем і передача його арбітру.
Використовується така схема доволі рідко. Це пов’язано з відсутністю
ефективних алгоритмів.
Однак, у даної схеми є численні переваги. Серед них:
- стійкість симетричних схем випливає із стійкості використовуваних
блокових шифрів, надійність яких також добре вивчена.
- Якщо стійкість шифру недостатня, то його можна легко замінити
іншим.
Серед недоліків симетричної схеми ЕЦП можна назвати:
- необхідність у підписуванні окремо кожного біту інформації, що
значно збільшує розмір підпису. В результаті він може стати довшим за
документ на порядок;
- згенеровані для підпису ключі можна використовувати лише один раз,
оскільки після підписування розкривається половина секретного ключа.
12
1.3.2. Асиметрична схема ЕЦП є більш популярною і будується на основі
алгоритмів асиметричного шифрування.
Дана схема є більш поширеною. Вона широко застосовуються на
практиці в інформаційних комп’ютерних системах.
Для асиметричних схем ЕЦП використання двох ключів (ключової
пари). Тому шифрування а таких схемах виконують на відкритому ключі, а
дешифрування – на закритому ключі одержувача. Процес підписування
проводиться за допомогою закритого ключа, а перевірку здійснюють за
допомогою відкритого ключа користувача, що передає повідомлення (схема
ЕЦП змінює ролі секретних та відкритих ключів) .
До переваг даного підпису можна віднести:
- створити легітимний цифровий підпис без володіння закритим
ключем має бути обчислювально складно.
- алгоритм ЕЦП можна відносно легко модифікувати.
До спірних моментів практичного застосування асиметричних схем ЕЦП
можна віднести:
- відносно велику обчислювальну складність. Це пов’язано з тим,
що асиметричні схеми ЕЦП базуються, як і асиметричне шифрування загалом,
на обчислювально складних задачах (задача дискретного логарифмування або
задача факторизації), складність яких суворо математично не доведена. Тому
прогрес у математиці може спричинити успішний злам таких алгоритмів. Але,
з іншого боку, обчислення можуть проводитися в групі точок еліптичних
кривих (наприклад, російська ЕЦП) та полях Галуа (наприклад, DSA);
- для збільшення криптостійкості треба збільшувати довжину
ключів, що змушує переписувати програми, що реалізують схеми, і навіть
перепроектувати апаратуру. Крім цього, існують інші різновиди цифрових
підписів (груповий підпис, незаперечний підпис, довірений підпис, сліпий
підпис).
13
РОЗДІЛ 2
ХЕШ-ФУНКЦІЇ ТА ЇХ ВИКОРИСТАННЯ В АЛГОРИТМАХ ЕЦП
2.1 Положення для застосування хеш-функцій в алгоритмах ЕЦП
Переваги алгоритмів ЕЦП, які використовують хеш-функції цілком
зрозумілі та мають просте пояснення. Так, документи, що підписуються,
мають різну, часто велику довжину, тому в схемах ЕЦП зручно
використовувати не сам документ, а його хеш. Хеша обчислюють за
допомогою криптографічних хеш-функцій, що гарантує виявлення змін
документа під час перевірки підпису.
Використання хеш-функцій в алгоритмах ЕЦП дає наступні переваги:
− виграш у обчислювальній складності. Хеш документа має
набагато меншу довжину, ніж сам документ, а алгоритми обчислення хеш-
функції швидше виконується, ніж алгоритми ЕЦП. Тому формувати хеш
документа та підписувати його набагато швидше, ніж підписувати сам
документ;
− сумісність. Хеш-функцію можна використовувати для
перетворення довільного вхідного тексту у потрібний і відповідний формат;
− цілісність. Без використання хеш-функції великий документ у
деяких схемах треба ділити на менші блоки, а лише після цього був
підписувати. В даному випадку при верифікації неможливо визначити, чи всі
блоки отримані і чи в коректному порядку відбулося їх отримання.
Використання хешування знімає ці питання. Проте, існують і певні
обмеження щодо використання хеш-функцій в алгоритмах ЕЦП:
14
− хешування не обов'язково для цифрового підпису, а сама функція
не є частиною алгоритму ЕЦП, тому хеш- функція може використовуватися
будь-яка або взагалі не використовуватися;
− всі алгоритми, що підписують хеш документа, відносяться до
традиційних схем ЕЦП.
Стійкість криптографічної хеш-функції зокрема забезпечується тим, що
з будь-якого унікального повідомлення формується унікальний хеш. В той же
час необхідно, щоб по одному хешу не можна було відтворити вихідне
повідомлення.
2.2 Базові алгоритми для застосування в схемах ЕЦП
Базуючись на огляді матеріалу розділу 2 можна говорити, що практично
використовується тільки асиметрична схема ЕЦП. Переважна більшість
алгоритмів ЕЦП, які мають прикладне застосування – це RSA, DSA та ECC (на
базі точок еліптичної кривої). Причому, модифікації з них можна піддати
схеми DSA і ECC. З огляду на практичну значущість та легкість такої
модифікації розглянемо основний елемент ЕЦП, який можна піддати
модифікації з метою пришвидшення формування та перевірки ЕЦП – хеш-
функцію (схема DSA).
На сьогодні можна виділити деякі розповсюджені хеш-функції: Md5,
SHA-1, SHA-2, SHA-256, Sha-3, Sha-256, Sha-384 та ряд модифікацій хеш-
функції SHA.
2.2.1 Хеш-функція Md5
MD5 - є широко використовуваною хеш-функцією, що видає 128-бітове
(16 байт) хеш-значення [10]. Тобто хеш, отриманий в результаті роботи даної
функції, робота якої заснована на цьому алгоритмі, видає значення, довжиною
16 байт (128) біт. Даний рядок включає 16 шістнадцяткових чисел. При цьому
15
зміна хоча б одного її символу призведе до подальшої зміни значень всіх інших
бітів рядка.
Хоча функція MD5 з самого початку розроблена для використання в
якості криптографічної хеш-функції, було виявлено, що вона має доволі
серйозні вразливості. Дана хеш-функція, як і раніше, може використовуватися
в якості контрольної суми для перевірки цілісності даних, але тільки проти
ненавмисного пошкодження. Таким чином, використання даної хеш-функції
за своїм прямим призначенням є недоречним.
Як і більшість інших хеш-функцій, MD5 не використовується для
шифруванням, або кодування. Дана функція може бути зламана шляхом атаки
грубої сили і страждає від деяких інших вразливостей. MD5 був розроблений
Рональдом Рівестом у 1991 році для заміни більш ранньої хеш-функції MD4.
Алгоритм хешування повідомлень MD5 - це 5-а версія алгоритму
хешування повідомлень, розробленого Роном Рівестом в 1991 для отримання
128-бітного вихідного повідомлення. Дана версія [10] була представлена, як
покращена з точки зору надійності щодо попереднього алгоритму MD4.
Інститут програмної інженерії CMY вважає MD5 по суті
"криптографічно зламаним та непридатним для подальшого використання".
Незважаючи на цю відому вразливість, MD5 залишається у використанні.
В даному алгоритмі передбачається наявність 5 кроків, за допомогою
яких отримуємо значення хеш-функції, а саме:
1. Вирівнювання потоку
2. Додавання довжини повідомлення
3. Ініціалізація буфера
4. Обчислення у циклі
5. Результат обчислень
Кожен з даних кроків має певне завдання.
16
Кожен з кроків даного алгоритму націлений на те, щоб максимально
зменшити кількість можливих колізій для значень та підвищити дисперсію.
Крок 1 - Вирівнювання потоку
Необхідне додавання додаткових бітів до вихідного повідомлення,
виконане таким чином, щоб довжина вихідного повідомлення з додатковими
бітами була еквівалентна 448 по модулю 512. Додавання виконується навіть у
тому випадку, якщо довжина вихідного повідомлення вже порівняна з 448. У
бітах заповнення тільки перший біт дорівнює 1 , інші біти рівні 0.
Крок 2 - Додавання довжини повідомлення
Наприкінці повідомлення дописується 64-бітове відораження довжини
даних (кількість біт у повідомленні) до моменту вирівнювання. На цьому етапі
отримане повідомлення має довжину, кратну 512 бітів. Обчислення
ґрунтуватимуться на поданні цього потоку даних у вигляді масиву слів по 512
біт.
Крок 3 - Ініціалізація MD-буфера
Буфер з чотирьох слів (A, B, C, D) використовується для обчислення
значень для дайджесту повідомлення. Тут A, B, C, D є 32-розрядними
регістрів, що складаються з шістнадцяткових чисел і ініціалізуються певним
чином (таблиця 2.1).
Таблиця 2.1 – значення буферу з 4 слів для обчислення дайджесту
повідомлення
Word A 01 23 45 67
Word B 89 AB CD EF
Word C FE DC BA 98
Word D 76 54 32 10
17
Крок 4: обробка повідомлення у циклі
MD5 використовує чотири допоміжні функції, які приймають на вхід три
32-бітні числа і виробляють 32-бітний висновок.
Ці функції використовують логічні оператори типу OR, XOR, AND,
NOT. Вміст чотирьох буферів поєднується з вхідними даними (з попереднього
кроку) за допомогою допоміжного буфера, який будується на основі
обчислень з допоміжними функціями. Виконується чотири раунди, у кожному
з яких використовується своя допоміжна функція.
Крок 5 - Результат обчислень
Після виконання всіх раундів буфер A, B, C, D містить вивід хеш-значень
MD5, що і являє з себе хеш.
Для того, щоб підвищити безпеку зберігання паролів алгоритм MD5
може використовуватися для хешування вихідних паролів. Таким чином, у базі
даних зберігатимуться значення хеш-функції відповідного алгоритму, а не
відкритого тексту. Під час автентифікації вхідний пароль також хешується
алгоритмом MD5 на стороні клієнта аналогічним чином, і хеш-значення, що
результує, порівнюється зі значенням в базі даних для конкретного
користувача.
2.2.2 Хеш-функція Sha-1
Secure Hash Algorithm 1 – алгоритм криптографічного хешування. Даний
алгоритм описаний в документі RFC 3174 [11]. Для будь-якого вхідного
повідомлення довільної довжини (максимум 264-1 біт, що дорівнює 2
ексабайти алгоритм генерує 160-бітове хеш-значення. Генероване значення
називається також дайджестом повідомлення. SHA-1 використовується в
18
багатьох криптографічних додатках і протоколах. Алгоритм рекомендований
в якості базового для використання у державних установах США. Принципи,
покладені в основу SHA-1, аналогічні тим, які використовував Рональд Рівест
при проектуванні іншого хеш-алгоритму MD4.
Алгоритм SHA-1 реалізує хеш-функцію, яка побудована на ідеї функції
стиснення. Входами функції стиснення є блок повідомлення довжиною 512 біт
та вихід попереднього блоку повідомлення. Вихід є значенням всіх хеш-блоків
до цього моменту. Іншими словами, хеш блоку Mi дорівнює hi=f(Mi,hi−1). Хеш-
значенням всього повідомлення є вихід останнього блоку.
Ініціалізація
Вихідне повідомлення розбивається на блоки по 512 біт у кожному.
Останній блок доповнюється до довжини, кратної 512 біт. Спочатку до блоку
додається 1, а потім нулі, щоб його довжина стала рівною (512 - 64 = 448) біт.
У 64 біти, що залишилися, записується довжина вихідного повідомлення в
бітах. Якщо останній блок має довжину більше 448 біт, але менше 512 біт,
доповнення виконується наступним чином: спочатку додається 1, потім нулі
до кінця 512-бітного блоку; після цього створюється ще один 512-бітний блок,
який заповнюється аж до 448 біт нулями, після чого в 64 біти, що залишилися,
записується довжина вихідного повідомлення в бітах.
Доповнення останнього блоку здійснюється завжди, навіть якщо
повідомлення має потрібну довжину.
Ініціалізуються п'ять 32-бітових змінних.
A = a = 0x67452301
B = b = 0xEFCDAB89
C = c = 0x98BADCFE
D = d = 0x10325476
E = e = 0xC3D2E1F0
Визначаються чотири нелінійні операції та чотири константи.
����(��, ��, ��) = (�� ∧ ��) ∨ (¬�� ∧ ��) Kt = 0x5A827999 0 ≤ �� ≤ 19
19
����(��, ��, ��) = ��⨁��⨁�� Kt = 0x6ED9EBA1 20 ≤ �� ≤ 39
����(��, ��, ��) = (�� ∧ ��) ∨ (�� ∧ ��) ∨ (�� ∧ ��) Kt = 0x8F1BBCDC 40 ≤ �� ≤ 59
����(��, ��, ��) = ��⨁��⨁�� Kt = 0xCA62C1D6 60 ≤ �� ≤ 79
Головний цикл перетворення
Головний цикл ітеративно обробляє кожен 512-бітовий блок. Ітерація
складається з чотирьох етапів по двадцять операцій у кожному. Блок
повідомлення перетворюється з 16 32-бітових слів Mi в 80 32-бітових
слів Wj за наступним правилом:
Рис.2.1 – лістинг коду 1
Після цього a, b, c, d, e додаються до A, B, C, D, E відповідно.
Починається чергова ітерація. Підсумковим значенням виконання ітерації є
поєднання п'яти 32-бітових слів в одне 160-бітове хеш-значення.
Хоча теоретично SHA-1 вважається зламаним (кількість
обчислювальних операцій скорочено в 280-63 = 131 000 разів),
20
на практиці подібний злом неможливий, тому що займе приблизно до п'яти
мільярдів років (залежить від обчислювальної потужності ПК).
Бурт Калінскі, голова дослідницького відділу в "лабораторії RSA"
передбачає, що перша атака по знаходженню прообразу буде успішно
здійснена в найближчі 5-10 років [12]. Фактично, на сьогодні алгоритм SHA-1
вже зламаний [12].
Зважаючи на те, що теоретичні атаки на SHA-1 виявилися успішними,
Національний інститут стандартів і технологій (NIST) планує повністю
відмовитися від використання SHA-1 у цифрових підписах.
Алгоритми Sha-2 і SHA-256
SHA-2 (Secure Hash Algorithm 2) — один з найпопулярніших сімейств
алгоритмів хешування [13]. Фактично, SHA-2 — це сімейство алгоритмів, яке
поєднано загальною ідеєю хешування даних. SHA-256 встановлює додаткові
константи, що визначають поведінку алгоритму SHA-2. Однією з таких
констант є розмір виведення даних. "256" і "512" відносяться до відповідних
розмірів вихідних даних у бітах.
Розглянемо на прикладі роботу SHA-256
Крок 1. Попередня обробка
1. Перетворюємо «hello world» в двійковий вид:
01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100
2. Додаємо одну одиницю:
01101000 01100101 01101100 01101100 01101111 00100000 01110111 01101111
01110010 01101100 01100100 1
3. Заповнюємо нулями блоки до ти, поки дані не стануть кратними 512 без
останніх 64 біт (в даному випадку 448 біт):
01101000 01100101 01101100 01101100 01101111 00100000 01110111
01101111
21
01110010 01101100 01100100 10000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
4. Додаємо 64 біти в кінець, де 64 біти - ціле число з порядком байтів у
форматі big-endian, що позначає довжину вхідних даних у двійковому вигляді.
Для даного випадку 88, у двійковому вигляді - "1011000".
01101000 01100101 01101100 01101100 01101111 00100000 01110111
01101111
01110010 01101100 01100100 10000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
00000000
00000000 00000000 00000000 00000000 00000000 00000000 00000000
01011000
Тепер маємо введення, яке завжди буде без залишку ділитися на 512.
22
Крок 2. Ініціалізація значень хешу (h)
Створимо 8 значень хешу. Це константи, що представляють перші 32 біти
дробових частин квадратного коріння перших 8 простих чисел: 2, 3, 5, 7, 11,
13, 17, 19.
h0:= 0x6a09e667
h1:= 0xbb67ae85
h2:= 0x3c6ef372
h3:= 0xa54ff53a
h4 := 0x510e527f
h5 := 0x9b05688c
h6 := 0x1f83d9ab
h7 := 0x5be0cd19
Крок 3. Ініціалізація заокруглених констант (k)
Створимо ще константи, цього разу їх 64. Кожне значення константи — це
перші 32 біти дробових частин кубічного коріння перших 64 простих чисел (2–
311).
0x428a2f98 0x71374491 0xb5c0fbcf 0xe9b5dba5 0x3956c25b 0x59f111f1
0x923f82a4 0xab1c5ed5
0xd807aa98 0x12835b01 0x243185be 0x550c7dc3 0x72be5d74 0x80deb1fe
0x9bdc06a7 0xc19bf174
0xe49b69c1 0xefbe4786 0x0fc19dc6 0x240ca1cc 0x2de92c6f 0x4a7484aa
0x5cb0a9dc 0x76f988da
0x983e5152 0xa831c66d 0xb00327c8 0xbf597fc7 0xc6e00bf3 0xd5a79147
0x06ca6351 0x14292967
0x27b70a85 0x2e1b2138 0x4d2c6dfc 0x53380d13 0x650a7354 0x766a0abb
0x81c2c92e 0x92722c85
23
0xa2bfe8a1 0xa81a664b 0xc24b8b70 0xc76c51a3 0xd192e819 0xd6990624
0xf40e3585 0x106aa070
0x19a4c116 0x1e376c08 0x2748774c 0x34b0bcb5 0x391c0cb3 0x4ed8aa4a
0x5b9cca4f 0x682e6ff3
0x748f82ee 0x78a5636f 0x84c87814 0x8cc70208 0x90befffa 0xa4506ceb
0xbef9a3f7 0xc67178f2
Крок 4. Основний цикл
Наступні кроки будуть виконуватися для кожного 512-бітного "відрізка"
вхідних даних. Тестова фраза "hello world" досить коротка, тому "відрізок"
буде всього один. На кожній ітерації циклу змінюватимемо значення хеш-
функцій h0–h7, щоб отримати остаточний результат.
Крок 5. Створюємо чергу повідомлень (w)
1. Копіюємо вхідні дані з кроку 1 у новий масив, де кожен запис є 32-
бітовим словом:
01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
2. Додаємо ще 48 слів, ініціалізованих нулями, для того, щоб отримати
масив даних w[0…63]:
01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
24
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
...
...
00000000000000000000000000000000 00000000000000000000000000000000
3. Змінюємо нульові індекси наприкінці масиву, використовуючи
наступний алгоритм:
Рис.2.2 – лістинг коду 2
Це залишає 64 слова в існуючій черзі повідомлень (w):
01101000011001010110110001101100 01101111001000000111011101101111
01110010011011000110010010000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000000000000
00000000000000000000000000000000 00000000000000000000000001011000
25
00110111010001110000001000110111 10000110110100001100000000110001
11010011101111010001000100001011 01111000001111110100011110000010
00101010100100000111110011101101 01001011001011110111110011001001
00110001111000011001010001011101 10001001001101100100100101100100
01111111011110100000011011011010 11000001011110011010100100111010
10111011111010001111011001010101 00001100000110101110001111100110
10110000111111100000110101111101 01011111011011100101010110010011
00000000100010011001101101010010 00000111111100011100101010010100
00111011010111111110010111010110 01101000011001010110001011100110
11001000010011100000101010011110 00000110101011111001101100100101
10010010111011110110010011010111 01100011111110010101111001011010
11100011000101100110011111010111 10000100001110111101111000010110
11101110111011001010100001011011 10100000010011111111001000100001
11111001000110001010110110111000 00010100101010001001001000011001
00010000100001000101001100011101 01100000100100111110000011001101
10000011000000110101111111101001 11010101101011100111100100111000
00111001001111110000010110101101 11111011010010110001101111101111
11101011011101011111111100101001 01101010001101101001010100110100
00100010111111001001110011011000 10101001011101000000110100101011
01100000110011110011100010000101 11000100101011001001100000111010
00010001010000101111110110101101 10110000101100000001110111011001
10011000111100001100001101101111 01110010000101111011100000011110
10100010110101000110011110011010 00000001000011111001100101111011
11111100000101110100111100001010 11000010110000101110101100010110
Крок 6. Цикл стискання
1. Ініціалізуємо змінні a, b, c, d, e, f, g, h та встановимо їх рівними
поточним значенням хешу відповідно: h0, h1, h2, h3, h4, h5, h6, h7.
2. Запускаємо цикл стиснення, який змінюватиме значення a…h.
Алгоритмічно даний цикл виглядає так:
26
Рис.2.3 – лістинг коду 3
Пройдемо першу ітерацію. Додавання розраховується за модулем 232:
a = 0x6a09e667 = 01101010000010011110011001100111
b = 0xbb67ae85 = 10111011011001111010111010000101
c = 0x3c6ef372 = 00111100011011101111001101110010
d = 0xa54ff53a = 10100101010011111111010100111010
e = 0x510e527f = 01010001000011100101001001111111
f = 0x9b05688c = 10011011000001010110100010001100
g = 0x1f83d9ab = 00011111100000111101100110101011
h = 0x5be0cd19 = 01011011111000001100110100011001
27
e rightrotate 6:
01010001000011100101001001111111 -> 11111101010001000011100101001001
e rightrotate 11:
01010001000011100101001001111111 -> 01001111111010100010000111001010
e rightrotate 25:
01010001000011100101001001111111 -> 10000111001010010011111110101000
S1=11111101010001000011100101001001XOR010011111110101000100001110
01010 XOR 10000111001010010011111110101000
S1 = 00110101100001110010011100101011
e and f:
01010001000011100101001001111111
& 10011011000001010110100010001100 =
00010001000001000100000000001100
not e:
01010001000011100101001001111111 ->
10101110111100011010110110000000
(not e) and g:
10101110111100011010110110000000
& 00011111100000111101100110101011 =
00001110100000011000100110000000
ch = (e and f) xor ((not e) and g)
= 00010001000001000100000000001100 xor
00001110100000011000100110000000
= 00011111100001011100100110001100
// k[i] is the round constant
// w[i] is the batch
temp1 = h + S1 + ch + k[i] + w[i]
28
temp1 = 01011011111000001100110100011001 +
00110101100001110010011100101011 + 00011111100001011100100110001100
+ 1000010100010100010111110011000 + 01101000011001010110110001101100
temp1 = 01011011110111010101100111010100
a rightrotate 2:
01101010000010011110011001100111 -> 11011010100000100111100110011001
a rightrotate 13:
01101010000010011110011001100111 -> 00110011001110110101000001001111
a rightrotate 22:
01101010000010011110011001100111 -> 00100111100110011001110110101000
S0=11011010100000100111100110011001XOR001100110011101101010000010
01111 XOR 00100111100110011001110110101000
S0 = 11001110001000001011010001111110
a and b:
01101010000010011110011001100111
& 10111011011001111010111010000101 =
00101010000000011010011000000101
a and c:
01101010000010011110011001100111& 00111100011011101111001101110010
= 00101000000010001110001001100010
b and c:
10111011011001111010111010000101& 00111100011011101111001101110010
= 00111000011001101010001000000000
maj = (a and b) xor (a and c) xor (b and c)
= 00101010000000011010011000000101 xor
00101000000010001110001001100010 xor
00111000011001101010001000000000
29
= 00111010011011111110011001100111
temp2 = S0 + maj
=11001110001000001011010001111110+00111010011011111110011001100111
= 00001000100100001001101011100101
h = 00011111100000111101100110101011
g = 10011011000001010110100010001100
f = 01010001000011100101001001111111
e=10100101010011111111010100111010
+01011011110111010101100111010100=00000001001011010100111100001110
d = 00111100011011101111001101110010
c = 10111011011001111010111010000101
b = 01101010000010011110011001100111
a=01011011110111010101100111010100
+00001000100100001001101011100101=01100100011011011111010010111001
Усі розрахунки виконуються ще 63 рази, змінюючи змінні а…h. У
результаті ми маємо отримати таке:
h0 = 6A09E667 = 01101010000010011110011001100111
h1 = BB67AE85 = 10111011011001111010111010000101
h2 = 3C6EF372 = 00111100011011101111001101110010
h3 = A54FF53A = 10100101010011111111010100111010
h4 = 510E527F = 01010001000011100101001001111111
h5 = 9B05688C = 10011011000001010110100010001100
h6 = 1F83D9AB = 00011111100000111101100110101011
h7 = 5BE0CD19 = 01011011111000001100110100011001
a = 4F434152 = 001001111010000110100000101010010
30
b = D7E58F83 = 011010111111001011000111110000011
c = 68BF5F65 = 001101000101111110101111101100101
d = 352DB6C0 = 000110101001011011011011011000000
e = 73769D64 = 001110011011101101001110101100100
f = DF4E1862 = 011011111010011100001100001100010
g = 71051E01 = 001110001000001010001111000000001
h = 870F00D0 = 010000111000011110000000011010000
Крок 7. Зміна остаточного значення
Після циклу стиснення, але ще всередині основного циклу відбувається
модифікація значення хеша шляхом додавання до нього відповідних змінних
a…h. Як і на попередніх кроках додавання відбувається за модулем 232:
h0 = h0 + a = 10111001010011010010011110111001
h1 = h1 + b = 10010011010011010011111000001000
h2 = h2 + c = 10100101001011100101001011010111
h3 = h3 + d = 11011010011111011010101111111010
h4 = h4 + e = 11000100100001001110111111100011
h5 = h5 + f = 01111010010100111000000011101110
h6 = h6 + g = 10010000100010001111011110101100
h7 = h7 + h = 11100010111011111100110111101001
Крок 8. Отримуємо фінальний хеш
На останньому кроці слід здійснити конкатенацію всіх отриманих блоків
повідомлення для отримання дайджесту:
digest = h0 append h1 append h2 append h3 append h4 append h5 append h6
append h7 =
B94D27B9934D3E08A52E52D7DA7DABFAC484EFE37A5380EE9088F7ACE2EFCDE9
31
Індустрія інфраструктури відкритих ключів рекомендує, щоб будь-який
об'єкт інфраструктури, що використовує SHA-1, був переведений на
безпечніший SHA-2 [14].
До 2017 року SHA-1 був найпопулярнішим алгоритмом для формування
хешів, який використовується для криптографічного підпису, і деякі, особливо
старі, додатки та пристрої не приймали або не розуміли хеші або сертифікати,
що базуються на алгоритмі SHA-2. Це була основна проблема переходу на
новий стандарт.
Серед інших функцій даного типу можна виділити хеш-функцію
Keccak (SHA-3). Вона базується на алгоритмі хешування змінної розрядності,
Даний алгоритм затверджено та опубліковано в якості стандарту FIPS 202 5
серпня 2015 року. Хоча назва функції SHA, але вона серйозно відрізняється за
будовою та принципом роботи від інших хеш-функцій даного сімейства.
Функція серйозно оптимізована для роботи з апаратною частиною. У
програмній реалізації автори заявляють про 12,5 циклах на байт при виконанні
на ПК з процесором Intel Core 2.
Основою функції стиснення алгоритму є функція f, яка виконує
перемішування внутрішнього стану алгоритму. Стан (позначимо його A)
представляється у вигляді масиву 5×5, елементами якого є 64-бітові слова,
ініційовані нульовими бітами (тобто, розмір стану складає 1600 бітів) [15].
Функція f виконує 24 раунди, в кожному з яких проводяться наступні дії:
C[x] = A[x, 0] A[x, 1] A[x 2] A[x 3] A[x 4], x = 0...4;
D[x] = C[x — 1] (З[x + 1] >>> 1), x = 0...4;
A[x, y] = A[x, y] D[x], x = 0...4, y = 0...4;
B[y, 2x + 3y] = A[x, y] >>> r[x, y], x = 0...4, y = 0...4;
A[x, y] = B[x, y] (~B[x + 1, y] & B[x + 2, y]), x = 0...4, y = 0...4,
32
Слід зазначити, що функція f, яка суттєво відрізняє SHA-3 від інших
алгоритмів сімейства SHA використовує лише операції. Ці операції є стійкими
до атак, що використовують витік даних по побічних каналах зв’язку.
Результуюче хеш-значення в SHA-3 обчислюється в процесі виконання
«вичавлень» фази криптографічної губки. Основу цих «вичавлень» становить
функція f. Можливі розміри геш-значень, які дозволяє отримати алгоритм
SHA-3 складає: 224, 256, 384 512 біт.
Оригінальний алгоритм Keccak має багато параметрів, які
налаштовуються з метою забезпечення оптимального
співвідношення криптостійкості та підвищення швидкодії для застосування
алгоритму на апаратній платформі. Регульованими величинами в даному
випадку є: розмір блоку даних, розмір стану алгоритму, кількість раундів у
функції f() та інші [14].
В залежності від типу параметрів на базі алгоритм Keccak можна
отримати ціле сімейство хеш-функції. Наприклад, такі, як представлені в
таблиці 2.2 [14].
Таблиця 2.2- сімейство хеш-функції SHA-3
Функція Формула
SHA3-224(M) Кессак[448](M||01,224)
SHA3-256(M) Кессак[512](M||01,256)
SHA3-384(M) Кессак[768](M||01,384)
SHA3-512(M) Кессак[1024](M||01,512)
SHAKE128(M,d) Кессак[256](M||1111,d)
SHAKE256(M,d) Кессак[512](M||1111,d)
2.3 Алгоритм DSA та його робота в якості цифрового підпису
33
Як було сказано вище, одним з перспективних та зручних для реалізації
ідеї модифікування алгоритмів ЕЦП є DSA. Дана асиметрична схема має
широке практичне застосування. Наприклад в SSL сертификатах. Компанія
DigiCert, яка займається випуском таких сертифікатів пропонує на вибір три
різних алгоритму шифрування - RSA, DSA, ECC.
Для того, аби провести подальшу модифікацію алгоритму ЕЦП
розглянемо більш детально обраний базовий алгоритм – DSA.
2.3.1 Опис DSA та принципу його роботи
DSA (Digital Signature Algorithm — алгоритм цифрового підпису) являє
собою криптографічний алгоритм, побудований за асиметричною схемою. В
даному алгоритмі використовується пара ключів (відкритий та закритий).
Закритий ключ потрібен для створення електронного підпису, але не для
шифрування (на відміну від алгоритму RSA та схеми Ель-Гамаля).
Електронний підпис створюється таємним чином (закритим ключем), але
може бути перевірений публічно (для чого використовується відповідний і
належним закритому - відкритий ключ). Це означає, що тільки один суб'єкт
може створити підпис повідомлення, але хто завгодно може перевірити його
коректність. Така схема є типовою для більшості сучасних технологій
електронного цифрового підпису. Криптографічна стійкість даного алгоритму
ґрунтується на обчислювальній складності взяття логарифмів у скінченних
числових полях.
До основних характеристик DSA можна віднести:
- розмір ключа (закритого): 160-256 біт, відкритого: 1024-3072 біт.
- розмір електронного підпису: два цілих числа в діапазоні від 160
до 256 біт.
Розглянемо в спрощеному вигляді приклад роботи даного алгоритму.
34
2.3.2 Принцип роботи алгоритма DSA
В алгоритмі DSA хеш-функція використовується при генерації підпису
для отримання стисненої версії повідомлення (даних) [17]. Така хеш-функції
інакше зветься функцією згортки. Отримані дані обробляються за допомогою
алгоритму DSA для отримання цифрового підпису. Для перевірки підпису
використовується та ж сама хеш-функція, що і для його створення. Хеш-
функція для алгоритма DSA описана в стандарті SHS (Secure Hash Standard)
[16].
До складу стандарту SHS входить сімейство криптографічних функцій
SHA-1, SHA-2 та інші. Всі ці хеш-функції використовуються для обчислення
стислого представлення цифрових даних (повідомлень). Будь-яка з хеш-
функцій даного стандарту використовується при генеруванні підпису для
отримання стиснутої версії даних (дайджесту). Для вхідного повідомлення,
яке належить підписати, одна з обраних криптографічних функцій стандарту
SHS створює дайджест повідомлення (хеш-значення). Розмір цього дайджесту
знаходиться в діапазоні від 160 до 512 біт (від 20 до 64 байт) і залежить
виключно від обраного типу алгоритму (SHA-1, SHA-2 тощо). Той самий
«дайджест» повідомлення має бути отриманий тією ж особою, що займається
перевіркою електронного підпису на іншій стороні криптосхеми. Зрозуміло,
що будь-які зміни повідомлення, що можуть мати місце під час його передачі,
з великою ймовірністю призведуть до зміни «дайджесту», і підпис майже на
100% не зможе пройти перевірку. При цьому робиться висновок при зміну
цілісності повідомлення в процесі передавання (санкціоновану або
несанкціоновану).
Розрядність отриманого результату роботи хеш-функції в схемі DSA
(так і ізольовано) сильно впливає на стійкість результату хешування до колізій.
Зважаючи на даний факт, після доказу успішності теоретичних атак на хеш-
функцію SHA-1 зі 160-бітним дайджестом повідомлення Національний
інститут стандартів і технологій США (NIST) повністю відмовився від
35
використання даного алгоритму хеш-функції SHA-1 в схемах електронного
цифрового підпису.
Функціональна схема роботи алгоритму ЕЦП DSA показаний на рис.2.1.
Рис.2.4 - Функціональна схема роботи алгоритму ЕЦП DSA
Як видно з рис.3.1 алгоритм ЕЦП DSA містить 3 механізми:
− побудова параметрів схеми ЕЦП
− підпис повідомлення
− перевірка підпису повідомлення
Для того, щоб реалізувати побудову параметрів ЕЦП, підписування
повідомлення, перевірка підпису повідомлення в даному алгоритмі
використовуються 2 допоміжні алгоритми (S,V):
1) для створення підпису повідомлення (S)
2) для перевірки підпису повідомлення (V).
36
Обидва алгоритми спочатку обчислюють хеш повідомлення,
використовуючи криптографічну хеш-функцію.
Алгоритм S використовує хеш та секретний ключ для створення підпису.
Алгоритм V використовує хеш повідомлення, підпис та відкритий ключ
для перевірки отриманого електронного підпису.
2.3 Генерування ЕЦП в DSA
Для побудови системи цифрового підпису необхідно виконати наступні
кроки:
1. Вибрати криптографічну хеш-функції H(x).
2. Вибрати просте числа q достатньо великої розрядності, розмірність
якого N в бітах має співпадати з розмірністю в бітах значень хеш-функції H(x).
3. Вибрати просте число p, таке, що (p-1) ділиться на q без остачі. Бітова
L-1 L
довжина числа p позначається, як L(2 <P<2 ).
4. Вибрати число g таке, що його мультиплікативний порядок по модулю
(p-
p дорівнює числу q. Для його отримання можна скористатися формулою g=h
1)/q
, де h — деяке довільне число, h(1;p-1) таке, що g1. В більшості випадків
значення h = 2 задовольняє даній вимозі.
Секретний ключ є числом в д=діапазоні x(0,q). Відкритий ключ
x
обраховується по формулі y=g mod p.
Відкритими параметрами алгоритму ЕЦП DSA є числа (p, q, g, y).
Закритий параметр в даному алгоритмі тільки один – число x. Числа (p, q, g)
можуть бути загальними для групи користувачів, а числа x і y - відповідно
закритий і відкритий ключ конкретного користувача системи ЕЦП.
Під час підписування повідомлення використовуються секретні числа x
і h, причому число h має обиратися випадковим чином при обчисленні підпису
для кожного наступного повідомлення.
37
Оскільки (p, q, g) можуть бути використані для декількох користувачів,
на практиці часто ділять користувачів за деякими критеріями групи з
однаковими (p, q, g). Тому ці параметри називають доменними параметрами
(Domain Parameters).
2.3.1 Підписування повідомлення в DSA
Типова процедура підписування повідомлення в алгоритмі DSA
виглядає так:
1. Обирається випадкове число k(0,q).
k
2. Обчислюється значення r=(g mod p) mod q.
3. Якщо в результаті обчислення на попередньому кроці r=0, то
обираємо інше значення параметра k і переходимо знову до виконання кроку
2.
-1
4. Обчислюємо значення s=k (H(m)+x*r) mod q.
5. Якщо на попередньому кроці отримали значення s=0, то обираємо
інше значення k.
6. Електронним підписом вважається отримана внаслідок
проведених на кроках 1-5 ключова пара (r,s) загальною довжиною 2N.
Обчислювально складні операції на етапі підписування:
k
- піднесення до ступеню за модулем (обчислення g mod p), для
якого існують швидкі алгоритми;
- обчислення хеша H(x), де складність залежить від обраного
алгоритму хешування та розміру вхідного повідомлення;
-1
- знаходження зворотного елементу k mod p можна реалізувати
використовуючи, наприклад, розширений алгоритм Евкліда або малу теорему
-1 q-2
Ферма у вигляді k mod q = k mod q.
2.3.2 Перевірка цифрового підпису в алгоритмі DSA
38
Для того, аби перевірити автентичність підпису необхідно реалізувати
наступну послідовність дій:
-1
1. Обчислення w=s mod q
2. Обчислення u =H(m)*w*mod q
1
3. Обчислення u =r*w*mod q
2
u u
4. Обчислення v=(g * y mod p) mod q
1 2
5. Підпис вірний, якщо v=r
При перевірці підпису можна констатувати, що до обчислювально-
складних операцій можна віднести:
u u
- піднесення до ступеню g * y
1 2;
- обчислення хеша H(x);
-1
- знаходження оберненого елементу s mod q.
Обидва алгоритми спочатку обчислюють хеш повідомлення,
використовуючи хеш-функцію. Алгоритм S використовує хеш та секретний
ключ для створення підпису, а алгоритм V використовує хеш повідомлення,
підпис та відкритий ключ для перевірки підпису.
При практичній реалізації ЕЦП, побудованої на базі алгоритму DSA
потрібна створити базу даних відповідності між реальними реквізитами автора
(це може бути як приватна особа, так і організація) і відкритими ключами, а
також усіма необхідними параметрами схеми цифрового підпису (хеш-
функція, прості числа). Наприклад, подібною базою може бути центр
сертифікації ключів ЕЦП.
39
РОЗДІЛ 3
МОДИФІКАЦІЯ БАЗОВОГО АЛГОРИТМУ ЕЦП DSA
Як було показано в пункті 2.3 існує декілька слабких місць при
функціонування алгоритму УЦП DSA. Серед них можна виділити
обчислювально складні операції на етапі підписування, зокрема - обчислення
хеша H(x). При отриманні хешу складність перетворення залежить від
обраного алгоритму хешування та розміру вхідного повідомлення. Отже існує
потреба в проведенні даної модифікації шляхом отримання нової хеш-функції.
3.1 Приклад роботи DSA
Розглянемо приклад роботи алгоритму DSA з використанням
початкових параметрів малої розрядності. Нехай значення хеш – функції для
повідомлення M, Н=9.
Етап 1. Генерація параметрів
1. H=910=10012
2. Через те, що отримана в п.1 довжина хеша = 4 біти, то можна
обрати q=1110=10112
3. Обираємо p=23, через те, що 23-1=22=2*q
4. Обираємо g=22=4
Етап 2. Створення ключів
1. В якості секретного ключа оберемо число x=7
2. Тоді, відкритий ключ y=gxmod p= 47mod23=16384mod
23=(712*23+8) mod 23 = 8
Етап 3. Підпис повідомлення
1. Оберемо k=3
2. Тоді r=(gk mod p) mod q = (43 mod 23) mod 11 =7
3. r0, тоді переходимо до наступного кроку
40
4. s=k-1(H(m)+x*r)mod q=4(9+7*7)mod=1, де враховано, що 3-1mod 11
= 4
5. s0, тоді переходимо до наступного кроку
6. Підписом є пара чисел (r,s)=(7,1)
Етап 4. Перевірка підпису
1. w=s-1 mod q =1-1 mod 11=1
2. u1=H(m)*w mod q = 9*1 mod 11 =9
3. u2=r*w mod q = 7*1 mod 11
4. v=(gu u
1*y 2 mod p) mod q = (49**87 mod 23) mod 11 = 7
5. Отримали, що v=r, значить підпис коректний.
3.2 Модифікація алгоритму цифрового підпису DSA
Запропонована хеш-функція, яка працює за принципом звичайної 64-
бітової функції згортки в 4 кроки за модулем 2. До алгоритму додано
модифікації, які покращують її криптостійкість і зменшують ймовірність
появи колізій.
Принцип роботи наступний:
Шифрування проводитися в декілька етапів:
Крок 1: Підготовка початкових даних:
В кінець повідомлення дописують 8/16/32/64-бітне представлення
довжини даних (кількість біт в повідомленні) до моменту вирівнювання.
Спочатку записують 1/2/4 молодший байти, потім – 1/2/4 старші. Якщо
довжина повідомлення перевищує 28-1, то дописуються тільки молодші біти
(еквівалентно взяттю по модулю28).
Після цього довжина потоку стане кратною 32/64/128/256/512.
Обчислення будуть засновуватися на представленні цього потоку у вигляді
масиву слів по 32/64/128/256/256 біт.
41
Наприклад, в оригінальному алгоритмі md5 виконується попереднє
«вирівнювання» даних, тобто, якщо, маємо на вході функції число 130 (в
бінарному форматі дане число виглядає, як 10000010), то, якщо додати до
нього одиничний біт, то отримаємо: 100000101. Після чого в кінець
отриманого числа дописуються нулі поки довжина потоку не досягне 448(56
байт) по модулю 512(64 байти): 10000010100…000. Тобто, дописувати «0» в
кінець повідомлення треба доти, доки не виконається умова: (N%512==448) –
бітова довжина отриманого повідомлення по модулю 512 не почне
дорівнювати 448.
Взявши за основу описаний вище принцип, всі наступні кроки роботи
алгоритму модифікованої хеш-функції описані в п.3.3.1.
Крок 2. Візьмемо повідомлення розміром 64 байти (для наочності).
для якого треба отримати хеш, наприклад, розмірністю 64 байти (чим
більше розмірність взятого повідомлення, тим краще для стійкості функції):
M= 1101 0010 1100 1100 1101 0100 0011 1101 1000 1101 1010 0001 0101 1100
1110 1101
Крок 3. Візьмемо повідомлення M для якого треба отримати хеш,
наприклад, розмірністю 64 біт (чим більше розмірність взятого повідомлення,
тим краще для стійкості функції):
b1= 1101 0010 1100 1100
b2= 1101 0100 0011 1101
b3= 1000 1101 1010 0001
b4= 0101 1100 1110 1101
Крок 4. Реалізуємо для отриманих блоків b1, b2, b3, b4 операцію XOR
таким чином:
b12 = b1 XOR b2 далі b23= b12 XOR b3, після b34 = b23 XOR b4
В результаті реалізації наступних перетворень:
b12 = b1 XOR b2 далі b23= b12 XOR b3, після b34 = b23 XOR b4
Отримаємо:
42
b12 = 0000 0110 1111 0001
b23 = 1000 1011 0101 0000
b34 = 1101 0111 1011 1101
Значення b34 і буде значенням нашої елементарної хеш-функції.
В зв'язку з тим, що замість 64 біт на вході, було отримано лише 64 біти
на виході (згортка).
3.2.1 Модифікація хеш-функції для алгоритму ЕЦП
Для реально взятого повідомлення:
Повідомлення (ПІБ –): 1000 1111 1100 1011 0010 1110 0010 1100 1011 1011
1011 0100 1111 0101 1101 0111 0000 0100 0010 1101 1111 1001 1111 0010 0110
0001 1101 1101 0000 0101 0110 1100 0011 1001 0011 1100 1110 1101 1101 1111
1101 1011 1100 1110 0011 1101 000
Крок 1.
На етапі підготовки даних змінюємо у нашому повідомленні значення
передостаннього біта на 1, останнього на 0 (для випадків, коли будуть тільки
нульові або тільки одиничні біти), а потім дописуємо дзеркально біти,
починаючи з кінця, поки дане повідомлення не буде кратне 64 (якщо не
вистачає бітів, дописуємо нулі):
Відкориговане повідомлення: 1000 1111 1100 1011 0010 1110 0010 1100
1011 1011 1011 0100 1111 0101 1101 0111 0000 0100 0010 1101 1111 1001 1111
0010 0110 0001 1101 1101 0000 0101 0110 1100 0011 1001 0011 1100 1110 1101
1101 1111 1101 1011 1100 1110 0011 1101 0100 1010.
Крок 2.
Розбиваємо відкориговане повідомлення на блоки по 16 біт і виконуємо
операцію XOR, виконавши інверсію 1 блоку:
b01: 0111 0000 0011 0100
b02: 0010 1110 0010 1100
b03: 1011 1011 1011 0100
43
b04: 1111 0101 1101 0111
b05: 0000 0100 0010 1101
b06: 1111 1001 1111 0010
b07: 0110 0001 1101 1101
b08: 0000 0101 0110 1100
b09: 0011 1001 0011 1100
b10: 1110 1101 1101 1111
b11: 1101 1011 1100 1110
b12: 0011 1101 0100 1010
H(M): 1011 1011 0111 0010 = 47986
3.2.2 Алгоритмічні реалізація модифікації ЕЦП
Етап 1: генерація параметрів:
− Хеш-функція: H = 47986;
− Вибір простого числа q, розмірність якого N в бітах співпадає з
розмірністю в бітах значень хеш-функції H: q = 30323;
− Вибір простого числа p, такого, що (p-1) ділиться на q: p = 60647 (q*2
+1);
− Вибір числа g такого, що g=h(p-1)/q, де h — деяке довільне число, h є (1;p-
1) таке, що g≠1: g = 2(p-1)/q = 4.
Етап 2: створення ключів:
− Секретним ключем є числом x є (0,q): x = 17;
− Відкритим ключем є число у, таке що y = gx mod p: y = 417 mod 60647 =
29612.
Етап 3: підпис повідомлення:
− Вибір випадкового числа k є (0,q): k = 11;
− Обчислення r = (gk mod p) mod q: r = (411 mod 60647) mod 30323 = 9661
mod 30323 = 9661;
− Вибір іншого k, якщо r=0: r≠0;
44
− Обчислення s = k-1 (H+x*r) mod q: s = k-1(47986+17*9661) mod 30323 =
8270*212223 mod 30323 = 19293;
− Вибір іншого k, якщо s=0: s≠0;
− Підписом є пара (r,s) = (9661, 19293).
Етап 4: перевірка підпису:
− Обчислення w = s-1 mod q: w = 19293-1 mod 30323 = 21545;
− Обчислення u1 = H*w mod q: u1 = 47986*21545 mod 30323 = 26008;
− Обчислення u2 = r*w mod q: u2 = 9661*21545 mod 30323 = 9173;
− Обчислення v = (gu1 * yu2 mod p) mod q: v = (426008*296129173 mod 60647)
mod 30323 = 9661 mod 30323 = 9661;
− Підпис вірний, якщо v=r: v = r = 9661, отже підпис вірний.
Даний алгоритм було реалізовано програмно мовою Python:
Код програми
main.py:
Дана реалізація передбачає використання:
1) Розширеного алгоритму Евкліда у власній реалізації –
gcdExtended().
2) Використання стандартних бібліотек мови Python: decimal, hash,
3) Нового механізму отримання хеш-функції – функції logic_xor();
inversion(); hash().
В програмі використовуються методи з модуля decimal. Дані методи
дозволяють виправити недоліки, які інколи виникають в програмі при роботі з
вбудованими числами типу float. Модуль decimal базується на трьох поняттях:
десяткове число, контекст обчислень і сигнали.
45
Рис.3.1 – лістинг коду 4
В програмі також використовуються методи з модуля користувацької
бібліотеки hash. В ній містяться основні функції, які використовуються в
програмному коді, який реалізує генерування хеш-значення власноруч
розробленої хеш-функцій.
Замість значень повідомлення mess можна використовувати інші
повідомлення, які будуть використовуватися для підписування в
модифікованому алгоритмі ЕЦП:
46
Рис.3.2 – лістинг коду 5
47
Безпосередньо програмний код створеного користувацького алгоритму
цифрового підпису для модифікованого алгоритму DSA наведений нижче:
Рис.3.3 – лістинг коду 6
48
Рис.3.4 – лістинг коду 6
49
В додатку А наведений повний програмний код програмної реалізації
модифікованого алгоритму цифрового підпису.
Результати роботи програмного засобу наведено на рис.3.1.
Рис.3.5 – Результати роботи програми
Як ми бачимо, результати співпадають, отже програмна реалізації
запропонованого алгоритму хеш-функції працює коректно.
50
ВИСНОВКИ
В результаті робіт з модифікації алгоритму цифрового підпису було:
− проаналізовано існуючі схеми електронного цифрового підпису та
технології їх використання;
− досліджено основні недоліки та переваги існуючих схем ЕЦП та
обрати варіант одної з таких схем для подальшої модифікації;
В результаті аналізу та дослідження існуючих алгоритмів та схем ЕЦП
асиметричного типу було:
− розробити криптографічну хеш-функцію по типу згортки на базі
існуючого алгоритму DSA, яка оперує значеннями в кільці числових полів
GF(2);
− створено програмний засіб мовою Python, який ілюструє роботу
модифікованої схеми ЕЦП та містить всі етапи даної схеми (формування
ключової пари, підписування та перевірки ЕЦП повідомлення).
51
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1. Закон України "Про електронні довірчі послуги" [Електронний
ресурс] // Відомості Верховної Ради (ВВР), № 45, ст.400. – 2017. – Режим
доступу до ресурсу: https://zakon.rada.gov.ua/laws/main/2155-19#Text
2. [Diffie, Hellman 1976] Diffie W., Hellman M. E. New directions in
cryptography // Information Theory, IEEE Transactions on. — 1976. — нояб. — т.
22, № 6. — с. 644—654. — ISSN 0018-9448. — DOI: 10.1109/TIT.1976.1055638.
3. Rivest, R. L.; Shamir, A.; Adleman, L. (1978). "A method for obtaining
digital signatures and public-key cryptosystems".Communications of the
ACM.21(2):120–126. CiteSeerX 10.1.1.607.2677. doi:10.1145/359340.359342.
ISSN 0001-0782. S2CID 2873616.
4. S. Goldwasser, S. Micali and R. L. Rivest, "A "Paradoxical" Solution
To The Signature Problem," 25th Annual Symposium onFoundations of Computer
Science, 1984., 1984, pp. 441-448, doi: 10.1109/SFCS.1984.715946.
5. Зміни до Вимог до формату підписаних даних [Електронний
ресурс] // Законодавство України. Верховна Рада України. – 2017. – Режим
доступу до ресурсу: https://zakon.rada.gov.ua/laws/show/z0424-17#Text.
6. FIPS PUB 186-4. FEDERAL INFORMATION PROCESSING
STANDARDS PUBLICATION. Digital Signature Standard (DSS). - Information
Technology Laboratory National Institute of Standards and Technology
Gaithersburg, MD 20899-8900 Issued July 2013. Access via:
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
7. Цифровий електронний підпис/ Архівовано 7 травня 2021
у Wayback Machine. // Юридична енциклопедія : [у 6 т.] / ред.
кол.: Ю. С. Шемшученко (відп. ред.) [та ін.]. — К. : Українська енциклопедія
ім. М. П. Бажана, 2004. — Т. 6 : Т — Я. — 768 с. — ISBN 966-7492-06-0.
8. Криптографічний захисту інформації. Функція гешування. ДСТУ
7564:2014. - К., Мінекономрозвитку, 2015. – 39 с.
52
9. Наказ 20.08.2012 №1236/5/453. Вимоги до формату посиленого
сертифіката відкритого ключа. // Верховна Рада України. – 2020. – С.
https://zakon.rada.gov.ua/laws/show/z1398–12#n25.
10. Rivest R., Rivest R. RFC 1321, The MD5 Message-Digest Algorithm
(англ.): The MD5 Message-Digest Algorithm // Request for comments — IETF,
1992. — 21 p. — ISSN 2070-1721 — doi:10.17487/RFC1321
11. RFC 3174. US Secure Hash Algorithm 1 (SHA1) [Електронний
ресурс] // D. Eastlake, 3rd. – 2001. – Режим доступу до ресурсу:
https://datatracker.ietf.org/doc/html/rfc3174.
12. Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, Yarik
Markov. The first collision for full SHA-1. CWI Amsterdam/Google Research.
13. Gilbert H., Handschuh H. Security Analysis of SHA-256 and
Sisters (англ.) // Selected Areas in Cryptography: 10th Annual International
Workshop, SAC 2003, Ottawa, Canada, August 14-15, 2003. Revised
Papers / M. Matsui, R. J. Zuccherato — Berlin, Heidelberg, New York,
NY, London [etc.]: Springer Berlin Heidelberg, 2004. — P. 175—193. — (Lecture
Notes in Computer Science; Vol. 3006) — ISBN 978-3-540-21370-3 —
ISSN 0302-9743; 1611-3349 — doi:10.1007/978-3-540-24654-1_13
14. Dworkin, M. (2015), SHA-3 Standard: Permutation-Based Hash and
Extendable-Output Functions, Federal Inf. Process. Stds. (NIST FIPS), National
Institute of Standards and Technology, Gaithersburg, MD, [online],
https://doi.org/10.6028/NIST.FIPS.202 (Accessed March 27, 2022)
15. The Keccak sponge function family / Сайт Noekeon, 2015-10-15 —
Офіційна сторінка хеш-функції Keccak(англ.)
16. Dang, Q. (2012), Secure Hash Standard (SHS), Federal Inf. Process.
Stds. (NIST FIPS), National Institute of Standards and Technology, Gaithersburg,
MD, [online], https://doi.org/10.6028/NIST.FIPS.180-4 (Accessed March 27, 2022)
53
17. Nguyen, Shparlinski The Insecurity of the Digital Signature Algorithm
with Partially Known Nonces. J. Cryptology 15, 151–176 (2002).
https://doi.org/10.1007/s00145-002-0021-3
54