Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої

 

1. Методи Полларда

Розглядаючи метод Полларда для вирішення проблеми дискретного логарифмування розв'яжемо наступну задачу.

Задача 1. Нехай точка  належить ЕК

,

причому  і , тобто

.

Відкритий ключ . Порядок точки , порядок ЕК , де -кофактор. Необхідно знайти відкритий ключ  із порівняння

У нашому випадку

.

Розв'язання задачі. Використовуючи співвідношення, отримаємо

Результати розв'язку задачі наведено в таблиці 1.

Таблиця 1 – Результати розв'язку задачі 1

	1	0
	2	0
	3	0
	4	1

Виберемо як  тоді  належить , тому

.

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

Отже  Таким чином,

У результаті маємо, що

Таким чином

Другий крок:  Знаходимо

Мультипликативно зворотний елемент числу 2 у полі  знаходимо з рівняння

дійсно

Таким чином,

Далі знаходимо

Таким чином, у таблиці ми знайшли, що

Знаходимо

Перевіряємо

Таким чином

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

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

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

Стійкість  заснована на складності розв’язання задачі дискретного логарифмування. У порівнянні з більше ранніми прототипами - криптосистемами Діффі-Хеллмана й Ель-Гамала - вони дають істотний виграш у криптостійкості, або практично на порядок дозволяють скоротити розмір поля при порівняній стійкості. Відомо, що  порядку 160 біт порівнянний щодо безпеки з RSA і криптосистемою Eль-Гамала з розміром ключа 1024 біт, причому цей виграш прогресує зі збільшенням довжини ключа.

Щоб оцінити складність  (Elliptic Curve Discrete Logarithm Problem), уявімо на хвилину, що піщина з лінійним розміром 0,1 мм є однією з точок ЕСС. Якої величини буде планета, складена з  таких піщин? Якщо -радіус планети в кілометрах, то  й  км. Це приблизно в  раз перевищує радіус нашої планети. Серед цього вражаючого числа піщин потрібно знайти одну. Це й буде розв’язком, порівнянним за складністю з  для  із числом точок порядку .

Практично обчислювальна складність вимірюється в MIPS-роках (MIPS – Million Instructions per Second - мільйон інструкцій за секунду). Під однією операцією тут розуміють одне додавання точок кривої. Оцінки часу рішення  за допомогою -методу Полларда залежно від розміру поля й порядку  криптосистеми наведено в таблиці 2

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

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

Таблиця 2 - Складність і час обчислення рішення ECDLP за допомогою -методу Полларда залежно від порядку  криптосистеми

Розмір поля, Біт	Порядок  криптосистеми, Біт	Складність	Час обчислень -роки
163	160
191	186
239	234
359	354
431	426

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

Операція експоненціювання  у мультиплікативній групі найбільш ефективно здійснюється методом послідовного піднесення до квадрата. Для цього число  подається у двійковій системі числення

як -розрядне двійкове число . Наприклад, мінімальним 5-розрядним числом (з 1 у старшому розряді) є двійкове число  (рівне 16 у десятковій системі), а максимальним – число 11111 (рівне 31 у десятковій системі). Тоді експоненціювання елемента  зводиться до послідовного піднесення до квадрата і множення на  (останнє за наявності 1 у двійковому записі від старшого розряду до молодшого):

У першому випадку виконується 4 операції множення, у другому 8-множень. У загальному випадку експоненціювання у двійкову -розрядний степінь цим методом здійснюється за допомогою від  до  операцій множення за модулем . Об'єм обчислень пропорційний розрядності числа . Така обчислювальна складність називається поліноміальною  а - коефіцієнт пропорційності).

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

Взагалі кажучи, поняття обчислювальної складності визначається через співвідношення вхідного й вихідного об'ємів даних деякого обчислювального алгоритму. Алгоритми поліноміального часу (швидкі алгоритми) характеризуються лінійним співвідношенням об'ємів даних на виході й вході процесора, а алгоритми експонентного часу (повільні), відповідно, експонентним. Зі збільшенням об'єму вхідних даних експонентна складність веде до практично нереалізованих обчислювальних витрат.

Сьогодні відомі досить ефективні субекспоненційні методи рішення DLP над скінченними полями. Це пов'язано з тим, що елемент поля  - ціле число, яке можна факторизувати у вигляді добутку ступенів простих чисел. Це затребувано з метою безпеки істотно збільшити розміри поля для криптосистем Діффі-Хеллмана й Ель-Гамала (до тисяч біт). З іншого боку, точку еліптичної кривої  факторизувати на зразок цілого числа не вдається. Тому для ЕСС поки не відомі методи розв’язання , більш ефективні, ніж класичні методи з експонентною складністю обчислень. Цим і пояснюється високий рівень безпеки криптосистем на еліптичних кривих.

Криптоатаки на  прийнято розділяти на дві групи: атаки на загальну структуру й атаки ізоморфізму. До першого звичайно відносять:

– метод Шенкса( Shenks Method- Giant Step-Baby step);

–  методи Полларда (Pollard¢s Method);

– метод Поліга- Хеллмана (Pohlig-Hellman Method);

– метод обчислення степенів (Index Calculus Method).

Ці методи застосовні для будь-якої скінченної групи, у тому числі й для еліптичної кривої (крім останнього). Атаки ізоморфізму специфічні для ECC. Серед них найбільш відомі:

– атака Менезиса, Окамото й Ванстоуна, або MOV- атака;

– ізоморфізм Семаєва;

– метод спуску Вейля й ін.

Атаки ізоморфізму базуються на перетвореннях, що переводять абелеву групу точок  в елементи мультиплікативної групи поля. Оскільки, рішення  у поле набагато простіше, ніж на еліптичній кривій (при порівнянних порядках), то знаходження ізоморфізму між двома групами істотно знижує безпека ЕСС. Поки відомі кілька класів криптографічно слабких кривих, для яких ці атаки успішні.