Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої
– визначення, у якому пів кола групи <P> перебуває деяка точка цієї групи;
– визначення
співвідношення
(більше - менше)
між двома довільними
точками
й
групи <P>;
– визначення
парності (
непарності)
числа
для точки
;
– чи
виконується
редукція за
модулем
при подвоєнні
довільної точки
із групи
порядку
?
Доки відповісти
на ці запитання
не вдається
ECC залишається
стійкою криптосистемою
з експоненційною
складністю
розв’язання
.
Для криптоаналізу
зовсім необов'язково
прийти до точки
або
,
достатньо
знайти точку
з
-координатою
точки, що раніше
зустрічалася
в цій процедурі,
або будь-якої
іншої відомої
точки групи
<P>. У першому
випадку рішення
при колізії
близько до
-
методу Полларда,
у другому – до
методу Шенкса.
Доцільно використовувати максимально можливу кількість інформації (передрозрахунки) з метою збільшення ймовірності колізій, однак це веде до збільшення кількості перевірок і розширення пам'яті.
крива поле дискретний логарифмування атака

Рисунок 2 - Геометрична ілюстрація методу ділення точок кривої на два
Якщо
в 1 залишити
лише одну операцію
ділення на два
з вибором точки
із групи
,
то ітераційна
процедура
ділення на два
в остаточному
підсумку також
призведе до
точки
(або іншої відомої
точки), якщо 2
є примітивним
елементом поля
.
Послідовне
ділення точок
на два вимагає
в НБ лише одне
множення в полі
на кожному
кроці, інші
операції практично
не вимагають
витрат. При
цьому, імовірно,
можна досягти
максимальної
швидкості
криптоаналізу.
Цей метод, однак,
рівносильний
повному перебору
всіх точок.
Більш доцільним,
можливо, є випадковий
пошук колізій
зі складністю
.
4. Аномальні криві й криві над розширеннями малого поля
Аномальні
криві над
розширеннями
поля
(криві Коблиця)
виду
,
мають особливості
структури групи
E, що
дозволяють
зменшити в
раз об'єм аналізованих
точок кривої
(у порівнянні
із групою загальної
структури) і,
відповідно,
у
раз обчислювальну
складність
пошуку колізій.
Це пов'язано
з виникненням
класів еквівалентності
точок кривої,
породжуваних
послідовним
піднесенням
у квадрат координат
вихідної точки.
Позначимо
функцію
при цьому
Для будь-якої
точки
порядку
кривої
над полем
визначається
ендоморфізм
Фробеніуса
(відображення
поля в поле),
який задовольняє
характеристичне
рівняння
![]()
Тут
операція додавання
визначена як
додавання в
групі E,
а параметр
називають
слідом ендоморфізма
Фробеніуса.
Зокрема, для
кривої Коблиця
з коефіцієнтами
з поля
й параметром
маємо
![]()
Тому
що функція
не змінює порядку
точки, справедлива
рівність
,
при цьому
,
а характеристичне
рівняння Фробеніуса
приймає вигляд
![]()
Розв’язання
цього квадратного
рівняння в
кільці
дає значення
параметра
,
що визначає
всі точки класу
еквівалентності

Через
те, що їхні
координати
визначаються
послідовним
піднесенням
у квадрат, простіше
всього їх виразити
в НБ, у якому
їх
-бітовий
запис утворює
циклічний код
із
слів для кожної
координати.
Такі точки
називають
помітними.
Задача розв’язання
,
таким чином,
зводиться до
пошуку класу
еквівалентності
з точністю до
циклічного
зсуву, що практично
не вимагає
додаткових
обчислень.
Неважко переконатися,
що для підгрупи
точок цієї
кривої порядку
коренем рівняння
![]()
є значення
,
а класи еквівалентності
містять точки
![]()
Для точок
максимального
порядку
корінь рівняння
![]()
дорівнює
Один із класів
еквівалентності
точок даного
порядку включає
точки
.
Їхні координати
утворюються
послідовним
піднесенням
у квадрат. Усього
є 4 класи еквівалентності
точок максимального
порядку.
В порівнянні
із загальним
типом груп
аномальні
бінарні криві
поступаються
у стійкості
в
раз, що не є
катастрофічною
втратою. Для
полів з розширенням
втрата складає
не більше 4-х
біт. Тому з
урахуванням
високої технологічності
такі криві не
виключаються
із криптографічних
застосувань
і входять у
відомі стандарти.
Подібні ж міркування
справедливі,
якщо як вихідну
прийняти криву
,
над малим полем
,
після чого ту
ж криву розглядати
над розширенням
(при цьому як
і раніше
).
Слід Фробеніуса
визначає порядок
кривої над
підполем
(і розв’язання
характеристичного
рівняння для
скаляра
),
а слід
-
порядок кривої
над полем
.
Виникнення
класів еквівалентності
точок кривої
над таким розширенням
приводить до
втрати складності
криптоатаки
в
раз. Крім того,
поле
є композиційним
і містить принаймні
підполя
.
Такі криві
уразливі стосовно
атаки методом
спуску Вейля.
Аномальні
криві над простим
полем
,
визначаються
як криві з порядком
й, відповідно,
слідом Фробеніуса
.
Такі криві
виявилися
криптографічно
слабкими, тому
що порядки
групи
й адитивної
групи поля
рівні, що дозволяє
порівняно
просто побудувати
атаку ізоморфізму,
що переводить
точки кривої
в елементи
групи
.
Цей метод уперше
був запропонований
І. Семаєвим, а
також незалежно
авторами Т.
Сатохом, К. Араки
й Н. Смартом.
Складність
при цій атаці
стає поліноміальною,
що робить аномальні
криві даного
типу неприйнятними
в криптографії.
5.
-
атака
Під час
вивчення властивостей
суперсингулярних
кривих виявилося,
що порядок
групи
над полем
ділить порядок
мультиплікативної
групи розширень
або
.
Це дозволяє
побудувати
ізоморфізм
між елементами
групи E
й мультиплікативної
групи розширеного
поля, після
чого розв’язувати
більше просту
задачу визначення
дискретного
логарифма в
полі. Ця атака
ізоморфізму
заснована на
використанні
Іспарювання
ВейляІ
і була запропонована
А. Менезисом
, Т. Окамото й
С. Ванстоном,
у зв'язку із
чим називається
-
атакою.
Суперсингулярні
криві над полем
при непарних
розширеннях
мають три класи
ізоморфізму,
зображених
у таблиці 3