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

--PAGE_BREAK--Таблиця 2 -Складність і час обчислення рішення ECDLP за допомогою <img width=«17» height=«19» src=«ref-1_1671844704-179.coolpic» v:shapes="_x0000_i1113">-методу Полларда залежно від порядку <img width=«15» height=«16» src=«ref-1_1671838680-87.coolpic» v:shapes="_x0000_i1114"> криптосистеми
Розмір поля, Біт

Порядок <img width=«15» height=«16» src=«ref-1_1671838680-87.coolpic» v:shapes="_x0000_i1115"> криптосистеми,Біт

Складність

<img width=«55» height=«28» src=«ref-1_1671847397-289.coolpic» v:shapes="_x0000_i1116">

Час обчислень

<img width=«49» height=«20» src=«ref-1_1671847686-151.coolpic» v:shapes="_x0000_i1117">-роки

163

160

<img width=«29» height=«24» src=«ref-1_1671847837-195.coolpic» v:shapes="_x0000_i1118">

<img width=«68» height=«28» src=«ref-1_1671848032-355.coolpic» v:shapes="_x0000_i1119">

191

186

<img width=«28» height=«24» src=«ref-1_1671848387-191.coolpic» v:shapes="_x0000_i1120">

<img width=«69» height=«28» src=«ref-1_1671848578-343.coolpic» v:shapes="_x0000_i1121">

239

234

<img width=«35» height=«24» src=«ref-1_1671848921-201.coolpic» v:shapes="_x0000_i1122">

<img width=«67» height=«28» src=«ref-1_1671849122-327.coolpic» v:shapes="_x0000_i1123">

359

354

<img width=«35» height=«24» src=«ref-1_1671849449-200.coolpic» v:shapes="_x0000_i1124">

<img width=«68» height=«25» src=«ref-1_1671849649-301.coolpic» v:shapes="_x0000_i1125">

431

426

<img width=«36» height=«24» src=«ref-1_1671849950-204.coolpic» v:shapes="_x0000_i1126">

<img width=«67» height=«28» src=«ref-1_1671850154-321.coolpic» v:shapes="_x0000_i1127">



<img width=«31» height=«20» src=«ref-1_1671846834-116.coolpic» v:shapes="_x0000_i1128"> історично була визначена як адитивна група, але з тим же успіхом можна було б визначити як мультиплікативну, назвавши групову операцію множенням точок.

Операція експоненціювання <img width=«80» height=«29» src=«ref-1_1671850591-320.coolpic» v:shapes="_x0000_i1129"> у мультиплікативній групі найбільш ефективно здійснюється методом послідовного піднесення до квадрата. Для цього число <img width=«15» height=«20» src=«ref-1_1671799126-94.coolpic» v:shapes="_x0000_i1130"> подається у двійковій системі числення
<img width=«348» height=«29» src=«ref-1_1671851005-851.coolpic» v:shapes="_x0000_i1131">
як <img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1132">-розрядне двійкове число <img width=«151» height=«25» src=«ref-1_1671851950-299.coolpic» v:shapes="_x0000_i1133">. Наприклад, мінімальним 5-розрядним числом (з 1 у старшому розряді) є двійкове число <img width=«79» height=«20» src=«ref-1_1671852249-335.coolpic» v:shapes="_x0000_i1134"> (рівне 16 у десятковій системі), а максимальним – число 11111 (рівне 31 у десятковій системі). Тоді експоненціювання елемента <img width=«16» height=«20» src=«ref-1_1671846003-96.coolpic» v:shapes="_x0000_i1135"> зводиться до послідовного піднесення до квадрата і множення на <img width=«16» height=«20» src=«ref-1_1671846003-96.coolpic» v:shapes="_x0000_i1136"> (останнє за наявності 1 у двійковому записі від старшого розряду до молодшого):
<img width=«260» height=«63» src=«ref-1_1671852776-1269.coolpic» v:shapes="_x0000_i1137">
У першому випадку виконується 4 операції множення, у другому 8-множень. У загальному випадку експоненціювання у двійкову <img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1138">-розрядний степінь цим методом здійснюється за допомогою від <img width=«56» height=«24» src=«ref-1_1671854139-270.coolpic» v:shapes="_x0000_i1139"> до <img width=«65» height=«24» src=«ref-1_1671854409-317.coolpic» v:shapes="_x0000_i1140"> операцій множення за модулем <img width=«17» height=«20» src=«ref-1_1671854726-95.coolpic» v:shapes="_x0000_i1141">. Об'єм обчислень пропорційний розрядності числа <img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1142">. Така обчислювальна складність називається поліноміальною <img width=«65» height=«24» src=«ref-1_1671854915-329.coolpic» v:shapes="_x0000_i1143"> а -
коефіцієнт пропорційності).

Зворотна функція дискретного логарифмування <img width=«91» height=«29» src=«ref-1_1671855244-403.coolpic» v:shapes="_x0000_i1144"> у найгіршому разі може зажадати перебору до <img width=«24» height=«29» src=«ref-1_1671855647-116.coolpic» v:shapes="_x0000_i1145"> значень, при цьому говорять про експонентну складність обчислень <img width=«56» height=«28» src=«ref-1_1671855763-163.coolpic» v:shapes="_x0000_i1146">

