Методи Вирішення проблем дискретного логаріфмування
1. Метод Поліга-Хелмана
Метод Поліга-Хелмана запропонованій в 1978 году для визначення дискретного логарифма в мультіплікатівній групі поля. p> ВІН Заснований на відомій для групи факторізації порядку групи за ступенями простих чисел
В
Стосовно до адітівної групи точок з генератором порядку маємо Відповідно до відомої китайської теореми про Залишки існує єдине натуральне число, таке что
В
После визначення Значення Дискретний логарифм здобувають помощью розширеного алгоритму Евкліда. Наведемо приклад. p> Приклад 1
Нехай порядок ціклічної групи дорівнює, а точка, тоб. Це Значення має буті визначене в підсумку решение ECDLP. p> Тут На первом етапі візначаємо точку Отрімуємо точку другого порядку з відомімі координатами Оскількі, маємо перше порівняння
В
На Наступний етапі знаходимо одну Із точок третього порядку Ці точки такоже відомі, тому з отрімуємо Наступний порівняння
В
Нарешті, візначаємо точку 5-го порядком ї отрімуємо
.
Наведені три порівняння дають єдине розв'язання В загально випадка звітність, знаті координат та точок Із Загальної кількості. p> Завдання ускладнюється Із ЗРОСТАННЯ Переважно простого співмножніка в розкладанні порядку групи. У цьом зв'язку для захисту від атаки Поліга-Хелмана порядок криптосистеми обірають рівнім великому простому числу, при цьом порядок крівої назівають ВІ почти пробачимо ВІ (з малим множніком).
2. Метод ділення точок на два
Метод ділення точок на два. Для кривих над полем запропонованій метод розв'язання , Заснований на процедурі, зворотної обчисления точки Шляхом послідовніх подвоєнь и додавань при двійковому поданні числа. h1> У звічайній аріфметіці двійкове Подання цілого числа ПОЧИНАЄТЬСЯ з визначення молодшого біта: при непарних з віднімається 1 (це молодший біт двійкового Подання) i результат діліться на 2.
Если Частка парна, ділення Триває, у протилежних випадка віконується віднімання 1 і ділення на 2 (Отрімуємо Наступний розряд числа Рівний відповідно 0 або 1). Процедура Триває до одержании Частки, рівної 1. Если точка - генератор простого порядку, то при знанні ВІДПОВІДІ на питання про парність (непарність) множніка точки легко вірішується (у поліноміальному часі) описом Вище послідовною процедурою віднімання-ділення на два.
У простому полі ділення на два тотожня множення на елемент
В В В
Віявляється вместо багаторазове додавання ділення точки на два віконується набагато ефектівніше ї швідше.
Візначімо порядок крівої як
В
де - ровері Прості числа (в існуючіх кріптографічніх стандартах), - непарний число.
Нехай - точка порядком, тоді генератор криптосистеми может буті визначеня як точка порядком . p> Введемо операцію ділення точки несуперсінгулярної крівої
: (1)
на два як зворотнього подвоєнню. Нехай маємо точку та точку з координатами
(2)
Інакше Кажучи, визначення означає знаходження координат точки з відомої точки Відповідно до (2) для цього звітність, вірішуваті квадратно рівняння
(3)
У загально випадка це рівняння має два розв'язки ї при наслідку
(4)
Если слід то точка - непарний точка - непарний). Во время Виконання (4) отрімуємо Дві точки: і ділення точки на два з координатами
(5)
З (1) і (5) неважко отріматі співвідношення между координатами точок ділення
В
Які могут буті Корисні при кріптоаналізі. Відзначімо Дві Властивості точок ділення. p> Точки ділення пов'язані як, де - точка іншого порядку, дорівнює. Дійсно,
,
того что
Если - точка непарного порядку, тоб, то крапка
В
АЄ порядок, ТОМУ ЩО
й.
У порівнянні з подвоєнням точки (2), Яке вімагає обчислення двох множення й інверсії елемента (найбільш трудомістка Обчислювальна Операція), ділення (5) більше не вімагає інверсії елемента ї может буті реалізоване набагато швідше. p> Найбільш Ефективне розв'язання рівняння (3) i операцій (4), (5) віконуються в НБ (нормальному базісі) мінімальної складності, зокрема, в ОНБ (оптимальному нормальному базісі). p> Розв'язання квадратного рівняння в НБ здійснюється за помощью простої-бітової рекурентної послідовності. Слід (4) ЕЛЕМЕНТІВ парної ваги дорівнює 0, а непарної ваги - 1.
Піднесення у квадрат (добування кореня квадратного) у нормальному базісі зводіться до ціклічного Зсув вправо (Вліво)-бітового елемента поля. p> Поряд з додаванням ЕЛЕМЕНТІВ за модулем 2 перераховані Операції часто назівають ВІ безкоштовна ВІ и НЕ враховують у набліженіх розрахунках обчіслювальної складності. Ділення відповідно до (5) вімагає позбав двох множення у н...
