Форма Гессе еліптичної кривої

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

ОзначенняРедагувати

 
Крива Гессе рівняння  

Нехай задано поле  . Розглянемо еліптичну криву   у наступному спеціальному випадку форми Вейерштрасса над полем  :

 

де крива має дискримінант  . Тоді точка   має порядок 3.

Щоб довести, що   має порядок 3, зауважимо, що дотична до   у точці   — пряма  , яка перетинає   в точці   з кратністю 3.

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

Тепер, щоб отримати криву Гессе, необхідно виконати таке перетворення[en]:

Спочатку позначимо через   корінь многочлена

 

Тоді

 

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

Тепер, визначивши наступне значення  , отримуємо іншу криву  , яка біраціонально еквівалентна[en]  :

  :  

в афінній площині його називають кубічною формою Гессепроективних координатах   та  )

 :  

Більш того,   (інакше, крива буде сингулярною[en]).

Починаючи з кривої Гессе, біраціонально еквівалентне[en] рівняння Вейерштрасса задається співвідношенням

 

за допомогою перетворень

 

та

 

де

 

та

 .

Закон групуванняРедагувати

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

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

У деяких застосуваннях еліптичної криптографії та факторизації за допомогою еліптичних кривих (ECM[en]) необхідно обчислювати множення на скаляр для точки  , наприклад,   з деяким цілим числом  , і вони базуються на методі швидкого піднесення до степеня; ці операції потребують формул додавання та подвоєння.

Подвоєння

Для точки   на еліптичній кривій можна визначити операцію "подвоєння" за допомогою формул Коші-Десбовеса:

 .

Додавання

Таким же чином для двох різних точок   та точки   можна визначити формулу додавання. Нехай   позначає суму цих точок,  , тоді її координати наступні:

 .

Алгоритми та прикладиРедагувати

Існує алгоритм, за допомогою якого можна додати або подвоїти дві різні точки, запропонований Джойєм (Joye) і Кіскватером (Jean-Jacques Quisquater[en]). Наступне трердження дає можливість отримати операцію подвоєння шляхом додавання:

Теорема. Нехай   - точка на еліптичній кривій Гессе  , тоді

 

Більш того,  .

На відміну від інших параметризацій[en],тут відсутнє віднімання для обчислення віддзеркалення точки. Отже, цей алгоритм додавання також може бути використаний для віднімання двох точок   і   на еліптичній кривій Гессе:

 

Підсумовуючи, шляхом адаптування порядку вводів відповідно до рівнянь (1) або (2), алгоритм додавання, наведений вище, можна використовувати для додавання двох (різних) точок, подвоєння точки і віднімання двох точок лише за допомогою 12 добутків і 7 допоміжних змінних, включаючи 3 початкові змінні. До появи кривих Едвардса[en] ці результати були найшвидшим відомим способом реалізації скалярного множення на еліптичній кривій для противаги атакам сторонніми каналами.

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

ДодаванняРедагувати

Нехай   і   дві точки відмінні від  , і  , тоді алгоритм наступний:

 
 
 
 
 

Для алгоритму необхідно: 8 множень та 3 додавання, а для відновлення: 7 множень та 3 додавання, в залежності від першої точки.

Приклад

Нехай задано точки кривої для  :   та  . Якщо  , то

 
 
 

Таким чином,  .

ПодвоєнняРедагувати

Нехай   — точка, тоді формула подвоєння має наступний вигляд:

 
 
 
 
 
 
 

Необхідні операції для алгоритму: 3 множення   3 піднесення до квадрату     додавань    .

Приклад

Якщо   точка кривої Гессе з параметром  , то координати подвоєної точки   наступні:

 
 
 

Отже,  .

Розширені координатиРедагувати

Існує ще одна система координат, за допомогою якої може бути зображена крива Гессе; ці нові координати називаються розширеними координатами. Вони можуть прискорити процес додавання та подвоєння. Щоб отримати більше інформації про операції з розширеними координатами, див.

http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd

Координати   і   представляються через  ,  ,  ,  ,  ,  ,  ,  ,  , що задовольняють наступним рівнянням:

 
 
 
 
 
 
 
 

Див. такожРедагувати

Для отримання додаткової інформації про час роботи, необхідний у конкретному випадку, див. Таблицю витрат на операції в еліптичних кривих[en].

Скручені криві Гессе[en].

Зовнішні посиланняРедагувати

Список літературиРедагувати