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

Размещено на

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

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), можна знайти усі л...