Метод оцінки ймовірності зламу компонент ЕЦП

Громовий, Сергій Павлович

Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал: https://er.chdtu.edu.ua/handle/ChSTU/7755

Назва:	Метод оцінки ймовірності зламу компонент ЕЦП
Автори:	Кунченко-Харченко, Валентина Іванівна Громовий, Сергій Павлович
Ключові слова:	електронний цифровий підпис;криптографічні алгоритми;хеш-функції;криптостійкість;ймовірність зламу;dsa та ecdsa
Дата публікації:	2021
Короткий огляд (реферат):	Електронний цифровий підпис та його елементи, основні алгоритми і компоненти ЕЦП, аналіз ймовірності зламу хеш-функції ЕЦП
URI (Уніфікований ідентифікатор ресурсу):	https://er.chdtu.edu.ua/handle/ChSTU/7755
Розташовується у зібраннях:	125 Кібербезпека та захист інформації (Безпека інформаційних і комунікаційних систем)

Файли цього матеріалу:

Файл	Опис	Розмір	Формат
М_125_Громовий_Кунченко-Харченко.pdf Restricted Access		2.04 MB	Adobe PDF	Переглянути/Відкрити Запит копії

Показати повний опис матеріалу Перегляд статистики

Усі матеріали в архіві електронних ресурсів захищено авторським правом, усі права збережено.

Extracted text

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
Факультет електронних технологій і робототехніки
Кафедра робототехнічних і телекомунікаційних систем та кібербезпеки

Пояснювальна записка

до кваліфікаційної роботи

магістра
(освітньо-кваліфікаційний рівень)

на тему «Метод оцінки ймовірності зламу компонент ЕЦП»

Виконав студент 2 курсу, групи БІ-001

Спеціальності 125 - «Кібербезпека»,
освітньої програми «Безпека
інформаційних і комунікаційних систем»
(шифр і назва спеціальності)
Громовий С.П.
(прізвище та ініціали)
Керівник Кунченко-Харченко В.І.
(прізвище та ініціали)
Рецензент Чепинога А.В.
(прізвище та ініціали)

Черкаси 2021
Форма № Н-9.01

ЧЕРКАСЬКИЙ ДЕРЖАВНИЙ ТЕХНОЛОГІЧНИЙ УНІВЕРСИТЕТ
(повне найменування вищого навчального закладу)
Факультет електронних технологій і робототехніки _______________________________________
(повна назва)
Кафедра робототехнічних і телекомунікаційних систем та кібербезпеки
(повна назва)
Освітньо-кваліфікаційний рівень магістр

Спеціальність 125 – «Кібербезпека»

Освітня програма Безпека інформаційних і комунікаційних систем

ЗАТВЕРДЖУЮ
Завідувач кафедри д.т.н., проф.
В.В. Палагін
“___” _____________ 2021 року

З А В Д А Н Н Я
НА КВАЛІФІКАЦІЙНУ РОБОТУ МАГІСТРА СТУДЕНТУ
Громовому Сергію Павловичу
(прізвище, ім’я, по батькові)

1. Тема роботи «Метод оцінки ймовірності зламу компонент ЕЦП» .
____________________________________________________________________________________
керівник роботи Кунченко-Харченко В.І, к.т.н., професор_____ _____________________________
(прізвище, ім’я, по батькові, науковий ступінь, вчене звання)
затверджені наказом Черкаського державного технологічного університету від
«21» Вересня2021 року №289/01.
2. Строк подання студентом роботи «23» грудня 2021 р.
3. Вихідні дані до роботи IEEE, FIPS, DSA, ECDSA, Типи алгоритмів ЕЦП, Принципи побудови
ЕЦП, Недоліки існуючих схем ЕЦП, Теорія надійності та криптостійкості, Оцінки ймовірності
зламу ЕЦП, Хеш-функції.
4. Зміст розрахунково-пояснювальної записки (перелік питань, що їх належить розробити)
Вступ, Розділ 1 Електронний цифровий підпис та його елементи, Розділ 2 Основні алгоритми і
компоненти ЕЦП, Розділ 3 Аналіз ймовірності зламу хеш-функцій ЕЦП, Висновок, Список
використаних джерел.
5. Перелік графічного матеріалу (з точним зазначенням обов’язкових креслень, плакатів):
мультимедійна презентація “Метод оцінки ймовірності зламу ЕЦП” – 14 слайди (додається до
роботи).

6. Консультанти розділів роботи
Підпис, дата
Розділ Прізвище, ініціали та посада консультанта
завдання видав завдання прийняв

7. Дата видачі завдання 21.09.2021 .

КАЛЕНДАРНИЙ ПЛАН

№ Строк виконання
Назва етапів кваліфікаційної роботи магістра Примітка
з/п етапів роботи
1. П ошук і аналіз інформації по заданій темі 23.09.2021-
30.09.2021
2. Н аписання І розділу “ЕЛЕКТРОННИЙ 01.10.2021-
ЦИФРОВИЙ ПІДПИС ТА ЙОГО ЕЛЕМЕНТИ” 19.10.2021
3. Н аписання ІІ розділу роботи “ОСНОВНІ 20.10.2021-
АЛГОРИТМИ І КОМПОНЕНТИ ЕЦП” 07.11.2021
4. Н аписання ІІІ розділу “ АНАЛІЗ ЙМОВІРНОСТІ 08.11.2021-
ЗЛАМУ ХЕШ-ФУНКЦІЇ ЕЦП ” 24.11.2021
5. Н аписання вступу і висновків, складання списку 25.11.2021
літератури
6. О формлення кваліфікаційної роботи магістра 01.12.2021
7. П одання роботи в ЕК 20.12.2021
8. З ахист роботи в ЕК 23.12.2021

Студент ____________________Громовий С.П.
(підпис) (прізвище та ініціали)
Керівник роботи Кунченко-Харченко В.І.
(підпис) (прізвище та ініціали)

ЗМІСТ

ВСТУП 6
РОЗДІЛ 1 ЕЛЕКТРОННИЙ ЦИФРОВИЙ ПІДПИС ТА ЙОГО 8
ЕЛЕМЕНТИ
1.1 Загальні питання побудови та практичного застосування 8
алгоритмів ЕЦП
1.2 Електронний підпис та типи алгоритмів ЕЦП 9
1.3 Базові принципи побудови ЕЦП на відкритому ключі 13
РОЗДІЛ 2 ОСНОВНІ АЛГОРИТМИ І КОМПОНЕНТИ ЕЦП 15
2.1 Існуючі схеми алгоритми ЕЦП 16
2.2 Алгоритми ЕЦП с відкритим ключем 17
2.3 Протоколи для систем ЕЦП 24
2.4 Недоліки існуючих схем ЕЦП та їх виправлення 25
РОЗДІЛ 3 АНАЛІЗ ЙМОВІРНОСТІ ЗЛАМУ ХЕШ-ФУНКЦІЇ ЕЦП 27
3.1 Загальна теорія надійності та криптостійкості компонент ЕЦП 27
3.2 Математичний апарат для оцінки ймовірності зламу ЕЦП 29
3.3 Існуючі методи та алгоритми атак на хеш-функції 31
3.4 Методи та алгоритми атак на хеш-функції 33
ЗАГАЛЬНІ ВИСНОВКИ 41
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ 43
ДОДАТОК А 47

ЧДТУ.21.20102.005.ПЗ
Змн. Арк. № докум. Підпис Дата
Розроб. Громовий С.П. Літ. Арк. Акруш ів
Перевір. Кунченко-Харченко В.І. Метод оцінки ймовірності 4 45
Реценз. Чепинога А.В. зламу компонент ЕЦП
Н. Контр. Кунченко-Харченко В.І. ЧДТУ БІ-001
Затверд. Палагін В.В.

Список умовних позначень і скорочень

ЕП – Електронний підпис
ЕЦП – Електронний цифровий підпис
IEEE - (англ.Institute of Electrical and Electronics Engineers) Институт
инженеров электротехники и электроники
FIPS - (англ.Federal Information Processing Standards) Федеральні
стандарти обробки інформації
DSA - (англ.Digital Signature Algorithm) криптографічний алгоритм з
використанням відкритого ключа для створення електронного підпису
ECDSA - (англ.Elliptic Curve Digital Signature Algorithm) алгоритм з
відкритим ключем для створення цифрового підпису, визначений кільцем
цілих чисел, в групі точок еліптичної кривої.

