Is there any code or command for doubling a point ?

2018 10 23
5 个回答
回答已采纳
更新时间：2022 2 21
2 次查看（30 天）

0 个投票

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 个评论
显示 无 隐藏 无

madhan ravi
madhan ravi 2018-10-23
can you give a clear example?
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

1 个投票

% 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更早的评论 隐藏 4更早的评论

Bruno Luong
Bruno Luong 2018-10-24
The above is just doubling for you to start; If you want the rest you must code the operator (G "+" H) for any G and H in EC.
Maria Hameed
Maria Hameed 2018-10-24
sir, I want rest too please explain how can I code (G "+" H)
Bruno Luong
Bruno Luong 2018-10-24
I told you to start with your own coding and then ask question if you have issue.
I won't code the whole thing for you.
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

1 个投票

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更早的评论 隐藏 9更早的评论

Maria Hameed
Maria Hameed 2018-10-26
I run this code at Matlab I returns an error i.e Function definitions are not permitted in this context.
Bruno Luong
Bruno Luong 2018-10-26
You seem using older MATLAB release.
Then save the 3 functions p_inverse, EL_add, ELiszero in separate mfiles.
Maria Hameed
Maria Hameed 2018-10-26
Did you mean I write
{function ia = p_inverse(a, p) [~,ia] = gcd(a,p); end
function R = EL_add(P,Q,EL,itab)
function b = ELiszero(P)}
in separate m .files?
Bruno Luong
Bruno Luong 2018-10-26
Not at all. I don't know why and where you get an idea to put this curly bracket.
Do you know what is an mfile? A MATLAB script? A function? Have you ever working with MATLAB? Please read the Doc if it's not clear for you.
Maria Hameed
Maria Hameed 2018-10-26
yup I know m.file a Matlab script and i worked in Matlab
Bruno Luong
Bruno Luong 2018-10-26
编辑：Bruno Luong 2018-10-26
And function? Do you know how to put a function to an mfile?
Maria Hameed
Maria Hameed 2018-10-27
I don't know how to put a function to an mfile
Bruno Luong
Bruno Luong 2018-10-27
编辑：Bruno Luong 2018-10-27
Open MATLAB editor (type "edit" in command line)
Use the mouse copy one of the function above (from function ... to ... end closing the body) and past to the editor (the "Untitle" tab).
Click on [Save] button then when asked give the same name than the function name.
Do this for the three functions p_inverse, EL_add, ELiszero I instruct you.
Cut the functions text to keep just the calling commands in the script.
If you still have problem ask someone who knows MATLAB around you.
Ammy
Ammy 2022-2-21
Dear @Bruno Luong I have tried the above code for some larger p as compared to above defined p=5003,
I have tried the following
for p=100019, a=0 , b=2, the above code generates all the point correctly, there is no issue.
But in any of the following I couldn't generate the correct points,
  1. p=957221, a=0 , b=2, its generator G=(762404,61090)
  2. p=997247, a=0 , b=2, its generator G=(386850,53128)
May I request for your help in this regard?
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

0 个投票

G=[1355,2421] ;
P = 1:1:5003 ;
Q = P'.*G ;

8 个评论
显示 6更早的评论 隐藏 6更早的评论

Maria Hameed
Maria Hameed 2018-10-23
an error occurs in last statement of code
KSSV
KSSV 2018-10-23
It is not showing any error in my pc.
KSSV
KSSV 2018-10-23
G=[1355,2421] ;
P = 1:1:5003 ;
Q = zeros(numel(P),2) ;
for i = 1:numel(P)
Q(i,:) = P(i)*G ;
end
Maria Hameed
Maria Hameed 2018-10-24
this code simply multiplies values I need point multiplication like in elliptic curves
Maria Hameed
Maria Hameed 2018-10-24
E:y^2=x^3+a*x+b under some mod p suppose if I have a point as G=(x,y) then we find 2*G by the following process : s=(3*x^2+a)/2*y , x1=s^2-2x , y1=s*(x-x1)-y , after passing through this process we get our doubled point as 2*G=(x1,y1)
Maria Hameed
Maria Hameed 2018-10-24
My target is to achieve such 2G, 3G, 4G,.... 5003G by considering the result of the first iteration to obtain the next result
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

0 个投票

double(points) %like this?

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Maria Hameed
Maria Hameed 2018-10-24
yup note that this point doubling is of elliptic curve not simple point multiplication

请先登录，再进行评论。

Bruno Luong
Bruno Luong 2018-10-23

0 个投票

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

类别

在 帮助中心 和 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