Взагалі кажучи, поняття обчислювальної складності визначається через співвідношення вхідного й вихідного об'ємів даних деякого обчислювального алгоритму. Алгоритми поліноміального часу (швидкі алгоритми) характеризуються лінійним співвідношенням об'ємів даних на виході й вході процесора, а алгоритми експонентного часу (повільні), відповідно, експонентним. Зі збільшенням об'єму вхідних даних експонентна складність веде до практично нереалізованих обчислювальних витрат.

Сьогодні відомі досить ефективні субекспоненційні методи рішення DLP над скінченними полями. Це пов'язано з тим, що елемент поля <img width=«24» height=«28» src=«ref-1_1671855926-115.coolpic» v:shapes="_x0000_i1147"> -ціле число, яке можна факторизувати у вигляді добутку ступенів простих чисел. Це затребувано з метою безпеки істотно збільшити розміри поля для криптосистем Діффі-Хеллмана й Ель-Гамала (до тисяч біт). З іншого боку, точку еліптичної кривої <img width=«24» height=«19» src=«ref-1_1671856041-109.coolpic» v:shapes="_x0000_i1148"> факторизувати на зразок цілого числа не вдається. Тому для ЕСС поки не відомі методи розв’язання <img width=«65» height=«20» src=«ref-1_1671842257-163.coolpic» v:shapes="_x0000_i1149">, більш ефективні, ніж класичні методи з експонентною складністю обчислень. Цим і пояснюється високий рівень безпеки криптосистем на еліптичних кривих.

Криптоатаки на <img width=«43» height=«20» src=«ref-1_1671841987-135.coolpic» v:shapes="_x0000_i1150"> прийнято розділяти на дві групи: атаки на загальну структуру й атаки ізоморфізму. До першого звичайно відносять:

– метод Шенкса( Shenks Method- Giant Step-Baby step);

– <img width=«31» height=«21» src=«ref-1_1671856448-117.coolpic» v:shapes="_x0000_i1151"> методи Полларда (Pollard¢s Method);

– метод Поліга- Хеллмана (Pohlig-Hellman Method);

– метод обчислення степенів (Index Calculus Method).

Ці методи застосовні для будь-якої скінченної групи, у тому числі й для еліптичної кривої (крім останнього). Атаки ізоморфізму специфічні для ECC. Серед них найбільш відомі:

– атака Менезиса, Окамото й Ванстоуна, або MOV- атака;

– ізоморфізм Семаєва;

– метод спуску Вейля й ін.

Атаки ізоморфізму базуються на перетвореннях, що переводять абелеву групу точок <img width=«31» height=«20» src=«ref-1_1671846834-116.coolpic» v:shapes="_x0000_i1152"> в елементи мультиплікативної групи поля. Оскільки, рішення <img width=«41» height=«19» src=«ref-1_1671845480-128.coolpic» v:shapes="_x0000_i1153"> у поле набагато простіше, ніж на еліптичній кривій (при порівнянних порядках), то знаходження ізоморфізму між двома групами істотно знижує безпека ЕСС. Поки відомі кілька класів криптографічно слабких кривих, для яких ці атаки успішні.


2. Метод Шенкса

Прямий метод розрахунку дискретного логарифма може використати два варіанти:<img width=«15» height=«20» src=«ref-1_1671799126-94.coolpic» v:shapes="_x0000_i1154">- кратне додавання точки <img width=«19» height=«20» src=«ref-1_1671856903-97.coolpic» v:shapes="_x0000_i1155"> до збігу із точкою <img width=«39» height=«20» src=«ref-1_1671857000-132.coolpic» v:shapes="_x0000_i1156"> (шлях від точки <img width=«19» height=«20» src=«ref-1_1671857132-97.coolpic» v:shapes="_x0000_i1157"> до точки <img width=«27» height=«20» src=«ref-1_1671857229-116.coolpic» v:shapes="_x0000_i1158">) або шлях від точки <img width=«27» height=«20» src=«ref-1_1671857229-116.coolpic» v:shapes="_x0000_i1159"> до точки<img width=«19» height=«20» src=«ref-1_1671857132-97.coolpic» v:shapes="_x0000_i1160">. У найгіршому випадку для визначення числа <img width=«15» height=«20» src=«ref-1_1671799126-94.coolpic» v:shapes="_x0000_i1161"> із точки <img width=«84» height=«24» src=«ref-1_1671857652-354.coolpic» v:shapes="_x0000_i1162"> може знадобитися до <img width=«33» height=«20» src=«ref-1_1671858006-213.coolpic» v:shapes="_x0000_i1163"> додавань точки <img width=«19» height=«20» src=«ref-1_1671856903-97.coolpic» v:shapes="_x0000_i1164">( при <img width=«61» height=«20» src=«ref-1_1671858316-278.coolpic» v:shapes="_x0000_i1165"> маємо множину зворотних за знаком точок, <img width=«15» height=«16» src=«ref-1_1671858594-88.coolpic» v:shapes="_x0000_i1166">- координати яких уже відомі). Обчислювальна складність безпосереднього розрахунку дискретного логарифма оцінюється числом операцій <img width=«41» height=«24» src=«ref-1_1671858682-253.coolpic» v:shapes="_x0000_i1167">. Щоб скоротити шлях до збігу (колізії) з відомою точкою, природно на всьому шляху поставити маркери <img width=«31» height=«20» src=«ref-1_1671858935-120.coolpic» v:shapes="_x0000_i1168">, <img width=«150» height=«23» src=«ref-1_1671859055-377.coolpic» v:shapes="_x0000_i1169">, координати яких визначено на етапі попередніх обчислень. Рухаючись від точки <img width=«24» height=«19» src=«ref-1_1671856041-109.coolpic» v:shapes="_x0000_i1170"> до найближчого маркера, ми істотно скорочуємо зону пошуку (рис 1). Виникає лише питання, як розставити маркери?




