Is there any code or command for doubling a point ?

10 次查看（过去 30 天）
Maria Hameed
Maria Hameed 2018-10-23
评论： Ammy 2022-2-21
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 个评论
Maria Hameed
Maria Hameed 2018-10-23
input:(G,2G,3G,4G,....5003G) output:[(1355,2421),(533,2804),(4896,1633),(2822,532),.....,(1329,2633)]

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Bruno Luong
Bruno Luong 2018-10-24
% 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 个评论
显示 4更早的评论
Maria Hameed
Maria Hameed 2018-10-26
% EL parameters a = 148 b = 225 % Group Z/pZ parameter p = 5003 % Point for i=1:256 Gi = [1355,2421]; % Compute G(i+1) = 2*Gi xi = Gi(1); yi = Gi(2); d = mod(2*yi,p); [~,invd,~] = gcd(d,p); n = mod(3*xi*xi + a,p); lambda = mod(n*invd,p); x2 = mod(lambda*lambda - 2*xi,p); y2 = mod(lambda*(xi-x(i+1))-y,p); G(i+1) = [x(i+1) y(i+1)]
% Compute G(i+2) = G(i+1)+Gi
d1 = mod((x(i+1)-xi),p); [~,invd,~] = gcd(d1,p); n1 = mod((y(i+1)-yi),p); lambda = mod(n1*invd,p); x(i+2) = mod(lambda*lambda - x-x(i+1),p); y(i+2) = mod(lambda*(x-x(i+2))-y,p); G(i+2) = [x(i+2) y(i+2)] end for sir how can I combine theses codes for point doubling ?
Bruno Luong
Bruno Luong 2018-10-26
Your code is incomplete, isn't it? I post the answer below.

请先登录，再进行评论。

更多回答（4 个）

Bruno Luong
Bruno Luong 2018-10-26
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 个评论
显示 9更早的评论
Bruno Luong
Bruno Luong 2022-2-21
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
KSSV 2018-10-23
G=[1355,2421] ;
P = 1:1:5003 ;
Q = P'.*G ;
  8 个评论
显示 6更早的评论
Walter Roberson
Walter Roberson 2018-10-24
Should the definition of s really divide by 2 and multiply the results by y, or should it be dividing by (2*y)?
Maria Hameed
Maria Hameed 2018-10-24
it should divide (2*y) and this is actually as s=[(3*x^2+a)modp]*[(2*y)^-1 mod p] and inverse of (2*y) should be found by extended euclidean algo

请先登录，再进行评论。

madhan ravi
madhan ravi 2018-10-23
double(points) %like this?
Bruno Luong
Bruno Luong 2018-10-23
I reiterate my answer previously, you need first to program the "+" operator for EL, then doubling point 2*Q is simply Q "+" Q.
Formula for addition in EC group in the section Elliptic Curves over Zp of this document

类别

在 Help Center 和 File Exchange 中查找有关 Special Values 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by