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

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

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

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

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

$IMAGE9$

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

Приклад 1

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

Тут $IMAGE16$ На першому етапі визначаємо точку $IMAGE17$  $IMAGE18$ Отримуємо точку $IMAGE19$ другого порядку з відомими координатами $IMAGE20$ Оскільки $IMAGE21$, маємо перше порівняння

$IMAGE22$

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

$IMAGE25$

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

$IMAGE27$.

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

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

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

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

У звичайній арифметиці двійкове подання цілого числа починається з визначення молодшого біта: при непарних $IMAGE11$ з $IMAGE11$ віднімається 1 (це молодший біт двійкового подання $IMAGE11$) і результат ділиться на 2.

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

У простому полі $IMAGE47$ ділення на два тотожно множення на елемент

$IMAGE48$ 

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

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

$IMAGE49$

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

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

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

$IMAGE57$: $IMAGE58$ (1)

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

$IMAGE61$ (2)

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

$IMAGE65$ (3)

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

$IMAGE68$ (4)

Якщо слід $IMAGE69$ $IMAGE70$ то точка $IMAGE71$ - непарна точка $IMAGE72$- непарне). Під час виконання (4) отримуємо дві точки: $IMAGE59$ і $IMAGE74$ ділення точки $IMAGE75$ на два з координатами

$IMAGE76$ (5)

З (1) і (5) неважко отримати співвідношення між координатами точок ділення

$IMAGE77$

які можуть бути корисні при криптоаналізі. Відзначимо дві властивості точок ділення.

Точки ділення пов'язані як $IMAGE78$ , де $IMAGE19$- точка другого порядку, дорівнює $IMAGE80$. Дійсно,

$IMAGE81$,

тому що $IMAGE82$

Якщо $IMAGE83$ - точка непарного порядку $IMAGE32$, тобто $IMAGE85$, то точка

$IMAGE78$

ає порядок $IMAGE87$, тому що

$IMAGE88$ й $IMAGE89$.

У порівнянні з подвоєнням точки (2), яке вимагає обчислення двох множень й інверсії елемента $IMAGE90$ (найбільш трудомістка обчислювальна операція), ділення (5) не вимагає інверсії елемента й може бути реалізоване набагато швидше.

Найбільш ефективне розв’язання рівняння (3) і операцій (4), (5) виконуються в НБ (нормальному базисі) мінімальної складності, зокрема, в ОНБ (оптимальному нормальному базисі).

Розв’язання квадратного рівняння в НБ здійснюється за допомогою простої $IMAGE91$-бітової рекурентної послідовності. Слід (4) елементів парної ваги дорівнює 0, а непарної ваги - 1.

Піднесення у квадрат (добування кореня квадратного) у нормальному базисі зводиться до циклічного зсуву вправо (вліво) $IMAGE91$-бітового елемента поля.

Поряд з додаванням елементів за модулем 2 перераховані операції часто називають ²безкоштовними² і не враховують у наближених розрахунках обчислювальної складності. Ділення відповідно до (5) вимагає лише двох множень у нормальному базисі $IMAGE93$ як найбільш складних операцій. Це приблизно на порядок збільшує швидкість виконання операцій ділення на два в порівнянні з операцією подвоєння точки.

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

$IMAGE94$,

$IMAGE95$, $IMAGE96$ 

з коефіцієнтом $IMAGE97$, порядок якої $IMAGE98$ 

Максимальний простий порядок $IMAGE32$ досягається при $IMAGE100$. Покладемо, що $IMAGE101$, а генератор $IMAGE102$ має порядок $IMAGE32$. У циклічній групі $IMAGE104$ всі точки є точками подільності на два, відповідно до (4) їх $IMAGE105$-координати мають слід $IMAGE106$ й, отже, непарну вагу при поданні в НБ. При діленні на два отримуємо дві точки, одна з яких належить групі $IMAGE104$ й має порядок $IMAGE32$, а інша максимальний порядок $IMAGE109$ 

Вони мають відповідно непарну й парну вагу $IMAGE105$-координат і легко розрізнюються без множення на $IMAGE111$ Вибір однієї із точок (5) порядку $IMAGE32$ здійснюється досить просто. Оскільки в групі $IMAGE104$ випливає, що

$IMAGE114$

то після множення $IMAGE115$ визначається вага елемента $IMAGE116$ або його слід.

При $IMAGE117$ (парна вага елемента) користуються другою формулою (5), у протилежному випадку - першою формулою (5). Таким чином, ділення на два з вибором точки порядку $IMAGE32$ практично зводиться до двох множень у поле.

Відзначимо, що при послідовному діленні на два для половини всіх кривих (з коефіцієнтом $IMAGE97$ і порядком $IMAGE120$ достатнім виявляється лише одне множення в поле.

Для цього при кожному діленні обчислюється лише розв'язання $IMAGE121$ квадратного рівняння (4) і $IMAGE122$ координата точки ділення. Нехай $IMAGE123$ $IMAGE104$, і при послідовному діленні на два з вибором точки із групи $IMAGE104$ одержуємо

$IMAGE126$.

Згідно з (5) (перша формула) $IMAGE127$, . . . , $IMAGE128$, тому підсумовуючи рівності

$IMAGE129$

отримуємо з урахуванням першого ділення

$IMAGE130$ (6)

де кожне з рішень $IMAGE131$ вибирається так, щоб виконувалася умова $IMAGE132$ тобто в НБ вагу вектора $IMAGE133$ була непарним.

Як видно, рекурентне обчислення за формулою (6) не вимагає обчислення $IMAGE134$ координати на кожному кроці ділення, замість неї слід лише запам'ятати параметри $IMAGE133$ й $IMAGE131$. За необхідності $IMAGE137$– координата обчислюється як $IMAGE138$

Таким чином, відповідно до (6) алгоритм послідовного ділення на дві точки із групи $IMAGE104$ вимагає лише одного множення елементів у поле $IMAGE35$. Це чудова властивість операції ділення на два можна використати з метою збільшення продуктивності обчислень як при криптоаналізі, так і при швидкому експоненціюванні $IMAGE37$ будь-якої точки із групи $IMAGE104$.

Якщо припустити, що для будь-якої точки $IMAGE37$ ми знайшли спосіб визначення парності (непарності) $IMAGE11$, то послідовна процедура віднімання й ділення на два з вибором точки із групи $IMAGE104$ за поліноміальний час приведе нас до відомої точки .

Значення $IMAGE11$ у двійковому поданні визначається самою процедурою віднімання-ділення. Зрозуміло, що така функція вже не однобічна. Це питання поки залишається відкритим і $IMAGE36$ доводиться вирішувати відомими методами з експонентною складністю.

Для кривої $IMAGE57$ з коефіцієнтом $IMAGE150$ оптимальний порядок $IMAGE151$. При діленні на дві точки із групи $IMAGE104$, як й у попередньому випадку, отримуємо дві точки порядку $IMAGE32$ й $IMAGE87$, однак обидві точки ділення парні й мають слід $IMAGE105$- координат $IMAGE156$ (і, відповідно, парна вага в нормальному базисі).

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

Приклад 1. Розглянемо криву Коблиця $IMAGE161$ над полем $IMAGE162$, яка має порядок $IMAGE163$. Всі точки $IMAGE164$ з генератором $IMAGE165$ наведено в таблиці 1

Таблиця 1- Координати точок $IMAGE164$ кривої $IMAGE161$ над полем $IMAGE162$