Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої
Таблиця
3 -
Порядки суперсингулярних
кривих над
полем
при
непарних
степенях
![]()
|
Крива
|
|
Порядок
|
|
|
Непарне |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Для кривої
з порядком
ізоморфізм
існує вже при
розширенні
,
тому що мультиплікативна
група цього
поля має порядок
.
Для інших кривих
ізоморфізм
виникає при
розширенні
,
тому що
й, отже,
ділить порядок
мультиплікативної
групи поля
.
Оскільки відомі
субекспоненційні
алгоритми
розв’язання
в полі, такі
розширення
порівняно
невеликі й
роблять атаку
успішною. У
цьому зв'язку
суперсингулярні
криві не рекомендуються
в криптографічних
стандартах.
Несурперсингулярні
криві й криві
над простими
полями також
проходять тест
на
-
атаку. Тест на
стійкість до
цієї атаки
можна рахувати
успішним, якщо
порядок
не ділить порядок
мультиплікативної
групи розширення
,
рівний
,
для всіх розширень
Верхня межа
безпеки звичайно
приймається
рівною
![]()
6. Метод спуску Вейля
Заснована
на методі спуску
Вейля атака
називається
-
атакою.
Нехай
несуперсингулярна
крива
визначена над
композиційним
полем
з непростим
розширенням.
Позначимо
,
,
(
мале поле,
-
розширення
поля
).
Тоді
![]()
Припустимо, що виконується хоча б одна з умов:
1.
-
непарне число;
2.
;
3.
Тут
-
Імагічне
числоІ,
певне в працях
А Менезиса,
М.Ку, Гаудрі,
Хасе й Смарта.
Воно визначає
рід
якоїсь гіпереліптичної
кривої
-атака
пропонує використати
метод спуску
Вейля для зведення
на кривій
до
якобіану
гіпереліптичної
кривої
роду
над полем
![]()
Порядок
підгрупи якобіану
може виявитися
більше порядку
поля
кривої
але для групи
існують субекспоненціальні
алгоритми
розв’язання
![]()
За допомогою
алгоритму
Кантора
у підгрупі
може бути вирішена
за
групових операцій.
При практичній
реалізації
для
часто залучаються
такі три методи:
1.
-
метод Полларда
зі складністю
бітових операцій.
2. Метод
Енге-Гаудрі,
що має субекспоненційну
обчислювальну
складність
![]()
3. Алгоритм Гаудри, який оцінюється складністю
бітових операцій.
Алгоритм
Гаудрі швидше,
ніж алгоритм
Полларда, якщо
У зв'язку зі
швидким зростанням
співмножника
цей алгоритм
стає непрактичним
при
.
У цьому випадку
доцільно використати
метод Енге-Гаудрі.
Він вважається
прийнятним
при
.
атака вважається
успішною, якщо
рід
гіпереліптичної
кривої
малий настільки,
що алгоритми
2 і 3 більш ефективні,
ніж метод Полларда.
Нехай, наприклад,
крива
визначена над
полем
й
,
,
тоді
.
У випадку
максимального
значення
величина
,
тому очікується,
що при
-атака
для майже всіх
кривих над
полем
буде успішною.
При
приходимо до
якобіану
ізоморфної
кривої
з експонентною
складністю
розв’язання
.
Щоб уникнути
атаки методом
спуску Вейля,
розширення
поля слід вибирати
простим. При
цьому