Стійкість асиметричних криптосистем, що базуються на криптоперетвореннях в простих полях
Работа из раздела: «
Математика»
/
Стійкість асиметричних криптосистем, що базуються на криптоперетвореннях в простих полях
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(2n) зі складністю.
Складність алгоритму Поліга-Хелмана можна оцінити безпосередньо за наведеним вище алгоритмом.
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
|
|
|
Аналізуючи значення , ми бачимо, що r1= r4= r7, r2= r5, r3= r6. Вибравши будь-яку пару та , знайдемо пари значень та . Наприклад, для r3=r6 маємо при r3. Ui=2 і Vi=2, для r6 Uj=4 і Vj=3. Підставивши ці значення
в (20), маємо
.
Далі знайдемо зворотний елемент y для числа 21 в кільці за модулем 22. Маємо рівняння
.
Розв'яжемо це рівняння, використовуючи алгоритм Евкліда
отже тоді
Тому
Таким чином, Прямим обчисленням перевіряємо пра-вильність розв'язку.
Приклад 2.
Розв'язати дискретне логарифмічне рівняння виду
Розв'язок.
Зробимо, використовуючи метод Поліга-Хеллмана. Розкладаємо число
Отже
Оскільки максимальні значення ступеня залишку і , то згідно з (25) та лишки матимуть лише два члени. Тому шукатимемо та лишки за модулями та відповідно
Тепер нам потрібно знайти та Для цього використаємо порівняння (35), в результаті отримаємо
або
обчисливши ліву частину, маємо
.
Тепер врахуємо, що коефіцієнти та , обчислюються за модулем 2, то або Підставивши ці значення, отримаємо, що Для знаходження використаємо порівняння (35), в результаті отримаємо
.
Після обчислень маємо
і
.
Отже
Таким чином,
Далі знайдемо аналогічно , для цього знайдемо та Аналогічно як і для маємо
або
Підставимо в перше порівняння послідовно
(оскільки ).
За аналогією як і для та , маємо
Тому
Тепер, знаючи лишки та , можна знайти Х, використовуючи формулу (37)
Таким чином,
.
Прямою перевіркою підтверджуємо, що дійсно дорівнює 20 за модулем 37.
