Криптоаналiз RSA методом квадратичного решета. Приклади розв’язку задач та задачі для самостійного розв’язання

1.14.1 Приклади розв'язку задач

Задача 1.

Факторизувати модуль N, використовуючи метод квадратичного решета, якщо N = 377.

Розв’язок задачі:

Знаходимо :

Таблиця 1.11 – Розрахунки

x	Z = x+	Z²mod N	2	3	5	7	Залишок
1	20	23	-	-	-	-	23
2	21	64	6	-	-	-	+
3	22	107	-	-	-	-	107
4	23	152	3	-	-	-	19
5	24	199	-	-	-	-	199
6	25	248	3	-	-	-	31
7	26	299	-	-	-	-	299
8	27	352	5	-	-	-	11
9	28	30	1	1	1	-	+
10	29	87	-	1	-	-	29
11	30	146	1	-	-	-	73
12	31	207	-	2	-	-	23
13	32	270	1	3	1	-	+
14	33	335	-	-	1	-	67
15	34	25	-	-	2	-	+

У першому стовпчику задаємо значення x, у другому Z = х+19, у третьому - Z² mod N. Далі значення Z² mod N розкладається на співмножники бази Р¢, точніше робиться спроба, - це числа 2, 3, 5, 7, добуток цих чисел р¢ = 210. Із таблиці бачимо, що число 23 не розкладається на співмножники бази. Число 64 розкладається на співмножники – 2 (2⁶ = 64).

Якщо Z² mod N повністю розкладається на співмножник або співмножники р¢, то таку спробу вважаємо позитивною та позначаємо рядок знаком “+”. Для успішної факторизації необхідно не менше k, де k – число співмножників бази розкладу, позитивних експериментів. Потім, перемножуючи значення
стовпців Z² mod N та результати розкладу за базою, необхідно скласти рівняння вигляду

Наприклад, другий рядок (тільки одна) дає такий результат

або

Тоді x = 21, y = 8; x - y = 21-8 = 13.

Далі НCД (x - y, N) = НCД (13, 377) = 29.

Тому, наприклад, P = 13, Q = 29 і N = 13*29 = 377.

Аналогічно можна взяти 15 рядок. Тоді маємо

Задача 2.

Нехай відомо, що в RSA cистемі використовується відкритий ключ
D_k = 107, а модуль перетворення N = 209. Необхідно знайти особистий (секретний) ключ E_k та оцінити складність криптоаналізу.

Розв’язок задач здійснимо в декілька етапів. На першому факторизуємо модуль N, використовуючи метод квадратичного решета. Потім, розв’язавши ключове порівняння, знайдемо особистий ключ D_k. На завершення оцінимо складність криптоаналізу, основний етап якого складає факторизація.

Розрахунки зведемо в таблицю 1.12, при цьому знаходитимемо НСД, використовуючи алгоритм Евкліда. Сутність алгоритму Евкліда:

Нехай

a₁ = x-y; a₂ = N.

1) if a₁ =a₂ then НСД:= a₂;

2) a₁ := max(a₁, a₂),

a₂ := min(a₁, a₂).

3) a₁/a₂ ®a₃ =r;

4) if a₃ = 0 then НСД :=a₂, END;

5) a₁:= a₂; a₁:= a₃; goto 3).

Аналогічно, як і в задачі 1, для факторизації використовується квадратичне решето.

При цьому

p = 2*3*5*7* = 210.

Значить N»P.

Таблиця 1.12 – Розрахунки

N/n	x	Z =ë x+ û	Z²mod N	2	3	5	7	Залишок
1	1	15	16	4	-	-	-	+
2	2	16	47	-	-	-	-	-47
3	3	17	80	4		1	-	+
4	4	18	115	-	-	1	-	-23
5	5	19	152	3	-	-	-	-19
6	6	20	191	-	-	-	-	-
7	7	21	23	-	-	-	-	-
8	8	22	66	1	1	-	-	-11
9	9	23	111	-	1	-	-	-37
10	10	24	158	1	-	-	-	-79
11	11	25	207	-	2	-	-	23-
12	12	26	47	-	-		2	+
13	13	27	102	1	1	-	-	17-
14	14	28	157	-	-	-	-	-
15	15	29	5	-	-	1	-	+
16	16	30	64	6	-	-	-	+
17	17	31	125	-	-	3	-	+
18	18	32	188	2	-	-	-	47

У таблиці 1.13 наведені позитивні рядки

Таблиця 1.13 – Позитивні рядки

x	Z =ë x+ û	Z²mod N	2	3	5	7	Залишок
1	15	16	4	-	-	-	+
3	17	80	4		1	-	+
12	26	47	-	-		2	+
15	29	5	-	-	1	-	+
16	30	64	6	-	-	-	+
17	31	125	-	-	3	-	+

Замінимо в таблиці всі парні числа 0, а непарні 1. У матриці розміром n x(n+1) із нулів та одиниць завжди можна обрати множину рядків, таку, що у всіх стовпцях буде парне число одиниць, а отже є сукупність рядків у яких

Наприклад, розв’язок дають рядки {3,15}, {3, 17}, {15, 17}, {1}, {12}, {16}.

1. 15² º 2⁴(mod 209); 15² º 4²(mod 209)

x=15, y=4.

НСД(15-4, 209) = 11,

P=11; Q=N:P=209:11=19.

2. {3,15}

17² 29² º 5²4²(mod 209); (17*29)² º (20)²(mod 209).

x=75, y=20.

НСД(75-20, 209).

3. {15, 17}

