Выполнение операций над точками ЭК с использованием функций библиотеки MIRACL

Лекция 10

Выполнение операций над точками ЭК с использованием функций библиотеки MIRACL

E(F2^m)E(Fp)

Инициализация:

BOOL. ecruve_init (int m, k3 ,k2 ,k1 ,big a, big b, BOOL check, int type);

                                                                           проверка неприводимости

                                                                           многочлена check==TRUE

f(t)=t^m+ t^k3+ t^k2+ t^k1+1

R₂=0 => f(t)=t^m+ t^k3+1 – трином

TYPE – тип координат, которые используются

MR_AFFINE – аффинные координаты (x,y)

MR_projective – проективные координаты (x,y,z)

E(Fp)

Void ecurve_init(big a, big b, big P, int type);

Функции:

epoint * epoint2_init(big x, big y, big z, int tmp); - выделение памяти под                    структуру epoint

void epoint_free(epoint * P) - освобождение памяти

Пример:

f(t)=t⁴+t+1;       a=1; b=0xB.

{ (0,E), (2,D) …

big a,b;

a=mirvar(1);

b=mirvar(0xB);

ecurve2_init(4,1,0,0,a,b,FALSE,MR_AFFINE);

epoint *P,*Q;

P=epoint2_init();

Q=epoint2_init();

Установление значений координат точки:

BOOL epoint2_set(big x, big y, int lsb, epoint *P); //BOOL== TRUE, если устанавливается точка, принадлежащая кривой

&x==&y, то можно найти коэффициенты

lsb – младший бит y/x

Обратная процедура получения координат x и y:

int epoint2_get(epoint *P, big x, big y) //int=> вернет младший бит y/x

&x==&y – сжатое представление точки

convert(0,a);

convert(0xE,b);

Установление значения точки:

Epoint2_set(0,b,0,P);

Дополнительные сервисные функции:

-копирование

void epoint2_copy(epoint *P, epoint *Q);

           Q<=P

-сравнение

BOOL epoint2_comp(epoint *P,epoint *Q);

  TRUE => P==Q

-определение порядка точки

BOOL point_at_infinity(epoint *P); //является ли точка точкой на             неопределенности

  TRUE=> P==I

-нормализация

BOOL epoint2_norm(epoint *P); //преобразовываем проективные координаты, чтобы z==1

Основные арифметические функции

Ограничение: точки Є ЕК (инициализация, выделение памяти)

-P+Q; 2P; dP

Ecurve2_add(epoint *P, epoint *Q);

   Q<=Q+P

-вычитание

ecurve2_sub(epoint *P, epoint *Q);

   Q<=Q-P

-умножение точки на скаляр

ecurve2_mult(big d, epoint *P, epoint *Q); //d<n_P(меньше порядка точки)

min d => d-P=I – порядок точки

   Q<=d•P;

-при проверке подписи

R=SP+rQ – одновременное двоичное скалярное умножение

P,Q Є ε

S,r – целые числа

Ecurve2_mult2(big Sepoint *P, big r, epoint *Q, epoint *R)

-одновременное многократное скалярное произведение

epoint2_multn(int n, big *d, epoint **P, epoint *Q);

Q<=d[0]•P[0]+ d[1]•P[1]+…+ d[n-1]•P[n-1]

- одновременное многократное сложение точек

ecurve2_multi_add(int n, epoint **P, epoint *Q);

Q<=P[0]+…+P[n-1], при условии, что используются аффинные         координаты

P, n_P. Вычисляем открытый ключ Q=d-P.

         Базовая, фиксированная точка, для нее используются предвычисления.

f(t), a, b, P (n_P)

Метод Биксела.

используются следующие функции:

-предвычисления (инициализация)

BOOL ebrick2_init(ebrick2*binst//указатель на структуру//, big x, big y, //координаты базовой точки// big a, big b, int m, k3, k2, k1, int d-MaxBitLen//максимальная битовая длина скалярного множителя – порядок базовой точки//);

-обратная процедура

ebrick2_end(ebrick2 *binst), освобождение памяти

-умножение точки на скаляр

int mul2_brick(ebrick2 *binst, big d, big x, big y);

Q=(x,y)=d•P, если &x=&y, то возвращается x.

Пример 1

Нужно вычислить R=SP+rQ; S=0xA, r=0xD; P≠(0,E), Q=(2,D)

big r;

big S,x,y;

S=mirvar(0xA);// выделение памяти

r=mirvar(0xD);

epoin2 *P,*Q;

P=epoint2_init();

Q= epoint2_init();// выделение памяти

x=mirvar(0);

y=mirvar(0xE);

epoint_set(x,y,0,P);

R=epoint2_init();

convert(2,x);

convert(0xD,y);

epoint2_set(x,y,0,Q);

ecurve_mult2(S,P,r,Q,R);

Пример 2

Определить порядок базовой точки

void ecurve2_point_order(epoint *P, big n)

epoint *R=epoint2_init();

epoint2_copy(P,P1);

convert(1,n);//заносим в n 1

while (!point-at-infinity(P1))

{

  pncr(n,1,n);

  ecurve_mult(n,P1,R);

  epoint2_copy(R,P1);

}

epoint2_free(P1);

epoint2_free(R);