Арк.
ЧДТУ.21.20102.005.ПЗ
5
Змн. Арк. № докум. Підпис Дата

ВСТУП

Сьогодні технологія електронного цифрового підпису (ЕЦП) є
поширеною технологією захисту цілісності даних. Деякі механізми даної
технології (хеш-функції) дуже широко використовуються також і в системах
генерації криптовалют. Розповсюдженість схем ЕЦП з використанням різних
хеш-функцій у прикладних системах викликає необхідність оцінки рівня
безпеки даних, які захищаються за допомогою даної технології. У багатьох
публікаціях досліджується проблема криптостійкості або ймовірності зламу
різних елементів ЕЦП [1-7]. Окремо можна виділити проблеми дослідження
ймовірності зіткнень першого або другого роду в генерованих значеннях
хеш-функцій [1-3], [5],[7],[9]. Для полегшення оцінки виявлення колізій
(поява двох однакових значень хеш-функцій) часто використовують парадокс
днів народження [7,8].
Актуальність теми пояснюється необхідністю врахування недоліків
окремих компонент ЕЦП при створенні практичних систем електронного
підпису, які можуть базуватися на різних криптографічних функціях.
Новизною роботи є аналіз стандартів, алгоритмів та компонент ЕЦП з
виділенням вразливої ланки хеш-функції та формування системного підходу
щодо оцінки ймовірності її зламу.
Для розв’язку даної задачі слід розв’язати наступні питання:
1) проаналізувати стандарти, алгоритми та хеш-функції, які
використовуються в електронному цифровому підписі (ЕЦП).
2) Проаналізувати основні компоненти електронного підпису.
Проаналізувати причини колізій, методи, алгоритми хеш-атак.
3) Сформувати математичний апарат для оцінки ймовірності
порушення хеш-функцій на основі різних статистичних та ймовірнісних
методів.
Арк.
ЧДТУ.21.20102.005.ПЗ
6
Змн. Арк. № докум. Підпис Дата

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

Арк.
ЧДТУ.21.20102.005.ПЗ
7
Змн. Арк. № докум. Підпис Дата

РОЗДІЛ 1

ЕЛЕКТРОННИЙ ЦИФРОВИЙ ПІДПИС ТА ЙОГО ЕЛЕМЕНТИ

1.1 Загальні питання побудови та практичного застосування
алгоритмів ЕЦП

У деяких країнах, зокрема в Канаді, Південній Африці, США, Алжирі,
Туреччині, Індії, Бразилії, Індонезії, Мексиці, Саудівській Аравії, Уругваї,
Швейцарії, Чилі, Росії, Україні та Європейському Союзі, електронні підписи
мають юридичне значення. Тому оцінка ймовірності зламу елементів ЕЦП
має велике практичне значення.
В даний час стабільність практично всіх сучасних стандартів ЕЦП
базується на складності розв’язання задачі дискретного логарифма в групі
точок еліптичних кривих [9]. Причому стандарти отримання основного
елемента інформаційної безпеки в ЕЦП – хеш-функцій дуже схожі.
Наприклад, тепер будь-яка схема ЕЦП повинна визначати щонайменше три
функціональні алгоритми, зокрема, алгоритм формування пари ключів для
підпису та її перевірки, алгоритм підпису, алгоритм перевірки підпису.
Розглянемо стандарти ЕЦП України, Росії та США. На даний час текст
специфікації ДСТУ 4145-2002 на алгоритм ЕЦП існує у вигляді відповідного
документа [4],[10-12]. Цей алгоритм заснований на еліптичних кривих над
полем F(2) (несуперсингулярні криві). Стандарт використовує криві в
поліноміальних і оптимальних нормальних базах. Причому, криві в
поліноміальному базисі можуть бути другого і третього типів. Основою для
розробки цього стандарту є міжнародний стандарт IEEE 1363a. ДСТУ 4145-
2002 є автентичним порівняно з IEEE 1363a, завдяки використанню власної
функції хешування. В якості алгоритму хеш-функції використовується
Арк.
ЧДТУ.21.20102.005.ПЗ 8
Змн. Ар к. № докум. Підпис Дата
міждержавний стандарт ГОСТ Р 34.311-95 (раніше ГОСТ 28147-89 в режимі
імітації вставки). У США існує нормативний документ FIPS 202, який описує
вимоги до алгоритму хешування в системах EDS, де в якості функції
хешування рекомендується використовувати «SHA-3 Standard: Permutation-
Based Hash and Extendable-Output Functions» [13].
Якщо порівняти державні стандарти на алгоритми ЕЦП у країнах, де є
законодавчі вимоги до алгоритмів та функцій у схемах ЕЦП, то, наприклад, в
Україні, Росії та США вони схожі, але відрізняються лише деякими
числовими параметрами та деталями: генерація пари ключів, механізм
розрахунку та перевірка підпису. Зокрема ці три алгоритми є варіантами
схеми Ель-Гамаля. [14].
Враховуючи високу подібність математичного апарату для процесу
пошуку та визначення криптостійкості основних криптографічних
алгоритмів ЕЦП, в цілому можна перенести отримані значення оцінок
ймовірності зламу хеш-функцій в ЕЦП на більшість з існуючих схем. Таким
чином, у порівнянні з існуючими методами, розглянутими в [7,8],
створюваний підхід щодо застосування методу оцінки ймовірності зламу
ЕЦП дозволить підтвердити можливість використання існуючого
математичного апарату для систем з ЕЦП.
1.2 Електронний підпис та типи алгоритмів ЕЦП

Електронний підпис (ЕП) або електронний цифровий підпис (ЕЦП) –
являє собою інформацію в електронній формі. Ця інформація приєднана до
іншої інформації в електронній формі (електронний документ) або іншим
чином та завжди пов'язана з тією інформацією, яка підписується даним ЕЦП.
Головним призначенням ЕЦП є визначення особи, яка підписала
інформацію (електронний документ).
За своєю суттю електронний підпис є реквізитом електронного
Арк.
ЧДТУ.21.20102.005.ПЗ 9
Змн. Арк. № докум. Підпис Дата

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

Рис.1.1 - Загальна схема для формування та перевірки ЕЦП

Існує кілька схем побудови цифрового підпису:
- на основі симетричних криптоалгоритмів [15];
Незважаючи на існування симетричних алгоритмів ЕЦП та їх
теоретичної пристосованості для підписування електронного документу, їх
використання не зручно для таких задач. Використання симетричних
алгоритмів передбачає наявність у системі ЕЦП третьої особи - арбітра, який
користується довірою обох сторін. В таких схемах авторизацією документа є
сам факт шифрування його секретним ключем та передача його арбітру.
Арк.
ЧДТУ.21.20102.005.ПЗ 10
Змн. Ар к. № докум. Підпис Дата
Набагато частіше використовуються алгоритми ЕЦП, що ґрунтуються на
асиметричних криптосхемах. Така схема є більш зручною і безпечною.
- на основі асиметричних криптоалгоритмів.
ЕЦП на основі алгоритмів асиметричного шифрування на даний
момент найбільш розповсюджені і знаходять найширше застосування в
практичному застосуванні.
Крім цього, існують інші різновиди цифрових підписів (груповий
підпис, незаперечний підпис, довірений підпис), які є модифікаціями
описаних вище схем [15]. Їхня поява зумовлена різноманітністю завдань, які
вирішуються за допомогою ЕП.

Рис.1.2 – схема генерування і перевірки ЕЦП

Загальновизнана схема цифрового підпису охоплює три процеси:
− генерація ключової пари. За допомогою алгоритму генерації
Арк.

ЧДТУ.21.20102.005.ПЗ
1 1
Змн. Арк. № докум. Підпис Дата

