search

miracl / MIRACL

MIRACL Cryptographic SDK: Multiprecision Integer and Rational Arithmetic Cryptographic Library is a C software library that is widely regarded by developers as the gold standard open source SDK for elliptic curve cryptography (ECC).
https://miracl.com
638 stars 241 forks source link

Problem recreating the points on the curve using get_point() and set() function #48

Closed manujain006 closed 7 years ago

manujain006 commented 7 years ago

Issue is in line number 449. I am trying to recreate the server and Alice points but it is not creating the exact same points. `/*

Scott's AKE Client/Server testbed

See http://eprint.iacr.org/2002/164

Compile as cl /O2 /GX /DZZNS=16 ake2cpt.cpp zzn2.cpp big.cpp zzn.cpp ecn.cpp miracl.lib using COMBA build

Cocks-Pinch curve - Tate Pairing

Requires file k2.ecs which contains details of non-supersingular elliptic curve, with order divisible by q=2^159+2^17+1, and security multiplier k=2. The prime p is 512 bits

CHANGES: Use twisted curve to avoid ECn2 arithmetic completely Use Lucas functions to evaluate powers. Output of tate pairing is now a ZZn (half-size)

Modified to prevent sub-group confinement attack

Speeded up using ideas from "Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields" by Sanjit Chatterjee1, Palash Sarkar1 and Rana Barua1

*/

include

include

include "ecn.h"

include

include "zzn2.h"

include

include

include <sys/types.h>

include

include

include

include

include

include

include <sys/socket.h> // For the socket (), bind () etc. functions.

include <netinet/in.h> // For IPv4 data struct..

include // For memset.

include <arpa/inet.h> // For inet_pton (), inet_ntop ().

include

include

include <sys/stat.h>

include

include

include

include

using namespace std;

Miracl precision(16,0);

// Using SHA-512 as basic hash algorithm

define HASH_LEN 64

// // Define one or the other of these // // Which is faster depends on the I/M ratio - See imratio.c // Roughly if I/M ratio > 16 use PROJECTIVE, otherwise use AFFINE //

ifdef MR_AFFINE_ONLY

#define AFFINE

else

#define PROJECTIVE

endif

// // Tate Pairing Code // // Extract ECn point in internal ZZn format //

void extract(ECn& A,ZZn& x,ZZn& y) { x=(A.get_point())->X; y=(A.get_point())->Y; }

ifdef PROJECTIVE

void extract(ECn& A,ZZn& x,ZZn& y,ZZn& z) { big t; x=(A.get_point())->X; y=(A.get_point())->Y; t=(A.get_point())->Z; if (A.get_status()!=MR_EPOINT_GENERAL) z=1; else z=t; }

endif

// // Line from A to destination C. Let A=(x,y) // Line Y-slope.X-c=0, through A, so intercept c=y-slope.x // Line Y-slope.X-y+slope.x = (Y-y)-slope.(X-x) = 0 // Now evaluate at Q -> return (Qy-y)-slope.(Qx-x) //

ZZn2 line(ECn& A,ECn& C,ECn& B,int type,ZZn& slope,ZZn& ex1,ZZn& ex2,ZZn& a,ZZn& d) { ZZn2 w; ZZn n=a;

ifdef AFFINE

ZZn x,y;
extract(A,x,y);
n+=x; n*=slope;  
w.set(y,-d); w-=n;

endif

ifdef PROJECTIVE

 if (type==MR_ADD)
 {
    ZZn x2,y2,x3,z3;
    extract(B,x2,y2);
    extract(C,x3,x3,z3);
    w.set(slope*(a+x2)-z3*y2,z3*d);
 } 
 if (type==MR_DOUBLE)
 {
    ZZn x,y,x3,z3;
    extract(A,x,y);
    extract(C,x3,x3,z3);
    w.set(-(slope*ex2)*a-slope*x+ex1,-(z3*ex2)*d);
 }

/ extract(A,x,y,z); x=z; t=z; z=z; z=t; n=z; n+=x;
z=d; w.set(y,-z); extract(C,x,y,z); // only need z - its the denominator of the slope w=z; n=slope; w-=n;
*/

endif

return w;

}

// // Add A=A+B (or A=A+A) // Bump up num //

ZZn2 g(ECn& A,ECn& B,ZZn& a,ZZn& d) { int type; ZZn lam,extra1,extra2; ECn P=A; big ptr,ex1,ex2;

// Evaluate line from A - lam is line slope type=A.add(B,&ptr,&ex1,&ex2); if (!type) return (ZZn2)1; lam=ptr; // in projective case slope = lam/A.z extra1=ex1; extra2=ex2;

return line(P,A,B,type,lam,extra1,extra2,a,d);

}

// // Tate Pairing - note denominator elimination has been applied // // P is a point of order q. Q(x,y) is a point of order q. // Note that P is a point on the curve over Fp, Q(x,y) a point on the // curve E(Fp^2) -> Q([Qx,0],[0,Qy]) // Here we have morphed Q onto the twisted curve E'(Fp) //

BOOL tate(ECn& P,ECn& Q,Big& q,ZZn& r) { int i,nb,qnr; ZZn2 res; ZZn a,d; Big p,x,y,n; ECn A;

p=get_modulus();

// Note that q is fixed - q.P=2^17*(2^142.P + P) + P

normalise(P);
normalise(Q);  // make sure z=1
extract(Q,a,d);

qnr=get_mip()->qnr;
if (qnr==-2)
{
    a=a/2;   /* Convert off twist */
    d=d/4;
}

A=P;           // remember A

n=q-1;
nb=bits(n);

res=1;

for (i=nb-2;i>=0;i--)
{
    res*=res;    // 2 modmul
    res*=g(A,A,a,d); 

    if (bit(n,i)) 
        res*=g(A,P,a,d);  // executed just once
}

if (A != -P || res.iszero()) return FALSE;

res=conj(res)/res;          // raise to power of (p-1)

r=powl(real(res),(p+1)/q);  // raise to power of (p+1)/q

if (r==1) return FALSE;
return TRUE;

}

/* void rmul(ECn& P,Big &q) { Big n; ECn A; int i,nb;

A=P;  
n=q-1;
nb=bits(n);

for (i=nb-2;i>=0;i--)
{
    A.add(A); 
    if (bit(n,i))
        A.add(P);
}

} */

// // Hash functions //

Big H1(char *string) { // Hash a zero-terminated string to a number < modulus Big h,p; char s[HASH_LEN]; int i,j; sha512 sh;

shs512_init(&sh);

for (i=0;;i++)
{
    if (string[i]==0) break;
    shs512_process(&sh,string[i]);
}
shs512_hash(&sh,s);
p=get_modulus();
h=1; j=0; i=1;
forever
{
    h*=256; 
    if (j==HASH_LEN)  {h+=i++; j=0;}
    else         h+=s[j++];
    if (h>=p) break;
}
h%=p;
return h;

}

Big H2(ZZn x) { // Hash an Fp to a big number sha sh; Big a,h,p; char s[20]; int m;

shs_init(&sh);
a=(Big)x;
while (a>0)
{
    m=a%256;
    shs_process(&sh,m);
    a/=256;
}
shs_hash(&sh,s);
h=from_binary(20,s);
return h;

}

// Hash an Identity to a curve point in G2

ECn Hash(char *ID) { ECn T; Big a=H1(ID);

while (!is_on_curve(a)) a+=1;
T.set(a);  // Make sure its on E(F_p)

return T;

}

// Hash an Identity to a curve point and map to point of order q in G1

ECn hash_and_map(char *ID,Big cof) { ECn T; Big a=H1(ID);

while (!is_on_curve(a)) a+=1;
T.set(a);

T*=cof;

return T;

}

/ Note that if #E(Fp) = p+1-t then #E(Fp2) = (p+1-t)(p+1+t) (a multiple of #E(Fp)) (Weil's Theorem) /

int main() { ifstream common("k2.ecs"); // elliptic curve parameters miracl mip=&precision; ECn Alice,Bob,sA,sB,Alice1; ECn Server,sS,Server1; ZZn res,res1,res2,res3,sp,ap,bp,sx,sy,ax,ay; Big r,a,b,s,ss,p,q,x,y,B,cof,ax1; int i,nbits,A,qnr; time_t seed; time_t start_time, end_time; common >> nbits; mip->IOBASE=16; common >> p; common >> A; common >> B; common >> cof; common >> q; // number of points on curve = cofq

time(&seed);
irand((long)seed);

// // initialise twisted curve for points in G2 // Server ID is hashed to points on this //

modulo(p);
qnr=mip->qnr;

ifdef AFFINE

ecurve(qnr*qnr*A,qnr*qnr*qnr*B,p,MR_AFFINE);

endif

ifdef PROJECTIVE

ecurve(qnr*qnr*A,qnr*qnr*qnr*B,p,MR_PROJECTIVE);

endif

mip->IOBASE=16;

// hash Identity to curve point in G2 // Server does not need to be of order q (its order is a multiple of q)

ss=rand(q);    // TA's super-secret 

cout << "Mapping Server ID to point on twisted curve" << endl;
Server=Hash((char *)"SERVER");

cout << "Server= " << Server << endl; cout << "Servercof= " << (2(p+1)-cofq)Server << endl;

cout << "Server visits trusted authority" << endl;
sS=ss*Server;

// initialise curve for points in G1

ifdef AFFINE

ecurve(A,B,p,MR_AFFINE);

endif

ifdef PROJECTIVE

ecurve(A,B,p,MR_PROJECTIVE);

endif

cout << "Mapping Alice & Bob ID's to points on curve" << endl;

Alice=hash_and_map((char *)"Alice",cof);
Bob=  hash_and_map((char *)"Robert",cof);

sA = ss*Alice;

tate(sA,Server,q,res);

sx = Server.get_point()->X;
sy = Server.get_point()->Y;
ax = Alice.get_point()->X;
ay = Alice.get_point()->Y;

// // initialise twisted curve for points in G2 // Server ID is hashed to points on this //

modulo(p);
qnr=mip->qnr;

ifdef AFFINE

ecurve(qnr*qnr*A,qnr*qnr*qnr*B,p,MR_AFFINE);

endif

ifdef PROJECTIVE

ecurve(qnr*qnr*A,qnr*qnr*qnr*B,p,MR_PROJECTIVE);

endif

mip->IOBASE=16;

Server1.set(sx,sy);

// initialise curve for points in G1

ifdef AFFINE

ecurve(A,B,p,MR_AFFINE);

endif

ifdef PROJECTIVE

ecurve(A,B,p,MR_PROJECTIVE);

endif

Alice1.set(ax,ay);

ax = Alice1.get_point()->X;
ax1 = Alice.get_point()->X; 

cout<<endl<<"Alice X: "<<ax1<<endl<<"Alice1 X: "<<ax<<endl; //They are not same - This is the issue.

sA = ss*Alice1;

tate(sA,Server1,q,res1);

cout<<endl<<"res: "<<res;
cout<<endl<<"res1: "<<res1;
cout<<endl; 

return 0;

} ake2cpt.cpp.zip

`