29² º 5¹(mod 209)

31² º 5³(mod 209)

(3129)² º 5⁴(mod 209); (2931)² º 25²(mod 209);

x=63; y=25; (x-y, 209) НСД=(38, 209)=(219, 209) = 19

Використовуючи алгоритм Евкліда маємо:

a₁ = 209; a₂ = 38

P=209:19=11;Q=19

209:38=5; r=19

a₁ = 38; a₂ = 19

39:19=2; r=0;

НСД (a₁, a₂)=a₂ = 19

Тепер розв’яжемо ключове порівняння

D_k = 103; N=209; j(N)= 10*18 = 180

j(N) (-k)+D_kE_k = 1; 180(-k)+103E_k = 1

180x+103y = 1 x=(-1)^m⁺¹b_m_-1; y = (-1)^ma_m_-1;

r₀ = 1;

r₁ = 1;

r₂ = 2;

r₃ = 1;

r₄ = 25;

m = 4;

a_m_-1 = r_m_-1a_m_-2+a_m_-3; b_m_-1 = r_m_-1b_m_-2+b_m_-3;

a₃ = r₃a₂ + a₁; b₃ = r₃b₂ + b₁;

;

a₂ = 1(1*2+1)+2 = 5; b₂ = 3;

a₃ = 7;

y = (-1)⁴7 = 7.

Таким чином E_k = 7.

В таблиці 1.14 наведені значення складності криптоаналізу, I₁ – методом Ленстри, І₂ – з використанням квадратичного решета.

Таблиця 1.14 – Значення складності криптоаналізу

N	lnN	lnlnN	(lnN)^1/3	(lnlnN)^2/3	I₁	I₂
256	179,2	5,29	5,64	2,99	1,7×10¹³	8,2×10¹³
512	358,4	5,98	7,10	3,25	8,5×10¹⁹	1,2×10¹⁹
768	537,6	6,29	8,13	3,41	1,7×10²⁴	7,4×10²²
1024	716,8	6,57	8,94	3,51	6,3×10²⁹	7,8×10²⁵
2048	1433,6	7,26	11,27	3,74	2,4×10⁴⁴	6×10³⁴
4096	2867,2	7,96	14,20	3,99	4,1×10⁶⁵	5,6×10⁴⁶
8192	5734,4	8,65	17,89	4,21	5,3×10⁹⁶	1,4×10⁶²

Перевірка E_k*D_k = 103*7 = 721(mod 180)º1 (mod 180). Тоді розв’язок зроблено правильно.

2.7 Аналіз методiв перетворень в перспективних симетричних
криптографічних системах . Приклади розв’язку задач та задачі для
самостійного розв’язання

2.7.1 П риклади розв’язку задач

Задача 1.

Знайти афінне перетворення виду , де С та - константи, що мають вигляд:

, .

При цьому , якщо =71. Знайти відстань Хемінга між вхідними та вихідними елементами.

Розв’язок.

1. Знайдемо . Для цього зведемо розв’язок порівняння

(2.57)

до розв’язку порівняння виду , яке в свою чергу можна звести до розв’язку Діафантового рівняння виду ax+by=1, тобто виділити

, (2.58)

де , . Треба знайти
та х = (-к).

Діафантове рівняння матиме розв’язок, якщо та . Подамо цей розв’язок у вигляді ланцюгового дробу. Для цього запишемо
=71 у вигляді поліному: = 01000111= . Тоді наш ланцюговий дріб матиме вигляд:

* Використані тут константи С та С₁ відрізняються від істинних, що наведені в п. 2.1

Тоді, якщо - порядок ланцюгового дробу, а - його параметри, то

Отже, .

Перевірку правильності розв’язку рівняння (2.58) виконуємо, підставивши значення та в (2.57). Маємо

Дійсно

= .

Знайдемо лишок:

Таким чином, лишок = 1. Елементи та є зворотними.

2. Знайдемо афінне перетворення . Для цього запишемо = 01101001 у вигляді матриці-стовпця:

Позначимо :

Тепер знайдемо :

Отже, =11111010₂=250₁₀.

3. Знайдемо відстань Хемінга між вхідним та вихідним елементами:

2.8.1 Приклади розв’язку задач

Задача 1.

Визначте допустимі параметри окремих рядків заміни (2.31) для ГОСТ 28147-89.

Розв'язок задачі.

В ГОСТ 28147-89 використовуються підстановки чотири біта в чотири біта, тобто здійснюється підстановка шістнадцяткових символів, тому n=2⁴=16.

Вибравши параметр а=1 із співвідношень (2.32) – (2.34), маємо:

(2.59)

Таким чином рядок кожної із таблиць заміни має відповідати таким умовам:

- число інверсій має змінюватися на відрізку від 50 до 70;

- число циклів – від 1 до 5;

- число зростань – від 7 до 9.

Задача 2.

Визначте параметри ключів підстановки (окремих рядків), що наведені в таблиці 2.12.

Таблиця 2.12 – Ключі підстановки

Розв’язок задачі.

Розглянемо перший рядок. Під інверсією розуміється загальне число символів в рядку, які менше символу, що розглядається. Далі знаходиться сума цих величин для кожного із символів рядка. Для першого символу – 14 визначаємо, що меншими від нього є числа 3, 7, 10, 1,0, 11, 12, 8, 4, 6, 9, 5, 13, 2 - всього 14 символів; для символу 3 є числа 1, 0, 2 - всього три числа. Далі для 7 - 6, 0 – 8, 1 - 1, 0 – 0, 11 - 6, 12 - 6, 15 - 7, 8 – 6, 4-1,6- 2, 9 – 2, 5 - 1,13- 1. Всього інверсій 14+3+6+8+1+0+6+6+7+6+1+2+2+1+1=62. Під циклом розуміється кількість переходів між нульовим рядком та відповідним рядком підстановки. Пояснимо на прикладі. Нехай є перестановка, що наведена у таблиці 2.13.

