Реализация операций на эллиптической кривой

Задача аутентификации документов решается с помощью использования механизма электронной цифровой подписи, который реализуется методами криптографии с открытым ключом. В основу алгоритмов цифровой подписи положены асимметричные криптографические преобразования, стойкость которых основана на сложности решения некоторой математической задачи. В последние годы широко ведутся исследования криптографических преобразований, основанных на операциях в группе точек эллиптической кривой. Арифметика эллиптических кривых, определенных над простыми и/или расширенными полями Галуа легла в основу стандартов электронной цифровой подписи многих стран, включая Украину. Это, например, такие стандарты:  ДСТУ 4145-2002, ГОСТ Р 34.10-2001, ECDSA, EC-GDSA, ECSS, EC-KCDSA.

Ниже представлена реализация в математическом пакете Maple операций сложения, удвоения точек эллиптической кривой, а также операции умножения точки кривой на число в простом поле Галуа.

Сложение точек эллиптической кривой P3=P1+P2

sum_Point:=proc(P1,P2,p)
local x1, y1, x2, y2, x3, y3, Lamda, P3:
x1:=P1[0]: y1:=P1[1]: x2:=P2[0]: y2:=P2[1]:
if (x1=0 and y1=0) then x3:=x2: y3:=y2:
else
if (x2=0 and y2=0) then x3:=x1: y3:=y1:
else
if (x1=x2 and y1=(-y2)mod p) then x3:=0: y3:=0:
else
Lamda:=((y2-y1)/(x2-x1) mod p):
x3:=(Lamda^2-x1-x2)mod p:
y3:=(Lamda*(x1-x3)-y1)mod p:
end if:
end if:
end if:
P3:=array(0..1,[x3,y3]);
end:

Удвоение точки эллиптической кривой P3=2P1

double_Point:=proc(P1,p,a)
local x1, y1, x3, y3, Lamda, P3:
x1:=P1[0]: y1:=P1[1]:
if (y1=0) then x3:=0: y3:=0:
else
Lamda:=(((3*x1^2+a)/2/y1) mod p):
x3:=(Lamda^2-2*x1) mod p:
y3:=(Lamda*(x1-x3)-y1) mod p:
end if:
P3:=array(0..1,[x3,y3]);
end:

Скалярное умножение на эллиптической кривой Q=dP

p_Mul:=proc(P,d,p,ka)
local N, i, Q, xqs, yqs;
Q:=P;
N:=convert(d,binary);
N:=convert(N,string);
for i from 2 to length(N) do
Q:=double_Point(Q,p,ka):
if (N[i]="1") then
if (Q[0]=P[0] and Q[1]=P[1]) then Q:=double_Point(Q,p,ka):
else Q:=sum_Point(Q,P,p):
end if:
end if:
end do;
Q:
end proc:

Пример программы, использующей данные функции

p:=5:
msolve(y^2=x^3+x+1,p);
N:=9: # Порядок кривой
d:=4: # Секретный ключ
x3:=0:y3:=0:
ka:=1:
xq:=0:yq:=0:
xp:=3:
yp:=6:
P:=array(0..1,[xp,yp]);
Q:=array(0..1,[0,0]);

Q:=p_Mul(P,d,p,ka):
xqs:=Q[0]: yqs:=Q[1]:
xqs:=convert(xqs,hex):
yqs:=convert(yqs,hex):
print(xqs,yqs);

Q:=p_Mul(P,N,p,ka):
xqs:=Q[0]: yqs:=Q[1]:
xqs:=convert(xqs,hex):
yqs:=convert(yqs,hex):
print(xqs,yqs);