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

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

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) особистий ключ.

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

. (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 — Результати розрахунків

Аналізуючи значення, ми бачимо, що 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.