Is there any code or command for doubling a point ?

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)

[madhan ravi]

can you give a clear example?

[Maria Hameed]

input:(G,2G,3G,4G,....5003G) output:[(1355,2421),(533,2804),(4896,1633),(2822,532),.....,(1329,2633)]

Answer 1

[Bruno Luong]

% 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

[Bruno Luong]

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]

sir, I want rest too please explain how can I code (G "+" H)

[Bruno Luong]

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]

ok thanks for this

[Maria Hameed]

% 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]

Your code is incomplete, isn't it? I post the answer below.

Answer 2

[Bruno Luong]

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

[Maria Hameed]

I run this code at Matlab I returns an error i.e Function definitions are not permitted in this context.

[Bruno Luong]

You seem using older MATLAB release.

Then save the 3 functions p_inverse, EL_add, ELiszero in separate mfiles.

[Maria Hameed]

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]

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]

yup I know m.file a Matlab script and i worked in Matlab

[Bruno Luong]

And function? Do you know how to put a function to an mfile?

[Maria Hameed]

I don't know how to put a function to an mfile

[Bruno Luong]

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]

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]

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

[Ammy]

Thank you very much@Bruno Luong.

Answer 3

[KSSV]

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

[Maria Hameed]

an error occurs in last statement of code

[KSSV]

It is not showing any error in my pc.

[KSSV]

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]

this code simply multiplies values I need point multiplication like in elliptic curves

[Maria Hameed]

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]

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]

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]

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

Answer 4

[madhan ravi]

double(points) %like this?

[Maria Hameed]

yup note that this point doubling is of elliptic curve not simple point multiplication

Answer 5

[Bruno Luong]

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