Is there any code or command for doubling a point ?
2 views (last 30 days)
Show older comments
I have an elliptic curve y*2=x*3+148x+225 mod 5003 I took G=(1355,2421) as the shared key I want to find points as (G,2G,3G,4G,......5003G)
2 Comments
Accepted Answer
Bruno Luong
on 24 Oct 2018
% EL parameters
a = 148
b = 225
% Group Z/pZ parameter
p = 5003
% Point
G = [1355,2421];
% Compute G2 = 2*G
x = G(1);
y = G(2);
d = mod(2*y,p);
[~,invd,~] = gcd(d,p);
n = mod(3*x*x + a,p);
lambda = mod(n*invd,p);
x2 = mod(lambda*lambda - 2*x,p);
y2 = mod(lambda*(x-x2)-y,p);
G2 = [x2 y2]
G2 =
533 2804
6 Comments
More Answers (4)
Bruno Luong
on 26 Oct 2018
EL = struct('a', 148, 'b', 225, 'p', 5003);
% Point
G = [1355,2421];
% Compute C*G for C=1,2,...,maxC
maxC = 5003;
maxk = nextpow2(maxC);
CG = zeros(maxC,2);
j = 1;
CG(j,:) = G;
G2k = G;
% precompute the inverse of 1...p-1, and stores in table itab
p = EL.p;
itab = p_inverse(1:p-1, p);
for k=1:maxk
for i=1:j-1
j = j+1;
CG(j,:) = EL_add(G2k,CG(i,:),EL,itab);
if j == maxC
break
end
end
if j == maxC
break
end
G2k = EL_add(G2k,G2k,EL,itab);
j = j+1;
CG(j,:) = G2k;
end
CG
function ia = p_inverse(a, p)
[~,ia] = gcd(a,p);
end
function R = EL_add(P,Q,EL,itab)
% R = ELadd(P,Q,EL,itab)
% Perform addition: R = P + Q on elliptic curve
% P, Q, R are (1x2) arrays of integers in [0,p) or [Inf,Inf] (null element)
% (EL) is a structure with scalar fields a, b, p.
% Together they represent the elliptic curve y^2 = x^3 + a*x + b on Z/pZ
% p is prime number
% itab is array of length p-1, inverse of 1,....,p-1 in Z/pZ
% WARNING: no overflow check, work on reasonable small p only
if ELiszero(P)
R = Q;
elseif ELiszero(Q)
R = P;
else
p = EL.p;
xp = P(1);
yp = P(2);
xq = Q(1);
yq = Q(2);
d = xq-xp;
if d ~= 0
n = yq-yp;
else
if yp == yq
d = 2*yp;
n = 3*xp*xp + EL.a;
else % P == -Q
R = [Inf,Inf];
return
end
end
invd = itab(mod(d,p)); % [~,invd,~] = gcd(d,p);
lambda = mod(n*invd,p); % slope
xr = lambda*lambda - xp - xq;
yr = lambda*(xp-xr) - yp;
R = mod([xr, yr],p);
end
end
function b = ELiszero(P)
% Check if the EL point is null-element
b = any(~isfinite(P));
end
11 Comments
Bruno Luong
on 21 Feb 2022
As stated in my code, for illustration only, there is no careful check for overflow of calculation. This code is more robust but still not bulet-proof
EL = struct('a', 0, 'b', 2, 'p', 957221);
% Point
G = [762404,61090];
% Compute C*G for C=1,2,...,maxC
maxC = 5003;
maxk = nextpow2(maxC);
CG = zeros(maxC,2);
j = 1;
CG(j,:) = G;
G2k = G;
% precompute the inverse of 1...p-1, and stores in table itab
p = EL.p;
itab = p_inverse(1:p-1, p);
for k=1:maxk
for i=1:j-1
j = j+1;
CG(j,:) = EL_add(G2k,CG(i,:),EL,itab);
if j == maxC
break
end
end
if j == maxC
break
end
G2k = EL_add(G2k,G2k,EL,itab);
j = j+1;
CG(j,:) = G2k;
end
CG
function ia = p_inverse(a, p)
[~,ia] = gcd(a,p);
end
function R = EL_add(P,Q,EL,itab)
% R = ELadd(P,Q,EL,itab)
% Perform addition: R = P + Q on elliptic curve
% P, Q, R are (1x2) arrays of integers in [0,p) or [Inf,Inf] (null element)
% (EL) is a structure with scalar fields a, b, p.
% Together they represent the elliptic curve y^2 = x^3 + a*x + b on Z/pZ
% p is prime number
% itab is array of length p-1, inverse of 1,....,p-1 in Z/pZ
% WARNING: no overflow check, work on reasonable small p only
if ELiszero(P)
R = Q;
elseif ELiszero(Q)
R = P;
else
p = EL.p;
xp = P(1);
yp = P(2);
xq = Q(1);
yq = Q(2);
d = xq-xp;
if d ~= 0
n = yq-yp;
else
if yp == yq
d = 2*yp;
n = 3*xp*xp + EL.a;
else % P == -Q
R = [Inf,Inf];
return
end
end
d = mod(d,p);
n = mod(n,p);
invd = itab(d); % [~,invd,~] = gcd(d,p);
lambda = mod(n*invd,p); % slope
xr = lambda*lambda - xp - xq;
xr = mod(xr,p);
yr = lambda*(xp-xr) - yp;
yr = mod(yr,p);
R = [xr, yr];
end
end
function b = ELiszero(P)
% Check if the EL point is null-element
b = any(~isfinite(P));
end
KSSV
on 23 Oct 2018
G=[1355,2421] ;
P = 1:1:5003 ;
Q = P'.*G ;
8 Comments
Walter Roberson
on 24 Oct 2018
Should the definition of s really divide by 2 and multiply the results by y, or should it be dividing by (2*y)?
Bruno Luong
on 23 Oct 2018
I reiterate my answer previously, you need first to program the "+" operator for EL, then doubling point 2*Q is simply Q "+" Q.
0 Comments
See Also
Categories
Find more on Special Values in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!