Таблиця 2.13 – Перестановка

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
14	3	7	10	1	0	11	12	15	8	4	6	9	5	13	2

Здійснюємо за таблицею 2.13 переходи:

0-14®13®5-0 – це перший цикл, ми розпочали з 0 і прийшли знову в 0 – цикл замкнувся. Пояснимо цикл: нуль першого рядка замінюється на 14 рядка підстановки (другого рядка), далі 14 першого рядка на 13 другого рядка, 13 першого рядка на 5 другого рядка i 5 першого рядка на 0 другого.

Другий цикл будуємо аналогічно:

1 - 3 → 10 → 4 -1

Третій цикл:

2 - 7 → 12 → 9 → 8 →15 - 2

Четвертий цикл:

6 -11 - 6.

Таким чином, рядок ключа має 4 цикли.

Число циклів визначаємо прямо по рядку.

Збільшення такі: 3®7; 7®10; 10®11; 11®12; 12®15; 4®6;6 ® 9;

5 ® 13.

Всього вісім збільшень.

Таким чином у розглянутої таблиці підстановки 62 - інверсії, 4 - цикли
по 8 збільшень. Порівнюючи отримані значення з пороговими, що наведені
в задачі 1, робимо висновок, що розглянута підстановка є випадковою.

2.9 Симетричні потокові шифри . Приклади розв’язку задач та
задачі для самостійного розв’язання

Приклади розв’язку задач

Задача 1.

Визначити період повторення двійкової послідовності, що формується за допомогою двох лінійних рекурентних регістрів ЛРР1 та ЛРР2, якщо ЛРР1 та ЛРР2 реалізовані з використанням примітивних поліномів та порядків відповідно.

Розв’язок задачі.

Оскільки числа та 127 є прості числа Ейлера і періоди повторень та є також прості числа, то період повторення L послідовності, що формується згідно з ЛРР1 примітивний поліном) та ЛРР2 примітивний поліном)

Якщо і , то послідовність L може бути сформована з використанням схеми, що наведена на рис. 2.22.

Рисунок 2.22 - Схема формування двійкової послідовності з періодом L

Задача 2.

Визначте закон формування гами скремблювання, якщо відомі відрізки послідовності

Покладемо спочатку, що ці послідовності сформовані лінійним рекурентним регістром m-го порядку з поліномом (для А₁) і, що перехоплено 2m символів. Значить для А₁ m=5.

Еквівалентна схема такого регістра наведена на рис. 2.23

Рисунок 2.23 - Еквівалентна схема ЛРР з невідомим зворотним зв’язком

Присвоюючи вектору послідовно значення 11111, 11110, 11100, 11000, 10000, отримаємо систему лінійних рівнянь

Цю систему можна розв’язати будь-яким методом, враховуючи тільки, що і

Із системи зразу видно, що Далі, підставивши в наступне рівняння, маємо

Підставивши в третє рівняння, маємо значить

Далі, підставивши в четверте рівняння, маємо

значить

Підставивши в останнє рівняння, маємо

Таким чином, тільки і не є нульові, тому

Для вектора А₂ маємо систему рівнянь

Розв’язок задачі.

Складемо за модулем 2 перше та друге рівняння системи

Далі складемо перше та третє рівняння

Складемо перше та четверте рівняння

Складемо перше та шосте рівняння

Складемо п’яте та сьоме рівняння

Складемо шосте та сьоме рівняння

Підставивши в останнє рівняння значення х_3,х₅ та х₇, маємо

Перевірка.

Згенеруємо послідовність згідно з .

На рис. 2.24 наведено схему ЛРР

Рисунок 2.24 - Схема ЛРР

Сформуємо послідовність, підставивши в ЛРР початкове значення його стану „1111111”.

Таким чином, вихідною є послідовність „11111110101010” і вона співпадає з А₂, тобто розв’язок зроблено правильно.

„Увага” – колізія. Перевірте чи можна сформувати послідовність А₂ з використанням ЛРР, у якого зворотний зв’язок реалізовано з використанням полінома Якщо можна, то зробіть відповідні пояснення

Задача 3.

Розробіть спрощену структурну схему та проведіть дослідження стійкості потокового шифру А5, що застосовується в системі зв’язку GSM.

Шифр А5 [10]– це потоковий шифр, що використовується в системі мобільного зв’язку GSM. Це європейський стандарт для мобільних цифрових сотових телефонів. Алгоритм А5 використовується для шифрування каналу “телефон/базова станція”. Відомо, що в середині восьмидесятих років різні таємні служби НАТО розв’язували задачу, чи має шифрування GSM бути сильним чи слабким. Німцям необхідна була сильна криптографія, так як вони були на кордоні з Варшавським договором. Але перемогла друга точка зору, був прийнятий відносно слабкий шифр А5, який розроблено Францією. Британська телефонна компанія передала всю документацію Брендфордському університету, забувши підписати з ним угоду про її конфіденційність. В результаті інформація про А5 була опублікована в Інтернет. Програмна реалізація А5 наведена в [10].

