ЛЕКЦІЯ 8 ДЕРЖАВНИЙ СТАНДАРТ УКРАЇНИ 4145-2002

Date: 2015-10-07; view: 358.

Cтандарт ДСТУ 4145-2002 встановлює механізм цифрового підпису, оснований на властивостях групи точок еліптичних кривих над полями характеристики 2, а саме, над полями , де - велике просте число.

8.1 Операції на еліптичних кривих над полями характеристики p≠3

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

а) для всіх ;

б) якщо , то ; для всіх ;

в) якщо - скінченні точки, такі, що , і , а , то

, ;

г) якщо - скінченні точки, , а , то , ;

д) Якщо знаменник виразу для дорівнює нулю, то результатом операції на кривій є .

Відомо, що цей алгоритм визначає комутативну і асоціативну групову операцію: (додавання на еліптичній кривій).

Операцію додавання двох однакових точок називають подвоєнням точки .

Опишемо тапер властивості групового закону з нейтральним елементом для невиродженої кривої над полем , яка в ДСТУ 4145-2002 задається рівнянням , .

Якщо і , - дві точки еліптичної кривої в афінних координатах, то і .

Крім того, сума точок обчислюється за такими правилами.

для всіх .

Якщо , то . Якщо , то координати точки обчислюються за формулами:

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

При подвоєнні точки з першою координатою результат приймаємо рівним .

Таким чином, у випадку нулів у знаменнику операції дають .

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

Якщо , то у виразі коефіцієнт можна зводити за модулем , а також розглядати вирази виду і , зокрема , , де , тощо.

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

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