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

В афінному поданні точка нескінченності введена як формальний символ та забезпечує виконання групових законів. Основним недоліком афінного подання є значна складність операції ділення за модулем у формулах (А.1.4) та (А.1.5). Ця задача зводиться до пошуку зворотного елемента для чисел  або  в полі . Зменшення складності виконання операцій додавання (А.1.2) та подвоєння (А.1.3) досягається при використанні проективного подання еліптичної кривої. Обидва подання еліптичних кривих сумісні (однозначні).

А.1.2.2 Проективне подання

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

А.1.2.2.1 Проективні площини над полем

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

Введемо для цієї множини  відношення еквівалентності, позначивши його символом “~”. Відношення еквівалентності має такі властивості.

, тобто існує таке , що  та .

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

А.1.2.2.2 Проективний опис еліптичної кривої  над полем

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

,                           (А.1.6)

де .

Еліптичні криві в поданні (А.1.6) складаються із усіх точок  проективної площини , таких, що кожна трійка  є розв’язком рівняння (А.1.6). Існує взаємно однозначне співвідношення між точками  на кривій , коли крива визначена в афінному поданні та точками  у проективному поданні. Для афінного та проективного подань мають виконуватися такі умови:

-  якщо  є точкою з афінним поданням на кривій , тоді точка  однозначно відповідає точці ;

-  якщо  є точкою еліптичної кривої (А.1.6), причому , тоді  є однозначно відповідною точкою кривої  в афінному поданні;

-  існує тільки одне розв’язання (А.1.6) при , а саме точка . Ця точка відповідає .

А.1.2.2.3 Груповий закон у проективному поданні.

У проективному поданні кривої (А.1.6) точки кривої відповідають таким властивостям:

-  точка  у відношенні до операції  є елементом, тотожним точці нескінченності ;

-  якщо  точка, що належить еліптичній кривій  у проективному поданні, тоді  є точкою ;

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

;                                                                

;                                    (А.1.7)

,                                                             

причому , , та ;

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

;                                                                

;                                             (А.1.8)

,                                                                 

причому ,  та .

А.2 Скінченне поле

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

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

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

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

-  у відношенні до операції множення  за модулем  є абелевою групою.

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