Структурна схема шифроутворюючого пристрою наведена на рис. 2.25. В склад пристрою входить три ЛРР з довжинами 19,22 та 23 бітів відповідно. Всі многочлени зворотного зв’язку є прорідженими. Виходом є результат операції XOR над трьома ЛРР. В А5 використовується також управління тактуванням. Кожний регістр тактується в залежності від свого середнього біта, потім над регістром виконується операція XOR зі зворотною пороговою функцією середніх бітів усіх трьох регістрів, звичайно на кожному етапі тактуються два ЛРР.

Знайдено тривіальне розкриття А5, що вимагає 2⁴⁰ шифрувань: якщо припустити відомими стани перших двох регістрів, то можна за гамою-шифруючою спробувати визначити стан третього ЛРР.

Рисунок 2.25 – Структурна схема алгоритму А5

В цілому, ідеї, що закладені в А5 є потужними. Алгоритм є ефективним, він задовольняє статистичним тестам. Єдиною його слабкістю є замалі довжини регістрів.

Оцінимо значення основних показників шифру А5 – безпечний час t_б, ентропію джерела ключів та відстань єдності

де n_кл=2⁶⁴ – число ключів, n_в=2⁴⁰ – число варіантів під час криптоаналізу, g=10¹⁰ – потужність криптоаналітичної системи, k=3,15×10⁷ с/рік, r – збитковість вихідного алфавіту.

В результаті маємо

Задача 4.

Побудуйте генератор Геффе та дослідіть його властивості [10].

Структурна схема генератора Геффе наведена на рис. 2.26.

ЛРР2

ЛРР3

ЛРР1

Мультиплексор

Рисунок 2.26 – Структурна схема генератора Геффе

В генераторі Геффе використовується комбінація із трьох ЛРР. Два ЛРР (ЛРР2-ЛРР3) є джерелами гам початкових, а ЛРР1 управляє виходом мультиплексера. Якщо та є виходами відповідних ЛРР, то вихід генератора можна задати у вигляді

Якщо довжини ЛРР є відповідно та , то лінійна складність генератора може бути оцінена як [10]

Період генератора дорівнює найменшому спільному кратному періодів трьох ЛРР. Якщо степені трьох примітивних поліномів зворотного зв’язку взаємно прості, то період цього генератора дорівнюватиме добутку періодів трьох ЛРР.

Основним недоліком генератора Геффе є незахищеність від кореляційної атаки [10].

Задача 5.

Побудуйте генератор Дженнінгса та дослідіть його властивості.

В генераторі Дженнінгса мультиплексор використовується для об’єднання бітів двох ЛРР [10]. Мультиплексор, що управляється ЛРР1, вибирає як черговий вихідний 1 біт ЛРР2. Крім того, використовується функція, що відображає вихід ЛРР2 на вхід мультиплексора. Структурна схема генератора Дженнінгса наведена на рис. 2.27.

ЛРР2

Мультиплексор

ЛРР1

0 1 n-1

Рисунок 2.27 – Структурна схема генератора Дженнінгса

Ключем в генераторі є початковий стан двох ЛРР- ЛРР1 та ЛРР2, а також функція відображення . Дослідження показали, що на генератор можна реалізувати ефективні атаки типу “зустріч посередині” та “кореляційне розкриття”.

2.10 Стійкість асиметричних криптосистем, що базуються
на криптоперетвореннях в простих полях. Приклади розв’язку задач
та задачі для самостійного розв’язання

2.10.1 Основні теоретичні та практичні відомості

Криптографічні перетворення в простих полях Галуа історично вперше були застосовані для забезпечення передачі відкритих ключів (сертифікатів) по відкритих каналах зв’язку. На основі цього перетворення в подальшому було розроблено ряд протоколів-примітивів, що прийняті як національні стандарти, наприклад, стандарт ANSI X9.42. Крім того, ряд таких криптографічних примітивів використовуються для виробки ключів стандартів на цифрові підписи США - FIPS-186, Росії - ГОСТ Р 34.10-94 та України - ГОСТ 34.310-95.

Розглянемо два основних протоколи виробки загального секрету (ключів), коли в процесі виробки ключів відкриті ключі (сертифікати) передаються по відкритих каналах зв’язку.

Перший протокол базується на використанні при виробці загального секрету довгострокових ключів.

Нехай в криптосистемі відомі загальносистемні параметри , де Р – просте число, а – твірний елемент поля Галуа GF(P). З кута зору вимоги найбільшої складності криптоаналізу число Р має бути “сильним”, наприклад, у вузько-
му значенні. Таке число можна подати у вигляді

, (2.60)

де R – також просте число.

В ряді випадків до числа Р ставиться вимога, щоби в канонічному розкладі числа Р-1 містилось велике просте число, скажімо q, тоді

. (2.61)

По суті, прості числа виду (2.60) та (2.61) дозволяють знайти (обчислити) також і твірний елемент а. Так в FIPS-186 та ГОСТ Р 34.10-94 прості числа
мають вид (2.61).

В цілому, загальносистемними параметрами можуть бути або пара , або трійка цілих чисел .

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

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

Кореспонденти А та В виробляють особисті ключі та . Потім кожен із них виробляє відкритий ключ

, (2.62)

. (2.63)

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

, (2.64)

. (2.65)

Можна легко перевірити, що

(2.66)

і у обох абонентів є один і той же загальний секрет. Використовуючи одну і ту ж функцію kdf виробки ключа, кожен із абонентів може виробити одинаковий ключ, наприклад,

(2.67)

де – є параметр виробки ключа. В найпростішому випадку значенням може бути номер сеансу.

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

