Криптоперетворення в групі точок еліптичних кривих, страница 2

 та ,

або

 та .

При цьому операція ділення заміняється знаходженням зворотного елемента, що є суттєво складною.

Особливістю криптографічних перетворень в групі точок ЕК є те, що відкритий ключ обчислюється згідно з (6.1). Якщо особистий ключ в d сформовано випадково, а Q є відкритий ключ, то задача криптоаналізу формулюється як знаходження особистого ключа d при відомих Q, G, а також .

6.4 Додаток А ОСНОВНА ІНФОРМАЦІЯ З ЕЛІПТИЧНИХ КРИВИХ

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

А.1 Скінченне просте поле

А.1.1 Визначення

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

-  елементи поля  у відношенні до операції додавання  є абелевою групою;

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

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

Зворотній елемент групи

Нехай  буде елементом групи . Тоді для кожного  існує  такий, що . Елемент  називається мультиплікативно зворотнім до елемента  (інверсією), позначається як , та може бути обчислений як .

Характеристика скінченного поля

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

Ділення в полі

Значення  в полі  існує, якщо знаменник не нульовий. У цьому випадку частка .

Квадрати й не квадрати в полі

Припустимо, що . Елемент  називається квадратом у полі , якщо існує елемент  такий, що . Факт існування квадратного кореня визначається за умови:

 є квадратом у полі , якщо .

Пошук квадратного кореня в полі

Для знаходження квадратних коренів у полі  існують різні методи. Їх застосування дозволяє для кожного  знайти  таке, що , де  є квадратом числа . Приклади таких методів наведено в [1] та [3].

А.1.2 Еліптичні криві над полем

У цій частині надаються два різних, але еквівалентних подання еліптичних кривих, що визначені над скінченними простими полями – афінне та проективне подання.

А.1.2.1 Афінне подання

Нехай  буде скінченним простим полем з . Еліптична крива  над полем  визначається несингулярним кубічним рівнянням над полем . У цьому документі допускається, що  крива  описана «коротким рівнянням Вейєрштраса», тобто

,                                      (А.1.1)

з  такими, що виконується умова  у полі . (Більш точно рівняння (А.1.1) називається афінним рівнянням Вейєрштраса).

Еліптична крива  над полем , що задається рівнянням виду (А.1.1) складається з набору точок  таких, що виконується рівняння , для усіх цих точок разом з додатковою точкою нескінченності .

Точка нескінченності  не міститься в  та не задовольняє рівняння (А.1.1). Набір точок на кривій  вигляду  є афінним поданням еліптичної кривої .

А.1.2.1.1 Груповий закон в афінному поданні

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

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

Якщо точка  є афінним поданням на кривій , тоді інверсна точка  має координати  та .

Якщо точки  та  є афінним поданням точок на кривій , причому , тоді  координати  суми  визначаються відповідно до формул:

;                                           (А.1.2)

.                                    (А.1.3)

При цьому, якщо , то

,                                 (А.1.4)

якщо , то

.                                     (А.1.5)