ключа з набору можливих закритих ключів з рівним значенням ймовірності
обирається закритий ключ та обчислюється відповідний йому відкритий
ключ.
− формування підпису. Для заданого електронного документа за
допомогою закритого ключа обчислюється електронний підпис;
− перевірка (верифікація) підпису. Для даних документа та підпису
за допомогою відкритого ключа визначається дійсність (автентичність)
підпису.
Для того, щоб використання цифрового підпису мало сенс, необхідно
обов’язкове виконання двох умов:
− верифікація підпису повинна здійснюватися відкритим ключем,
який відповідає саме тому закритому ключу, який використовувався під час
підписання;
− без володіння закритим ключем повинно бути надзвичайно
складно створити легітимний цифровий підпис.
Електронний цифровий підпис будується на основі двох компонентів:
1) змісту інформації, що підписується,
2) особистої інформації (код, пароль, ключ) особи, хто підписує даний
документ.
Очевидно, що зміна кожної компоненти (змісту інформації, особистої
інформації) призводить до зміни електронного цифрового підпису.
Бітовий рядок, який приєднується до документа після підписання і
називається електронним цифровим підписом. Даний рядок і є підписом,
який пов'язаний як з автором, так і з самим документом за допомогою
криптографічних методів, і не може бути підроблений за допомогою
звичайного копіювання.
Взагалі загальною рисою більшості сучасних асиметричних
криптоалгоритмів, які використовуються для систем ЕЦП є те, що відкритий
і закритий ключ утворюють ключову пару. Кожному відкритому ключу
Арк.
ЧДТУ.21.20102.005.ПЗ
12
Змн. Арк. № докум. Підпис Дата

відповідає лише один пов’язаний з ним закритий ключ. Тобто, підбір різних
комбінацій пар відкритих та закритих ключів неможливий теоретично. На
практиці реалізувати такий підбір можливо лише для вкрай примітивних та
коротких початкових числових параметрів алгоритму електронного підпису.
1.3 Базові принципи побудови ЕЦП на відкритому ключі

Технологія електронного підпису, що широко використовується на
даний, заснована на асиметричному шифруванні з відкритим ключем і
спирається на наступні принципи:
можна згенерувати кілька дуже великих чисел (відкритий ключ та
закритий ключ) так, щоб, знаючи відкритий ключ, не можна було б
обчислити закритий ключ за розумний термін. Механізм генерації ключів
чітко визначений і є загальновідомим. Тут кожному відкритому ключу
відповідає певний закритий ключ. Якщо, наприклад, Петро Петренко
публікує на сервері свій відкритий ключ, можна бути впевненим, що
відповідний закритий ключ є тільки в нього (інакше зловмисник може її
використати за своїм розсудом).
Існують надійні методи шифрування, що дозволяють зашифрувати
повідомлення закритим ключем так, щоб розшифрувати його можна було
лише відкритим ключем [16]. Механізм такого шифрування загальновідомий.
Якщо електронний документ розшифровується за допомогою
відкритого ключа [17,18] то можна бути цілком впевненим, що він був
зашифрований за допомогою унікального закритого ключа. Якщо документ
розшифрований за допомогою відкритого ключа Петра Петренка, то це
підтверджує його авторство. Адже, зашифрувати цей документ міг лише
Петренко, тому, що він є єдиним володарем унікального закритого ключа.
Однак шифрувати весь документ нереально. Це пов’язано з тим, що
Арк.
ЧДТУ.21.20102.005.ПЗ
1 3
Змн. Арк. № докум. Підпис Дата

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

Арк.
ЧДТУ.21.20102.005.ПЗ 1 4
Змн. Арк. № докум. Підпис Дата

РОЗДІЛ 2

ОСНОВНІ АЛГОРИТМИ І КОМПОНЕНТИ ЕЦП

2.1 Існуючі схеми алгоритми ЕЦП

Як було відмічено в попередньому розділі, перші варіанти цифрового
підпису було реалізовано за допомогою симетричних криптосистем. В якості
алгоритму криптографічного перетворення раніше можна було
використовувати будь-яку симетричну криптосистема, що володіє
спеціальними режимами функціонування. Сьогодні в практичних реалізаціях
систем захисту інформації найбільш розповсюдженими є алгоритми
асиметричні алгоритми ЕЦП. Наприклад, такі:
RSA – криптографічний алгоритм з відкритим ключем, що базується на
обчислювальній складності задачі факторизації великих цілих чисел
DSA – алгоритм заснований на обчислювальній складності взяття
логарифмів в скінченних полях.
El-Gamal – являє собою криптосистему з відкритим ключем, яку
засновано на складності обчислення дискретних логарифмів у скінченному
полі. Криптосистема включає в себе алгоритм шифрування і алгоритм
цифрового підпису. Схема Ель-Гамаля лежить в основі колишніх стандартів
електронного цифрового підпису в США (DSA) і Росії. Являє собою
модифікацію алгоритму Діффі-Хеллмана. Даний алгоритм не
запатентований.
ECDSA – криптографічний алгоритм з відкритим ключем для
створення електронного цифрового підпису, аналогічний за будовою до
алгоритму DSA, але, на відміну від останнього, не над скінченним числовим
полем, а над групою точок еліптичної кривої.

Арк.
ЧДТУ.21.20102.005.ПЗ
15
Змн. Арк. № докум. Підпис Дата

Основні технічні характеристики даних алгоритмів наведені в таблиці
2.1.
Таблиця 2.1
Основні технічні характеристики сучасних алгоритмів ЕЦП
Назва Розмір ключа, біт Призначення Механізм
алгоритму криптостійкості
RSA до 4096 Шифрування та Базується на
ЕЦП складності задачі
«великих чисел».
El Gamal до 4096 Шифрування та Заснований на
ЕЦП складності задачі
обчислення
дискретних
логарифмів у
кінцевому полі.
DSA до 1024 ЕЦП Забезпечується
складністю
задачі пошуку
дискретного
логарифму у
кінцевому полі.
ECDSA 160 біт ЕЦП

Алгоритм RSA є одним з найперших алгоритмів з відкритим ключем.
Він включений до багатьох сучасних стандартів, реалізується в багатьох
практичних криптосистемах.
Особливістю алгоритму El-Gamal є те, що він дозволяє швидко

Арк.
ЧДТУ.21.20102.005.ПЗ 1 6
Змн. Арк . № докум. Підпис Дата
генерувати ключі без зниження стійкості. Даний алгоритм використовується
в якості допоміжного в алгоритмі DSA – стандарту DSS.
Алгоритм DSA довгий час залишався стандартом ЕЦП у США. Він
використовується для секретних і несекретних комунікацій.
Алгоритм ECDSA сьогодні є найбільш перспективним для
застосування алгоритмом ЕЦП. Головною його перевагою є можливість його
роботи на значно менших розмірах числових полів. Наприклад, при рівні
безпеки в 80 біт (тобто атакуючому необхідно приблизно 280 версій підписів
для розкриття секретного ключа, розмір відкритого ключа DSA дорівнює,
принаймні, 1024 біт, тоді як відкритого ключа ECDSA - всього 160 біт. З
іншого боку розмір підпису однаковий і для DSA, і для ECDSA [19].
2.2 Алгоритми ЕЦП с відкритим ключем

Всі сучасні процедури створення та перевірки електронного цифрового
підпису базуються на шифруванні з відкритим ключем.
В асиметричних криптосистемах (системах з відкритим ключем)
використовуються:
1) відкритий ключ – для шифрування;
2) відповідний йому секретний – для дешифрування:

Ek1(P) = C
Dk2(C) = P,

де k1 – відкритий ключ, k2 – секретний ключ.
Застосування криптографії з відкритим ключем для створення ЕЦП
ґрунтується на таких принципах:
1) шифрування повідомлення відбувається секретним (закритим)
ключем,
Арк.
ЧДТУ.21.20102.005.ПЗ 17
Змн. Арк. № докум. Підпис Дата

2) дешифрування (перевірка підпису) – відкритим таким чином:

Ek1(P) = C
Dk2(C) = P.

де k1 – секретний, k2 – відкритий ключ.
Протокол підписання документа можна описати в наступний спосіб:
1. Аліса шифрує документ своїм закритим ключем (підписує його);
2. Аліса надсилає Бобу підписаний документ;
3. Боб розшифровує документ, використовуючи відкритий ключ Аліси
(перевіряючи цим достовірність підпису).
Процес підписання повідомлення закритим ключем k2 позначається, як
Sk2 (M), а процес перевірки автентичності підпису за допомогою відповідного
відкритого ключа k1 - Vk1(M).
Як зазначалося, застосування алгоритму RSA до створення ЕЦП
засновано на повідомлення секретним (закритим) ключем, і розшифруванні
– відкритим:

Ek1(P) = C.
Dk2(C) = P,

де k1 – секретний, k2 – відкритий ключ.

2.2.1 Найвідомішим і найпоширенішим алгоритмом створення та
перевірки ЕЦП є алгоритм DSA – алгоритм цифрових сигнатур.
Коротка характеристика алгоритму DSA:
- алгоритм з відкритим ключем;
- розмір ключа – від 512 до 1024 біт;