Сеансові ключі формуються при кожному сеансі зв’язку. Спочатку формуються особисті сеансові ключі та , потім відкриті сеансові ключі

, (2.68)

. (2.69)

Відкриті сеансові ключі пересилаються перед кожним сеансом або поміщаються в першому блоці, що пересилається.

Спочатку обчислюється сеансовий загальний секрет

, (2.70)

. (2.71)

Із (2.70) та (2.71) видно, що , тому кожен із абонентів може виробити однаковий секретний сеансовий ключ

. (2.72)

В подальшому, використовуючи довгостроковий ключ та сеансовий , можна здійснити конфіденційний зв’язок.

Більш переважним є формування сеансового ключа відповідно до правила

, (2.73)

де символ || є знаком конкатенації значень, наприклад, та .

Аналіз показує [26], що найбільшу загрозливість для криптоперетворень в простих полях складають атаки типу універсальне розкриття та повне розкриття. Сутність атаки типу універсальне розкриття заключається в знаходженні деякого математичного алгоритму, що дозволяє, в загальному випадку, обчислити та і та . До сьогодні такі випадки не відомі.

Сутність атаки типу повне розкриття заключається в розв’язку дискретних логарифмічних рівнянь

, (2.74)

та

При розв’язку (2.74) вважається, що загальносистемні параметри (Р, а) та відкриті ключі та є відомими.

Якщо криптоаналітик визначить особистий ключ , то в подальшому він зможе нав’язувати хибні загальні секрети та відповідно хибні пові-домлення. Для суттєвого ускладнення можливості нав’язування хибних загальних секретів використовують як довгострокові, так і сеансові загальні секрети. Тобто на кожний сеанс ключ формують за правилом (2.73). В цьому випадку для порушення конфіденційності необхідно розв’язувати вже два дискретних логарифмічних рівняння, наприклад, (2.62) та (2.68) або (2.63) та (2.69). При удачі криптоаналітик може визначити три особистих ключі або .

Розглянемо основні алгоритми та складність розв’язку дискретних логарифмічних рівнянь. На сьогодні відомо декілька алгоритмів і відповідно методик складності розв’язку дискретних логарифмічних рівнянь. Основними із них є алгоритм -Полларда, Поліга-Хелмана [11], загального решета числового поля [10,11] та алгоритм Купершмідта [11].

Історично першим з’явився метод і на його основі алгоритм -Полларда. Нехай необхідно розв’язати дискретне логарифмічне рівняння

. (2.75)

Формуватимемо випадкові пари цілих чисел та . Нехай знайдено такі дві пари чисел та , що

. (2.76)

Підставимо (2.75) в (2.76), в результаті маємо

або

. (2.77)

В рівнянні (2.77) згідно з теоремою Ойлера ступені можна прирівняти за модулем (Р-1), тобто

. (2.78)

Із (2.78) в свою чергу маємо

або

. (2.79)

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

Виберемо як перший елемент послідовності як

. (2.80)

Далі обчислюватимемо послідовність за рекурентним правилом

(2.81)

Постійну с вибирають таким чином, щоби с знаходилось між а та b приблизно на однаковій відстані. Але в більшості випадків його підбирають.

Послідовність називають послідовністю -Полларда. Для успішного розв’язку дискретного логарифмічного рівняння необхідно знайти два значення та таких, що

. (2.82)

Після цього знаходять значення та та обчислюють згідно з (2.79) особистий ключ.

Метод Поліга-Хемана базується на китайській теоремі про лишки [17]. Нехай знову необхідно розв’язати рівняння

. (2.83)

Розв’язок виконується в декілька етапів:

- знаходиться канонічний розклад числа Р-1;

- обчислюються лишки за модулями канонічного розкладу;

- обчислюється значення Х згідно з китайською теоремою про лишки.

Перший етап виконується достатньо просто, так як згідно з (2.60) та (2.61) на етапі побудови пари розклад числа Р-1 є відомим. Інакше довести, що а – твірний елемент, дуже складно. Тому на першому етапі Р-1 подається у
вигляді:

(2.84)

Далі знайдемо лишки від ділення Х на , в результаті для кожного отримаємо

, (2.85)

причому .

Необхідно знайти коефіцієнти для усіх i. Оскільки лишки подано за модулем , то

. (2.86)

Запишемо далі (2.83) у вигляді

. (2.87)

та піднесемо ліву і праві частини (2.87) до ступеня . В результаті отримаємо

. 2.88)

Обчислимо значення , підставивши в нього (2.86), в результаті маємо

. (2.89)

Якщо перемножити на вираз в дужках, то ми отримаємо

. (2.90)

В цьому можна переконатися, так як всі члени, крім діляться на Р-1, тому вони даватимуть лишок рівний 0. З урахуванням (2.90) (2.10.88) має вигляд

. (2.91)

Тепер піднесемо ліву та праві частини (2.87) до ступеня , в результаті отримаємо

. (2.92)

Підставивши в (2.92) вираз (2.86), отримаємо

. (2.93)

Оскільки на (Р-1) тепер не ділитимуться два члени

та ,

тому вони не дорівнюватимуть нулю.

Аналогічно можна перетворити (2.87) для усіх і для усіх ступенів. В результаті для конкретного модуля ступеня отримаємо порівнянь

(2.94)

Використовуючи (2.94), можна знайти усі лишки виду (2.84), для цього достатньо знайти коефіцієнти . Їх ми знаходимо, використовуючи (2.94). Спочатку, перебираючи значення , знаходимо і так далі для усіх ступенів, включно до

