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

--PAGE_BREAK--Якщо частка парна, ділення триває, у протилежному випадку виконується віднімання 1 і ділення на 2 (отримуємо наступний розряд числа рівний відповідно 0 або 1). Процедура триває до одержання частки, рівної 1. Якщо точка <img width=«19» height=«20» src=«ref-1_1666893390-97.coolpic» v:shapes="_x0000_i1066">– генератор простого порядку <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1067">, то при знанні відповіді на питання про парність (непарність) множника <img width=«15» height=«20» src=«ref-1_1666895111-94.coolpic» v:shapes="_x0000_i1068"> точки <img width=«27» height=«20» src=«ref-1_1666903338-117.coolpic» v:shapes="_x0000_i1069"> <img width=«65» height=«20» src=«ref-1_1666903173-165.coolpic» v:shapes="_x0000_i1070"> легко вирішується ( у поліноміальному часі ) описаною вище послідовною процедурою віднімання-ділення на два. У простому полі <img width=«24» height=«25» src=«ref-1_1666904391-109.coolpic» v:shapes="_x0000_i1071"> ділення на два тотожно множення на елемент <img width=«173» height=«47» src=«ref-1_1666904500-853.coolpic» v:shapes="_x0000_i1072">  Виявляється замість багаторазового додавання ділення точки на два виконується набагато ефективніше й швидше.
Визначимо порядок кривої як
<img width=«193» height=«29» src=«ref-1_1666905353-508.coolpic» v:shapes="_x0000_i1073">
де <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1074"> -велике просте число (в існуючих криптографічних стандартах <img width=«63» height=«25» src=«ref-1_1666905948-245.coolpic» v:shapes="_x0000_i1075">), <img width=«13» height=«16» src=«ref-1_1666902961-85.coolpic» v:shapes="_x0000_i1076"> -непарне число.
Нехай <img width=«17» height=«19» src=«ref-1_1666906278-95.coolpic» v:shapes="_x0000_i1077">-точка порядку <img width=«33» height=«25» src=«ref-1_1666906373-195.coolpic» v:shapes="_x0000_i1078">, тоді генератор криптосистеми може бути визначений як точка <img width=«68» height=«25» src=«ref-1_1666906568-237.coolpic» v:shapes="_x0000_i1079"> порядку <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1080">.

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


<img width=«29» height=«25» src=«ref-1_1666906892-121.coolpic» v:shapes="_x0000_i1081">: <img width=«272» height=«29» src=«ref-1_1666907013-574.coolpic» v:shapes="_x0000_i1082"> (1)
на два як зворотну подвоєнню. Нехай маємо точку <img width=«92» height=«25» src=«ref-1_1666907587-331.coolpic» v:shapes="_x0000_i1083"> та точку <img width=«137» height=«25» src=«ref-1_1666907918-407.coolpic» v:shapes="_x0000_i1084"> з координатами
<img width=«307» height=«87» src=«ref-1_1666908325-1233.coolpic» v:shapes="_x0000_i1085"> (2)
Інакше кажучи, визначення <img width=«61» height=«36» src=«ref-1_1666909558-275.coolpic» v:shapes="_x0000_i1086"> означає знаходження координат точки <img width=«92» height=«25» src=«ref-1_1666907587-331.coolpic» v:shapes="_x0000_i1087"> з відомої точки <img width=«99» height=«25» src=«ref-1_1666910164-338.coolpic» v:shapes="_x0000_i1088"> Відповідно до (2) для цього необхідно вирішувати квадратне рівняння
<img width=«261» height=«44» src=«ref-1_1666910502-602.coolpic» v:shapes="_x0000_i1089"> (3)
У загальному випадку це рівняння має два розв'язки <img width=«19» height=«25» src=«ref-1_1666911104-97.coolpic» v:shapes="_x0000_i1090"> й <img width=«21» height=«25» src=«ref-1_1666911201-100.coolpic» v:shapes="_x0000_i1091"> при наслідку
<img width=«221» height=«25» src=«ref-1_1666911301-521.coolpic» v:shapes="_x0000_i1092"> (4)
Якщо слід <img width=«13» height=«25» src=«ref-1_1666911822-73.coolpic» v:shapes="_x0000_i1093"><img width=«113» height=«25» src=«ref-1_1666911895-366.coolpic» v:shapes="_x0000_i1094"> то точка <img width=«56» height=«20» src=«ref-1_1666912261-141.coolpic» v:shapes="_x0000_i1095"> -непарна точка <img width=«20» height=«24» src=«ref-1_1666912402-175.coolpic» v:shapes="_x0000_i1096">-непарне). Під час виконання (4) отримуємо дві точки: <img width=«92» height=«25» src=«ref-1_1666907587-331.coolpic» v:shapes="_x0000_i1097"> і <img width=«87» height=«29» src=«ref-1_1666912908-347.coolpic» v:shapes="_x0000_i1098"> ділення точки <img width=«17» height=«20» src=«ref-1_1666913255-95.coolpic» v:shapes="_x0000_i1099"> на два з координатами