Арк.
ЧДТУ.21.20102.005.ПЗ 18
Змн. Арк. № докум. Підпис Дата

- під час перевірки достовірності сигнатури DSA працює в 10-40
разів повільніше за RSA;
- використовується лише для цифрового підпису, не для
шифрування.
Основними параметрами алгоритму DSA є:
Відкритий ключ ((p, q, g, y) з параметрами:
p – просте число довжиною від 512 до 1024 бітів;
q – 160-бітовий простий множник p-1;
g – = h(p-1)/q mod p, де h – будь-яке число < (p-1), для якого h(p-1)/q mod
p > 1;
y - = gx mod p (p-бітове число).
Закритий ключ (x) повинен задовольняти вимозі: x - < q (160-бітове
число).

2.2.2 Схема роботи DSA
Формування підпису повідомлення:
1. Аліса генерує випадкове число k, менше q;
2. Аліса генерує
r = (gk mod p) mod q
s = (k-1 (H(m) + x r )) mod q
де H(m) – хеш-функція
3. Аліса посилає Бобу свій підпис - (r, s).
Перевірка підпису виконується наступним чином:
1. Боб перевіряє підпис, в процесі чого обраховує:
w = s-1 mod q
u1 = (H(m) * w) mod q
u2 = (r w) mod q
v = ((g u1 * yu2 ) mod p ) mod q

Арк.
ЧДТУ.21.20102.005.ПЗ 19
Змн. Арк . № докум. Підпис Дата
2. Якщо виконується умова v = r , то підпис коректний.
В основі стандарту США (1994) DSS (Digital Signature Standard) лежить
алгоритм DSA та функція хешування SHA-1.
Системи ЕЦП, які визначаються більшістю стандартів, є
модифікаціями схеми формування ЕЦП Ель-Гамалю.
Відповідно до схеми Ель-Гамаля підписом до повідомлення mZp-1 є
розв’язок (r, s) Z*
p ´ Zp-1 рівняння виду:

���� ≡ ��������(������ ��) (1.1)

де p – просте число, g – первісний корінь Z*
p, y = gx mod p, x  Zp-1.
Відкритим ключем є тройка (p, q, y), секретним ключем – x.
Підпис створюється з використанням наступного алгоритму:
1. обирається випадкове число k Z* p-1;
2. обчислюється параметр r = gk mod p;
3. обчислюється параметр s = k-1(m-xr) mod (p-1).
Для криптоатаки на схему Ель-Гамаля необхідно розв’язати рівняння
(1.1) або:
− відносно s при обраному параметрі r;
− відносно r при обраному s;
− відносно s і r.
Для вирішення першої задачі необхідно вирішити задачу дискретного
логарифмування. Способи вирішення другої та третьої задачі на
сьогоднішній день недостатньо вивчені, але немає підстав припускати, що є
ефективні алгоритми вирішення у загальному випадку [19].
В алгоритмах ЕЦП, таких, як DSA і ECDSA використовують хеш-
функції.
Для підписування повідомлень необхідна пара ключів - відкритий і
Арк.
ЧДТУ.21.20102.005.ПЗ 20
Змн. Арк . № докум. Підпис Дата
закритий. При цьому закритий ключ повинен бути відомий тільки тому, хто
підписує повідомлення, а відкритий - будь-кому хто бажає перевірити
справжність повідомлення.
Для зменшення часу, необхідного для генерації та перевірки ЕЦП, а
також для скорочення його довжини застосовується різноманітні хеш-
функції. Причому, частіше за інші, функції групи SHA. Принцип
застосування функцій SHA-групи наведений в [20].
Відображення повідомлення, що підписується, отримане в результаті
застосування хеш-функції h, повинно мати невелику фіксовану довжину,
набагато меншу за довжину самого повідомлення.
Тоді, підписане повідомлення m буде мати наступний вигляд:

(m, S(h(m))), (1.2)

де S – функція генерування підпису.
Функція h, використана у виразі (1.2) повинна бути односторонньою -
не має існувати алгоритму поліноміальної складності для обчислення m за
відомим значення хеш-функції h(m).
Також загальнодоступними є параметри самого алгоритму.
Принцип роботи алгоритму ECDSA наступний:
1. Вибір хеш-функції H(x). Для використання алгоритму необхідно,
щоб повідомлення, яке підписується, було числом. Хеш-функція повинна
перетворити будь-яке повідомлення в послідовність бітів, які можна потім
перетворити в число.
2. Вибір великого простого числа q - порядок однієї з циклічних
підгруп групи точок еліптичної кривої. Зауваження: Якщо розмірність цього
числа в бітах менше розмірності в бітах
Арк.
ЧДТУ.21.20102.005.ПЗ 2 1
Змн. Арк. № докум. Підпис Дата

значень хеш-функції H(x) то використовуються тільки ліві біти значення
хеш-функції.
3. Простим числом p позначається характеристика поля
координат Fp.
2.2.3 Принцип роботи алгоритму DSA можна описати в наступному
вигляді (табл.2.2).
Таблиця 2.2
Принцип роботи алгоритму DSA
Опис етапу алгоритму Приклад виконання
Вибір хеш-функції H(x). Для використання Візьмемо повідомлення pt – це
алгоритму необхідно, щоб повідомлення, що число 15, тому використання
підписується, було простим числом. хеш-функції необов’язкове.
Вибір простого числа q, розмірність якого в бітах q=13
співпадає з розмірністю в бітах значень хеш-
функції H(x) або повідомлення.
Вибір простого числа p, такого, що (p-1) ділиться p=27
на q.
Вибір числа g такого, що його мультиплікативний h=2
порядок по модулю p дорівнює q. Для його
g=272/13 mod 27
обчислення можна скористатися формулою g=h(p-
1)/q mod p, де h – деяке довільне число, для якого
h(1;p-1) таке, що g1.
Вибір секретного ключа x, з умовою, що x(0,q). x=8; 8(0,13)
Параметр (x) зберігається в секреті.
Обчислення відкритого ключа по формулі y=gx (7)
mod p, набір (p,q,g,y) надається.

Арк.
ЧДТУ.21.20102.005.ПЗ 22
Змн. Арк . № докум. Підпис Дата
Для цих алгоритмів відрізнятися буде лише процедура генерування
ключів. Для ECDSA процедура генерування ключів наступна:
Для простоти будемо розглядати еліптичні криві над полем Fp, де Fp -
кінцеве просте поле. Причому, якщо необхідно, конструкцію можна легко
адаптувати для еліптичних кривих над іншим полем.
Припустимо, що E - еліптична крива, визначена над полем Fp, і P -
точка простого порядку q еліптичної кривої E(Fp). Крива E і точка P є
системними параметрами, а число p - просте. Кожен користувач, наприклад
Аліса - створює свою ключову пару за допомогою наступних дій:
1. Вибирає випадкове або псевдовипадкове ціле число х з
інтервалу [1,q-1].
2. Обчислює (кратний) параметр q=xP.
Відкритим ключем для користувача Аліси A є точка Q, а закритим
ключем - параметр x.
Замість використання E і P в якості глобальних системних параметрів,
можна фіксувати тільки поле Fp для всіх користувачів і дозволити кожному
користувачеві вибирати свою власну еліптичну криву E і точку PE(Fp). В
цьому випадку певне рівняння кривої E, координати точки P, а також
порядок q цієї точки P повинні бути включені у відкритий ключ користувача.
Якщо скінчене числове поле Fp є фіксованим, то апаратна і програмна
складові можуть бути побудовані так, щоб оптимізувати обчислення в
даному полі. Але, наразі, існує величезна кількість варіантів вибору
еліптичної кривої над полем Fp [21], що обумовлює вибір тільки окремих
варіантів рівнянь еліптичних кривих, зокрема, в апараті ЕЦП.

Арк.
ЧДТУ.21.20102.005.ПЗ 23
Змн. Арк. № докум. Підпис Дата

2.3 Протоколи для систем ЕЦП

Протокол, за допомогою якого отримувач повідомлення впевнюється в
автентичності відправника і цілісності повідомлення, називається перевіркою
достовірності (автентифікацією).
Існуючі на сьогодні протоколи в системах ЕЦП:
− OpenPGP
− OpenSSL/TLS
− Діффі-Хеллмана
− SSH
− S/MIME
Для прикладу аналізу зламу компонента ЕЦП можна розглянути
протокол Діффі — Хеллмана. Цей криптографічний протокол дозволяє двом і
більше сторонам, які беруть участь в роботі з ЕЦП та відкритим ключем,
отримати загальний секретний ключ, використовуючи незахищений від
прослуховування каналу зв’язку. Отриманий стороною ключ
використовується для шифрування подальшого обміну за допомогою
алгоритмів симетричного шифрування.
Схема відкритого розподілу ключів Діффі-Хеллманом, вирішує
основну проблему класичної криптографії – проблему розподілу ключів [22].
У чистому вигляді алгоритм Діффі-Хеллмана вразливий для
модифікації даних у каналі зв'язку, у тому числі для атаки "Man-in-the-middle
(людина посередині)", тому схеми з її використанням застосовують додаткові
методи односторонньої або двосторонньої автентифікації.
З огляду даного протоколу видно, що він є компонентом ЕЦП, а
вирішує задачу розподілу вже згенерованих ключів. Тому розглядати його

Арк.
ЧДТУ.21.20102.005.ПЗ 2 4
Змн. Арк . № докум. Підпис Дата
вразливості з метою оцінки зламу ЕЦП немає потреби. Це ж стосується і
інших протоколів підтримки ЕЦП.

2.4 Недоліки існуючих схем ЕЦП та їх виправлення

Фахівцями достатньо вивчені питання ненадійності практичних
реалізацій алгоритмів формування та перевірки ЕЦП.
Аналіз вразливостей існуючих схем ЕЦП дозволяє фахівцям
стверджувати, що «кількість вразливих точок електронного підпису, що
базується на шифруванні з відкритим ключем, настільки велика, що
доцільність використання такого методу викликає великі сумніви» [23].
Такі недоліки характерні в цілому для всіх асиметричних
криптоперетворень, зокрема:
− повільна робота алгоритмів формування і перевірки підпису;
− обмеження на довжину повідомлення, що підписується.
Одним із вирішень проблеми, пов'язаної з обмеженнями на довжину
повідомлення, є розбиття повідомлення на фрагменти та підпис кожного
фрагмента.
Однак таке рішення часто неприйнятне для використання на практиці,
оскільки результатом буде збільшення обсягу повідомлення та часу
виконання процедур створення та перевірки ЕЦП. Це до того, що часовий
показник роботи асиметричних набагато перевищує асиметричні.
Багато з недоліків існуючих схем ЕЦП можна виправити,
використовуючи хеш-функції, наприклад:

Арк.
ЧДТУ.21.20102.005.ПЗ
25
Змн. Арк. № докум. Підпис Дата

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

Арк.
ЧДТУ.21.20102.005.ПЗ 2 6
Змн. Арк. № докум. Підпис Дата

РОЗДІЛ 3

АНАЛІЗ ЙМОВІРНОСТІ ЗЛАМУ ХЕШ-ФУНКЦІЇ ЕЦП

3.1 Загальна теорія надійності та криптостійкості компонент ЕЦП

Основною причиною вразливості ЕЦП є вразливість алгоритму
шифрування з відкритим ключем, що лежить в основі технології
електронного підпису.
Друга причина – передача відкритого ключа в одному конверті з
електронним підписом (до структури ЕЦП, згідно з міжнародним стандартом
CCITT X.509, входить не тільки відкритий ключ відправника, але і
обов’язковий реквізит – його ім'я, серійний номер ЕЦП, назва та власна ЕЦП
уповноваженої організації, що видала дану ключову пару: секретний та
відкритий ключ).
На даний час реалізовані та опубліковані схеми механізмів зламу ЕЦП,
засновані на генерації нової пари (відкритий, секретний) ключів та
включення нового відкритого ключа в конверт ЕЦП.
Надійність системи ЕЦП складається з надійності окремих елементів,
до яких крім алгоритмів генерування та перевірки електронного підпису
належать механізм генерації та розподілу ключів та ряд інших необхідних
елементів. На надійність системи ЕЦП важливий вплив справляє розподіл
ключів між абонентами, що беруть участь в обміні електронними
повідомленнями.
Насправді такий розподіл може здійснюватися двома
розповсюдженими способами:

| Арк.
ЧДТУ.21.20102.005.ПЗ 27
Змн. Арк. № докум. Підпис Дата

− створенням центру генерації та розподілу ключів;
− прямим обміном ключами між абонентами.
У першому випадку компрометація центру призводить до
компрометації всієї інформації, що передається. У другому випадку
необхідно забезпечити справжність кожного абонента.
Помилки реалізації систем ЕЦП також суттєво впливають зниження
рівня надійності схем.
Розповсюдженими помилками є:
1) періодичне повторення тих самих значень, одержуваних
поширеними алгоритмами генерації випадкових або псевдовипадкових
чисел;
Слід зауважити, що насправді випадкові числа не повинні бути
передбачуваними. Генератори випадкових чисел видають псевдовипадкові
числа (при кожному виконанні алгоритму генерації випадкових чисел
отримаємо той самий список випадкових чисел).
Тому часто практично використовують спеціальну апаратуру для
генерації справжніх випадкових чисел (апаратні генератори випадкових
чисел).
Наприклад, ОС Unix (Linux) мають спеціальний код у складі драйверів
пристроїв нижнього рівня, який безперервно збирає випадкові сигнали
клавіатурних вводів та інших апаратних пристроїв та надає їх додаткам в
якості джерела випадкових чисел.
2) наявність колізій – можливість генерування однакових хеш
функцій для різних повідомлень (ідеальні хеш-функції існують тільки в
теорії, але рідко можуть бути реалізовані на практиці);
3) розробка власних алгоритмів, які мають властивості якісних
криптографічних алгоритмів.