Таким чином, для фіксованого система (2.94) дозволяє визначити коефіцієнти і, як наслідок, лишок (2.85). Для знаходження другого лишку необхідно взяти наступне значення .

Таким чином, ми одержуємо лишки

(2.95)

Використовуючи китайську теорему про лишки, отримаємо [17]

, (2.96)

де

Зворотний елемент знаходимо із порівняння

Таким чином, (2.96) дає розв’язок дискретного логарифмічного порівняння виду (2.83) або (2.87).

Важливими в теоретичному плані є задачі оцінки складності розв’язку дискретних логарифмічних рівнянь. Для алгоритму -Полларда як асимптотич-ну оцінку складності розв’язку можна використовувати співвідношення

. (2.97)

Інші алгоритми мають субекспоненціальну складність виду

(2.98)

Так, при застосуванні загального решета числового поля Є відомості, що алгоритм Купершмідта дозволяє розв’язати дискретне логарифмічне рівняння в полі GF(2ⁿ⁾зі складністю .

Складність алгоритму Поліга-Хелмана можна оцінити безпосередньо за наведеним вище алгоритмом.

2.10.2 Приклади розв’язку задач

Задача 1.

Розв’язати дискретне логарифмічне рівняння виду методом -Полларда.

Розв’язок.

Обчислюватимемо значення з урахуванням того, що

Виберемо С=6 та розрахуємо значення . Результати зведено до таблиці 2.19.

Таблиця 2.19 – Результати розрахунків

І	1	2	3	4	5	6	7
r_i	b=9	ab=20	a²b=1	a²b²=9	a³b²=20	a⁴b²=1	a⁴b³=9
U_i	0	1	2	2	3	4	4
V_i	1	1	1	2	2	2	3

Аналізуючи значення , ми бачимо, що r ₁= r ₄= r ₇, r ₂= r ₅, r ₃= r ₆. Вибравши будь-яку пару та , знайдемо пари значень та . Наприклад, для r ₃=r ₆ маємо при r ₃. U_i=2 і V_i=2, для r ₆ U_j=4 і V_j=3. Підставивши ці значення
в (2.79), маємо

Далі знайдемо зворотний елемент y для числа 21 в кільці за модулем 22. Маємо рівняння

Розв’яжемо це рівняння, використовуючи алгоритм Евкліда

отже тоді

Тому

Таким чином, Прямим обчисленням перевіряємо пра-вильність розв’язку.

Приклад 2.

Розв’язати дискретне логарифмічне рівняння виду

Розв’язок.

Зробимо, використовуючи метод Поліга-Хеллмана. Розкладаємо число

Отже

Оскільки максимальні значення ступеня залишку і , то згідно з (2.84) та лишки матимуть лише два члени. Тому шукатимемо та лишки за модулями та відповідно

Тепер нам потрібно знайти та Для цього використаємо порівняння (2.94), в результаті отримаємо

або

обчисливши ліву частину, маємо

Тепер врахуємо, що коефіцієнти та , обчислюються за модулем 2, то або Підставивши ці значення, отримаємо, що Для знаходження використаємо порівняння (2.94), в результаті отримаємо

Після обчислень маємо

Отже

Таким чином,

Далі знайдемо аналогічно , для цього знайдемо та Аналогічно як і для маємо

або

Підставимо в перше порівняння послідовно

(оскільки ).

За аналогією як і для та , маємо

Тому

Тепер, знаючи лишки та , можна знайти Х, використовуючи формулу (2.96)

Таким чином,

Прямою перевіркою підтверджуємо, що дійсно дорівнює 20 за
модулем 37.

2.11 Стійкість асиметричних криптосистем, що базуються на
криптоперетвореннях в групі точок еліптичних кривих. Приклади розв’язку задач та задачі для самостійного розв’язання

2.11.1 Основні теоретичні відомості

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

Під час аналізу стійкості необхідно розглядати дві проблеми стійкості - розв’язання задачі дискретного логарифму та задачі Діффі-Хеллмана.

Проблема дискретного логарифму формується в наступному вигляді. Нехай задано точку G на еліптичній кривій E(F(q)), де q=p (p - просте число) або q=p^m (p - просте число, m - натуральне, mÎN). Відомо також значення відкритого ключа Q, причому

. (2.99)

Необхідно знайти конфіденційний (особистий) ключ d.

Проблема Діффі-Хеллмана формується в наступному вигляді. Нехай дано ЕК E(F(q)), відомо значення точки , а також відкритий ключ . Необхідно знайти загальний секрет

, (2.100)

де та - особисті ключі відповідно першого та другого користувачів.

На сьогодні для аналізу стійкості та проведення криптоаналізу знайшли розповсюдження декілька методів Поларда - та оптимальний . Розглянемо метод Поларда на прикладі ЕК над простим полем Галуа , тобто

. (2.101)

Для всіх точок задано операції додавання та подвоєння. Наприклад, якщо , а , то

де

(2.102)

Для ЕК над полем виду

, (2.103)

причому , сума двох точок та

де

(2.104)

примітивний поліном m-го ступеня;

(2.105)

Для розв’язання задачі пошуку конфіденційного ключа в порівнянні (2.99) розглянемо -метод Поларда над простим полем . Нехай
- базова точка, - відкритий ключ, шукатимемо пари цілих та , таких що

. (2.106)

Позначимо в загальному вигляді

. (2.107)

Суть -методу Поларда розв’язання порівняння (2.99) заключається в наступному. Знайдемо деяку функцію , вибравши , де - порядок точки на ЕК

. (2.108)

Далі знайдемо послідовність:

для пар , таких що:

. (2.109)

Рекомендується в простих випадках (при відносно невеликих ) послі-довність розраховувати у вигляді:

(2.110)

При цьому , та складають частини області . Якщо область рівномірно ділиться, то (2.11.12) має вигляд:

(2.111)

При побудові множини пошук буде успішним, якщо ми знайдемо

що еквівалентно знаходженню

. (2.112)

Зробивши прості перетворення, маємо:

(2.113)

і далі

. (2.114)

З (2.99) та (2.114) випливає, що

, (2.115)

Більш ефективним є розрахунок з розбиванням інтервалу на інтервалів. Для реальних значень рекомендується . В цьому випадку замість (2.110) маємо

(2.116)

причому та є випадкові цілі із інтервалу .

У випадку (2.116) рішення знаходиться як і раніше у вигляді (2.111), а
потім (2.115). З урахуванням позначень в (2.116)

. (2.117)

Успішне розв’язання задачі дискретного логарифму в групі точок ЕК
вимагає

(2.118)

операцій на ЕК.

Із (2.117) та (2.118) випливає, що задачу пошуку пар та може бути розпаралелено на процесів, тоді

. (2.119)

Розроблено методику та алгоритми, які дозволяють розв’язати задачу (2.99) зі складністю

, (2.120)

а при розпаралелюванні на процесорах складність визначається, як

. (2.121)

При розв’язанні задачі важливо правильно (вірніше успішно) вибрати . Значення рекомендується вибирати у вигляді

також можна вибирати як

, (2.122)

де .

2.11.2 Приклади розв’язку задач

Задача 1.

Нехай точка належить ЕК

причому і , тобто

Відкритий ключ . Порядок точки , порядок ЕК , де - кофактор. Необхідно знайти відкритий ключ із порівняння

В нашому випадку

Розв’язання задачі.

Використовуючи співвідношення (2.110), отримаємо

(2.123)

Результати розв’язку задачі наведено в таблиці 2.20.

Таблиця 2.20 – Результати розв’язку задачі 1


	1	0
	2	0
	4	0
	4	1

Виберемо як , тоді належить , тому

Згідно з (2.102)

Розв’язуємо це рівняння, використовуючи алгоритм Евкліда

Отже . Таким чином .

В результаті маємо, що

Таким чином .

Другий крок

.Знаходимо .

Мультиплікативно зворотний елемент числу 2 в полі знаходимо із
рівняння

дійсно

;

Таким чином

;

Знаходимо

;

Таким чином в таблиці ми знайшли, що

;

Знаходимо

Перевіряємо

Таким чином

Задача 2.

Визначте складність та вартість криптоаналізу методом повного розкриття для криптоперетворень в групі точок ЕК над полем , якщо порядок базової точки , потужність криптоаналітичної системи
додавань на ЕК/с., а вартість одного міпсороку складає грн.

Розв’язок задачі.

Знайдемо складність криптоаналізу, вважаючи, що він здійснюється методом повного розкриття з використанням оптимального методу Поларда. В цьому випадку складність криптоаналізу визначається з використанням формули (2.120)

В таблиці 2.21 наведено значення складності криптоаналізу методом повного розкриття, тобто з визначенням таємного ключа . Одиницею виміру складності є число операцій додавання в групі точок ЕК.

Таблиця 2.21 - Складність криптоаналізу

Знаючи загальну складність, вартість криптоаналізу визначаємо таким чином: безпечний час виконання криптоаналізу (в роках)

де с./рік.

Для досягнення потужності криптоаналітичної системи оп/с необхідно затратити років або паралельно використати комп’ютерів з потужністю оп. додавання на ЕК/с. Тому вартість криптоаналізу можна визначити як

В таблиці 2.22 наведено значення безпечного часу та вартості криптоаналізу.

Таблиця 2.22 - Безпечний час та вартість криптоаналізу


(років)
(грн.)

Задача 3.

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

бітів.

Потужність криптоаналітичної системи в кільці та полі складає , а в групі точок ЕК . Вартість одного міпсороку складає для криптоперетворень в кільці та полі 30 грн., а в групі точок ЕК - 600 грн.

Розв’яжемо задачу при .

При маємо . Спочатку визначаємо складність криптоаналізу для перетворень в кільці. Очевидно найменш складним буде криптоаналіз, що застосовується на факторизації модуля перетворення з використанням загального решета числового поля. Вона визначається як

. (2.124)

При криптоаналізі криптографічних перетворень в полі Галуа найбільш складною є задача розв’язку дискретного логарифмічного рівняння

. (2.125)

Складність розв’язку (2.125) також може бути оцінена з використанням (2.11.26), при цьому, якщо розв’язок (2.125) базується на використанні загального решета числового поля, то , при факторизації .

Складність криптоаналізу в групі точок ЕК при використанні оптимального методу Поларда можна оцінити як

, (2.126)

де - порядок базової точки в групі точок ЕК. Таким чином для оцінки складності криптоаналізу використовуємо формули в кільці

В полі:

В групі точок ЕК

Для кільця маємо:

Для поля маємо:

Для групи точок ЕК

Наступні задачі 4 - 8 є додаткові, вони призначені для практичного засвоєння перетворень в розширених полях Галуа .

Задача 4.

Знайдіть елементи поля , якщо неприводимий поліном .

Розв’язок.

Враховуючи, що поле містить 16 елементів та використовуючи поліноміальне перетворення, маємо:

Задача 5.

Знайдіть суму та добуток елементів поля , якщо .

Розв’язок.

Сума за модулем 2: .

Добуток має вигляд: .

Дійсно .

Задача 6.

Знайдіть усі елементи поля , використовуючи первисний елемент поля , .

Розв’язок.


	1

. Дійсно


	1

Задача 7.

Нехай супернесингулярна крива над полем . Примітивний поліном . Знайдіть точки, які задовольняють цьому рівнянню.

Розв’язок.

Порівняння має вигляд: .

Розв’язком є точки:

Використовуючи формули для додавання точок:

маємо

При подвоєнні маємо:

Задача 8.

Знайдіть вирішення , . Мультиплікативний елемент .

Розв’язок.

Рівнянню відповідають такі елементи:

Будуємо множину відкритих ключів

Таким чином порядок точки n=20.

2.12 Електронні цифрові підписи та їх застосування. Приклади
розв’язку задач та задачі для самостійного розв’язання

2.12.1 Приклади розв’язку задач

Задача 1.

Визначте ЕЦП, зробіть класифікацію та оцініть ступінь дії загроз відносно ЕЦП.

Згідно з прийнятою класифікацією можна зазначити такі види загроз.

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

2. Селективна підробка (selective forgery). Є загроза створення для раніше вибраного повідомлення М правильного ЕЦП (М).

3. Універсальна підробка (universal forgery). Сутність цієї загрози в тому, що криптоаналітик, використовуючи ненадійність математичного стандарту ЕЦП, може знайти другий алгоритм цифрового підпису, функціонально еквівалентний істинному, що дозволяє йому створити або модифікувати істинні повідомлення.

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

Задача 2.

Визначте, зробіть класифікацію та оцініть атаки, що можуть бути реалізовані на ЕЦП.

Відносно ЕЦП можуть бути здійснені такі атаки:

- атака на основі відомого відкритого ключа;

- атака на основі відомих підписаних повідомлень;

- проста атака з вибором підписаних повідомлень;

- направлена атака з вибором підписаних повідомлень;

- адаптивна атака з вибором підписаного повідомлення.

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

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

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

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

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

Задача 3.

Визначте умови та сформуйте пропозиції з реалізації в системі КЗІ загрози типу екзистенційна на підробку ЕЦП.

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

При доведенні стійкості ЕЦП проти цієї загрози вважається, що значення геш-функції формується деяким оракулом (чорним ящиком). На його вхід подаються випадкові повідомлення M₁,M₂,M₃,…,M_k , в результаті чого на виході формуються також випадкові значення геш-функції Послідовності M_i та h_i, що обчислені, він запам’ятовує і, якщо M_i=M_j, i¹j, то оракул видає раніше обчислене значення h_i.

Для захисту від екзистенціальної підробки ЕЦП геш-функція має задовольняти такі вимоги:

1) не вище ніж поліноміальна складність обчислення значення геш-функції;