<img width=«332» height=«271» src=«ref-1_1671859541-4298.coolpic» v:shapes="_x0000_i1171">

Рисунок 1 -Подання елементів циклічної групи точками на колі й інтервал аналізу за методом Шенкса
По суті введення маркерів -це обмін обчислень на пам'ять. Якщо об'єми цих ресурсів зробити рівними, то відстань між маркерами слід вибирати рівною <img width=«55» height=«27» src=«ref-1_1671863839-238.coolpic» v:shapes="_x0000_i1172"> . Ця ідея запропонована Д.Шенксом.

Метод Шенкса часто називають методом великих і малих кроків (Giant step-Baby step). Маркери <img width=«31» height=«20» src=«ref-1_1671864077-118.coolpic» v:shapes="_x0000_i1173"> -це Giant step. Номери <img width=«11» height=«19» src=«ref-1_1671864195-83.coolpic» v:shapes="_x0000_i1174"> цих точок з їх <img width=«15» height=«16» src=«ref-1_1671858594-88.coolpic» v:shapes="_x0000_i1175">-координатами зберігаються в пам'яті. Baby step – це послідовні додавання точок <img width=«148» height=«24» src=«ref-1_1671864366-403.coolpic» v:shapes="_x0000_i1176"> після чого обчислені <img width=«15» height=«16» src=«ref-1_1671858594-88.coolpic» v:shapes="_x0000_i1177">-координати порівняюються з координатами маркерів. При збігу координат отримуємо <img width=«124» height=«24» src=«ref-1_1671864857-392.coolpic» v:shapes="_x0000_i1178">, звідки визначається шукане значення <img width=«15» height=«20» src=«ref-1_1671799126-94.coolpic» v:shapes="_x0000_i1179">. Метод Шенкса є детерміністським.

Обчислювальна складність методу <img width=«72» height=«31» src=«ref-1_1671865343-375.coolpic» v:shapes="_x0000_i1180"> оцінюється як середнє число малих кроків. Основний недолік методу – надмірний об'єм необхідної пам'яті, пропорційний <img width=«49» height=«25» src=«ref-1_1671865718-258.coolpic» v:shapes="_x0000_i1181">.

Крім того, на кожному кроці порівняння координат здійснюється по всіх точках, що зберігаються в пам'яті. Для задач реального криптоаналізу метод не знайшов застосування. Однак, часто метод Шенкса приводиться як теоретична основа для інших, більш практичних методів рішення <img width=«65» height=«20» src=«ref-1_1671842257-163.coolpic» v:shapes="_x0000_i1182">.


3.    
Метод ділення точок на два ( продовження)

Він заснований на використанні точок <P> з максимальним порядком <img width=«64» height=«25» src=«ref-1_1671866139-245.coolpic» v:shapes="_x0000_i1183">, <img width=«35» height=«20» src=«ref-1_1671866384-192.coolpic» v:shapes="_x0000_i1184"> (коефіцієнт кривої a=0). Задамо рекурентну функцію ділення-відрахування
<img width=«187» height=«71» src=«ref-1_1671866576-995.coolpic» v:shapes="_x0000_i1185"><img width=«77» height=«23» src=«ref-1_1671867571-314.coolpic» v:shapes="_x0000_i1186"> (1)
Оскільки кожне ділення дає дві точки, повна процедура утворює дерево розв’язків із <img width=«28» height=«23» src=«ref-1_1671867885-183.coolpic» v:shapes="_x0000_i1187"> галузями (<img width=«11» height=«17» src=«ref-1_1671868068-84.coolpic» v:shapes="_x0000_i1188">-число віднімань точки <img width=«17» height=«19» src=«ref-1_1671868152-95.coolpic» v:shapes="_x0000_i1189">). В ідеальному випадку, при правильному виборі точок ділення, одна з галузей найбільш коротким шляхом веде до точки <img width=«17» height=«19» src=«ref-1_1671868152-95.coolpic» v:shapes="_x0000_i1190">, а інша – <img width=«41» height=«24» src=«ref-1_1671868342-235.coolpic» v:shapes="_x0000_i1191">. При цьому двійковий запис алгоритму ділення (0) або відрахування – ділення (1) дає шукане число <img width=«29» height=«24» src=«ref-1_1671868577-198.coolpic» v:shapes="_x0000_i1192"> або <img width=«69» height=«28» src=«ref-1_1671868775-322.coolpic» v:shapes="_x0000_i1193">. Для цього буде потрібно не більше <img width=«48» height=«25» src=«ref-1_1671869097-262.coolpic» v:shapes="_x0000_i1194"> ділень. Зрозуміло, при випадковому виборі точок ділення ймовірність знаходження таких галузей мізерно мала.