Арк.
ЧДТУ.21.20102.005.ПЗ 2 8
Змн. Арк. № докум. Підпис Дата

4) Схеми формування ЕЦП, що базуються на шифруванні з
відкритим ключем, є принципово вразливими.
Взагалі, криптоаналіз хеш-функцій має за мету дослідити вразливості
хеша до різного виду атак. Основні з них такі:
- знаходження колізій — випадок, коли для двох різних вхідних
відкритих повідомлень відповідають абсолютно ідентичні значення хеш-
функцій.
- знаходження прообразу — вихідного повідомлення, яке
відбувається за його хешем.
Відомо, що при застосуванні методу перебору «грубої сили»:
- друга задача вимагає виконання 2160 операцій перебору.
- перша задача вимагає виконання в середньому 2160/2=280 операцій
(за умови використання атаки «Парадоксу Днів народження».
В сучасний схемах цифрового підпису від стійкості хеш-функції та її
схильності до знаходження колізій залежить безпека ЕЦП, що використовує
даний хеш-алгоритм. Від стійкості до знаходження прообразу залежить
безпека зберігання хешів паролів для автентифікації.

3.2 Математичний апарат для оцінки ймовірності зламу ЕЦП

Парадокс дня народження — це уявне парадоксальне твердження, що
ймовірність збігу днів (дат) принаймні двох членів групи з 23 і більше осіб
перевищує 0,5. Для 60 і більше осіб ймовірність такого збігу перевищує 0,99,
хоча ймовірність 1,0 вона теоретично досягає лише тоді, коли в групі буде не
менше 367 осіб. Це твердження може здатися неочевидним, оскільки
ймовірність збігу днів народження двох людей у будь-який день року (1/365
= 0,0027), помножена на кількість людей у групі з 23 осіб, дає лише 23/365 =
0,063. Таке міркування невірне, оскільки кількість можливих пар (253)
значно перевищує кількість людей у групі. У цьому немає жодної логічної
Арк.
ЧДТУ.21.20102.005.ПЗ 2 9
Змн. Арк . № докум. Підпис Дата
суперечності, а парадокс — лише відмінності між інтуїтивним сприйняттям і
математичним розрахунком. Однак, за умов використання цього парадоксу в
криптоаналізі, а особливо якщо атака здійснюється на набір відомих
відкритих повідомлень. Це дозволяє з досить високою точністю оцінити
ймовірність порушення хеш-функції [24,25]. Це дозволить здійснити «атаку
днів народження», під час якої випробовуються випадкові значення, поки не
буде знайдено два таких, які спрацюють.
«Атака дня народження» використовується в криптоаналізі в якості
методів зламу шифрів або знаходження колізій хеш-функцій. Суть методу
полягає в тому, щоб значно зменшити кількість переданих хеш-функції
аргументів, необхідних для виявлення колізії, тому що, якщо хеш-функція
генерує �� – бітове значення, кількість випадкових аргументів хеш-функції,
яка, ймовірно, виявить принаймні одне зіткнення хеш-функції, не складає
точно 2��, але знаходиться в районі 2��/2 [26,27].
Слід зазначити, що ці умови «парадоксів дня народження» не
обов’язково мають місце в реальному світі. Зокрема, в реальному світі люди
не народжуються з однорідною випадковістю. Може бути точна статистика
за днями народження людей. Але ця модель не є точним відображенням
реального світу, її простота значно полегшує аналіз проблеми. Зокрема, в
криптоаналізі ця модель має задовільну точність. Так, наприклад, цей
парадокс можна застосувати для оцінки криптографічної міцності різних
елементів технології блокчейн через те, що вона також використовує хеш-
функції, подібні до розглянутих.

Арк.
ЧДТУ.21.20102.005.ПЗ 3 0
Змн. Арк . № докум. Підпис Дата
3.3 Існуючі методи та алгоритми атак на хеш-функції

Ви можете розглянути всі можливі основні хеш-атаки, пов’язані з
колізією генерації значень:
1) Лобовий напад. Наявність згортки типу ��(��1) повідомлення ��1,
криптоаналітик повинен використовувати метод пошуку, щоб знайти
повідомлення ��2 (��2 ≠ ��1), для кожного ��(��1) = ��(��2). Якщо ця умова
виконується, криптоаналітик може оголосити, що отримана згортка
відповідає повідомленню ��2, але не до повідомлення ��1. Якщо хеш-функція
виводить n-бітовий рядок, то складність цього методу криптоаналізу
оцінюється як ��(2��).
2) Атака на основі «парадоксів дня народження». Цей парадокс
використовується для багатьох прикладних задач (включаючи проблеми
криптоаналізу). В його основі лежить відома статистична проблема –
«парадокс дня народження».
Тому загальне завдання криптоаналізу можна звести до завдання
пошуку колізій, а саме - скільки відкритих повідомлень потрібно переглянути
криптоаналітику, щоб знайти повідомлення з однаковими хешами [17].
Ймовірність зустріти однакові хеші для повідомлень із двох різних
наборів, що містять відповідно ��1 і ��2 відкритих тексти визначається згідно
виразу:

��1��2
�� ≈ 1 − �� �� (3.1)

Якщо у виразі (3.1) �� = �� = 2��/2
1 2 , тоді ймовірність успіху такої атаки
��
буде: �� ≈ 1 − ��−1 ≈ 0.63 +1
, і складність атаки можна оцінити як 22 . Щоб
визначити колізію, необхідно сформувати два псевдовипадкових набори
повідомлень, щоб було 2��/2 повідомлення в кожному наборі, а потім

Арк.
ЧДТУ.21.20102.005.ПЗ 31
Змн. Арк. № докум. Підпис Дата

необхідно знайти відповідні хеш-значення Тоді, згідно з «парадоксом дня
народження», ймовірність того, що серед них буде пара повідомлень з
однаковими хеш-значеннями, буде більше 0,5. Така атака вимагає великого
обсягу пам’яті для зберігання наборів відкритого тексту та застосування
ефективних методів їх сортування [28].
Сценарій атаки на хеш-функцію, заснований на «парадоксі дня
народження», коли зловмисник А хоче атакувати сторону B і підписати
договір, невигідний стороні B, виглядає так:
1) Зловмисник А готує два варіанти контракту – «хороший» варіант ��1
і "поганий" варіант ��2. Потім він вносить незначні зміни до кожного
документа, маніпулюючи крапками, комами та іншими розділовими знаками,
пробілами.
2) Зловмисник А обчислює значення хеш-функцій для всіх створених
ним версій контракту, порівнює набори хешів, шукає однакові пари. Якщо
довжина хеша 64 біти, то для цієї мети достатньо 232 пар. Зловмисник А
вибирає пару повідомлень, для яких значення хеш-функції подібне.
3) Зловмисник A вибирає обрану пару з подібними хешами і передає
«погану» версію контракту M_2 на підпис стороні B. У цьому випадку
зловмисник A може довести в суді, що сторона B свідомо підписала
невигідний договір.
Таким чином, для заданої хеш-функції H(m) метою атаки є пошук
зіткнення другого роду.
Надійність ЕЦП визначається стійкістю до криптологічних атак її
компонентів, таких як: 1) хеш-функції, 2) алгоритми ЕЦП.
Основним завданням криптоаналізу EDS є оцінка ймовірності
порушення хеш-функції при наступних атаках: а) груба сила (грубий відбір);
б) вибір хеш-значення. згруповані за приналежністю.

Арк.
ЧДТУ.21.20102.005.ПЗ 32
Змн. Арк . № докум. Підпис Дата
3.4 Методи та алгоритми атак на хеш-функції

На основі сформульованого вище апарату криптоаналізу оцінимо
ймовірність порушення хеш-функції. Для атаки за допомогою цього методу
(грубої сили) розглядалося два способи:
1) Метод стійкості до зіткнень. За відомим значенням хеш-функції
��(��), атакуючий створює інший документ ��`, який позначимо, як ��(��`) =
��(��). Зловмисник намагається знайти два випадкових повідомлення �� і ��`
такі, що ��(��`) = ��(��).
Припустимо, що хеш-функція є абсолютно надійною і
односпрямованою, і немає іншого способу її зламати, крім повного пошуку її
значень. На виході цієї функції отримуємо число, розрядність якого дорівнює
��. Таким чином, кількість вихідних значень функцій �� = 2��. Позначимо
��(��, ��) ймовірність того, що для конкретного значення �� існує принаймні
одне значення ���� в діапазоні від ��1 … ���� дорівнює і задовільняє умові ��(��) =
��(��). Для одного значення �� ймовірність того, що ��(��) = ��(��) буде
складати 1/��. Звідси легко знайти, що ймовірність тотожності виразу ��(��) ≠
��(��) складатиме (1 − (1/��)). Якщо згенерувати ��-кількість таких значень,
тоді ймовірність того, що жодне з них не повториться визначається як
добуток ймовірностей, та обчислюється як (1 − (1/��)��). Отже, ймовірність
хоча б одного збігу буде рівною ��(��, ��) = 1 − (1 − (1/��)). Для випадку
абсолютного зламу ймовірність такого випадку дорівню ��(��, ��) = 1.
Використовуючи «парадокс дня народження», розглянутий вище, для
оцінки ймовірності зіткнення в хеш-функції, ми можемо оцінити ймовірність
такого випадку, як ��(��, ��) = 0.5, звідки значення параметра �� = ��/2 =
2(��−1). Таким чином, можна стверджувати, що відносна ймовірність
успішної атаки методом злому «стійкості до зіткнень» (знаходження такого

Арк.
ЧДТУ.21.20102.005.ПЗ 3 3
Змн. Арк. № докум. Підпис Дата

хешу, що генерується для заданого значення відкритого повідомлення)
досягається для кількості випадкових повідомлень, яка складає 2(��−1). Тоді
ймовірність порушення хеш-функції дорівнює 1/2(��−1) [14-16]. Отримані
значення ймовірностей зламу хеш-функції для різних n-бітових довжин
повідомлення (Таблиця 1).

Арк.
ЧДТУ.21.20102.005.ПЗ 3 4
Змн. Арк. № докум. Підпис Дата

Таблиця 3.1.
Оцінка ймовірності порушення хеш-функції методом взламостійкості до
зіткнень
Довжина хешу, біт Ймовірність зламу хеш-функції
64 1,0842021724855044340074528008699e-19
128 5,8774717541114375398436826861112e-39
192 3,1861838222649045540577607955354e-58
256 1,7272337110188889250772703725601e-77
384 5,0758836746312984465480491116611e-116
512 1,4916681462400413486581930630926e-154
1024 1,112536929253600691545116358662е-308
2048 6,1886920947651565509603667399424e-617

Графік функцій, що показує значення оцінки ймовірності зламу хеш-
функції методом «стійкості до зіткнень», показано на рис.1.

Рис 3.1. Оцінка ймовірності зламу хеш-функції методом «стійкості до зіткнень»
Арк.
ЧДТУ.21.20102.005.ПЗ 35
Змн. Арк. № докум. Підпис Дата

2) Метод зламу «суворої стійкості до зіткнень». Нехай ��(��, ��) – це
ймовірність того, що в наборі з �� елементів, кожен з яких може приймати
значення ��, є принаймні два елементи, значення яких ідентичні. Тоді
значення, яке має набути g, щоб умова була виконана можна описати
виразом:

