Складність методів вирішення проблеми дискретного логарифмування в групі точок еліптичної кривої (стр. 5 из 5)

Крива		Порядок
	Непарне

Для кривої

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

Несурперсингулярні криві й криві над простими полями також проходять тест на

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

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

Заснована на методі спуску Вейля атака називається

- атакою.

Нехай несуперсингулярна крива

визначена над композиційним полем з непростим розширенням. Позначимо , , ( мале поле, - розширення поля ). Тоді

Припустимо, що виконується хоча б одна з умов:

1.

- непарне число;

2.

;

3.

Тут - ²магічне число², певне в працях А Менезиса, М.Ку, Гаудрі, Хасе й Смарта. Воно визначає рід якоїсь гіпереліптичної кривої -атака пропонує використати метод спуску Вейля для зведення на кривій до якобіану гіпереліптичної кривої роду над полем

Порядок підгрупи якобіану

може виявитися більше порядку поля кривої але для групи існують субекспоненціальні алгоритми розв’язання

За допомогою алгоритму Кантора

у підгрупі може бути вирішена за групових операцій. При практичній реалізації для часто залучаються такі три методи:

1.

- метод Полларда зі складністю бітових операцій.

2. Метод Енге-Гаудрі, що має субекспоненційну обчислювальну складність

3. Алгоритм Гаудри, який оцінюється складністю

бітових операцій.

Алгоритм Гаудрі швидше, ніж алгоритм Полларда, якщо

У зв'язку зі швидким зростанням співмножника цей алгоритм стає непрактичним при . У цьому випадку доцільно використати метод Енге-Гаудрі. Він вважається прийнятним при .

атака вважається успішною, якщо рід гіпереліптичної кривої малий настільки, що алгоритми 2 і 3 більш ефективні, ніж метод Полларда. Нехай, наприклад, крива визначена над полем й , , тоді . У випадку максимального значення величина , тому очікується, що при -атака для майже всіх кривих над полем буде успішною. При приходимо до якобіану ізоморфної кривої з експонентною складністю розв’язання .

Щоб уникнути атаки методом спуску Вейля, розширення

поля слід вибирати простим. При цьому й , а рід гіпереліптичної кривої набагато перевищує граничне значення 1024. Практично у всіх сучасних стандартах у цьому зв'язку рекомендується степінь поля вибирати як просте число.