Точки групи <P> зручно подати у вигляді еквідистантних точок кола, починаючи відлік від точки ПРО, розташованої ліворуч за годинниковою стрілкою (рис. 2). Будь-якій парній точці групи <P> ®<img width=«59» height=«20» src=«ref-1_1671869359-219.coolpic» v:shapes="_x0000_i1195"> відповідають дві точки ділення <img width=«17» height=«19» src=«ref-1_1671869578-96.coolpic» v:shapes="_x0000_i1196"> й <img width=«28» height=«19» src=«ref-1_1671869674-183.coolpic» v:shapes="_x0000_i1197">, розташовані на одній діагоналі кола й пов'язані співвідношенням <img width=«88» height=«19» src=«ref-1_1671869857-256.coolpic» v:shapes="_x0000_i1198"> із точкою <img width=«20» height=«19» src=«ref-1_1671870113-98.coolpic» v:shapes="_x0000_i1199"> другого порядку. Значення точок <img width=«24» height=«19» src=«ref-1_1671870211-106.coolpic» v:shapes="_x0000_i1200">, <img width=«129» height=«36» src=«ref-1_1671870317-442.coolpic» v:shapes="_x0000_i1201"> верхнього півкола можна розглядати як додатні, а нижнього півкола <img width=«35» height=«19» src=«ref-1_1671870759-116.coolpic» v:shapes="_x0000_i1202"> -як від’ємні. Координати <img width=«20» height=«25» src=«ref-1_1671870875-98.coolpic» v:shapes="_x0000_i1203"> кожної такої пари збігаються, а <img width=«100» height=«25» src=«ref-1_1671870973-187.coolpic» v:shapes="_x0000_i1204">. У процедурі ділення, що прагне до точки <img width=«19» height=«20» src=«ref-1_1671857132-97.coolpic» v:shapes="_x0000_i1205">, можна ігнорувати знак точки, зазначимо, що є лише <img width=«15» height=«16» src=«ref-1_1671858594-88.coolpic» v:shapes="_x0000_i1206">- координата точки. Назвемо «правильною» точкою ділення точку лівого півкола (на рис 2 – точка <img width=«28» height=«19» src=«ref-1_1671869674-183.coolpic» v:shapes="_x0000_i1207">). Послідовний вибір «правильних» точок ділення в процедурі <img width=«167» height=«28» src=«ref-1_1671871528-399.coolpic» v:shapes="_x0000_i1208"> веде до точки <img width=«19» height=«20» src=«ref-1_1671857132-97.coolpic» v:shapes="_x0000_i1209"> й, відповідно до розв’язання <img width=«65» height=«20» src=«ref-1_1671842257-163.coolpic» v:shapes="_x0000_i1210">. Злом криптосистеми, у такий спосіб зводиться до вирішення еквівалентних проблем:

– визначення, у якому пів кола групи <P> перебуває деяка точка цієї групи;

– визначення співвідношення (більше — менше) між двома довільними
точками <img width=«27» height=«25» src=«ref-1_1671872187-117.coolpic» v:shapes="_x0000_i1211"> й <img width=«29» height=«25» src=«ref-1_1671872304-121.coolpic» v:shapes="_x0000_i1212"> групи <P>;

– визначення парності ( непарності) числа <img width=«13» height=«15» src=«ref-1_1671841901-86.coolpic» v:shapes="_x0000_i1213"> для точки <img width=«24» height=«19» src=«ref-1_1671870211-106.coolpic» v:shapes="_x0000_i1214">;

– чи виконується редукція за модулем <img width=«20» height=«20» src=«ref-1_1671872617-103.coolpic» v:shapes="_x0000_i1215"> при подвоєнні довільної точки <img width=«24» height=«19» src=«ref-1_1671870211-106.coolpic» v:shapes="_x0000_i1216"> із групи <img width=«17» height=«19» src=«ref-1_1671868152-95.coolpic» v:shapes="_x0000_i1217"> порядку <img width=«20» height=«20» src=«ref-1_1671872617-103.coolpic» v:shapes="_x0000_i1218">?

Доки відповісти на ці запитання не вдається ECC залишається стійкою криптосистемою з експоненційною складністю розв’язання <img width=«41» height=«19» src=«ref-1_1671845480-128.coolpic» v:shapes="_x0000_i1219">. Для криптоаналізу зовсім необов'язково прийти до точки <img width=«17» height=«19» src=«ref-1_1671868152-95.coolpic» v:shapes="_x0000_i1220"> або <img width=«28» height=«19» src=«ref-1_1671873247-104.coolpic» v:shapes="_x0000_i1221">, достатньо знайти точку з <img width=«15» height=«16» src=«ref-1_1671858594-88.coolpic» v:shapes="_x0000_i1222">-координатою точки, що раніше зустрічалася в цій процедурі, або будь-якої іншої відомої точки групи <P>. У першому випадку рішення <img width=«41» height=«19» src=«ref-1_1671845480-128.coolpic» v:shapes="_x0000_i1223"> при колізії <img width=«69» height=«25» src=«ref-1_1671873567-182.coolpic» v:shapes="_x0000_i1224"> близько до <img width=«17» height=«19» src=«ref-1_1671844704-179.coolpic» v:shapes="_x0000_i1225">- методу Полларда, у другому – до методу Шенкса.

Доцільно використовувати максимально можливу кількість інформації (передрозрахунки) з метою збільшення ймовірності колізій, однак це веде до збільшення кількості перевірок і розширення пам'яті.
крива поле дискретний логарифмування атака


<img width=«345» height=«236» src=«ref-1_1671873928-9654.coolpic» v:shapes="_x0000_i1226">
    продолжение
