2. Метод Шенкса
Прямий метод розрахунку дискретного логарифма може використати два варіанти: - кратне додавання точки
до збігу із точкою
(шлях від точки
до точки
) або шлях від точки
до точки
. У найгіршому випадку для визначення числа
із точки
може знадобитися до
додавань точки
( при
маємо множину зворотних за знаком точок,
- координати яких уже відомі). Обчислювальна складність безпосереднього розрахунку дискретного логарифма оцінюється числом операцій
. Щоб скоротити шлях до збігу (колізії) з відомою точкою, природно на всьому шляху поставити маркери
,
, координати яких визначено на етапі попередніх обчислень. Рухаючись від точки
до найближчого маркера, ми істотно скорочуємо зону пошуку (рис 1). Виникає лише питання, як розставити маркери?
Рисунок 1 - Подання елементів циклічної групи точками на колі й інтервал аналізу за методом Шенкса
По суті введення маркерів - це обмін обчислень на пам'ять. Якщо об'єми цих ресурсів зробити рівними, то відстань між маркерами слід вибирати рівною . Ця ідея запропонована Д.Шенксом.
Метод Шенкса часто називають методом великих і малих кроків (Giant step-Baby step). Маркери - це Giant step. Номери
цих точок з їх
-координатами зберігаються в пам'яті. Baby step – це послідовні додавання точок
після чого обчислені
-координати порівняюються з координатами маркерів. При збігу координат отримуємо
, звідки визначається шукане значення
. Метод Шенкса є детерміністським.
Обчислювальна складність методу оцінюється як середнє число малих кроків. Основний недолік методу – надмірний об'єм необхідної пам'яті, пропорційний
.
Крім того, на кожному кроці порівняння координат здійснюється по всіх точках, що зберігаються в пам'яті. Для задач реального криптоаналізу метод не знайшов застосування. Однак, часто метод Шенкса приводиться як теоретична основа для інших, більш практичних методів рішення .
3. Метод ділення точок на два ( продовження)
Він заснований на використанні точок <P> з максимальним порядком ,
(коефіцієнт кривої a=0). Задамо рекурентну функцію ділення-відрахування
(1)
Оскільки кожне ділення дає дві точки, повна процедура утворює дерево розв’язків із галузями (
- число віднімань точки
). В ідеальному випадку, при правильному виборі точок ділення, одна з галузей найбільш коротким шляхом веде до точки
, а інша –
. При цьому двійковий запис алгоритму ділення (0) або відрахування – ділення (1) дає шукане число
або
. Для цього буде потрібно не більше
ділень. Зрозуміло, при випадковому виборі точок ділення ймовірність знаходження таких галузей мізерно мала.
Точки групи <P> зручно подати у вигляді еквідистантних точок кола, починаючи відлік від точки ПРО, розташованої ліворуч за годинниковою стрілкою (рис. 2). Будь-якій парній точці групи <P> ® відповідають дві точки ділення
й
, розташовані на одній діагоналі кола й пов'язані співвідношенням
із точкою
другого порядку. Значення точок
,
верхнього півкола можна розглядати як додатні, а нижнього півкола
- як від’ємні. Координати
кожної такої пари збігаються, а
. У процедурі ділення, що прагне до точки
, можна ігнорувати знак точки, зазначимо, що є лише
- координата точки. Назвемо "правильною" точкою ділення точку лівого півкола (на рис 2 – точка
). Послідовний вибір "правильних" точок ділення в процедурі
веде до точки
й, відповідно до розв’язання
. Злом криптосистеми, у такий спосіб зводиться до вирішення еквівалентних проблем:
– визначення, у якому пів кола групи <P> перебуває деяка точка цієї групи;
– визначення співвідношення (більше - менше) між двома довільними
точками й
групи <P>;
– визначення парності ( непарності) числа для точки
;
– чи виконується редукція за модулем при подвоєнні довільної точки
із групи
порядку
?
Доки відповісти на ці запитання не вдається ECC залишається стійкою криптосистемою з експоненційною складністю розв’язання . Для криптоаналізу зовсім необов'язково прийти до точки
або
, достатньо знайти точку з
-координатою точки, що раніше зустрічалася в цій процедурі, або будь-якої іншої відомої точки групи <P>. У першому випадку рішення
при колізії
близько до
- методу Полларда, у другому – до методу Шенкса.
Доцільно використовувати максимально можливу кількість інформації (передрозрахунки) з метою збільшення ймовірності колізій, однак це веде до збільшення кількості перевірок і розширення пам'яті.
крива поле дискретний логарифмування атака
Аномальні криві над розширеннями поля (криві Коблиця) виду
,
мають особливості структури групи E, що дозволяють зменшити в
раз об'єм аналізованих точок кривої (у порівнянні із групою загальної структури) і, відповідно, у
раз обчислювальну складність пошуку колізій. Це пов'язано з виникненням класів еквівалентності точок кривої, породжуваних послідовним піднесенням у квадрат координат вихідної точки.
Позначимо функцію при цьому
Для будь-якої точки
порядку
кривої
над полем
визначається ендоморфізм Фробеніуса (відображення поля в поле), який задовольняє характеристичне рівняння
Тут операція додавання визначена як додавання в групі E, а параметр називають слідом ендоморфізма Фробеніуса. Зокрема, для кривої Коблиця з коефіцієнтами з поля
й параметром
маємо
Тому що функція не змінює порядку точки, справедлива рівність
, при цьому
, а характеристичне рівняння Фробеніуса приймає вигляд
Розв’язання цього квадратного рівняння в кільці дає значення параметра
, що визначає всі точки класу еквівалентності
Через те, що їхні координати визначаються послідовним піднесенням у квадрат, простіше всього їх виразити в НБ, у якому їх -бітовий запис утворює циклічний код із
слів для кожної координати. Такі точки називають помітними. Задача розв’язання
, таким чином, зводиться до пошуку класу еквівалентності з точністю до циклічного зсуву, що практично не вимагає додаткових обчислень. Неважко переконатися, що для підгрупи
точок цієї кривої порядку
коренем рівняння
є значення , а класи еквівалентності містять точки
Для точок максимального порядку корінь рівняння
дорівнює Один із класів еквівалентності точок даного порядку включає точки
. Їхні координати утворюються послідовним піднесенням у квадрат. Усього є 4 класи еквівалентності точок максимального порядку.
В порівнянні із загальним типом груп аномальні бінарні криві поступаються у стійкості в
раз, що не є катастрофічною втратою. Для полів з розширенням
втрата складає не більше 4-х біт. Тому з урахуванням високої технологічності такі криві не виключаються із криптографічних застосувань і входять у відомі стандарти. Подібні ж міркування справедливі, якщо як вихідну прийняти криву
,
над малим полем
, після чого ту ж криву розглядати над розширенням
(при цьому як і раніше
). Слід Фробеніуса
визначає порядок кривої над підполем
(і розв’язання характеристичного рівняння для скаляра
), а слід
- порядок кривої над полем
. Виникнення класів еквівалентності точок кривої над таким розширенням приводить до втрати складності криптоатаки в
раз. Крім того, поле
є композиційним і містить принаймні підполя
. Такі криві уразливі стосовно атаки методом спуску Вейля.
Аномальні криві над простим полем ,
визначаються як криві з порядком
й, відповідно, слідом Фробеніуса
. Такі криві виявилися криптографічно слабкими, тому що порядки групи
й адитивної групи поля
рівні, що дозволяє порівняно просто побудувати атаку ізоморфізму, що переводить точки кривої в елементи групи
. Цей метод уперше був запропонований І. Семаєвим, а також незалежно авторами Т. Сатохом, К. Араки й Н. Смартом. Складність
при цій атаці стає поліноміальною, що робить аномальні криві даного типу неприйнятними в криптографії.
5. - атака
Під час вивчення властивостей суперсингулярних кривих виявилося, що порядок групи над полем
ділить порядок мультиплікативної групи розширень
або
. Це дозволяє побудувати ізоморфізм між елементами групи E й мультиплікативної групи розширеного поля, після чого розв’язувати більше просту задачу визначення дискретного логарифма в полі. Ця атака ізоморфізму заснована на використанні ²спарювання Вейля² і була запропонована А. Менезисом , Т. Окамото й С. Ванстоном, у зв'язку із чим називається
- атакою.
Суперсингулярні криві над полем при непарних розширеннях
мають три класи ізоморфізму, зображених у таблиці 3 з порядками
,
,
.
Таблиця 3 - Порядки суперсингулярних кривих над полем при непарних степенях
Крива | | Порядок |
| Непарне | |
| | |
| | |
| | |
| | |
Для кривої з порядком
ізоморфізм існує вже при розширенні
, тому що мультиплікативна група цього поля має порядок
. Для інших кривих ізоморфізм виникає при розширенні
, тому що
й, отже,
ділить порядок
мультиплікативної групи поля
. Оскільки відомі субекспоненційні алгоритми розв’язання
в полі, такі розширення порівняно невеликі й роблять атаку успішною. У цьому зв'язку суперсингулярні криві не рекомендуються в криптографічних стандартах.
Несурперсингулярні криві й криві над простими полями також проходять тест на - атаку. Тест на стійкість до цієї атаки можна рахувати успішним, якщо порядок
не ділить порядок мультиплікативної групи розширення
, рівний
, для всіх розширень
Верхня межа безпеки звичайно приймається рівною
0 комментариев