Методи вирішенняпроблем дискретного логарифмування
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
/> 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
/>
23P
24P
25P
26P
27P
28P
29P
30P
31P
32P
33P
/> 26 2 18 15 11 1 21 27 22 8
/> 13 30 20 19 21 15 23 14 11 27
/>
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 — Елементи поля /> як степені елемента /> в ОНБ 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 координат).