<img width=«163» height=«135» src=«ref-1_1666913350-1362.coolpic» v:shapes="_x0000_i1100"> (5)
З (1) і (5) неважко отримати співвідношення між координатами точок ділення
<img width=«195» height=«29» src=«ref-1_1666914712-426.coolpic» v:shapes="_x0000_i1101">
які можуть бути корисні при криптоаналізі. Відзначимо дві властивості точок ділення.

Точки ділення пов'язані як <img width=«92» height=«24» src=«ref-1_1666915138-190.coolpic» v:shapes="_x0000_i1102"> , де <img width=«20» height=«19» src=«ref-1_1666897579-98.coolpic» v:shapes="_x0000_i1103">-точка другого порядку, дорівнює <img width=«57» height=«28» src=«ref-1_1666915426-334.coolpic» v:shapes="_x0000_i1104">. Дійсно,
<img width=«147» height=«24» src=«ref-1_1666915760-436.coolpic» v:shapes="_x0000_i1105">,
тому що <img width=«61» height=«20» src=«ref-1_1666916196-262.coolpic» v:shapes="_x0000_i1106">

Якщо <img width=«17» height=«19» src=«ref-1_1666916458-96.coolpic» v:shapes="_x0000_i1107"> -точка непарного порядку <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1108">, тобто <img width=«53» height=«20» src=«ref-1_1666916641-227.coolpic» v:shapes="_x0000_i1109">, то точка
<img width=«92» height=«24» src=«ref-1_1666915138-190.coolpic» v:shapes="_x0000_i1110">
ає порядок <img width=«24» height=«20» src=«ref-1_1666917058-181.coolpic» v:shapes="_x0000_i1111">, тому що
<img width=«199» height=«29» src=«ref-1_1666917239-463.coolpic» v:shapes="_x0000_i1112"> й <img width=«72» height=«25» src=«ref-1_1666917702-291.coolpic» v:shapes="_x0000_i1113">.


У порівнянні з подвоєнням точки (2), яке вимагає обчислення двох множень й інверсії елемента <img width=«29» height=«29» src=«ref-1_1666917993-123.coolpic» v:shapes="_x0000_i1114"> (найбільш трудомістка обчислювальна операція), ділення (5) не вимагає інверсії елемента й може бути реалізоване набагато швидше.

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

Розв’язання квадратного рівняння в НБ здійснюється за допомогою простої <img width=«19» height=«16» src=«ref-1_1666918116-94.coolpic» v:shapes="_x0000_i1115">-бітової рекурентної послідовності. Слід (4) елементів парної ваги дорівнює 0, а непарної ваги -1.

Піднесення у квадрат (добування кореня квадратного) у нормальному базисі зводиться до циклічного зсуву вправо (вліво) <img width=«19» height=«16» src=«ref-1_1666918116-94.coolpic» v:shapes="_x0000_i1116">-бітового елемента поля.

Поряд з додаванням елементів за модулем 2 перераховані операції часто називають ²безкоштовними²і не враховують у наближених розрахунках обчислювальної складності. Ділення відповідно до (5) вимагає лише двох множень у нормальному базисі <img width=«75» height=«25» src=«ref-1_1666918304-307.coolpic» v:shapes="_x0000_i1117"> як найбільш складних операцій. Це приблизно на порядок збільшує швидкість виконання операцій ділення на два в порівнянні з операцією подвоєння точки.

Розглянемо можливі підходи до розв’язання задач дискретного логарифма. Найбільш проста ситуація виникає для кривої
<img width=«201» height=«29» src=«ref-1_1666918611-366.coolpic» v:shapes="_x0000_i1118">,

<img width=«61» height=«23» src=«ref-1_1666918977-239.coolpic» v:shapes="_x0000_i1119">, <img width=«41» height=«20» src=«ref-1_1666919216-222.coolpic» v:shapes="_x0000_i1120"> 
з коефіцієнтом <img width=«40» height=«20» src=«ref-1_1666919438-148.coolpic» v:shapes="_x0000_i1121">, порядок якої <img width=«81» height=«25» src=«ref-1_1666919586-274.coolpic» v:shapes="_x0000_i1122"> 