--PAGE_BREAK--Рисунок 2 -Геометрична ілюстрація методу ділення точок кривої на два Якщо в 1 залишити лише одну операцію ділення на два з вибором точки із групи <img width=«47» height=«20» src=«ref-1_1671883582-214.coolpic» v:shapes="_x0000_i1227">, то ітераційна процедура ділення на два в остаточному підсумку також призведе до точки <img width=«19» height=«20» src=«ref-1_1671856903-97.coolpic» v:shapes="_x0000_i1228"> (або іншої відомої точки), якщо 2 є примітивним елементом поля <img width=«23» height=«25» src=«ref-1_1671883893-109.coolpic» v:shapes="_x0000_i1229">. Послідовне ділення точок на два вимагає в НБ лише одне множення в полі на кожному кроці, інші операції практично не вимагають витрат. При цьому, імовірно, можна досягти максимальної швидкості криптоаналізу. Цей метод, однак, рівносильний повному перебору всіх точок. Більш доцільним, можливо, є випадковий пошук колізій зі складністю <img width=«55» height=«29» src=«ref-1_1671884002-292.coolpic» v:shapes="_x0000_i1230">. 4. Аномальні криві й криві над розширеннями малого поля


Аномальні криві над розширеннями поля <img width=«24» height=«25» src=«ref-1_1671884294-108.coolpic» v:shapes="_x0000_i1231"> (криві Коблиця) виду <img width=«163» height=«29» src=«ref-1_1671884402-327.coolpic» v:shapes="_x0000_i1232">, <img width=«68» height=«28» src=«ref-1_1671884729-373.coolpic» v:shapes="_x0000_i1233"> мають особливості структури групи E, що дозволяють зменшити в <img width=«28» height=«20» src=«ref-1_1671885102-189.coolpic» v:shapes="_x0000_i1234"> раз об'єм аналізованих точок кривої (у порівнянні із групою загальної структури) і, відповідно, у <img width=«43» height=«25» src=«ref-1_1671885291-229.coolpic» v:shapes="_x0000_i1235"> раз обчислювальну складність пошуку колізій. Це пов'язано з виникненням класів еквівалентності точок кривої, породжуваних послідовним піднесенням у квадрат координат вихідної точки.

Позначимо функцію <img width=«147» height=«29» src=«ref-1_1671885520-483.coolpic» v:shapes="_x0000_i1236"> при цьому <img width=«168» height=«29» src=«ref-1_1671886003-565.coolpic» v:shapes="_x0000_i1237"> Для будь-якої точки <img width=«76» height=«24» src=«ref-1_1671886568-306.coolpic» v:shapes="_x0000_i1238"> порядку <img width=«20» height=«20» src=«ref-1_1671872617-103.coolpic» v:shapes="_x0000_i1239"> кривої <img width=«17» height=«19» src=«ref-1_1671886977-94.coolpic» v:shapes="_x0000_i1240"> над полем <img width=«24» height=«28» src=«ref-1_1671887071-114.coolpic» v:shapes="_x0000_i1241"> визначається ендоморфізм Фробеніуса (відображення поля в поле), який задовольняє характеристичне рівняння
<img width=«236» height=«29» src=«ref-1_1671887185-595.coolpic» v:shapes="_x0000_i1242">
Тут операція додавання визначена як додавання в групі E, а параметр <img width=«11» height=«17» src=«ref-1_1671868068-84.coolpic» v:shapes="_x0000_i1243"> називають слідом ендоморфізма Фробеніуса. Зокрема, для кривої Коблиця з коефіцієнтами з поля <img width=«24» height=«25» src=«ref-1_1671884294-108.coolpic» v:shapes="_x0000_i1244"> й параметром <img width=«83» height=«29» src=«ref-1_1671887972-308.coolpic» v:shapes="_x0000_i1245"> маємо
<img width=«272» height=«29» src=«ref-1_1671888280-725.coolpic» v:shapes="_x0000_i1246">
Тому що функція <img width=«47» height=«24» src=«ref-1_1671889005-289.coolpic» v:shapes="_x0000_i1247"> не змінює порядку точки, справедлива рівність <img width=«87» height=«24» src=«ref-1_1671889294-392.coolpic» v:shapes="_x0000_i1248">, при цьому <img width=«123» height=«29» src=«ref-1_1671889686-434.coolpic» v:shapes="_x0000_i1249">, а характеристичне рівняння Фробеніуса приймає вигляд <img width=«212» height=«29» src=«ref-1_1671890120-641.coolpic» v:shapes="_x0000_i1250">

Розв’язання цього квадратного рівняння в кільці <img width=«29» height=«25» src=«ref-1_1671890761-118.coolpic» v:shapes="_x0000_i1251"> дає значення параметра <img width=«16» height=«20» src=«ref-1_1671890879-168.coolpic» v:shapes="_x0000_i1252">, що визначає всі точки класу еквівалентності
<img width=«229» height=«49» src=«ref-1_1671891047-889.coolpic» v:shapes="_x0000_i1253">
Через те, що їхні координати визначаються послідовним піднесенням у квадрат, простіше всього їх виразити в НБ, у якому їх <img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1254">-бітовий запис утворює циклічний код із <img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1255"> слів для кожної координати. Такі точки називають помітними. Задача розв’язання <img width=«65» height=«20» src=«ref-1_1671892124-165.coolpic» v:shapes="_x0000_i1256">, таким чином, зводиться до пошуку класу еквівалентності з точністю до циклічного зсуву, що практично не вимагає додаткових обчислень. Неважко переконатися, що для підгрупи <img width=«48» height=«20» src=«ref-1_1671892289-213.coolpic» v:shapes="_x0000_i1257"> точок цієї кривої порядку <img width=«48» height=«20» src=«ref-1_1671892502-165.coolpic» v:shapes="_x0000_i1258"> коренем рівняння
<img width=«167» height=«25» src=«ref-1_1671892667-496.coolpic» v:shapes="_x0000_i1259">
є значення <img width=«44» height=«20» src=«ref-1_1671893163-218.coolpic» v:shapes="_x0000_i1260">, а класи еквівалентності містять точки
<img width=«341» height=«24» src=«ref-1_1671893381-1056.coolpic» v:shapes="_x0000_i1261">
Для точок максимального порядку <img width=«71» height=«25» src=«ref-1_1671894437-250.coolpic» v:shapes="_x0000_i1262"> корінь рівняння
<img width=«169» height=«25» src=«ref-1_1671894687-509.coolpic» v:shapes="_x0000_i1263">
дорівнює <img width=«153» height=«20» src=«ref-1_1671895196-515.coolpic» v:shapes="_x0000_i1264"> Один із класів еквівалентності точок даного порядку включає точки <img width=«153» height=«24» src=«ref-1_1671895711-648.coolpic» v:shapes="_x0000_i1265">. Їхні координати утворюються послідовним піднесенням у квадрат. Усього є 4 класи еквівалентності точок максимального порядку.