mcarrickscott commented 7 years ago

Hello Manu,

You have ax1 as a Big. Should be a ZZn

Mike

On Mon, Jun 26, 2017 at 10:20 AM, Manu Jain notifications@github.com wrote:

Issue is in line number 449. I am trying to recreate the server and Alice points but it is not creating the exact same points. `/*

Scott's AKE Client/Server testbed

See http://eprint.iacr.org/2002/164

Compile as cl /O2 /GX /DZZNS=16 ake2cpt.cpp zzn2.cpp big.cpp zzn.cpp ecn.cpp miracl.lib using COMBA build

Cocks-Pinch curve - Tate Pairing

Requires file k2.ecs which contains details of non-supersingular elliptic curve, with order divisible by q=2^159+2^17+1, and security multiplier k=2. The prime p is 512 bits

CHANGES: Use twisted curve to avoid ECn2 arithmetic completely Use Lucas functions to evaluate powers. Output of tate pairing is now a ZZn (half-size)

Modified to prevent sub-group confinement attack

Speeded up using ideas from "Efficient Computation of Tate Pairing in Projective Coordinate over General Characteristic Fields" by Sanjit Chatterjee1, Palash Sarkar1 and Rana Barua1

*/

include

include

include "ecn.h"

include

include "zzn2.h"

include

include

include <sys/types.h>

include

include

include

include

include

include

include <sys/socket.h> // For the socket (), bind () etc. functions.

include <netinet/in.h> // For IPv4 data struct..

include // For memset.

include <arpa/inet.h> // For inet_pton (), inet_ntop ().

include

include

include <sys/stat.h>

include

include

include

include

using namespace std;

Miracl precision(16,0);

// Using SHA-512 as basic hash algorithm

define HASH_LEN 64

// // Define one or the other of these // // Which is faster depends on the I/M ratio - See imratio.c // Roughly if I/M ratio > 16 use PROJECTIVE, otherwise use AFFINE //

ifdef MR_AFFINE_ONLY

define AFFINE

else

define PROJECTIVE

endif

// // Tate Pairing Code // // Extract ECn point in internal ZZn format //

void extract(ECn& A,ZZn& x,ZZn& y) { x=(A.get_point())->X; y=(A.get_point())->Y; }

ifdef PROJECTIVE

void extract(ECn& A,ZZn& x,ZZn& y,ZZn& z) { big t; x=(A.get_point())->X; y=(A.get_point())->Y; t=(A.get_point())->Z; if (A.get_status()!=MR_EPOINT_GENERAL) z=1; else z=t; }

endif

// // Line from A to destination C. Let A=(x,y) // Line Y-slope.X-c=0, through A, so intercept c=y-slope.x // Line Y-slope.X-y+slope.x = (Y-y)-slope.(X-x) = 0 // Now evaluate at Q -> return (Qy-y)-slope.(Qx-x) //

ZZn2 line(ECn& A,ECn& C,ECn& B,int type,ZZn& slope,ZZn& ex1,ZZn& ex2,ZZn& a,ZZn& d) { ZZn2 w; ZZn n=a;

ifdef AFFINE

ZZn x,y; extract(A,x,y); n+=x; n*=slope; w.set(y,-d); w-=n;

endif

ifdef PROJECTIVE

if (type==MR_ADD) { ZZn x2,y2,x3,z3; extract(B,x2,y2); extract(C,x3,x3,z3); w.set(slope(a+x2)-z3y2,z3d); } if (type==MR_DOUBLE) { ZZn x,y,x3,z3; extract(A,x,y); extract(C,x3,x3,z3); w.set(-(slopeex2)a-slopex+ex1,-(z3*ex2)

d); } / extract(A,x,y,z); x=z; t=z; z=z; z=t; n=z; n+=x; z=d; w.set(y,-z); extract(C,x,y,z); // only need z - its the denominator of the slope w=z; n=slope; w-=n; /

endif

return w;

}

// // Add A=A+B (or A=A+A) // Bump up num //

ZZn2 g(ECn& A,ECn& B,ZZn& a,ZZn& d) { int type; ZZn lam,extra1,extra2; ECn P=A; big ptr,ex1,ex2;

// Evaluate line from A - lam is line slope type=A.add(B,&ptr,&ex1,&ex2); if (!type) return (ZZn2)1; lam=ptr; // in projective case slope = lam/A.z extra1=ex1; extra2=ex2;

return line(P,A,B,type,lam,extra1,extra2,a,d);

}

// // Tate Pairing - note denominator elimination has been applied // // P is a point of order q. Q(x,y) is a point of order q. // Note that P is a point on the curve over Fp, Q(x,y) a point on the // curve E(Fp^2) -> Q([Qx,0],[0,Qy]) // Here we have morphed Q onto the twisted curve E'(Fp) //

BOOL tate(ECn& P,ECn& Q,Big& q,ZZn& r) { int i,nb,qnr; ZZn2 res; ZZn a,d; Big p,x,y,n; ECn A;

p=get_modulus();

// Note that q is fixed - q.P=2^17*(2^142.P + P) + P

normalise(P); normalise(Q); // make sure z=1 extract(Q,a,d);

qnr=get_mip()->qnr; if (qnr==-2) { a=a/2; / Convert off twist / d=d/4; }

A=P; // remember A

n=q-1; nb=bits(n);

res=1;

for (i=nb-2;i>=0;i--) { res=res; // 2 modmul res=g(A,A,a,d);

if (bit(n,i))
    res*=g(A,P,a,d);  // executed just once

}

if (A != -P || res.iszero()) return FALSE;

res=conj(res)/res; // raise to power of (p-1)

r=powl(real(res),(p+1)/q); // raise to power of (p+1)/q

if (r==1) return FALSE; return TRUE;

}

/* void rmul(ECn& P,Big &q) { Big n; ECn A; int i,nb;

A=P; n=q-1; nb=bits(n);

for (i=nb-2;i>=0;i--) { A.add(A); if (bit(n,i)) A.add(P); }

} */

// // Hash functions //

Big H1(char *string) { // Hash a zero-terminated string to a number < modulus Big h,p; char s[HASH_LEN]; int i,j; sha512 sh;

shs512_init(&sh);

for (i=0;;i++) { if (string[i]==0) break; shs512_process(&sh,string[i]); } shs512_hash(&sh,s); p=get_modulus(); h=1; j=0; i=1; forever { h*=256; if (j==HASH_LEN) {h+=i++; j=0;} else h+=s[j++]; if (h>=p) break; } h%=p; return h;

}

Big H2(ZZn x) { // Hash an Fp to a big number sha sh; Big a,h,p; char s[20]; int m;

shs_init(&sh); a=(Big)x; while (a>0) { m=a%256; shs_process(&sh,m); a/=256; } shs_hash(&sh,s); h=from_binary(20,s); return h;

}

// Hash an Identity to a curve point in G2

ECn Hash(char *ID) { ECn T; Big a=H1(ID);

while (!is_on_curve(a)) a+=1; T.set(a); // Make sure its on E(F_p)

return T;

}

// Hash an Identity to a curve point and map to point of order q in G1

ECn hash_and_map(char *ID,Big cof) { ECn T; Big a=H1(ID);

while (!is_on_curve(a)) a+=1; T.set(a);

T*=cof;

return T;

}

/ Note that if #E(Fp) = p+1-t then #E(Fp2) = (p+1-t)(p+1+t) (a multiple of #E(Fp)) (Weil's Theorem) /

int main() { ifstream common("k2.ecs"); // elliptic curve parameters miracl mip=&precision; ECn Alice,Bob,sA,sB,Alice1; ECn Server,sS,Server1; ZZn res,res1,res2,res3,sp,ap,bp,sx,sy,ax,ay; Big r,a,b,s,ss,p,q,x,y,B,cof,ax1; int i,nbits,A,qnr; time_t seed; time_t start_time, end_time; common >> nbits; mip->IOBASE=16; common >> p; common >> A; common >> B; common >> cof; common >> q; // number of points on curve = cofq

time(&seed); irand((long)seed);

// // initialise twisted curve for points in G2 // Server ID is hashed to points on this //

modulo(p); qnr=mip->qnr;

ifdef AFFINE

ecurve(qnrqnrA,qnrqnrqnr

B,p,MR_AFFINE); #endif #ifdef PROJECTIVE ecurve(qnrqnrA,qnrqnrqnr B,p,MR_PROJECTIVE);

endif

mip->IOBASE=16;

// hash Identity to curve point in G2 // Server does not need to be of order q (its order is a multiple of q)

ss=rand(q); // TA's super-secret

cout << "Mapping Server ID to point on twisted curve" << endl; Server=Hash((char *)"SERVER");

cout << "Server= " << Server << endl; cout << "Servercof= " << (2(p+1)-cofq)Server << endl;

cout << "Server visits trusted authority" << endl; sS=ss*Server;

// initialise curve for points in G1

ifdef AFFINE

ecurve(A,B,p,MR_AFFINE);

endif

ifdef PROJECTIVE

ecurve(A,B,p,MR_PROJECTIVE);

endif

cout << "Mapping Alice & Bob ID's to points on curve" << endl;

Alice=hash_and_map((char )"Alice",cof); Bob= hash_and_map((char )"Robert",cof);

sA = ss*Alice;

tate(sA,Server,q,res);

sx = Server.get_point()->X; sy = Server.get_point()->Y; ax = Alice.get_point()->X; ay = Alice.get_point()->Y;

// // initialise twisted curve for points in G2 // Server ID is hashed to points on this //

modulo(p); qnr=mip->qnr;

ifdef AFFINE

ecurve(qnrqnrA,qnrqnrqnr

B,p,MR_AFFINE); #endif #ifdef PROJECTIVE ecurve(qnrqnrA,qnrqnrqnr B,p,MR_PROJECTIVE);

endif

mip->IOBASE=16;

Server1.set(sx,sy);

// initialise curve for points in G1

ifdef AFFINE

ecurve(A,B,p,MR_AFFINE);

endif

ifdef PROJECTIVE

ecurve(A,B,p,MR_PROJECTIVE);

endif

Alice1.set(ax,ay);

ax = Alice1.get_point()->X; ax1 = Alice.get_point()->X;

cout<<endl<<"Alice X: "<<ax1<<endl<<"Alice1 X: "<<ax<<endl; //They are not same - This is the issue.

sA = ss*Alice1;

tate(sA,Server1,q,res1);

cout<<endl<<"res: "<<res; cout<<endl<<"res1: "<<res1; cout<<endl;

return 0;

} ake2cpt.cpp.zip https://github.com/miracl/MIRACL/files/1101601/ake2cpt.cpp.zip

`

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/miracl/MIRACL/issues/48, or mute the thread https://github.com/notifications/unsubscribe-auth/ACm8jjhrusoe_SioynBpLF5yrE0ncywMks5sH3figaJpZM4OFEAn .

