Размещено на http://www.allbest.ru/

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

1. Криптографічні перетворення

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

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

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

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

, (1)

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

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

. (2)

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

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

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

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

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

, (3)

. (4)

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

, (5)

. (6)

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

 (7)

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

(8)

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

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

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

, (9)

. (10)

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

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

, (11)

. (12)

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

. (13)

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

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

, (14)

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

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

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

, (15)

та

.

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

Якщо криптоаналітик визначить особистий ключ , то в подальшому він зможе нав'язувати хибні загальні секрети та відповідно хибні повідомлення. Для суттєвого ускладнення можливості нав'язування хибних загальних секретів використовують як довгострокові, так і сеансові загальні секрети. Тобто на кожний сеанс ключ формують за правилом (14). В цьому випадку для порушення конфіденційності необхідно розв'язувати вже два дискретних логарифмічних рівняння, наприклад, (3) та (9) або (4) та (10). При удачі криптоаналітик може визначити три особистих ключі або .

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

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

. (16)

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

криптографічний ключ алгоритм

. (17)

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

або

. (18)

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

. (19)

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

або

. (20)

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

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

. (21)

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

(22)

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

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

. (23)

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

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

. (24)

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

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

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

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

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

(25)

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

, (26)

причому .

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

. (27)

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

. (28)

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

. 29)

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

. (30)

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

. (31)

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

. (32)

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

. (33)

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

. (34)

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

та ,

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

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

(35)

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

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

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

 (36)

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

, (37)

де

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

.

Таким чином, (37) дає розв'язок дискретного логарифмічного порівняння виду (24) або (28).

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

. (38)

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

(39)

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

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

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

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

Розв'язок.

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

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

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

І	1	2	3	4	5	6	7
ri	b=9	ab=20	a2b=1	a2b2=9	a3b2=20	a4b2=1	a4b3=9
Ui	0	1	2	2	3	4	4
Vi	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. Підставивши ці значення
в (20), маємо

.

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

.

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

отже тоді

Тому

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

Приклад 2.

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

Розв'язок.

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

Отже

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

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

або

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

.

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

.

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

і

.

Отже

Таким чином,

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

або

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

(оскільки ).

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

Тому

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



Таким чином,

.

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

Размещено на Allbest.ru