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

1. Метод Поліга-Хелмана

 

Метод Поліга-Хелмана запропонований в 1978 році для визначення дискретного логарифма в мультиплікативній групі поля .

Він заснований на відомій для групи факторизації порядку  групи за ступенями простих чисел

Стосовно до адитивної групи точок з генератором  порядку  маємо  Відповідно до відомої китайської теореми про залишки існує єдине натуральне число , таке що

Після визначення значення  дискретний логарифм  здобувають за допомогою розширеного алгоритму Евкліда. Наведемо приклад.

Приклад 1

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

Тут  На першому етапі визначаємо точку   Отримуємо точку  другого порядку з відомими координатами  Оскільки , маємо перше порівняння

На наступному етапі знаходимо одну із точок третього порядку  Ці точки також відомі, тому з  отримуємо наступне порівняння

Нарешті, визначаємо точку 5-го порядку  й отримуємо

.

Наведені три порівняння дають єдине розв’язання  В загальному випадку необхідно знати координати  точок із загальної кількості .

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

2. Метод ділення точок на два

 

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

У звичайній арифметиці двійкове подання цілого числа починається з визначення молодшого біта: при непарних  з  віднімається 1 (це молодший біт двійкового подання ) і результат ділиться на 2. Якщо частка парна, ділення триває, у протилежному випадку виконується віднімання 1 і ділення на 2 (отримуємо наступний розряд числа рівний відповідно 0 або 1). Процедура триває до одержання частки, рівної 1. Якщо точка – генератор простого порядку , то при знанні відповіді на питання про парність (непарність) множника  точки   легко вирішується ( у поліноміальному часі ) описаною вище послідовною процедурою віднімання-ділення на два. У простому полі  ділення на два тотожно множення на елемент   Виявляється замість багаторазового додавання ділення точки на два виконується набагато ефективніше й швидше.

Визначимо порядок кривої як

де  - велике просте число (в існуючих криптографічних стандартах ),  - непарне число.

Нехай - точка порядку , тоді генератор криптосистеми може бути визначений як точка  порядку .

Введемо операцію ділення точки несуперсингулярної кривої

:  (1)

на два як зворотну подвоєнню. Нехай маємо точку  та точку  з координатами

 (2)

Інакше кажучи, визначення  означає знаходження координат точки  з відомої точки  Відповідно до (2) для цього необхідно вирішувати квадратне рівняння

 (3)

У загальному випадку це рівняння має два розв'язки  й  при наслідку

 (4)

Якщо слід  то точка  - непарна точка - непарне). ............