2) не нижче ніж експоненціальна складність визначення повідомлення M_iза відомим значенням h_i;

3) практична захищеність від колізій, коли можна знайти M_i та M_j, такі, що H(M_i)=H(M_j), з імовірністю не вище ніж P_k, де P_k завідомо задане значення.

Розглянемо реалізацію загрози. Нехай Q та G є відкритий ключ і базова точка для ЕЦП ECDSA. Зловмисник вибирає випадкове число l та обчислює параметр цифрового підпису , де r є х координата. Далі приймається, що s=r та обислюється , де n – порядок базової точки. Якщо криптоаналітик може сформувати повідомлення М₁ таке, що

то є дійсний ЕЦП.

Далі, якщо геш-функція не захищена від колізій, то криптоаналітик може знайти M₂ таке, що H(M₂)=H(M₁), де M₁ – дійсне, уже підписане повідомлення. Потім ЕЦП приєднується до і M₂ посилається замість M₁. Отримувач не визначить, що до M₂ приклеєний підпис від M₁ і йому буде нав’язано хибне повідомлення.

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

Задача 4.

При виробці цифрового підпису використовуються однонаправлені геш-функції SHA-1 ГОСТ 34.311-95 та SHA-2. Вони формують геш значення для SHA-1 довжина l =160 бітів, для ГОСТ 34.311-95 l=256 бітів і SHA-2 – 256,384 чи 512 бітів. Оракул здійснює обчислення геш значень зі швидкістю Мбіт/с для SHA-1, для ГОСТ 34.311-95, для SHA-2 (l_h=256 бітів) і для SHA-2 (l_h=512 бітів).

Необхідно знайти імовірність екзистенціальної підробки, якщо оракул функціонує протягом одного року.

Розв’язок задачі зробимо, використовуючи загальну теорію колізій, що базується на “парадоксі про день народження”.

Справедливо рівняння

де k – число обчислень, зроблених оракулом за один рік, n – розмір множини допустимих значень геш, P_k – імовірність колізії.

Обчислимо значення n_i та k_i. Величини n_i обчислюються просто

Далі обчислено число k геш-значень, що можуть бути сформовані оракулом протягом року, якщо довжина повідомлень, що гешуються Кбіт= 1 Кбайт.

де с/рік.

Підставивши значення, маємо

Оскільки усі , то для обчислення імовірності колізії можна застосувати формулу

Підставивши в наведену формулу значення k_i та n_i , маємо:

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

Задача 5.

Виробіть особистий ключ, обчисліть для нього відкритий ключ, виробіть та перевірте цифровий підпис, якщо в ECDSA використовується еліптична крива , базова точка G=(13,7) має порядок , величина кофактора h=4.