��(��, ��) > 0.5 (3.2)

У виразі (3.2) сформульована умова оцінки ймовірності зустрічі
однакових значень хеш-функції. З виразу (3.2) можна зрозуміти, що кількість
способів виділення елементів, що не повторюються складає: ��! (�� − ��)!
Загальна кількість способів виділення таких елементів дорівнює ����.
Ймовірність того, що елементи не повторюються можна визначити, як:
��!/[(�� − ��)! ����]. Вираз (3.2) можна переписати для випадків визначення
ймовірності повторення таким чином:

��(��, ��) = 1 − [��!/((�� − ��)!)����] (3.3)

У виразі (3.3) формулюється загальна оцінка ймовірності для випадків
повторення кількох елементів. Якщо ймовірність ��(��, ��) = 0.5, тоді �� =
√������2 = ����2√�� ≈ ��1/2. Припустимо, що довжина хеша дорівнює m – біт, тоді
кількість значень, які набуває даний хеш, дорівнює 2��, отже �� = √2�� =
2��/2. Тому для визначення двох повідомлень з однаковим змістом
(отримання класичної колізії при генеруванні хеш-функцій) необхідно
обчислити хеш від 2��/2 випадкових відкритих повідомлень. Ймовірність
зламу хеш-функції оцінюється, як (1/2)��/2 [24-26]. Використовуючи вираз
(3), можна отримати значення ймовірності зламу хеш-функції при різних
значеннях розрядності отриманого хеша (таблиця 2).

Арк.
ЧДТУ.21.20102.005.ПЗ 3 6
Змн. Арк. № докум. Підпис Дата

Таблиця 3.2.
Оцінка ймовірності зламу хеш-функції для атаки «методом суворої
стійкості» до зіткнень
Довжина хешу, біт Ймовірність зламу хеш-функції
64 0,00000000023283064365386962890625
128 5,4210108624275221700372640043497e-20
192 1,2621774483536188886587657044525e-29
256 2,9387358770557187699218413430556e-39
384 1,5930919111324522770288803977677e-58
512 8,6361685550944446253863518628004e-78
1024 7,4583407312002067432909653154629e-155
2048 5,562684646268003457725581793331e-309

З отриманих результатів порівняння ймовірностей зламу хеш-функції
видно, що при одній і тій самій довжині хеш-значення злам хеш-значення за
«методом стійкості до зіткнень» значно нижчий, ніж при застосуванні
«строгого методу стійкості» до зіткнень (колізій).
На першому (рис. 1) і другому (2) графіках можна побачити серйозні
відмінності в ймовірності зламу хешів при використанні першого і другого
методів.
Арк.
ЧДТУ.21.20102.005.ПЗ 3 7
Змн. Арк. № докум. Підпис Дата

Рис 3.2. Оцінка ймовірності зламу хеш-функції для атаки «методом суворої
стійкості до зіткнень»

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

Арк.
ЧДТУ.21.20102.005.ПЗ 3 8
Змн. Арк. № докум. Підпис Дата

Таким чином, не формуючи вибірки даних для даної криптографічної
хеш-функції f, можна легко визначити ймовірність колізії другого роду. Для
цього достатньо використовувати лише вираз (3.3).
Небезпечність додавання ключа на початку або в кінці повідомлення
можна пояснити наступним чином:
- нехай на початку повідомлення буде додано ключ k, а функція
згортки буде побудована за схемою Меркла-Дамгора. Таким чином, згідно з
повідомленням М, відомому криптоаналітику, маючи функцію �� = ��(��‖��),
можна визначити значення згортки для всіх повідомлень цього типу ��‖��`,
де після повідомлення �� додається будь-яке повідомлення ��`. Справді, через
ітераційний характер хеш-функції немає необхідності знати ключ для
визначення ��` = ��(��‖��‖��`). Досить лише використати проміжне значення
обчислене значення згортки ��;
- нехай ключ k додається в кінці повідомлення �� = ��(��‖��).
Значення колізії для хеш-функції (пара ��1, ��2) за умови, що ��1 ≠ ��2, але
��(��1) = ��(��2) можна обчислити за допомогою хешів ��(��1, ��) = ��(��2, ��)
для будь-якого значення k. З цього можна зробити висновок, що складність
зміни повідомлення ��1 більше не оцінюється значенням ��(2��). Завдяки
використанню парадоксу днів народження складність значно зменшиться і
складе Для того, щоб зменшити ймовірність успішного криптоаналізу,
рекомендується переписати ключ при обчисленні згортки в хеш-функції
кілька разів. Наприклад, виразі �� = (��‖��‖��‖��) можна переписати як �� =
��(��‖��1‖��(��‖��2‖��)), де ��, ��1, ��2 є доповненням ключа до розміру, кратного
довжині блоку хешування.
За цим принципом побудовані функції без ключа. Вони надзвичайно
надійні для атак зіткнень першого і другого роду, але їх недоліком є велика
довжина отриманої згортки, що значно ускладнює їх використання.

Арк.
ЧДТУ.21.20102.005.ПЗ 3 9
Змн. Арк. № докум. Підпис Дата

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

Арк.
ЧДТУ.21.20102.005.ПЗ 4 0
Змн. Арк. № докум. Підпис Дата

ЗАГАЛЬНІ ВИСНОВКИ

В результаті виконання дослідження було:
1) проаналізовано стандарти, алгоритми та хеш-функції, які
використовуються в електронному цифровому підписі (ЕЦП).
2) виділено в результаті розгляду та аналізу основних компонент
електронного підпису вразливу компоненту декількох існуючих схем ЕЦП -
хеш-функцію. Для хеш-функцій проаналізовано причини колізій, методи,
алгоритми хеш-атак.
Можна зробити висновок, що для підвищення криптографічної
стійкості хеш-функції в схемі ЕЦП до зламу хоча б до рівня 10-25 слід
використовувати хеш довжиною не менше 192 біт.
3) Сформований математичний апарат для оцінки ймовірності
порушення хеш-функцій на основі різних статистичних та ймовірнісних
методів, а саме - моделі ймовірнісної оцінки. Використаний підхід дає
можливість оцінити залежність вхідних і вихідних даних під час
шифрування, а також виділити «погані» ключів, які на практиці можуть бути
ненадійними.
4) Отримано результати ймовірності зламу для хеш-функцій, що
використовуються в ЕЦП для 128-бітової хеш-функції ймовірність зламу для
обох розглянутих методів відрізняється в 9223372036854775808 разів. Також
можна оцінити час роботи машини, необхідний для зламу хеш-функції за
першим і другим методами. Наприклад, ймовірний час знаходження колізії
першим методом, за умови, що хеш має розмірність m = 128, необхідно
обчислити 2128 = 3,4 ⋅ 1038 варіантів. Тоді, використовуючи «парадокс днів
народження», кількість цих варіантів можна визначити, як 2��/2 =
1,8446744073709551616 ⋅ 1019 за другим методом та 2��−1 = 1,7 ⋅ 1038 за
першим методом оцінки.
Арк.
ЧДТУ.21.20102.005.ПЗ 41
Змн. Арк. № докум. Підпис Дата

Підтверджується, що при однаковій довжині хеша ймовірність зламати
хеш методом “стійкості до зіткнень» значно нижча, ніж при « суворої
стійкості до зіткнень».
Під час роботи з функціями хешування ключів небезпечно додавати
ключ на початку або в кінці повідомлення.
Отримані в цій роботі результати можуть знайти практичне
застосування при вирішенні низки завдань сучасної криптографії, наприклад,
при оцінці ефективності паралельної реалізації методів визначення
множинних колізій хеш-функцій, а також пошуку дискретного логарифму,
подібних до ρ-методу Полларда [29].