manujain006 commented 7 years ago

screenshot from 2017-06-27 15-03-38 Thank You Mike, I tried it but still doesn't work. res and res1 are not same at the end of the program. The problem might be the point Alice1 which is coming to be infinity. I have attached a snapshot of the output of the code. You can notice the above explained two problems here.

mcarrickscott commented 7 years ago

OK, problem is you should be using

Big ax,bx;

Alice.get(&ax,&bx);

to get the true x and y coordinates of Alice.

The get_point() method extracts the raw X and Y coordinates from the internal projective representation (X,Y,Z);

In fact x=X/(ZZ), y=Y/(ZZ*Z);

so X and Y are not the same as x and y.

Mike

On Tue, Jun 27, 2017 at 10:51 AM, Manu Jain notifications@github.com wrote:

Thank You Mike, I tried it but still doesn't work. res and res1 are not same at the end of the program. The problem might be the point Alice1 which is coming to be infinity.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/miracl/MIRACL/issues/48#issuecomment-311310203, or mute the thread https://github.com/notifications/unsubscribe-auth/ACm8jnOEz8ypcd9cMDyNN4vYzHDjL62tks5sINCWgaJpZM4OFEAn .

manujain006 commented 7 years ago

Thanks a lot Mike, This worked for me and the problem is solved. Thank You again.