Максимальний простий порядок <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1123"> досягається при <img width=«37» height=«20» src=«ref-1_1666919947-143.coolpic» v:shapes="_x0000_i1124">. Покладемо, що <img width=«71» height=«25» src=«ref-1_1666920090-256.coolpic» v:shapes="_x0000_i1125">, а генератор <img width=«60» height=«20» src=«ref-1_1666920346-221.coolpic» v:shapes="_x0000_i1126"> має порядок <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1127">. У циклічній групі <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1128"> всі точки є точками подільності на два, відповідно до (4) їх <img width=«15» height=«16» src=«ref-1_1666920867-88.coolpic» v:shapes="_x0000_i1129">-координати мають слід <img width=«71» height=«24» src=«ref-1_1666920955-301.coolpic» v:shapes="_x0000_i1130"> й, отже, непарну вагу при поданні в НБ. При діленні на два отримуємо дві точки, одна з яких належить групі <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1131"> й має порядок <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1132">, а інша максимальний порядок <img width=«27» height=«20» src=«ref-1_1666921556-186.coolpic» v:shapes="_x0000_i1133"> 

Вони мають відповідно непарну й парну вагу <img width=«15» height=«16» src=«ref-1_1666920867-88.coolpic» v:shapes="_x0000_i1134">-координат і легко розрізнюються без множення на <img width=«17» height=«16» src=«ref-1_1666921830-100.coolpic» v:shapes="_x0000_i1135"> Вибір однієї із точок (5) порядку <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1136"> здійснюється досить просто. Оскільки в групі <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1137"> випливає, що
<img width=«147» height=«25» src=«ref-1_1666922230-451.coolpic» v:shapes="_x0000_i1138">
то після множення <img width=«36» height=«25» src=«ref-1_1666922681-123.coolpic» v:shapes="_x0000_i1139"> визначається вага елемента <img width=«75» height=«25» src=«ref-1_1666922804-171.coolpic» v:shapes="_x0000_i1140"> або його слід.

При <img width=«136» height=«25» src=«ref-1_1666922975-427.coolpic» v:shapes="_x0000_i1141"> (парна вага елемента) користуються другою формулою (5), у протилежному випадку -першою формулою (5). Таким чином, ділення на два з вибором точки порядку <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1142"> практично зводиться до двох множень у поле.