В порівнянні із загальним типом груп <img width=«29» height=«25» src=«ref-1_1671896359-121.coolpic» v:shapes="_x0000_i1266"> аномальні бінарні криві поступаються у стійкості в <img width=«32» height=«29» src=«ref-1_1671896480-134.coolpic» v:shapes="_x0000_i1267"> раз, що не є катастрофічною втратою. Для полів з розширенням <img width=«105» height=«20» src=«ref-1_1671896614-424.coolpic» v:shapes="_x0000_i1268"> втрата складає не більше 4-х біт. Тому з урахуванням високої технологічності такі криві не виключаються із криптографічних застосувань і входять у відомі стандарти. Подібні ж міркування справедливі, якщо як вихідну прийняти криву <img width=«179» height=«29» src=«ref-1_1671897038-305.coolpic» v:shapes="_x0000_i1269">, <img width=«71» height=«29» src=«ref-1_1671897343-245.coolpic» v:shapes="_x0000_i1270"> над малим полем <img width=«27» height=«29» src=«ref-1_1671897588-119.coolpic» v:shapes="_x0000_i1271">, після чого ту ж криву розглядати над розширенням <img width=«35» height=«29» src=«ref-1_1671897707-139.coolpic» v:shapes="_x0000_i1272"> (при цьому як і раніше <img width=«71» height=«29» src=«ref-1_1671897343-245.coolpic» v:shapes="_x0000_i1273">). Слід Фробеніуса <img width=«15» height=«25» src=«ref-1_1671898091-95.coolpic» v:shapes="_x0000_i1274"> визначає порядок кривої над підполем <img width=«27» height=«29» src=«ref-1_1671897588-119.coolpic» v:shapes="_x0000_i1275"> (і розв’язання характеристичного рівняння для скаляра <img width=«16» height=«20» src=«ref-1_1671890879-168.coolpic» v:shapes="_x0000_i1276">), а слід <img width=«19» height=«25» src=«ref-1_1671898473-102.coolpic» v:shapes="_x0000_i1277"> -порядок кривої над полем <img width=«35» height=«29» src=«ref-1_1671897707-139.coolpic» v:shapes="_x0000_i1278">. Виникнення класів еквівалентності точок кривої над таким розширенням приводить до втрати складності криптоатаки в <img width=«31» height=«25» src=«ref-1_1671898714-129.coolpic» v:shapes="_x0000_i1279"> раз. Крім того, поле <img width=«35» height=«29» src=«ref-1_1671897707-139.coolpic» v:shapes="_x0000_i1280"> є композиційним і містить принаймні підполя <img width=«89» height=«29» src=«ref-1_1671898982-287.coolpic» v:shapes="_x0000_i1281">. Такі криві уразливі стосовно атаки методом спуску Вейля.

Аномальні криві над простим полем <img width=«25» height=«28» src=«ref-1_1671899269-114.coolpic» v:shapes="_x0000_i1282">, <img width=«44» height=«24» src=«ref-1_1671899383-230.coolpic» v:shapes="_x0000_i1283"> визначаються як криві з порядком <img width=«64» height=«25» src=«ref-1_1671899613-164.coolpic» v:shapes="_x0000_i1284"> й, відповідно, слідом Фробеніуса <img width=«35» height=«20» src=«ref-1_1671899777-141.coolpic» v:shapes="_x0000_i1285">. Такі криві виявилися криптографічно слабкими, тому що порядки групи <img width=«17» height=«19» src=«ref-1_1671886977-94.coolpic» v:shapes="_x0000_i1286"> й адитивної групи поля <img width=«28» height=«32» src=«ref-1_1671900012-127.coolpic» v:shapes="_x0000_i1287"> рівні, що дозволяє порівняно просто побудувати атаку ізоморфізму, що переводить точки кривої в елементи групи <img width=«28» height=«32» src=«ref-1_1671900012-127.coolpic» v:shapes="_x0000_i1288">. Цей метод уперше був запропонований І. Семаєвим, а також незалежно авторами Т. Сатохом, К. Араки й Н.Смартом. Складність <img width=«65» height=«20» src=«ref-1_1671892124-165.coolpic» v:shapes="_x0000_i1289"> при цій атаці стає поліноміальною, що робить аномальні криві даного типу неприйнятними в криптографії.
5.
<img width=«48» height=«20» src=«ref-1_1671900431-149.coolpic» v:shapes="_x0000_i1290">— атака
Під час вивчення властивостей суперсингулярних кривих виявилося, що порядок групи <img width=«17» height=«19» src=«ref-1_1671886977-94.coolpic» v:shapes="_x0000_i1291"> над полем <img width=«24» height=«28» src=«ref-1_1671887071-114.coolpic» v:shapes="_x0000_i1292"> ділить порядок мультиплікативної групи розширень <img width=«27» height=«32» src=«ref-1_1671900788-127.coolpic» v:shapes="_x0000_i1293"> або <img width=«27» height=«32» src=«ref-1_1671900915-130.coolpic» v:shapes="_x0000_i1294">. Це дозволяє побудувати ізоморфізм між елементами групи Eй мультиплікативної групи розширеного поля, після чого розв’язувати більше просту задачу визначення дискретного логарифма в полі. Ця атака ізоморфізму заснована на використанні ²спарювання Вейля²і була запропонована А. Менезисом, Т. Окамото й С. Ванстоном, у зв'язку із чим називається <img width=«48» height=«20» src=«ref-1_1671900431-149.coolpic» v:shapes="_x0000_i1295">— атакою.

