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

Позначимо функцію

при цьому Для будь-якої точки порядку кривої над полем визначається ендоморфізм Фробеніуса (відображення поля в поле), який задовольняє характеристичне рівняння

Тут операція додавання визначена як додавання в групі E, а параметр

називають слідом ендоморфізма Фробеніуса. Зокрема, для кривої Коблиця з коефіцієнтами з поля й параметром маємо

Тому що функція

не змінює порядку точки, справедлива рівність , при цьому , а характеристичне рівняння Фробеніуса приймає вигляд

Розв’язання цього квадратного рівняння в кільці

дає значення параметра , що визначає всі точки класу еквівалентності

Через те, що їхні координати визначаються послідовним піднесенням у квадрат, простіше всього їх виразити в НБ, у якому їх

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

є значення

, а класи еквівалентності містять точки

Для точок максимального порядку

корінь рівняння

дорівнює

Один із класів еквівалентності точок даного порядку включає точки . Їхні координати утворюються послідовним піднесенням у квадрат. Усього є 4 класи еквівалентності точок максимального порядку.

В порівнянні із загальним типом груп

аномальні бінарні криві поступаються у стійкості в раз, що не є катастрофічною втратою. Для полів з розширенням втрата складає не більше 4-х біт. Тому з урахуванням високої технологічності такі криві не виключаються із криптографічних застосувань і входять у відомі стандарти. Подібні ж міркування справедливі, якщо як вихідну прийняти криву , над малим полем , після чого ту ж криву розглядати над розширенням (при цьому як і раніше ). Слід Фробеніуса визначає порядок кривої над підполем (і розв’язання характеристичного рівняння для скаляра ), а слід - порядок кривої над полем . Виникнення класів еквівалентності точок кривої над таким розширенням приводить до втрати складності криптоатаки в раз. Крім того, поле є композиційним і містить принаймні підполя . Такі криві уразливі стосовно атаки методом спуску Вейля.

Аномальні криві над простим полем

, визначаються як криві з порядком й, відповідно, слідом Фробеніуса . Такі криві виявилися криптографічно слабкими, тому що порядки групи й адитивної групи поля рівні, що дозволяє порівняно просто побудувати атаку ізоморфізму, що переводить точки кривої в елементи групи . Цей метод уперше був запропонований І. Семаєвим, а також незалежно авторами Т. Сатохом, К. Араки й Н. Смартом. Складність при цій атаці стає поліноміальною, що робить аномальні криві даного типу неприйнятними в криптографії.

5.

- атака

Під час вивчення властивостей суперсингулярних кривих виявилося, що порядок групи

над полем ділить порядок мультиплікативної групи розширень або . Це дозволяє побудувати ізоморфізм між елементами групи E й мультиплікативної групи розширеного поля, після чого розв’язувати більше просту задачу визначення дискретного логарифма в полі. Ця атака ізоморфізму заснована на використанні ²спарювання Вейля² і була запропонована А. Менезисом , Т. Окамото й С. Ванстоном, у зв'язку із чим називається - атакою.

Суперсингулярні криві над полем

при непарних розширеннях мають три класи ізоморфізму, зображених у таблиці 3 з порядками , , .

Таблиця 3 - Порядки суперсингулярних кривих над полем

при непарних степенях