Cryptography Reference
In-Depth Information
The function
EllipticRhoDiscreteLog
takes as input
P
,
Q
,
E
,
n
, where
P
is a point of order
n
on the elliptic curve
E
and
Q
∈
P
, and computes log
P
Q
:
> EllipticRhoDiscreteLog := proc(P::{list(integer),identical(0)},
Q::{list(integer),identical(0)}, E::(list(integer)), n::posint)
local p, f, b, c, found, sols, i, finished, ans, u;
p := E[3];
f := proc(X, r, s)
if X[1] < p/3 then
EllipticAdd(P, X, E), (r+1) mod n, s
elif X[1] < 2*p/3 then
EllipticMult(2, X, E), 2*r mod n, 2*s mod n
else
EllipticAdd(Q, X, E), r, (s+1) mod n
end if
end proc;
b:=0,0,0;
c:=0,0,0;
finished := false;
while not finished do
found := false;
while not found do
b := f(b);
c := f(f(c));
found := evalb(b[1] = c[1])
end do;
if b[3] <> c[3] or n < 1000 then
sols := Roots((b[3]-c[3])*x-c[2]+b[2]) mod n;
sols := [seq(sols[i][1], i=1..nops(sols))];
for i in sols do
if Q = EllipticMult(i, P, E) then
return i
end if
end do
end if;
ans := readstat("Not found, continue?, y/n");
if ans = y then
print("Computation proceeds with new initial values...");
randomize();
u := RandomTools:-Generate(integer(range = 1 .. n-1));
b := EllipticMult(u, P, E), u, 0;
c:=b
else
finished := true;
print("Computation interrupted")
end if
end do
end proc:
Example 11.18
Let us consider the curve
ec192
defined in Example 11.16, which
has order
o192
(we assume these variables still hold the values assigned in Example
11.16), and the point
P
1 defined below, which we see is on the curve:
> P1 := [4628838975151188443075672732350192991625776830582167450636,
232962521192206620161428768426615311258262622352045578590]:
> IsEllipticPoint(P1, ec192);
true
The order of this point is:
> oP1 := EllipticPointOrder(P1, ec192, o192);
109152774691
