Оцінка стійкості доказовo стійких криптосистем

Сутність методу Поліга - Хелмана.

Нехай є система Діфі - Хелмана, причому відкритий ключ обчислюється як:

(1.142)

Нехай параметри – доступні КРА.

Тоді аналіз виразу (1.142) показує, що основним фактором, що визначає стійкість, є складність вирішення рівняння відносно :

. (1.143)

Якщо – первісний елемент, а – просте, то послідовність для різних значень , належатиме простому полю Галуа. У полі Галуа кожному значенню відповідає своє значення , і навпаки. Тут відкритий ключ і особистий однозначно зв'язані між собою.

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

Визначаємо

. (1.144)

Далі знаходимо канонічний розклад :

. (1.145)

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

-1 – називатимемо сильним у вузькому значенні, якщо воно має вигляд:

, (1.146)

де R в свою чергу просте.

Просте число вважається сильним у широкому значенні якщо: P -1 містить у своєму розкладі велике просте число R, P +1 – велике просте число S, R -1 – велике просте число T

(1.147)

де – великі прості числа.

Нехай число -1 містить у своєму розкладанні, велике просте число =R.

У заданих умовах необхідно знайти .

Розглянемо можливість розв’язання задачі на основі застосування Китайської теореми про залишки [17]. Теорема стверджує, що:

(1.148)

де – кількість членів розкладання;

– залишок числа за -м модулем, тобто за модулем ;

(1.149)

– це зворотний елемент , тобто

Число нам не відомо, тоді як знайти його розкладання?

Враховуючи, що може бути наведений у вигляді залишків:

.

Для розв’язання першим етапом є побудування канонічного розкладання числа -1.

Уявімо собі, що КРА виявляє, що число – сильне у вузькому значенні, тоді йому не треба шукати канонічне розкладання, тому що воно дорівнюватиме 2 R. У сумі (1.6.23) буде 2 суми й операції будуть за модулем 2 і за модулем R. У такий спосіб Китайська теорема нам мало чого дасть.

Розглянемо другий випадок.

Тепер нехай є сильним у широкому значенні. У цьому випадку канонічне розкладання буде більш спектральним, але в ньому всерівно міститиметься велике просте число .

Розглянемо третій випадок.

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

Нехай у нас залишок має якесь значення, подамо його у вигляді -ічної підстановки, тоді:

(1.150)

; (1.151)

. (1.152)

Підносимо до ступеня ліву і праву частини, у результаті отримаємо:

. (1.153)

Якщо підставити (1.151) у (1.153), то після ряду перетворень можна отримати:

. (1.154)

Наша задача при відомому знайти коефіцієнти .

Будь-яким методом знайдемо з (1.154(1))(наприклад, підбором), після того як ми знайдемо , підставляємо його в (1.154(2)) і знаходимо таким же способом. На якомусь кроці ми знайдемо всі коефіцієнти .

У такий же спосіб необхідно визначити коефіцієнти всіх залишків Далі підставляємо отримані значення у вираз (1.148). У такий спосіб ми можемо знайти ключ.

Методи оцінки стійкості ймовірно стійких криптосистем.

Основним методом оцінки стійкості системи є перевірка складності розв’язання деяких задач.

В RSA N = PQ – розклад модуля на прості множники.

У схемі Діффі-Хеллмана x =log _QY (mod P) – розв’язок дискретного логариф-мічного рівняння.

Складність задач RSA в групових операціях, можна оцінити як:

. (1.155)

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

Якщо для розв’язання дискретного логарифма використовується загальне решето числового поля, то складність вирішення дискретного логарифма носить також субекспоненціальний характер, але .

Для ЕК складність розв’язання задачі дискретного еліптичного рівняння, визначається числом операцій додавання в групі точок ЕК:

, (1.156)

де – порядок базової точки ЕК.

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

Найбільш слабким ланцюгом цифрових підписів в полі Галуа є субекспоненціальна складність розв’язання дискретного логарифма, тобто знаходження особистого ключа х _а при відомих відкритому ключі Y_а та модулі перетворення Р. Суттєво підвищення стійкості може бути здійснене за рахунок використання перетворень в групі точок еліптичних кривих. У цьому випадку стійкість
визначається складністю розв’язку порівнянь [26]

(1.157)

для розширеного поля, або

(1.158)

для еліптичної кривої над простим полем.

Чисто з інтуітивних розумінь функцію запропонували формувати у вигляді лінійної комбінації базової точки G і відкритого ключа Q:

, (1.159)

де – коефіцієнти, що дозволяють формувати точку, тому що ми шукаємо розв’язок d_i, де , а n– порядок базової точки на ЕК.

Першу базову точку задаємо як:

. (1.160)

Припустимо, що ми використовуємо метод Флойда. Обчислимо -точку:

. (1.161)

Припустимо, що на j -му кроці нам „повезло”, тобто:

. (1.162)

Це дозволяє нам порівняти (1.159) і (1.161):

. (1.163)

Далі маємо

.

Звідси знайдемо Q:

. (1.164)

Порівняємо (1.158) і (1.164), з порівняння випливає, що:

. (1.165)

Висновок: очевидно, що для розв’язання порівняння (1.165) потрібно знайти безліч коефіцієнтів , при яких виконується умова (1.163).

Побудуємо точки , використовуючи -метод, а також правило:

. (1.166)

Для розв’язку зафіксуємо деяке початкове положення .

Область S визначається над безліччю значень . Для реальних значень число областей розбивок, має бути не менше ніж 20.

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

Нехай необхідно вирішити дискретне логарифмічне рівняння:

. (1.167)

Скористаємося методом Поларда, і вважатимемо, що ми знайшли деяку пару параметрів (u,v) і (t,w), таких що:

. (1.168)

Підставимо в порівняння (1.168) значення b з (1.167):

, (1.169)

. (1.170)

У рівнянні (1.170) можна прирівняти показники, але за модулем функції Ейлера від , тобто:

За допомогою - методу Поларда сформуємо значення , тобто задамо правило, аналогічне з правилом розподілу на область:

, (1.171)

де .

Для розв’язання дискретного логарифма вигляду (1.167) метод - Полар-
да є обчислювально складним (при „сильних” P субекспоненційно).