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

Рисунок 1 - Подання елементів циклічної групи точками на колі й інтервал аналізу за методом Шенкса

По суті введення маркерів - це обмін обчислень на пам'ять. Якщо об'єми цих ресурсів зробити рівними, то відстань між маркерами слід вибирати рівною

. Ця ідея запропонована Д.Шенксом.

Метод Шенкса часто називають методом великих і малих кроків (Giant step-Baby step). Маркери

- це Giant step. Номери цих точок з їх -координатами зберігаються в пам'яті. Baby step – це послідовні додавання точок після чого обчислені -координати порівняюються з координатами маркерів. При збігу координат отримуємо , звідки визначається шукане значення . Метод Шенкса є детерміністським.

Обчислювальна складність методу

оцінюється як середнє число малих кроків. Основний недолік методу – надмірний об'єм необхідної пам'яті, пропорційний .

Крім того, на кожному кроці порівняння координат здійснюється по всіх точках, що зберігаються в пам'яті. Для задач реального криптоаналізу метод не знайшов застосування. Однак, часто метод Шенкса приводиться як теоретична основа для інших, більш практичних методів рішення

.

3. Метод ділення точок на два ( продовження)

Він заснований на використанні точок <P> з максимальним порядком

, (коефіцієнт кривої a=0). Задамо рекурентну функцію ділення-відрахування

(1)

Оскільки кожне ділення дає дві точки, повна процедура утворює дерево розв’язків із

галузями ( - число віднімань точки ). В ідеальному випадку, при правильному виборі точок ділення, одна з галузей найбільш коротким шляхом веде до точки , а інша – . При цьому двійковий запис алгоритму ділення (0) або відрахування – ділення (1) дає шукане число або . Для цього буде потрібно не більше ділень. Зрозуміло, при випадковому виборі точок ділення ймовірність знаходження таких галузей мізерно мала.

Точки групи <P> зручно подати у вигляді еквідистантних точок кола, починаючи відлік від точки ПРО, розташованої ліворуч за годинниковою стрілкою (рис. 2). Будь-якій парній точці групи <P> ®

відповідають дві точки ділення й , розташовані на одній діагоналі кола й пов'язані співвідношенням із точкою другого порядку. Значення точок , верхнього півкола можна розглядати як додатні, а нижнього півкола - як від’ємні. Координати кожної такої пари збігаються, а . У процедурі ділення, що прагне до точки , можна ігнорувати знак точки, зазначимо, що є лише - координата точки. Назвемо "правильною" точкою ділення точку лівого півкола (на рис 2 – точка ). Послідовний вибір "правильних" точок ділення в процедурі веде до точки й, відповідно до розв’язання . Злом криптосистеми, у такий спосіб зводиться до вирішення еквівалентних проблем:

– визначення, у якому пів кола групи <P> перебуває деяка точка цієї групи;

– визначення співвідношення (більше - менше) між двома довільними
точками

й групи <P>;

– визначення парності ( непарності) числа

для точки ;

– чи виконується редукція за модулем

при подвоєнні довільної точки із групи порядку ?

Доки відповісти на ці запитання не вдається ECC залишається стійкою криптосистемою з експоненційною складністю розв’язання

. Для криптоаналізу зовсім необов'язково прийти до точки або , достатньо знайти точку з -координатою точки, що раніше зустрічалася в цій процедурі, або будь-якої іншої відомої точки групи <P>. У першому випадку рішення при колізії близько до - методу Полларда, у другому – до методу Шенкса.

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

крива поле дискретний логарифмування атака

Рисунок 2 - Геометрична ілюстрація методу ділення точок кривої на два

Якщо в 1 залишити лише одну операцію ділення на два з вибором точки із групи

, то ітераційна процедура ділення на два в остаточному підсумку також призведе до точки

(або іншої відомої точки), якщо 2 є примітивним елементом поля

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

.

4. Аномальні криві й криві над розширеннями малого поля

Аномальні криві над розширеннями поля

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