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
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. Підставивши ці значення в (2.79), маємо

.

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

.

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

отже тоді

Тому

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

Приклад 2.

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

Розв’язок.

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

Отже

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

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

або

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

.

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

.

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

і

.

Отже

Таким чином,

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

або

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

(оскільки ).

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

Тому

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

Таким чином,

.

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