Спосіб визначення суми двох точок еліптичної кривої над двійковим розширеним полем у проективних координатах

Спосіб визначення суми двох точок еліптичної кривої над двійковим розширеним полем у проективних координатах, який полягає у виконанні 2 3 38400 Х3=a×E+A×(A+Z3)+B2×В; Y3=Х3×(A+Z 3)+E×(X2×Y1+D×X1); Z3=B×Z 1, де 2 C = Z1 ; D=Y2×Z 1; А=Y1+С×D; B=X1+X2×C; 2 E = Z3 . Недоліком цього способу є те, що додавання точок кривої залежить від параметру кривої а, що не дозволяє використовувати однакову процедуру додавання точок при використанні різних кривих, а також вимагає великої кількості операцій, що виконуються за допомогою послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля GF(2n), згідно алгоритму додавання точок. Найбільш близьким по сукупності ознак до запропонованого технічним рішенням, обраним як прототип, є спосіб визначення суми двох точок еліптичної кривої над полем GF(2n) у проективних координатах Лопеса-Дахаба [2], що ґрунтується на виконанні процедури додавання двох точок, за допомогою послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля CF(2n), згідно алгоритму додавання точок, а при обчисленні суми двох точок користуються проективними координатами Лопеса-Дахаба. Проективній точці (X:Y:Z), Z¹0, стави ться у відповідність точка з афінними координатами (X/Z, Y/Z2). Еліптична крива Е над GF(2n) має вигляд Y2+XYZ=X3 Z+aX2Z 2+bZ4, де а,b Î GF(2n) при b¹0. Процедура додавання двох точок кривої у проективних координатах у випадку P1(X1:Y1:Z 1)¹P2(X2 :Y2:Z2) виконується згідно виразів: X3=А2+В2×(D+a×C2)+A×D; 2ö æ æ ö Y3 = Z 3 × ç X3 + B 2 × Y2Z1 ÷ + A × B × ç X1Z 2 × Z 3 + X3 × B 2 ÷; è ø è ø Z3=D2, де A = Y1 × Z 2 + Y2 × Z 2 ; 2 1 B = X1 × Z2 + X2 × Z1; C=Z1×Z2 ; D=B×C, у випадку P1(X1:Y1:Z 1) = P2(X2 :Y2 :Z2) й P æ X1 / Z1, Y1 / Z 2 ö = P2 æ X 2 / Z 2 , Y2 / Z2 ö ç 1ç 1÷ 2÷ è ø è ø процедура додавання виконується згідно виразів 4 4 X3 = X1 = b × Z1 ; 4 2 4ö æ Y3 = bZ1 × Z 3 + X3 × ç a × Z 3 + Y1 + bZ1 ÷; è ø Z3 = (X1 × Z1) 2, 4 у випадку, коли одна з точок подана у проективних координатах, а інша в а фінних координатах Р1(Х1:Y1:Z 1), P2(X2:Y2:1), æ ö æ ö P ç X1 / Z1, Y1 / Z 2 ÷ ¹ P2 ç X 2 / Z 2 , Y2 / Z 2 ÷ , 1 1ø 2ø è è процедура додавання виконується згідно виразів X3 = A 2 + A × C + ( C + a × Z 2 ) × B2 ; 1 Y3=(X2×Z 3+X3)×AC+(X3+Y2×Z 3)×Z3 ; де 2 A = Y1 + Y2 × Z1 ; В= Х1+X2×Z 1, C=Z1×B. Недоліком цього способу є те, що додавання точок кривої залежить від параметру кривої a, що не дозволяє використовувати однакову процедуру додавання точок при використанні різних кривих, а також вимагає великої кількості операцій, що виконуються за допомогою послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля GF(2n), згідно алгоритму додавання точок. В основу корисної моделі поставлена задача створення способу визначення суми двох точок еліптичної кривої над полем GF(2n) у проективних координатах, який дозволив би звільнитися залежності від параметру кривої та виконувати меншу кількість операцій за допомогою послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля gGF(2n), згідно алгоритму додавання точок. Технічний результат, який може бути отриманий при здійснені винаходу полягає в можливості звільнитися від залежності параметру кривої а та зниження обчислювальної складності завдяки виконанню процедури додавання двох точок з меншою кількістю операцій за допомогою послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля GF(2n), згідно алгоритму додавання точок. Сутність запропонованого способу визначення суми двох точок еліптичної кривої над двійковим розширеним полем у проективних координатах полягає в виконанні процедури додавання двох точок, за допомогою послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля GF(2n), згідно алгоритму додавання точок, а при обчисленні суми двох точок користуються проективними координатами, який відрізняється від способу-прототипу додатковим включенням тимчасових змінних, які зберігаються у відповідних пристроях, виконанням над ними послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля GF(2n) та відсутністю залежності від параметру кривої а. Процедуру додавання у випадку æ ö æ ö P ç X1 : Z1 : Y1 : Z 2 ÷ ¹ P2 ç X 2 : Z 2 : Y2 : Z 2 ÷ 1 1ø 2ø è è виконують згідно виразів: X3=D×(G+J)+E×(F+H); Y3=A×B×(K×D+X3)+(F×K2+X3×Z 3); Z3=K×С, 5 38400 де D=X1×Z2; E=X2×Z1 ; 6 2 P æ X1 : Z1 : Y : Z1 ö , ÷ 1ç 1 è ø P2 (X 2 : Z2 : 1 : 1) , F = Y1 × Z 2; 2 P æ X1 / Z1, Y1 / Z 2 ö ¹ P2 æ X 2 / Z 2 , Y2 / Z 2 ö , ç 1ç 1÷ 2÷ è ø è ø G = Y2 × Z 2 ; 1 то процедуру додавання виконують згідно виразів: X3=X1×(G+J)+E×(Y1+H); Y3=A×B×(K×X1+X3)+(F×K2+X3×Z3); де Z3=K×X1+X3); A=D+E; B=F+G; C=Z1×Z2; H=D2; J=E2; K=A2=H+J. У випадках G = Y2 × Z 2 ; 1 2ö æ æ ö P ç X1 : Z1 : Y : Z1 ÷ = P2 ç X 2 : Z 2 : Y2 : Z 2 ÷ 1 1 2ø è ø è A=X1+E; B=Y1+G; й 2 H = X1 ; J=E2; K=A2=H=J. У таблиці 1 наведено кількість пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля GF(2n), у порівнянні з відомим способом [1] та у порівнянні зі способом-прототипом [2]. У таблиці позначено: «Ù2» - кількість операцій піднесення до квадрату; «*» - кількість операцій добутку; «+» - кількість операцій додавання. P æ X1 / Z1, Y1 / Z 2 ö ¹ P2 æ X 2 / Z 2 , Y2 / Z 2 ö ç 1ç 1÷ 2÷ è ø è ø процедуру додавання виконують згідно виразів: 4 4 X3 = X1 + b × Z1 ; 4 2 4 Y3 = bZ1 × Z 3 + X3 × æ a × Z 3 + Y1 + bZ1 ö; ç ÷ è ø 2 2 Z3 = X1 × Z1 . Якщо одна з точок подана в проективних координатах, а інша в афінних: Таблиця 1 Порівняльна таблиця за кількістю операцій над елементами двійкового розширеного поля Система координат Відомий спосіб [1] Відомий спосіб-прототип [2] Запропонований спосіб Загальне додавання ^2 5 6 5 * 15 15 13 Таким чином, за рахунок додаткового включення тимчасових змінних, які зберігаються у відповідних пристроях, виконанням над ними послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів поля GF(2n), вдається на [1] операцію піднесення до квадрату, 1 операцію добутку зменшити кількість виконуваних операцій з елементами поля GF(2n) та уникнути залежності від параметру кривої a. На Фіг.. показана схема електрична структурна пристрою визначення двох точок еліптичної кривої над двійковим розширеним полем у проективних координатах запропонованим способом. Визначення двох точок еліптичної кривої виконується наступним чином. Виконується обчислення тимчасової змінної D, яка дорівнює добутку координати Х точки P1, на координату Z точки Р2: D=X1×Z 2. Виконується обчислення тимчасової змінної E, яка дорівнює добутку координати Х точки Р2 на координату Z точки P1: + 8 8 9 Загальне додавання (змішані координати) ^2 * + 3 11 8 4 10 8 4 10 9 Подвоєння ^2 5 6 5 * 5 5 5 + 4 4 4 Е=X1×Z2 . Виконується обчислення тимчасової змінної F, яка дорівнює добутку координати Y точки P1 на квадрат координати Z точки Р2: F = Y1 × Z 2 . 2 Виконується обчислення тимчасової змінної G, яка дорівнює добутку координати Y точки P2 на квадрат координати Z точки Р,: 2 G = Y2 × Z1 . Виконується обчислення тимчасової змінної А, яка дорівнює сумі тимчасових змінних D та Е: A=D+E. Виконується обчислення тимчасової змінної 5, яка дорівнює сумі тимчасових змінних F та G: B=F+G. Виконується обчислення тимчасової змінної С, як добуток Z координат точок: С=Z1×Z2. Виконується обчислення тимчасової змінної H, як квадрат тимчасової змінної D: H=D2. Виконується обчислення тимчасової змінної J, як квадрат тимчасової змінної Е: 7 38400 J=E2. Виконується обчислення тимчасової змінної К, як сума тимчасової змінної Я та тимчасової змінної: K=A2=H+J. Виконується обчислення Z координати результуючої точки P3, як добуток тимчасової змінної К та тимчасової змінної С: Z3=К×С. Виконується обчислення Х координати результуючої точки Р3, як сума добутку тимчасової змінної D на суму тимчасових змінних G та J, з добутком тимчасової змінної Е на суму тимчасових змінних F та Н: Х3=D×(G+J)+Е×(F+H). Виконується обчислення Y координати точки P3, як сума добутків тимчасової змінної А, В з сумою Х координати точки Р^ з добутком тимчасових змінних К і D, та тимчасової змінної F з квадратом тимчасової змінної К, а також добутку X3 на Z3 координат результуючої точки P3: Y3=A×B×(K×D+X3)+F×K2+X3×Z3). Спосіб визначення суми двох точок еліптичної кривої над полем GF(2n) у проективних координатах у випадку Р1 = P2 та P æ X1 / Z1, Y1 / Z 2 ö = P2 æ X 2 / Z 2 , Y2 / Z2 ö , ç 1ç 1÷ 2÷ è ø è ø може бути реалізований у наступній послідовності. Виконується обчислення тимчасової змінної А, яка дорівнює квадрату координати Х точки Р1: A = X2 . 1 Виконується обчислення тимчасової змінної В, 2 яка дорівнює квадрату координати Z точки B = Z1 . Виконується обчислення тимчасової змінної С, яка дорівнює квадрату тимчасової змінної А: С=А2. Виконується обчислення тимчасової змінної Z), яка дорівнює добутку квадрата тимчасової змінної В на коефіцієнт кривої b: D=b×B2. Виконується обчислення X координати результуючої точки P3, як добуток тимчасової змінної А на В: Z2=А×В. Виконується обчислення Х координати результуючої точки P3, як сума тимчасової змінної С та D: X3=C+D. Виконується обчислення Y координати точки Р3, як сума добутку Z координати точки Р3 на тимчасову змінну D, та добутку Х координати точки P3 на дужки, в дужках - сума добутку коефіцієнту кривої а на Z координати точки Д, квадрату У координати точки P1 та тимчасової змінної D: Y3=D×Z 3+X3×(a×Z 3+Y1 2+D). Спосіб визначення суми двох точок еліптичної кривої над полем GF(2n) у проективних координатах у випадку, якщо одна з точок подана у проективних координатах, а інша у афінних координатах 2 P æ X1 : Z1 : Y : Z1 ö , ÷ 1ç 1 è ø P2 (X 2 : Y2 : 1: 1) , 8 P æ X1 / Z1, Y1 / Z 2 ö ¹ P2 æ X 2 / Z 2 , Y2 / Z 2 ö , ç 1ç 1÷ 2÷ è ø è ø може бути реалізований наступним чином. Виконується обчислення тимчасової змінної Е, яка дорівнює добутку координати Х точки Р2 та добутку координати Z точки Р1: E=X2×Z1 . Виконується обчислення тимчасової змінної G, яка дорівнює добутку координати Х точки Р, та координати Z точки P1: E=X2×Z1 . Виконується обчислення тимчасової змінної А, яка дорівнює сумі тимчасової змінної Е та координати Х точки P1: А=Х1+Е. Виконується обчислення тимчасової змінної В, яка дорівнює сумі тимчасової змінної G та координати Y точки Р1. В=Y1+G. Виконується обчислення тимчасової змінної Я, яка дорівнює квадрату координати Х точки P1 : Z3 = K × Z1. Виконується обчислення тимчасової змінної J, яка дорівнює квадрату тимчасової змінної Е: J=E2, Виконується обчислення тимчасової змінної K, яка дорівнює сумі тимчасової змінної Н та J: К=А2=H+J. Виконується обчислення Z координати результуючої точки Р3, як добуток тимчасової змінної К та координати Z точки P1: Z3=А×Z 1. Виконується обчислення Х координати результуючої точки Р3, як сума добутків координати Х точки P1 з сумою тимчасових змінних G та J, та добутку тимчасової змінної Е з сумою координати Y точки Р1 та тимчасової змінної Н: X3=X1×(G+J)+E×(Y1+H). Виконується обчислення У координати точки P3, як сума добутків тимчасової змінної А, В з сумою добутку тимчасової змінної К з координатою Х точки P1, та Х координати точки P3, та координати Y точки Р1 з квадратом тимчасової змінної К, а також добутку Х3 на Z3 координат результуючої точки Р3: Y3=A×B×(K×X1+X3)+(Y×K2+X3×Z3). Таким чином, за рахунок додаткового включення тимчасових змінних, які зберігаються у відповідних пристроях, виконанням над ними послідовної дії пристроїв „добуток”, „піднесення до квадрату” та „додавання” елементів двійкового розширеного поля, вдається зменшити кількість виконуваних операцій з елементами двійкового розширеного поля та уникнути залежності від параметру кривої. Джерела інформації: 1. D.V. Chudnovsky, G.V. Chudnovsky, Sequence of number generated by addition in formal group and new primal ity and factorization test, Ad vanced in Applied Math., 7 (1987), 385-434. 2. J. Lopez and R. Dahab, Improved algorithms for elliptic curve arithmetic’s in GF(2n), Selected Areas in Cryptography -SAC'98, LNCS 1556, 1999, 201-212. 9 Комп’ютерна в ерстка Н. Лисенко 38400 Підписне 10 Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601