Методи вирішення проблем дискретного логарифмування
Методи вирішення
проблем дискретного логарифмування
1. Метод Поліга-Хелмана
Метод Поліга-Хелмана запропонований в 1978 році для визначення
дискретного логарифма в мультиплікативній групі поля .
Він заснований на відомій для
групи факторизації порядку групи
за ступенями простих чисел
Стосовно до адитивної групи точок
з генератором порядку маємо Відповідно до відомої китайської теореми про
залишки існує єдине натуральне число , таке що
Після визначення значення дискретний логарифм здобувають за допомогою
розширеного алгоритму Евкліда. Наведемо приклад.
Приклад 1
Нехай порядок циклічної групи дорівнює , а точка , тобто . Це значення має бути визначене в підсумку рішення
ECDLP.
Тут На першому етапі визначаємо точку Отримуємо точку другого порядку з відомими координатами Оскільки , маємо перше порівняння
На наступному етапі знаходимо одну
із точок третього порядку Ці
точки також відомі, тому з отримуємо
наступне порівняння
Нарешті, визначаємо точку 5-го
порядку й отримуємо
.
Наведені три порівняння дають
єдине розв’язання В загальному
випадку необхідно знати координати точок із загальної кількості .
Задача ускладнюється із зростанням переважно простого
співмножника в розкладанні порядку групи. У цьому зв'язку для захисту від атаки
Поліга-Хелмана порядок криптосистеми
обирають рівним великому простому числу, при цьому порядок кривої називають ² майже
простим ² (з малим множником ).
2. Метод ділення точок на два
Метод ділення точок на два. Для кривих над полем запропонований метод розв’язання
, заснований на процедурі,
зворотної обчисленню точки шляхом
послідовних подвоєнь і додавань при двійковому поданні числа .
У звичайній
арифметиці двійкове подання цілого числа починається з визначення молодшого
біта: при непарних з віднімається 1 (це молодший біт
двійкового подання ) і
результат ділиться на 2.
Якщо частка парна,
ділення триває, у протилежному випадку виконується віднімання 1 і ділення на 2
(отримуємо наступний розряд числа рівний відповідно 0 або 1). Процедура триває
до одержання частки, рівної 1. Якщо точка – генератор простого порядку , то при знанні відповіді на питання про
парність (непарність) множника точки легко
вирішується ( у поліноміальному часі ) описаною вище послідовною процедурою
віднімання-ділення на два.
У простому полі ділення на два тотожно множення
на елемент
Виявляється
замість багаторазового додавання ділення точки на два виконується набагато
ефективніше й швидше.
Визначимо порядок кривої як
де - велике
просте число (в існуючих криптографічних стандартах ), - непарне число.
Нехай - точка
порядку , тоді генератор криптосистеми
може бути визначений як точка порядку
.
Введемо операцію ділення точки
несуперсингулярної кривої
: (1)
на два як зворотну подвоєнню.
Нехай маємо точку та точку з координатами
(2)
Інакше кажучи, визначення означає знаходження координат точки
з відомої точки Відповідно до (2) для цього необхідно
вирішувати квадратне рівняння
(3)
У загальному випадку це рівняння
має два розв'язки й
при наслідку
(4)
Якщо слід то
точка - непарна точка - непарне).
Під час виконання (4) отримуємо дві точки: і ділення
точки на два з координатами
(5)
З (1) і (5) неважко отримати
співвідношення між координатами точок ділення
які можуть бути корисні при
криптоаналізі. Відзначимо дві властивості точок ділення.
Точки ділення пов'язані як , де - точка
другого порядку, дорівнює .
Дійсно,
,
тому що
Якщо - точка
непарного порядку , тобто , то точка
ає порядок , тому що
й .
У порівнянні з подвоєнням точки
(2), яке вимагає обчислення двох множень й інверсії елемента (найбільш трудомістка обчислювальна операція),
ділення (5) не вимагає інверсії елемента й може бути реалізоване набагато
швидше.
Найбільш ефективне розв’язання
рівняння (3) і операцій (4), (5) виконуються в НБ (нормальному базисі)
мінімальної складності, зокрема, в ОНБ (оптимальному нормальному базисі).
Розв’язання квадратного рівняння в
НБ здійснюється за допомогою простої -бітової рекурентної послідовності. Слід (4)
елементів парної ваги дорівнює 0, а непарної ваги - 1.
Піднесення у квадрат (добування
кореня квадратного) у нормальному базисі зводиться до циклічного зсуву вправо
(вліво) -бітового елемента
поля.
Поряд з додаванням елементів за
модулем 2 перераховані операції часто називають ²безкоштовними² і
не враховують у наближених розрахунках обчислювальної складності. Ділення
відповідно до (5) вимагає лише двох множень у нормальному базисі як найбільш складних операцій. Це
приблизно на порядок збільшує швидкість виконання операцій ділення на два в
порівнянні з операцією подвоєння точки.
Розглянемо можливі підходи до
розв’язання задач дискретного логарифма. Найбільш проста ситуація виникає для
кривої
,
,
з коефіцієнтом , порядок якої
Максимальний простий порядок досягається при . Покладемо, що , а генератор має порядок . У циклічній групі всі точки є точками подільності на два, відповідно
до (4) їх -координати мають
слід й, отже, непарну вагу
при поданні в НБ. При діленні на два отримуємо дві точки, одна з яких належить
групі й має порядок , а інша максимальний порядок
Вони мають відповідно непарну й
парну вагу -координат і
легко розрізнюються без множення на Вибір однієї із точок (5) порядку здійснюється досить просто. Оскільки в
групі випливає, що
то після множення визначається вага елемента або його слід.
При (парна вага елемента) користуються другою формулою
(5), у протилежному випадку - першою
формулою (5). Таким чином, ділення на два з вибором точки порядку практично зводиться до двох
множень у поле.
Відзначимо, що при послідовному
діленні на два для половини всіх кривих (з коефіцієнтом і порядком достатнім виявляється лише одне множення в поле.
Для цього при кожному діленні
обчислюється лише розв'язання квадратного рівняння (4) і координата точки ділення. Нехай , і при послідовному діленні на два з вибором точки
із групи одержуємо
.
Згідно з (5) (перша формула) , . . . , , тому підсумовуючи рівності
отримуємо з урахуванням першого
ділення
(6)
де кожне з рішень вибирається так, щоб виконувалася умова тобто в НБ вагу вектора була непарним.
Як видно, рекурентне обчислення за
формулою (6) не вимагає обчислення координати на кожному кроці ділення, замість неї
слід лише запам'ятати параметри й .
За необхідності – координата
обчислюється як
Таким чином, відповідно до (6)
алгоритм послідовного ділення на дві точки із групи вимагає лише одного множення елементів у поле . Це чудова властивість операції
ділення на два можна використати з метою збільшення продуктивності обчислень як
при криптоаналізі, так і при швидкому експоненціюванні будь-якої точки із групи .
Якщо припустити, що для будь-якої
точки ми знайшли спосіб
визначення парності (непарності) , то послідовна процедура віднімання й ділення на
два з вибором точки із групи за
поліноміальний час приведе нас до відомої точки .
Значення у двійковому поданні визначається самою процедурою
віднімання-ділення. Зрозуміло, що така функція вже не однобічна. Це питання
поки залишається відкритим і доводиться
вирішувати відомими методами з експонентною складністю.
Для кривої з коефіцієнтом оптимальний порядок . При діленні на дві точки із групи , як й у попередньому випадку, отримуємо
дві точки порядку й , однак обидві точки ділення
парні й мають слід -
координат (і, відповідно,
парна вага в нормальному базисі).
Визначити, яка з них має порядок , можна шляхом множення кожної з
них на , але це вимагає
більших обчислювальних витрат. Більш раціональне дворазове ділення на два, яке
в одній з галузей дасть дві точки порядку , вони не діляться на два й мають координати
непарної ваги. Ця галузь відбраковується й залишається точка із групи
Приклад 1. Розглянемо криву Коблиця над полем , яка має порядок . Всі точки з генератором наведено в таблиці 1
Таблиця 1- Координати точок кривої над полем
|
|
|
|
|
|
|
|
|
|
|
|
|
5
|
29
|
13
|
16
|
20
|
30
|
10
|
4
|
9
|
23
|
0
|
|
9
|
7
|
22
|
7
|
5
|
19
|
30
|
29
|
10
|
28
|
_
|
|
12P
|
13P
|
14P
|
15P
|
16P
|
17p
|
18P
|
19P
|
20P
|
21P
|
22P
|
|
8
|
22
|
27
|
21
|
1
|
11
|
15
|
18
|
2
|
26
|
_
|
|
19
|
30
|
28
|
26
|
14
|
15
|
25
|
23
|
28
|
27
|
0
|
|
23P
|
24P
|
25P
|
26P
|
27P
|
28P
|
29P
|
30P
|
31P
|
32P
|
33P
|
|
26
|
2
|
18
|
15
|
11
|
1
|
21
|
27
|
22
|
8
|
0
|
|
13
|
30
|
20
|
19
|
21
|
15
|
23
|
14
|
11
|
27
|
0
|
|
34P
|
35P
|
36P
|
37P
|
38P
|
39P
|
40P
|
41P
|
42P
|
43P
|
44P
|
|
23
|
9
|
4
|
10
|
30
|
20
|
16
|
13
|
29
|
5
|
*
|
|
25
|
27
|
25
|
18
|
7
|
29
|
23
|
29
|
14
|
15
|
*
|
Приймемо
.
При діленні
точки на два отримаємо дві точки
й .
Розглянемо
всі операції при діленні точки
відповідно до (3), (5) (друга з формул) в ОНБ із ізоморфізмом, тобто
, .
У нормальному базисі маємо . Розв’язуємо рівняння (3)
.
Відповідно до таблиці 2 , тоді одне з розв’язань для легко отримати, задаючи перший
біт, скажімо, рівним 0.
Таблиця 2 - Елементи поля як степені елемента в ОНБ
0
|
00000
|
1
|
11111
|
-
|
-
|
|
10000
|
|
00011
|
|
01101
|
|
01000
|
|
10001
|
|
10110
|
|
00100
|
|
11000
|
|
01011
|
|
00010
|
|
01100
|
|
10101
|
|
00001
|
|
00110
|
|
11010
|
|
10010
|
|
10111
|
|
10011
|
|
01001
|
|
11011
|
|
11001
|
|
10100
|
|
11101
|
|
11100
|
|
01010
|
|
11110
|
|
01110
|
|
00101
|
|
01111
|
|
00111
|
При цьому інші біти визначаються
із суми
, тобто
.
Друге розв’язання, мабуть,
дорівнює . Легко перевірити,
що отримані розв’язання задовольняють рівняння
.
Згідно з (5) (перша з формул) і
даних таблиці 2 маємо
Отримано дві точки:
і .
Для визначення кожної необхідно
виконати по два множення елементів поля. Неважко перевірити виконання умови
дискретне
логарифмування метод
, ,
зокрема,
.
Обидві точки мають сліди
,
і, отже, діляться на два, але
мають різні порядки. Точка має
порядок 22, а точка - порядок Для визначення порядку достатньо виконати ще
одне ділення на два. Якщо поділити точку, то отримаємо дві точки порядку 44, що не діляться
на два (з непарною вагою x координат). При діленні точки отримаємо дві точки з порядками 22 й 11
(з парною вагою x координат).
/