Суперсингулярні криві над полем <img width=«31» height=«29» src=«ref-1_1671901194-127.coolpic» v:shapes="_x0000_i1296"> при непарних розширеннях <img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1297"> мають три класи ізоморфізму, зображених у таблиці 3 з порядками <img width=«39» height=«24» src=«ref-1_1671901415-159.coolpic» v:shapes="_x0000_i1298">, <img width=«89» height=«31» src=«ref-1_1671901574-329.coolpic» v:shapes="_x0000_i1299">, <img width=«52» height=«29» src=«ref-1_1671901903-224.coolpic» v:shapes="_x0000_i1300">.
Таблиця 3 -Порядки суперсингулярних кривих над полем <img width=«31» height=«29» src=«ref-1_1671901194-127.coolpic» v:shapes="_x0000_i1301">принепарних степенях <img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1302">

Крива <img width=«24» height=«25» src=«ref-1_1671902348-107.coolpic» v:shapes="_x0000_i1303">

<img width=«19» height=«16» src=«ref-1_1671851856-94.coolpic» v:shapes="_x0000_i1304">

Порядок <img width=«29» height=«25» src=«ref-1_1671902549-128.coolpic» v:shapes="_x0000_i1305">

<img width=«93» height=«29» src=«ref-1_1671902677-196.coolpic» v:shapes="_x0000_i1306">

Непарне

<img width=«53» height=«24» src=«ref-1_1671902873-226.coolpic» v:shapes="_x0000_i1307">

<img width=«124» height=«29» src=«ref-1_1671903099-230.coolpic» v:shapes="_x0000_i1308">

<img width=«115» height=«24» src=«ref-1_1671903329-521.coolpic» v:shapes="_x0000_i1309">

<img width=«119» height=«41» src=«ref-1_1671903850-399.coolpic» v:shapes="_x0000_i1310">

<img width=«124» height=«29» src=«ref-1_1671903099-230.coolpic» v:shapes="_x0000_i1311">

<img width=«116» height=«24» src=«ref-1_1671904479-544.coolpic» v:shapes="_x0000_i1312">

<img width=«117» height=«41» src=«ref-1_1671905023-391.coolpic» v:shapes="_x0000_i1313">

<img width=«149» height=«29» src=«ref-1_1671905414-286.coolpic» v:shapes="_x0000_i1314">

<img width=«115» height=«24» src=«ref-1_1671903329-521.coolpic» v:shapes="_x0000_i1315">

<img width=«117» height=«41» src=«ref-1_1671905023-391.coolpic» v:shapes="_x0000_i1316">

<img width=«149» height=«29» src=«ref-1_1671905414-286.coolpic» v:shapes="_x0000_i1317">

<img width=«116» height=«24» src=«ref-1_1671904479-544.coolpic» v:shapes="_x0000_i1318">

<img width=«113» height=«41» src=«ref-1_1671907442-388.coolpic» v:shapes="_x0000_i1319">



Для кривої <img width=«93» height=«29» src=«ref-1_1671902677-196.coolpic» v:shapes="_x0000_i1320"> з порядком <img width=«87» height=«25» src=«ref-1_1671908026-227.coolpic» v:shapes="_x0000_i1321"> ізоморфізм існує вже при розширенні <img width=«28» height=«20» src=«ref-1_1671885102-189.coolpic» v:shapes="_x0000_i1322">, тому що мультиплікативна група цього поля має порядок <img width=«133» height=«31» src=«ref-1_1671908442-474.coolpic» v:shapes="_x0000_i1323">. Для інших кривих ізоморфізм виникає при розширенні <img width=«28» height=«20» src=«ref-1_1671908916-175.coolpic» v:shapes="_x0000_i1324">, тому що <img width=«283» height=«31» src=«ref-1_1671909091-823.coolpic» v:shapes="_x0000_i1325"> й, отже, <img width=«29» height=«25» src=«ref-1_1671902549-128.coolpic» v:shapes="_x0000_i1326"> ділить порядок <img width=«64» height=«29» src=«ref-1_1671910042-291.coolpic» v:shapes="_x0000_i1327"> мультиплікативної групи поля <img width=«37» height=«29» src=«ref-1_1671910333-144.coolpic» v:shapes="_x0000_i1328">. Оскільки відомі субекспоненційні алгоритми розв’язання <img width=«41» height=«19» src=«ref-1_1671910477-130.coolpic» v:shapes="_x0000_i1329"> в полі, такі розширення порівняно невеликі й роблять атаку успішною. У цьому зв'язку суперсингулярні криві не рекомендуються в криптографічних стандартах.