Арк.
ЧДТУ.21.20102.005.ПЗ 42
Змн. Арк. № докум. Підпис Дата

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ
1. Miller, V. Use of elliptic curves in cryptography. CRYPTO. Lecture
Notes in Computer Science. 85. pp. 417–426, 1985, doi:10.1007/3-540-39799-
X_31.
2. Christof Paar, Jan Pelzl, Bart Preneel. Understanding Cryptography: A
Textbook for Students and Practitioners 1st ed. 2010 Edition, 390 pp.
3. Schneier, Bruce. Applied Cryptography, Second Edition, John Wiley
& Sons, 1996, available at: https://mrajacse.files.wordpress.com/2012/01/applied-
cryptography-2nd-ed-b-schneier.pdf.
4. An Introduction to Bitcoin, Elliptic Curves and the Mathematics of
ECDSA, N.Minstry, B121555, Supervisor Dr. B.Winn, Module Code: Mac200,
21.04.2015, available at:
https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff
03859/ecdsa_bitcoin.pdf
5. Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman. An Introduction to
Mathematical Cryptography. — Springer Science+Business Media New York 2014.
— p. 53, available at https://doi.org/10.1007/978-1-4939-1711-2.
6. Johnson, D., Menezes, A. & Vanstone, S. The Elliptic Curve Digital
Signature Algorithm (ECDSA). IJIS 1, 36–63 (2001), available at
https://doi.org/10.1007/s102070100002.
7. Benger, Naomi; van de Pol, Joop; Smart, Nigel P.; Yarom, Yuval
(2014). Batina, Lejla; Robshaw, Matthew (eds.). "Ooh Aah... Just a Little Bit" : A
Small Amount of Side Channel Can Go a Long Way (PDF). Cryptographic
Hardware and Embedded Systems – CHES 2014. Lecture Notes in Computer
Science. 8731. Springer. pp. 72–95. doi:10.1007/978-3-662-44709-3_5.
8. Nigel P. Smart. Cryptography Made Simple. Springer International
Publishing, 1st Ed: XII, 481 p, 2015, doi:10.1007/978-3-319-21936-3.
9. Arpita Patra & Nigel P. Smart. Progress in Cryptology –
INDOCRYPT, 2017. Springer-Verlag. ISBN 978-3-319-71667-1.
Арк.
ЧДТУ.21.20102.005.ПЗ 43
Змн. Арк . № докум. Підпис Дата
10. Rory Hector, Ramachandran Vaidyanathan, Gokarna Sharma and
Jerry L. Trahan, Optimal Convex Hull Formation on a Grid by Asynchronous
Robots with Lights. Conference: 2020 IEEE International Parallel and Distributed
Processing Symposium (IPDPS), Year: 2020, Page 1051.
DOI: 10.1109/IPDPS47924.2020.00111.
11. Эллиптическая криптография [Електронний ресурс] // TECH-
GEEK.RU. – 2021. – Режим доступу до ресурсу: https://tech-geek.ru/elliptic-
cryptography/.
12. Збірник наукових праць за матеріалами ІV Всеукраїнської
науково-практичної інтернет конференції студентів і аспірантів «Теороетичні
та прикладні аспекти розробки компютерних систем‘2021», 29 квітня 2021
року, НУБіП України, Київ. – 209 с. (електронне видання)
13. [10 Mandal, A. K., Parakash, C. and Tiwari, A. (2012). Performance
evaluation of cryptographic algorithms: DES and AES. Electrical, Electronics and
Computer Science (SCEECS), 2012 IEEE Students’ Conference on. IEEE, 2012]
14. [Hercigonja Z. Comparative Analysis of Cryptographic Algorithms /
Zoran Hercigonja. – 2016].
15. Difference between RSA algorithm and DSA. [Електронний ресурс]
// @geeksforgeeks – Режим доступу до ресурсу:
https://www.geeksforgeeks.org/difference-between-rsa-algorithm-and-dsa/.
Retrieved 2020-05-22.
16. DigiCert World's. Largest High-Assurance Certificate Authority
[Електронний ресурс] // Netcraft Ltd. – 2021. – Режим доступу до ресурсу:
https://trends.netcraft.com/www.digicert.com#extended-validation.
17. Apache HTTP Server [Електронний ресурс] // wikipedia. – 2021. –
Режим доступу до ресурсу: https://uk.wikipedia.org/wiki/Apache_HTTP_Server.
18. Web Server Survey [Електронний ресурс] // Netcraft Ltd. –
Retrieved 26, July 2021. – Режим доступу до ресурсу:
https://news.netcraft.com/archives/2021/07/26/july-2021-web-server-survey.html.
Арк.
ЧДТУ.21.20102.005.ПЗ 44
Змн. Арк. № докум. Підпис Дата

19. Lawrence C. Washington. Elliptic Curves: Number Theory and
Cryptography, Second Edition (Discrete Mathematics and Its
Applications). Chapman and Hall/CRC; 2 edition, April 3, 2008, 536 p.
20. Hans Knutson. What is the math behind elliptic curve cryptography?
April 6th 2018, available at: https://hackernoon.com/what-is-the-math-behind-
elliptic-curve-cryptography-f61b25253da3.
21. Koblitz, Neal. A Course in Number Theory and Cryptography
(Graduate Texts in Mathematics), Springer; 2nd edition, September 2, 1994, 235 p.
22. Lay, G., Zimmer, H. Constructing elliptic curves with given group
order over large finite fields. Algorithmic Number Theory Symposium. Lecture
Notes in Computer Science. 877. pp. 250–263, 1994, doi:10.1007/3-540-58691-
1_64.
23. Alain J. Brizard, Notes on the Weierstrass Elliptic Function,
Department of Physics, Saint Michael’s College, Colchester, VT 05439, USA.
October 13 2015, available at
https://www.researchgate.net/publication/283335205_Notes_on_the_Weierstrass_
Elliptic_Function.
24. Доступно о криптографии на эллиптических кривых
[Електронний ресурс] // company.habr.com. – Retrieved 28 Aug 2017. – Режим
доступу до ресурсу: https://habr.com/ru/post/335906/.
25. R. Schoof. Elliptic Curves over Finite Fields and the Computation of
Square Roots mod p. Math. Comp. T. 44, No. 170, pp. 483–494, 1985.
26. R. Schoof. Counting Points on Elliptic Curves over Finite Fields, J.
Theor. Nombres Bordeaux. No. 7. — pp. 219–254, 1995.
27. Elliptic Curve point addition // cdn.rawgit.com, available at:
https://cdn.rawgit.com/andreacorbellini/ecc/920b29a/interactive/reals-add.html.
28. S., Dummit, David. Abstract algebra. Foote, Richard M., 1950- (3.
ed.). Hoboken, NJ: WileyOCLC 248917264, 2004.

Арк.
ЧДТУ.21.20102.005.ПЗ 45
Змн. Арк. № докум. Підпис Дата

29. Raval S. Decentralized Applications. Harnessing Bitcoin's Blockchain
Technology, O'Reilly Media; 1st edition, 118 p., (August 16, 2016).
30. Kefa Rabah. Review of Methods for Integer Factorization Applied to
Cryptography. Journal of Applied Sciences, 6: 458–481 2006,
DOI: 10.3923/jas.2006.458.481m, available at
https://scialert.net/abstract/?doi=jas.2006.458.481.
31. Standarts for Efficient Cryptography. SEC 2. Recommended Curve
Domain Parametres. Certicom Research. January 27, 2010, Version 2.0, available
at http://www.secg.org/sec2-v2.pdf.
32. Коржев В. Цифровая подпись. Эллиптические кривые.
«Открытые системы» (8 августа 2002). Дата обращения: 16 ноября 2008.
33. ANSI X9.62 Public Key Cryptography for the Financial Services
Industry: the Elliptic Curve Digital Signature Algorithm (ECDSA). ANSI. 16
November 2005. 163 p.
34. RFC 3174. US Secure Hash Algorithm 1 (SHA1). Network Working
Group. Cisco Systems. September 2001, available at
https://tools.ietf.org/html/rfc3174
35. Sahun, A.V., Lakhno, V.A., Kravchuk, P.Y., Kosenko, S.S., Kisiliuk,
E.M. Elliptic curves in modern cryptographic systems (2020) International Journal
of Advanced Trends in Computer Science and Engineering, 9 (4), статья № 259,
pp. 5949- 5955.
36. R. Barnes; M. Thomson; A. Pironti; A. Langley (June 2015).
"Deprecating Secure Sockets Layer Version 3.0", available at:
https://tools.ietf.org/html/rfc7568.
37. https://cryptography.fandom.com/wiki/Nothing_up_my_sleeve_numb
er
38. Fildes J. iPhone hacker publishes secret Sony PlayStation 3 key / BBC
News. – 2011, available at https://www.bbc.com/news/technology-12116051.

Арк.
ЧДТУ.21.20102.005.ПЗ
46
Змн. Арк. № докум. Підпис Дата

ДОДАТОК А
ПРЕЗЕНТАЦІЯ ДО КВАЛІФІКАЦІЙНОЇ РОБОТИ

47

48

49

50

51

52

53

Репозиторій ЧДТУ