![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Сутність методу Поліга - Хелмана.
Нехай є система Діфі - Хелмана, причому відкритий ключ обчислюється як:
(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)
де – коефіцієнти, що дозволяють формувати
точку, тому що ми шукаємо розв’язок di, де
, а 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 субекспоненційно).
Дата публикования: 2015-01-14; Прочитано: 411 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!