Несурперсингулярні криві й криві над простими полями також проходять тест на <img width=«48» height=«20» src=«ref-1_1671900431-149.coolpic» v:shapes="_x0000_i1330">— атаку. Тест на стійкість до цієї атаки можна рахувати успішним, якщо порядок <img width=«15» height=«16» src=«ref-1_1671838680-87.coolpic» v:shapes="_x0000_i1331"> <img width=«43» height=«20» src=«ref-1_1671910843-135.coolpic» v:shapes="_x0000_i1332"> не ділить порядок мультиплікативної групи розширення <img width=«52» height=«32» src=«ref-1_1671910978-310.coolpic» v:shapes="_x0000_i1333">, рівний <img width=«51» height=«29» src=«ref-1_1671911288-179.coolpic» v:shapes="_x0000_i1334">, для всіх розширень <img width=«99» height=«23» src=«ref-1_1671911467-343.coolpic» v:shapes="_x0000_i1335"> Верхня межа безпеки звичайно приймається рівною <img width=«91» height=«20» src=«ref-1_1671911810-355.coolpic» v:shapes="_x0000_i1336">

6. Метод спуску Вейля

Заснована на методі спуску Вейля атака називається <img width=«43» height=«20» src=«ref-1_1671912165-139.coolpic» v:shapes="_x0000_i1337">— атакою.

Нехай несуперсингулярна крива <img width=«29» height=«25» src=«ref-1_1671896359-121.coolpic» v:shapes="_x0000_i1338"> визначена над композиційним полем <img width=«35» height=«29» src=«ref-1_1671897707-139.coolpic» v:shapes="_x0000_i1339"> з непростим розширенням. Позначимо <img width=«51» height=«29» src=«ref-1_1671912564-220.coolpic» v:shapes="_x0000_i1340">,<img width=«52» height=«28» src=«ref-1_1671912784-156.coolpic» v:shapes="_x0000_i1341">, <img width=«63» height=«32» src=«ref-1_1671912940-177.coolpic» v:shapes="_x0000_i1342"> (<img width=«29» height=«20» src=«ref-1_1671913117-107.coolpic» v:shapes="_x0000_i1343">мале поле, <img width=«20» height=«19» src=«ref-1_1671913224-99.coolpic» v:shapes="_x0000_i1344">-розширення поля <img width=«15» height=«20» src=«ref-1_1671799126-94.coolpic» v:shapes="_x0000_i1345">). Тоді
<img width=«344» height=«29» src=«ref-1_1671913417-705.coolpic» v:shapes="_x0000_i1346">
Припустимо, що виконується хоча б одна з умов:

1. <img width=«16» height=«20» src=«ref-1_1671799220-94.coolpic» v:shapes="_x0000_i1347">-непарне число;

2. <img width=«73» height=«24» src=«ref-1_1671914216-336.coolpic» v:shapes="_x0000_i1348">;

3. <img width=«72» height=«24» src=«ref-1_1671914552-340.coolpic» v:shapes="_x0000_i1349"> Тут <img width=«47» height=«23» src=«ref-1_1671914892-255.coolpic» v:shapes="_x0000_i1350"> -²магічне число², певне в працях А Менезиса, М.Ку, Гаудрі, Хасе й Смарта. Воно визначає рід <img width=«15» height=«19» src=«ref-1_1671915147-163.coolpic» v:shapes="_x0000_i1351"> якоїсь гіпереліптичної кривої <img width=«123» height=«28» src=«ref-1_1671915310-353.coolpic» v:shapes="_x0000_i1352"> <img width=«39» height=«20» src=«ref-1_1671915663-135.coolpic» v:shapes="_x0000_i1353">-атака пропонує використати метод спуску Вейля для зведення<img width=«65» height=«20» src=«ref-1_1671892124-165.coolpic» v:shapes="_x0000_i1354">на кривій <img width=«47» height=«24» src=«ref-1_1671915963-262.coolpic» v:shapes="_x0000_i1355"> до <img width=«41» height=«19» src=«ref-1_1671910477-130.coolpic» v:shapes="_x0000_i1356"> якобіану <img width=«48» height=«25» src=«ref-1_1671916355-260.coolpic» v:shapes="_x0000_i1357"> гіпереліптичної кривої <img width=«17» height=«20» src=«ref-1_1671916615-95.coolpic» v:shapes="_x0000_i1358"> роду <img width=«15» height=«19» src=«ref-1_1671915147-163.coolpic» v:shapes="_x0000_i1359"> над полем <img width=«17» height=«20» src=«ref-1_1671845374-106.coolpic» v:shapes="_x0000_i1360">

Порядок підгрупи якобіану <img width=«96» height=«29» src=«ref-1_1671916979-344.coolpic» v:shapes="_x0000_i1361"> може виявитися більше порядку <img width=«25» height=«29» src=«ref-1_1671917323-119.coolpic» v:shapes="_x0000_i1362"> поля <img width=«20» height=«19» src=«ref-1_1671913224-99.coolpic» v:shapes="_x0000_i1363"> кривої <img width=«51» height=«24» src=«ref-1_1671917541-277.coolpic» v:shapes="_x0000_i1364"> але для групи <img width=«48» height=«25» src=«ref-1_1671916355-260.coolpic» v:shapes="_x0000_i1365">    продолжение
--PAGE_BREAK--