Відзначимо, що при послідовному діленні на два для половини всіх кривих (з коефіцієнтом <img width=«40» height=«20» src=«ref-1_1666919438-148.coolpic» v:shapes="_x0000_i1143"> і порядком <img width=«85» height=«25» src=«ref-1_1666923637-310.coolpic» v:shapes="_x0000_i1144"> достатнім виявляється лише одне множення в поле.

Для цього при кожному діленні обчислюється лише розв'язання <img width=«17» height=«25» src=«ref-1_1666923947-96.coolpic» v:shapes="_x0000_i1145"> квадратного рівняння (4) і <img width=«19» height=«25» src=«ref-1_1666924043-97.coolpic» v:shapes="_x0000_i1146"> координата точки ділення. Нехай <img width=«91» height=«24» src=«ref-1_1666924140-363.coolpic» v:shapes="_x0000_i1147"><img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1148">, і при послідовному діленні на два з вибором точки із групи <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1149"> одержуємо
<img width=«459» height=«44» src=«ref-1_1666924929-1257.coolpic» v:shapes="_x0000_i1150">.


Згідно з (5) (перша формула) <img width=«237» height=«25» src=«ref-1_1666926186-580.coolpic» v:shapes="_x0000_i1151">,..., <img width=«112» height=«25» src=«ref-1_1666926766-344.coolpic» v:shapes="_x0000_i1152">, тому підсумовуючи рівності
<img width=«203» height=«57» src=«ref-1_1666927110-804.coolpic» v:shapes="_x0000_i1153">
отримуємо з урахуванням першого ділення
<img width=«343» height=«63» src=«ref-1_1666927914-1157.coolpic» v:shapes="_x0000_i1154"> (6)
де кожне з рішень <img width=«21» height=«25» src=«ref-1_1666929071-103.coolpic» v:shapes="_x0000_i1155"> вибирається так, щоб виконувалася умова <img width=«85» height=«25» src=«ref-1_1666929174-331.coolpic» v:shapes="_x0000_i1156"> тобто в НБ вагу вектора <img width=«23» height=«25» src=«ref-1_1666929505-105.coolpic» v:shapes="_x0000_i1157"> була непарним.

Як видно, рекурентне обчислення за формулою (6) не вимагає обчислення <img width=«16» height=«20» src=«ref-1_1666929610-92.coolpic» v:shapes="_x0000_i1158"> координати на кожному кроці ділення, замість неї слід лише запам'ятати параметри <img width=«23» height=«25» src=«ref-1_1666929505-105.coolpic» v:shapes="_x0000_i1159"> й <img width=«21» height=«25» src=«ref-1_1666929071-103.coolpic» v:shapes="_x0000_i1160">. За необхідності <img width=«24» height=«25» src=«ref-1_1666929910-108.coolpic» v:shapes="_x0000_i1161">– координата обчислюється як <img width=«140» height=«25» src=«ref-1_1666930018-386.coolpic» v:shapes="_x0000_i1162">

Таким чином, відповідно до (6) алгоритм послідовного ділення на дві точки із групи <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1163"> вимагає лише одного множення елементів у поле <img width=«31» height=«29» src=«ref-1_1666903046-127.coolpic» v:shapes="_x0000_i1164">. Це чудова властивість операції ділення на два можна використати з метою збільшення продуктивності обчислень як при криптоаналізі, так і при швидкому експоненціюванні <img width=«27» height=«20» src=«ref-1_1666903338-117.coolpic» v:shapes="_x0000_i1165"> будь-якої точки із групи <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1166">.

Якщо припустити, що для будь-якої точки <img width=«27» height=«20» src=«ref-1_1666903338-117.coolpic» v:shapes="_x0000_i1167"> ми знайшли спосіб визначення парності (непарності) <img width=«15» height=«20» src=«ref-1_1666895111-94.coolpic» v:shapes="_x0000_i1168">, то послідовна процедура віднімання й ділення на два з вибором точки із групи <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1169"> за поліноміальний час приведе нас до відомої точки <img width=«19» height=«20» src=«ref-1_1666893390-97.coolpic» v:shapes="_x0000_i1170">.

Значення <img width=«15» height=«20» src=«ref-1_1666895111-94.coolpic» v:shapes="_x0000_i1171"> у двійковому поданні визначається самою процедурою віднімання-ділення. Зрозуміло, що така функція вже не однобічна. Це питання поки залишається відкритим і <img width=«65» height=«20» src=«ref-1_1666903173-165.coolpic» v:shapes="_x0000_i1172"> доводиться вирішувати відомими методами з експонентною складністю.

Для кривої <img width=«29» height=«25» src=«ref-1_1666906892-121.coolpic» v:shapes="_x0000_i1173"> з коефіцієнтом <img width=«43» height=«20» src=«ref-1_1666931975-206.coolpic» v:shapes="_x0000_i1174"> оптимальний порядок <img width=«71» height=«25» src=«ref-1_1666932181-240.coolpic» v:shapes="_x0000_i1175">. При діленні на дві точки із групи <img width=«48» height=«20» src=«ref-1_1666920654-213.coolpic» v:shapes="_x0000_i1176">, як й у попередньому випадку, отримуємо дві точки порядку <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1177"> й <img width=«24» height=«20» src=«ref-1_1666917058-181.coolpic» v:shapes="_x0000_i1178">, однак обидві точки ділення парні й мають слід <img width=«15» height=«16» src=«ref-1_1666920867-88.coolpic» v:shapes="_x0000_i1179">- координат <img width=«73» height=«24» src=«ref-1_1666932990-332.coolpic» v:shapes="_x0000_i1180"> (і, відповідно, парна вага в нормальному базисі).

Визначити, яка з них має порядок <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1181">, можна шляхом множення кожної з них на <img width=«15» height=«16» src=«ref-1_1666902705-87.coolpic» v:shapes="_x0000_i1182">, але це вимагає більших обчислювальних витрат. Більш раціональне дворазове ділення на два, яке в одній з галузей дасть дві точки порядку <img width=«24» height=«20» src=«ref-1_1666933496-166.coolpic» v:shapes="_x0000_i1183">, вони не діляться на два й мають координати непарної ваги. Ця галузь відбраковується й залишається точка із групи <img width=«55» height=«20» src=«ref-1_1666933662-220.coolpic» v:shapes="_x0000_i1184">

Приклад 1. Розглянемо криву Коблиця <img width=«119» height=«29» src=«ref-1_1666933882-268.coolpic» v:shapes="_x0000_i1185"> над полем <img width=«25» height=«29» src=«ref-1_1666934150-121.coolpic» v:shapes="_x0000_i1186">, яка має порядок <img width=«67» height=«25» src=«ref-1_1666934271-249.coolpic» v:shapes="_x0000_i1187">. Всі точки <img width=«25» height=«20» src=«ref-1_1666934520-112.coolpic» v:shapes="_x0000_i1188"> з генератором <img width=«96» height=«29» src=«ref-1_1666934632-338.coolpic» v:shapes="_x0000_i1189"> наведено в таблиці 1
Таблиця 1-Координати точок <img width=«25» height=«20» src=«ref-1_1666934520-112.coolpic» v:shapes="_x0000_i1190"> кривої <img width=«119» height=«29» src=«ref-1_1666933882-268.coolpic» v:shapes="_x0000_i1191"> над полем <img width=«25» height=«29» src=«ref-1_1666934150-121.coolpic» v:shapes="_x0000_i1192">
    продолжение
--PAGE_BREAK--