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

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

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 координат).