http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pair.c ---------------------------------------------------------------------- diff --git a/version3/c/pair.c b/version3/c/pair.c new file mode 100644 index 0000000..57cad56 --- /dev/null +++ b/version3/c/pair.c @@ -0,0 +1,808 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* AMCL BN Curve pairing functions */ + +//#define HAS_MAIN + +#include "pair_ZZZ.h" + +/* Line function */ +static void PAIR_ZZZ_line(FP12_YYY *v,ECP2_ZZZ *A,ECP2_ZZZ *B,FP_YYY *Qx,FP_YYY *Qy) +{ + FP2_YYY X1,Y1,T1,T2; + FP2_YYY XX,YY,ZZ,YZ; + FP4_YYY a,b,c; + + if (A==B) + { + /* doubling */ + FP2_YYY_copy(&XX,&(A->x)); //FP2 XX=new FP2(A.getx()); //X + FP2_YYY_copy(&YY,&(A->y)); //FP2 YY=new FP2(A.gety()); //Y + FP2_YYY_copy(&ZZ,&(A->z)); //FP2 ZZ=new FP2(A.getz()); //Z + + + FP2_YYY_copy(&YZ,&YY); //FP2 YZ=new FP2(YY); //Y + FP2_YYY_mul(&YZ,&YZ,&ZZ); //YZ.mul(ZZ); //YZ + FP2_YYY_sqr(&XX,&XX); //XX.sqr(); //X^2 + FP2_YYY_sqr(&YY,&YY); //YY.sqr(); //Y^2 + FP2_YYY_sqr(&ZZ,&ZZ); //ZZ.sqr(); //Z^2 + + FP2_YYY_imul(&YZ,&YZ,4); //YZ.imul(4); + FP2_YYY_neg(&YZ,&YZ); //YZ.neg(); + FP2_YYY_norm(&YZ); //YZ.norm(); //-4YZ + + FP2_YYY_imul(&XX,&XX,6); //6X^2 + FP2_YYY_pmul(&XX,&XX,Qx); //6X^2.Xs + + FP2_YYY_imul(&ZZ,&ZZ,3*CURVE_B_I_ZZZ); //3Bz^2 + + FP2_YYY_pmul(&YZ,&YZ,Qy); //-4YZ.Ys + +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_YYY_div_ip2(&ZZ); //6(b/i)z^2 +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_mul_ip(&ZZ); + FP2_YYY_add(&ZZ,&ZZ,&ZZ); // 6biz^2 + FP2_YYY_mul_ip(&YZ); + FP2_YYY_norm(&YZ); +#endif + FP2_YYY_norm(&ZZ); // 6bi.Z^2 + + FP2_YYY_add(&YY,&YY,&YY); // 2y^2 + FP2_YYY_sub(&ZZ,&ZZ,&YY); // + FP2_YYY_norm(&ZZ); // 6b.Z^2-2Y^2 + + FP4_YYY_from_FP2s(&a,&YZ,&ZZ); // -4YZ.Ys | 6b.Z^2-2Y^2 | 6X^2.Xs +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP4_YYY_from_FP2(&b,&XX); + FP4_YYY_zero(&c); +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP4_YYY_zero(&b); + FP4_YYY_from_FP2H(&c,&XX); +#endif + + ECP2_ZZZ_dbl(A); //A.dbl(); + } + else + { + /* addition */ + + FP2_YYY_copy(&X1,&(A->x)); //FP2 X1=new FP2(A.getx()); // X1 + FP2_YYY_copy(&Y1,&(A->y)); //FP2 Y1=new FP2(A.gety()); // Y1 + FP2_YYY_copy(&T1,&(A->z)); //FP2 T1=new FP2(A.getz()); // Z1 + + FP2_YYY_copy(&T2,&T1); //FP2 T2=new FP2(A.getz()); // Z1 + + FP2_YYY_mul(&T1,&T1,&(B->y)); //T1.mul(B.gety()); // T1=Z1.Y2 + FP2_YYY_mul(&T2,&T2,&(B->x)); //T2.mul(B.getx()); // T2=Z1.X2 + + FP2_YYY_sub(&X1,&X1,&T2); //X1.sub(T2); + FP2_YYY_norm(&X1); //X1.norm(); // X1=X1-Z1.X2 + FP2_YYY_sub(&Y1,&Y1,&T1); //Y1.sub(T1); + FP2_YYY_norm(&Y1); //Y1.norm(); // Y1=Y1-Z1.Y2 + + FP2_YYY_copy(&T1,&X1); //T1.copy(X1); // T1=X1-Z1.X2 + + FP2_YYY_pmul(&X1,&X1,Qy); //X1.pmul(Qy); // X1=(X1-Z1.X2).Ys +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_mul_ip(&X1); + FP2_YYY_norm(&X1); +#endif + + FP2_YYY_mul(&T1,&T1,&(B->y)); //T1.mul(B.gety()); // T1=(X1-Z1.X2).Y2 + + FP2_YYY_copy(&T2,&Y1); //T2.copy(Y1); // T2=Y1-Z1.Y2 + FP2_YYY_mul(&T2,&T2,&(B->x)); //T2.mul(B.getx()); // T2=(Y1-Z1.Y2).X2 + FP2_YYY_sub(&T2,&T2,&T1); //T2.sub(T1); + FP2_YYY_norm(&T2); //T2.norm(); // T2=(Y1-Z1.Y2).X2 - (X1-Z1.X2).Y2 + FP2_YYY_pmul(&Y1,&Y1,Qx); //Y1.pmul(Qx); + FP2_YYY_neg(&Y1,&Y1); //Y1.neg(); + FP2_YYY_norm(&Y1); //Y1.norm(); // Y1=-(Y1-Z1.Y2).Xs + + FP4_YYY_from_FP2s(&a,&X1,&T2); // (X1-Z1.X2).Ys | (Y1-Z1.Y2).X2 - (X1-Z1.X2).Y2 | - (Y1-Z1.Y2).Xs +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP4_YYY_from_FP2(&b,&Y1); //b=new FP4(Y1); + FP4_YYY_zero(&c); +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP4_YYY_zero(&b); + FP4_YYY_from_FP2H(&c,&Y1); //b=new FP4(Y1); +#endif + ECP2_ZZZ_add(A,B); //A.add(B); + } + + FP12_YYY_from_FP4s(v,&a,&b,&c); +} + +/* Optimal R-ate pairing r=e(P,Q) */ +void PAIR_ZZZ_ate(FP12_YYY *r,ECP2_ZZZ *P1,ECP_ZZZ *Q1) +{ + + BIG_XXX x,n,n3; + FP_YYY Qx,Qy; + int i,nb,bt; + ECP2_ZZZ A,NP,P; + ECP_ZZZ Q; + FP12_YYY lv; +#if PAIRING_FRIENDLY_ZZZ==BN + ECP2_ZZZ KA; + FP2_YYY X; + + FP_YYY_rcopy(&Qx,Fra_YYY); + FP_YYY_rcopy(&Qy,Frb_YYY); + FP2_YYY_from_FPs(&X,&Qx,&Qy); + +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_inv(&X,&X); + FP2_YYY_norm(&X); +#endif +#endif + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + +#if PAIRING_FRIENDLY_ZZZ==BN + BIG_XXX_pmul(n,x,6); +#if SIGN_OF_X_ZZZ==POSITIVEX + BIG_XXX_inc(n,2); +#else + BIG_XXX_dec(n,2); +#endif +#else + BIG_XXX_copy(n,x); +#endif + + BIG_XXX_norm(n); + BIG_XXX_pmul(n3,n,3); + BIG_XXX_norm(n3); + + ECP2_ZZZ_copy(&P,P1); + ECP_ZZZ_copy(&Q,Q1); + + ECP2_ZZZ_affine(&P); + ECP_ZZZ_affine(&Q); + + FP_YYY_copy(&Qx,&(Q.x)); + FP_YYY_copy(&Qy,&(Q.y)); + + ECP2_ZZZ_copy(&A,&P); + ECP2_ZZZ_copy(&NP,&P); ECP2_ZZZ_neg(&NP); + + FP12_YYY_one(r); + nb=BIG_XXX_nbits(n3); //n + + /* Main Miller Loop */ + for (i=nb-2; i>=1; i--) //0 + { + FP12_YYY_sqr(r,r); + PAIR_ZZZ_line(&lv,&A,&A,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + bt=BIG_XXX_bit(n3,i)-BIG_XXX_bit(n,i); + if (bt==1) + { + + PAIR_ZZZ_line(&lv,&A,&P,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + if (bt==-1) + { + PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + + } + + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP12_YYY_conj(r,r); +#endif + + /* R-ate fixup required for BN curves */ +#if PAIRING_FRIENDLY_ZZZ==BN + ECP2_ZZZ_copy(&KA,&P); + ECP2_ZZZ_frob(&KA,&X); +#if SIGN_OF_X_ZZZ==NEGATIVEX + ECP2_ZZZ_neg(&A); +#endif + PAIR_ZZZ_line(&lv,&A,&KA,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + ECP2_ZZZ_frob(&KA,&X); + ECP2_ZZZ_neg(&KA); + PAIR_ZZZ_line(&lv,&A,&KA,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); +#endif +} + +/* Optimal R-ate double pairing e(P,Q).e(R,S) */ +void PAIR_ZZZ_double_ate(FP12_YYY *r,ECP2_ZZZ *P1,ECP_ZZZ *Q1,ECP2_ZZZ *R1,ECP_ZZZ *S1) +{ + BIG_XXX x,n,n3; + FP_YYY Qx,Qy,Sx,Sy; + int i,nb,bt; + ECP2_ZZZ A,B,NP,NR,P,R; + ECP_ZZZ Q,S; + FP12_YYY lv; +#if PAIRING_FRIENDLY_ZZZ==BN + FP2_YYY X; + ECP2_ZZZ K; + + FP_YYY_rcopy(&Qx,Fra_YYY); + FP_YYY_rcopy(&Qy,Frb_YYY); + FP2_YYY_from_FPs(&X,&Qx,&Qy); + +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_inv(&X,&X); + FP2_YYY_norm(&X); +#endif +#endif + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + +#if PAIRING_FRIENDLY_ZZZ==BN + BIG_XXX_pmul(n,x,6); +#if SIGN_OF_X_ZZZ==POSITIVEX + BIG_XXX_inc(n,2); +#else + BIG_XXX_dec(n,2); +#endif +#else + BIG_XXX_copy(n,x); +#endif + + BIG_XXX_norm(n); + BIG_XXX_pmul(n3,n,3); + BIG_XXX_norm(n3); + + ECP2_ZZZ_copy(&P,P1); + ECP_ZZZ_copy(&Q,Q1); + + ECP2_ZZZ_affine(&P); + ECP_ZZZ_affine(&Q); + + ECP2_ZZZ_copy(&R,R1); + ECP_ZZZ_copy(&S,S1); + + ECP2_ZZZ_affine(&R); + ECP_ZZZ_affine(&S); + + FP_YYY_copy(&Qx,&(Q.x)); + FP_YYY_copy(&Qy,&(Q.y)); + + FP_YYY_copy(&Sx,&(S.x)); + FP_YYY_copy(&Sy,&(S.y)); + + ECP2_ZZZ_copy(&A,&P); + ECP2_ZZZ_copy(&B,&R); + + ECP2_ZZZ_copy(&NP,&P); ECP2_ZZZ_neg(&NP); + ECP2_ZZZ_copy(&NR,&R); ECP2_ZZZ_neg(&NR); + + + FP12_YYY_one(r); + nb=BIG_XXX_nbits(n3); + + /* Main Miller Loop */ + for (i=nb-2; i>=1; i--) + { + FP12_YYY_sqr(r,r); + PAIR_ZZZ_line(&lv,&A,&A,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + PAIR_ZZZ_line(&lv,&B,&B,&Sx,&Sy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + bt=BIG_XXX_bit(n3,i)-BIG_XXX_bit(n,i); + if (bt==1) + { + PAIR_ZZZ_line(&lv,&A,&P,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + PAIR_ZZZ_line(&lv,&B,&R,&Sx,&Sy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + + if (bt==-1) + { + PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + PAIR_ZZZ_line(&lv,&B,&NR,&Sx,&Sy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + + } + + + /* R-ate fixup required for BN curves */ + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP12_YYY_conj(r,r); +#endif + +#if PAIRING_FRIENDLY_ZZZ==BN + +#if SIGN_OF_X_ZZZ==NEGATIVEX + ECP2_ZZZ_neg(&A); + ECP2_ZZZ_neg(&B); +#endif + + ECP2_ZZZ_copy(&K,&P); + ECP2_ZZZ_frob(&K,&X); + + PAIR_ZZZ_line(&lv,&A,&K,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + ECP2_ZZZ_frob(&K,&X); + ECP2_ZZZ_neg(&K); + PAIR_ZZZ_line(&lv,&A,&K,&Qx,&Qy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + ECP2_ZZZ_copy(&K,&R); + ECP2_ZZZ_frob(&K,&X); + + PAIR_ZZZ_line(&lv,&B,&K,&Sx,&Sy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + ECP2_ZZZ_frob(&K,&X); + ECP2_ZZZ_neg(&K); + PAIR_ZZZ_line(&lv,&B,&K,&Sx,&Sy); + FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + +#endif +} + +/* final exponentiation - keep separate for multi-pairings and to avoid thrashing stack */ +void PAIR_ZZZ_fexp(FP12_YYY *r) +{ + FP2_YYY X; + BIG_XXX x; + FP_YYY a,b; + FP12_YYY t0,y0,y1,y2,y3; + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + FP_YYY_rcopy(&a,Fra_YYY); + FP_YYY_rcopy(&b,Frb_YYY); + FP2_YYY_from_FPs(&X,&a,&b); + + /* Easy part of final exp */ + + FP12_YYY_inv(&t0,r); + FP12_YYY_conj(r,r); + + FP12_YYY_mul(r,&t0); + FP12_YYY_copy(&t0,r); + + FP12_YYY_frob(r,&X); + FP12_YYY_frob(r,&X); + FP12_YYY_mul(r,&t0); + + /* Hard part of final exp - see Duquesne & Ghamman eprint 2015/192.pdf */ +#if PAIRING_FRIENDLY_ZZZ==BN + FP12_YYY_pow(&t0,r,x); // t0=f^-u +#if SIGN_OF_X_ZZZ==POSITIVEX + FP12_YYY_conj(&t0,&t0); +#endif + FP12_YYY_usqr(&y3,&t0); // y3=t0^2 + FP12_YYY_copy(&y0,&t0); + FP12_YYY_mul(&y0,&y3); // y0=t0*y3 + FP12_YYY_copy(&y2,&y3); + FP12_YYY_frob(&y2,&X); // y2=y3^p + FP12_YYY_mul(&y2,&y3); //y2=y2*y3 + FP12_YYY_usqr(&y2,&y2); //y2=y2^2 + FP12_YYY_mul(&y2,&y3); // y2=y2*y3 + + FP12_YYY_pow(&t0,&y0,x); //t0=y0^-u +#if SIGN_OF_X_ZZZ==POSITIVEX + FP12_YYY_conj(&t0,&t0); +#endif + FP12_YYY_conj(&y0,r); //y0=~r + FP12_YYY_copy(&y1,&t0); + FP12_YYY_frob(&y1,&X); + FP12_YYY_frob(&y1,&X); //y1=t0^p^2 + FP12_YYY_mul(&y1,&y0); // y1=y0*y1 + FP12_YYY_conj(&t0,&t0); // t0=~t0 + FP12_YYY_copy(&y3,&t0); + FP12_YYY_frob(&y3,&X); //y3=t0^p + FP12_YYY_mul(&y3,&t0); // y3=t0*y3 + FP12_YYY_usqr(&t0,&t0); // t0=t0^2 + FP12_YYY_mul(&y1,&t0); // y1=t0*y1 + + FP12_YYY_pow(&t0,&y3,x); // t0=y3^-u +#if SIGN_OF_X_ZZZ==POSITIVEX + FP12_YYY_conj(&t0,&t0); +#endif + FP12_YYY_usqr(&t0,&t0); //t0=t0^2 + FP12_YYY_conj(&t0,&t0); //t0=~t0 + FP12_YYY_mul(&y3,&t0); // y3=t0*y3 + + FP12_YYY_frob(r,&X); + FP12_YYY_copy(&y0,r); + FP12_YYY_frob(r,&X); + FP12_YYY_mul(&y0,r); + FP12_YYY_frob(r,&X); + FP12_YYY_mul(&y0,r); + + FP12_YYY_usqr(r,&y3); //r=y3^2 + FP12_YYY_mul(r,&y2); //r=y2*r + FP12_YYY_copy(&y3,r); + FP12_YYY_mul(&y3,&y0); // y3=r*y0 + FP12_YYY_mul(r,&y1); // r=r*y1 + FP12_YYY_usqr(r,r); // r=r^2 + FP12_YYY_mul(r,&y3); // r=r*y3 + FP12_YYY_reduce(r); +#else +// Ghamman & Fouotsa Method + + FP12_YYY_usqr(&y0,r); + FP12_YYY_pow(&y1,&y0,x); +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP12_YYY_conj(&y1,&y1); +#endif + + + BIG_XXX_fshr(x,1); + FP12_YYY_pow(&y2,&y1,x); +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP12_YYY_conj(&y2,&y2); +#endif + + + BIG_XXX_fshl(x,1); // x must be even + FP12_YYY_conj(&y3,r); + FP12_YYY_mul(&y1,&y3); + + FP12_YYY_conj(&y1,&y1); + FP12_YYY_mul(&y1,&y2); + + FP12_YYY_pow(&y2,&y1,x); +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP12_YYY_conj(&y2,&y2); +#endif + + FP12_YYY_pow(&y3,&y2,x); +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP12_YYY_conj(&y3,&y3); +#endif + FP12_YYY_conj(&y1,&y1); + FP12_YYY_mul(&y3,&y1); + + FP12_YYY_conj(&y1,&y1); + FP12_YYY_frob(&y1,&X); + FP12_YYY_frob(&y1,&X); + FP12_YYY_frob(&y1,&X); + FP12_YYY_frob(&y2,&X); + FP12_YYY_frob(&y2,&X); + FP12_YYY_mul(&y1,&y2); + + FP12_YYY_pow(&y2,&y3,x); +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP12_YYY_conj(&y2,&y2); +#endif + FP12_YYY_mul(&y2,&y0); + FP12_YYY_mul(&y2,r); + + FP12_YYY_mul(&y1,&y2); + FP12_YYY_copy(&y2,&y3); + FP12_YYY_frob(&y2,&X); + FP12_YYY_mul(&y1,&y2); + FP12_YYY_copy(r,&y1); + FP12_YYY_reduce(r); + +#endif +} + +#ifdef USE_GLV_ZZZ +/* GLV method */ +static void glv(BIG_XXX u[2],BIG_XXX e) +{ +#if PAIRING_FRIENDLY_ZZZ==BN + int i,j; + BIG_XXX v[2],t,q; + DBIG_XXX d; + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + for (i=0; i<2; i++) + { + BIG_XXX_rcopy(t,CURVE_W_ZZZ[i]); + BIG_XXX_mul(d,t,e); + BIG_XXX_ddiv(v[i],d,q); + BIG_XXX_zero(u[i]); + } + BIG_XXX_copy(u[0],e); + for (i=0; i<2; i++) + for (j=0; j<2; j++) + { + BIG_XXX_rcopy(t,CURVE_SB_ZZZ[j][i]); + BIG_XXX_modmul(t,v[j],t,q); + BIG_XXX_add(u[i],u[i],q); + BIG_XXX_sub(u[i],u[i],t); + BIG_XXX_mod(u[i],q); + } + +#else +// -(x^2).P = (Beta.x,y) + + BIG_XXX x,x2,q; + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + BIG_XXX_smul(x2,x,x); + BIG_XXX_copy(u[0],e); + BIG_XXX_mod(u[0],x2); + BIG_XXX_copy(u[1],e); + BIG_XXX_sdiv(u[1],x2); + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + BIG_XXX_sub(u[1],q,u[1]); + +#endif + + return; +} +#endif // USE_GLV + +/* Galbraith & Scott Method */ +static void gs(BIG_XXX u[4],BIG_XXX e) +{ + int i; +#if PAIRING_FRIENDLY_ZZZ==BN + int j; + BIG_XXX v[4],t,q; + DBIG_XXX d; + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + for (i=0; i<4; i++) + { + BIG_XXX_rcopy(t,CURVE_WB_ZZZ[i]); + BIG_XXX_mul(d,t,e); + BIG_XXX_ddiv(v[i],d,q); + BIG_XXX_zero(u[i]); + } + + BIG_XXX_copy(u[0],e); + for (i=0; i<4; i++) + for (j=0; j<4; j++) + { + BIG_XXX_rcopy(t,CURVE_BB_ZZZ[j][i]); + BIG_XXX_modmul(t,v[j],t,q); + BIG_XXX_add(u[i],u[i],q); + BIG_XXX_sub(u[i],u[i],t); + BIG_XXX_mod(u[i],q); + } + +#else + + BIG_XXX x,w,q; + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + BIG_XXX_copy(w,e); + + for (i=0; i<3; i++) + { + BIG_XXX_copy(u[i],w); + BIG_XXX_mod(u[i],x); + BIG_XXX_sdiv(w,x); + } + BIG_XXX_copy(u[3],w); + + /* */ +#if SIGN_OF_X_ZZZ==NEGATIVEX + BIG_XXX_modneg(u[1],u[1],q); + BIG_XXX_modneg(u[3],u[3],q); +#endif + +#endif + + + + return; +} + +/* Multiply P by e in group G1 */ +void PAIR_ZZZ_G1mul(ECP_ZZZ *P,BIG_XXX e) +{ +#ifdef USE_GLV_ZZZ /* Note this method is patented */ + int np,nn; + ECP_ZZZ Q; + FP_YYY cru; + BIG_XXX t,q; + BIG_XXX u[2]; + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + glv(u,e); + + ECP_ZZZ_copy(&Q,P); ECP_ZZZ_affine(&Q); + FP_YYY_rcopy(&cru,CURVE_Cru_ZZZ); + FP_YYY_mul(&(Q.x),&(Q.x),&cru); + + /* note that -a.B = a.(-B). Use a or -a depending on which is smaller */ + + np=BIG_XXX_nbits(u[0]); + BIG_XXX_modneg(t,u[0],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[0],t); + ECP_ZZZ_neg(P); + } + + np=BIG_XXX_nbits(u[1]); + BIG_XXX_modneg(t,u[1],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[1],t); + ECP_ZZZ_neg(&Q); + } + BIG_XXX_norm(u[0]); + BIG_XXX_norm(u[1]); + ECP_ZZZ_mul2(P,&Q,u[0],u[1]); + +#else + ECP_ZZZ_mul(P,e); +#endif +} + +/* Multiply P by e in group G2 */ +void PAIR_ZZZ_G2mul(ECP2_ZZZ *P,BIG_XXX e) +{ +#ifdef USE_GS_G2_ZZZ /* Well I didn't patent it :) */ + int i,np,nn; + ECP2_ZZZ Q[4]; + FP2_YYY X; + FP_YYY fx,fy; + BIG_XXX x,y,u[4]; + + FP_YYY_rcopy(&fx,Fra_YYY); + FP_YYY_rcopy(&fy,Frb_YYY); + FP2_YYY_from_FPs(&X,&fx,&fy); + +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_inv(&X,&X); + FP2_YYY_norm(&X); +#endif + + BIG_XXX_rcopy(y,CURVE_Order_ZZZ); + gs(u,e); + + ECP2_ZZZ_copy(&Q[0],P); + for (i=1; i<4; i++) + { + ECP2_ZZZ_copy(&Q[i],&Q[i-1]); + ECP2_ZZZ_frob(&Q[i],&X); + } + + for (i=0; i<4; i++) + { + np=BIG_XXX_nbits(u[i]); + BIG_XXX_modneg(x,u[i],y); + nn=BIG_XXX_nbits(x); + if (nn<np) + { + BIG_XXX_copy(u[i],x); + ECP2_ZZZ_neg(&Q[i]); + } + BIG_XXX_norm(u[i]); + } + + ECP2_ZZZ_mul4(P,Q,u); + +#else + ECP2_ZZZ_mul(P,e); +#endif +} + +/* f=f^e */ +void PAIR_ZZZ_GTpow(FP12_YYY *f,BIG_XXX e) +{ +#ifdef USE_GS_GT_ZZZ /* Note that this option requires a lot of RAM! Maybe better to use compressed XTR method, see fp4.c */ + int i,np,nn; + FP12_YYY g[4]; + FP2_YYY X; + BIG_XXX t,q; + FP_YYY fx,fy; + BIG_XXX u[4]; + + FP_YYY_rcopy(&fx,Fra_YYY); + FP_YYY_rcopy(&fy,Frb_YYY); + FP2_YYY_from_FPs(&X,&fx,&fy); + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + gs(u,e); + + FP12_YYY_copy(&g[0],f); + for (i=1; i<4; i++) + { + FP12_YYY_copy(&g[i],&g[i-1]); + FP12_YYY_frob(&g[i],&X); + } + + for (i=0; i<4; i++) + { + np=BIG_XXX_nbits(u[i]); + BIG_XXX_modneg(t,u[i],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[i],t); + FP12_YYY_conj(&g[i],&g[i]); + } + BIG_XXX_norm(u[i]); + } + FP12_YYY_pow4(f,g,u); + +#else + FP12_YYY_pow(f,f,e); +#endif +} + + +#ifdef HAS_MAIN + +int main() +{ + int i; + char byt[32]; + csprng rng; + BIG_XXX xa,xb,ya,yb,w,a,b,t1,q,u[2],v[4],m,r; + ECP2_ZZZ P,G; + ECP_ZZZ Q,R; + FP12_YYY g,gp; + FP4_YYY t,c,cp,cpm1,cpm2; + FP2_YYY x,y,X; + + + BIG_XXX_rcopy(a,CURVE_Fra); + BIG_XXX_rcopy(b,CURVE_Frb); + FP2_YYY_from_BIGs(&X,a,b); + + BIG_XXX_rcopy(xa,CURVE_Gx); + BIG_XXX_rcopy(ya,CURVE_Gy); + + ECP_ZZZ_set(&Q,xa,ya); + if (Q.inf) printf("Failed to set - point not on curve\n"); + else printf("G1 set success\n"); + + printf("Q= "); + ECP_ZZZ_output(&Q); + printf("\n"); + + BIG_XXX_rcopy(xa,CURVE_Pxa); + BIG_XXX_rcopy(xb,CURVE_Pxb); + BIG_XXX_rcopy(ya,CURVE_Pya); + BIG_XXX_rcopy(yb,CURVE_Pyb); + + FP2_YYY_from_BIGs(&x,xa,xb); + FP2_YYY_from_BIGs(&y,ya,yb); + + ECP2_ZZZ_set(&P,&x,&y); + if (P.inf) printf("Failed to set - point not on curve\n"); + else printf("G2 set success\n"); + + printf("P= "); + ECP2_ZZZ_output(&P); + printf("\n"); + + for (i=0; i<1000; i++ ) + { + PAIR_ZZZ_ate(&g,&P,&Q); + PAIR_ZZZ_fexp(&g); + } + printf("g= "); + FP12_YYY_output(&g); + printf("\n"); +} + +#endif
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pair.h ---------------------------------------------------------------------- diff --git a/version3/c/pair.h b/version3/c/pair.h new file mode 100644 index 0000000..81b710c --- /dev/null +++ b/version3/c/pair.h @@ -0,0 +1,103 @@ +/* + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, + software distributed under the License is distributed on an + "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + KIND, either express or implied. See the License for the + specific language governing permissions and limitations + under the License. +*/ + +/** + * @file pair.h + * @author Mike Scott + * @brief PAIR Header File + * + */ + +#ifndef PAIR_ZZZ_H +#define PAIR_ZZZ_H + +#include "fp12_YYY.h" +#include "ecp2_ZZZ.h" +#include "ecp_ZZZ.h" + +/* Pairing constants */ + +extern const BIG_XXX CURVE_Bnx_ZZZ; /**< BN curve x parameter */ +extern const BIG_XXX CURVE_Cru_ZZZ; /**< BN curve Cube Root of Unity */ + +extern const BIG_XXX CURVE_W_ZZZ[2]; /**< BN curve constant for GLV decomposition */ +extern const BIG_XXX CURVE_SB_ZZZ[2][2]; /**< BN curve constant for GLV decomposition */ +extern const BIG_XXX CURVE_WB_ZZZ[4]; /**< BN curve constant for GS decomposition */ +extern const BIG_XXX CURVE_BB_ZZZ[4][4]; /**< BN curve constant for GS decomposition */ + +/* Pairing function prototypes */ +/** @brief Calculate Miller loop for Optimal ATE pairing e(P,Q) + * + @param r FP12 result of the pairing calculation e(P,Q) + @param P ECP2 instance, an element of G2 + @param Q ECP instance, an element of G1 + + */ +extern void PAIR_ZZZ_ate(FP12_YYY *r,ECP2_ZZZ *P,ECP_ZZZ *Q); +/** @brief Calculate Miller loop for Optimal ATE double-pairing e(P,Q).e(R,S) + * + Faster than calculating two separate pairings + @param r FP12 result of the pairing calculation e(P,Q).e(R,S), an element of GT + @param P ECP2 instance, an element of G2 + @param Q ECP instance, an element of G1 + @param R ECP2 instance, an element of G2 + @param S ECP instance, an element of G1 + */ +extern void PAIR_ZZZ_double_ate(FP12_YYY *r,ECP2_ZZZ *P,ECP_ZZZ *Q,ECP2_ZZZ *R,ECP_ZZZ *S); +/** @brief Final exponentiation of pairing, converts output of Miller loop to element in GT + * + Here p is the internal modulus, and r is the group order + @param x FP12, on exit = x^((p^12-1)/r) + */ +extern void PAIR_ZZZ_fexp(FP12_YYY *x); +/** @brief Fast point multiplication of a member of the group G1 by a BIG number + * + May exploit endomorphism for speed. + @param Q ECP member of G1. + @param b BIG multiplier + + */ +extern void PAIR_ZZZ_G1mul(ECP_ZZZ *Q,BIG_XXX b); +/** @brief Fast point multiplication of a member of the group G2 by a BIG number + * + May exploit endomorphism for speed. + @param P ECP2 member of G1. + @param b BIG multiplier + + */ +extern void PAIR_ZZZ_G2mul(ECP2_ZZZ *P,BIG_XXX b); +/** @brief Fast raising of a member of GT to a BIG power + * + May exploit endomorphism for speed. + @param x FP12 member of GT. + @param b BIG exponent + + */ +extern void PAIR_ZZZ_GTpow(FP12_YYY *x,BIG_XXX b); +/** @brief Tests FP12 for membership of GT + * + @param x FP12 instance + @return 1 if x is in GT, else return 0 + + */ +extern int PAIR_ZZZ_GTmember(FP12_YYY *x); + + + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pair192.c ---------------------------------------------------------------------- diff --git a/version3/c/pair192.c b/version3/c/pair192.c new file mode 100644 index 0000000..2e4f4e0 --- /dev/null +++ b/version3/c/pair192.c @@ -0,0 +1,676 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* AMCL BLS Curve pairing functions */ + +//#define HAS_MAIN + +#include "pair192_ZZZ.h" + + +/* Line function */ +static void PAIR_ZZZ_line(FP24_YYY *v,ECP4_ZZZ *A,ECP4_ZZZ *B,FP_YYY *Qx,FP_YYY *Qy) +{ + FP4_YYY X1,Y1,T1,T2; + FP4_YYY XX,YY,ZZ,YZ; + FP8_YYY a,b,c; + + if (A==B) + { + /* doubling */ + FP4_YYY_copy(&XX,&(A->x)); //FP4_YYY XX=new FP4_YYY(A.getx()); //X + FP4_YYY_copy(&YY,&(A->y)); //FP4_YYY YY=new FP4_YYY(A.gety()); //Y + FP4_YYY_copy(&ZZ,&(A->z)); //FP4_YYY ZZ=new FP4_YYY(A.getz()); //Z + + + FP4_YYY_copy(&YZ,&YY); //FP4_YYY YZ=new FP4_YYY(YY); //Y + FP4_YYY_mul(&YZ,&YZ,&ZZ); //YZ.mul(ZZ); //YZ + FP4_YYY_sqr(&XX,&XX); //XX.sqr(); //X^2 + FP4_YYY_sqr(&YY,&YY); //YY.sqr(); //Y^2 + FP4_YYY_sqr(&ZZ,&ZZ); //ZZ.sqr(); //Z^2 + + FP4_YYY_imul(&YZ,&YZ,4); //YZ.imul(4); + FP4_YYY_neg(&YZ,&YZ); //YZ.neg(); + FP4_YYY_norm(&YZ); //YZ.norm(); //-4YZ + + FP4_YYY_imul(&XX,&XX,6); //6X^2 + FP4_YYY_qmul(&XX,&XX,Qx); //6X^2.Xs + + FP4_YYY_imul(&ZZ,&ZZ,3*CURVE_B_I_ZZZ); //3Bz^2 + + FP4_YYY_qmul(&YZ,&YZ,Qy); //-4YZ.Ys + +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP4_YYY_div_2i(&ZZ); //6(b/i)z^2 +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP4_YYY_times_i(&ZZ); + FP4_YYY_add(&ZZ,&ZZ,&ZZ); // 6biz^2 + FP4_YYY_times_i(&YZ); + FP4_YYY_norm(&YZ); +#endif + FP4_YYY_norm(&ZZ); // 6bi.Z^2 + + FP4_YYY_add(&YY,&YY,&YY); // 2y^2 + FP4_YYY_sub(&ZZ,&ZZ,&YY); // + FP4_YYY_norm(&ZZ); // 6b.Z^2-2Y^2 + + FP8_YYY_from_FP4s(&a,&YZ,&ZZ); // -4YZ.Ys | 6b.Z^2-2Y^2 | 6X^2.Xs +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP8_YYY_from_FP4(&b,&XX); + FP8_YYY_zero(&c); +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP8_YYY_zero(&b); + FP8_YYY_from_FP4H(&c,&XX); +#endif + + ECP4_ZZZ_dbl(A); //A.dbl(); + } + else + { + /* addition */ + + FP4_YYY_copy(&X1,&(A->x)); //FP4_YYY X1=new FP4_YYY(A.getx()); // X1 + FP4_YYY_copy(&Y1,&(A->y)); //FP4_YYY Y1=new FP4_YYY(A.gety()); // Y1 + FP4_YYY_copy(&T1,&(A->z)); //FP4_YYY T1=new FP4_YYY(A.getz()); // Z1 + + FP4_YYY_copy(&T2,&T1); //FP4_YYY T2=new FP4_YYY(A.getz()); // Z1 + + FP4_YYY_mul(&T1,&T1,&(B->y)); //T1.mul(B.gety()); // T1=Z1.Y2 + FP4_YYY_mul(&T2,&T2,&(B->x)); //T2.mul(B.getx()); // T2=Z1.X2 + + FP4_YYY_sub(&X1,&X1,&T2); //X1.sub(T2); + FP4_YYY_norm(&X1); //X1.norm(); // X1=X1-Z1.X2 + FP4_YYY_sub(&Y1,&Y1,&T1); //Y1.sub(T1); + FP4_YYY_norm(&Y1); //Y1.norm(); // Y1=Y1-Z1.Y2 + + FP4_YYY_copy(&T1,&X1); //T1.copy(X1); // T1=X1-Z1.X2 + + FP4_YYY_qmul(&X1,&X1,Qy); //X1.pmul(Qy); // X1=(X1-Z1.X2).Ys +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP4_YYY_times_i(&X1); + FP4_YYY_norm(&X1); +#endif + + FP4_YYY_mul(&T1,&T1,&(B->y)); //T1.mul(B.gety()); // T1=(X1-Z1.X2).Y2 + + FP4_YYY_copy(&T2,&Y1); //T2.copy(Y1); // T2=Y1-Z1.Y2 + FP4_YYY_mul(&T2,&T2,&(B->x)); //T2.mul(B.getx()); // T2=(Y1-Z1.Y2).X2 + FP4_YYY_sub(&T2,&T2,&T1); //T2.sub(T1); + FP4_YYY_norm(&T2); //T2.norm(); // T2=(Y1-Z1.Y2).X2 - (X1-Z1.X2).Y2 + FP4_YYY_qmul(&Y1,&Y1,Qx); //Y1.pmul(Qx); + FP4_YYY_neg(&Y1,&Y1); //Y1.neg(); + FP4_YYY_norm(&Y1); //Y1.norm(); // Y1=-(Y1-Z1.Y2).Xs + + FP8_YYY_from_FP4s(&a,&X1,&T2); // (X1-Z1.X2).Ys | (Y1-Z1.Y2).X2 - (X1-Z1.X2).Y2 | - (Y1-Z1.Y2).Xs +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP8_YYY_from_FP4(&b,&Y1); //b=new FP4(Y1); + FP8_YYY_zero(&c); +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP8_YYY_zero(&b); + FP8_YYY_from_FP4H(&c,&Y1); //b=new FP4(Y1); +#endif + ECP4_ZZZ_add(A,B); //A.add(B); + } + + FP24_YYY_from_FP8s(v,&a,&b,&c); +} + +/* Optimal R-ate pairing r=e(P,Q) */ +void PAIR_ZZZ_ate(FP24_YYY *r,ECP4_ZZZ *P1,ECP_ZZZ *Q1) +{ + BIG_XXX x,n,n3; + FP_YYY Qx,Qy; + int i,j,nb,bt; + ECP4_ZZZ A,NP,P; + ECP_ZZZ Q; + FP24_YYY lv; + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + + BIG_XXX_copy(n,x); + + BIG_XXX_pmul(n3,n,3); + BIG_XXX_norm(n3); + + ECP4_ZZZ_copy(&P,P1); + ECP_ZZZ_copy(&Q,Q1); + + ECP4_ZZZ_affine(&P); + ECP_ZZZ_affine(&Q); + + + FP_YYY_copy(&Qx,&(Q.x)); + FP_YYY_copy(&Qy,&(Q.y)); + + ECP4_ZZZ_copy(&A,&P); + ECP4_ZZZ_copy(&NP,&P); ECP4_ZZZ_neg(&NP); + + FP24_YYY_one(r); + nb=BIG_XXX_nbits(n3); // n3 + + j=0; + /* Main Miller Loop */ + for (i=nb-2; i>=1; i--) + { + j++; + FP24_YYY_sqr(r,r); + PAIR_ZZZ_line(&lv,&A,&A,&Qx,&Qy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + bt= BIG_XXX_bit(n3,i)-BIG_XXX_bit(n,i); + if (bt==1) + { + PAIR_ZZZ_line(&lv,&A,&P,&Qx,&Qy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + if (bt==-1) + { + PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + + } + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP24_YYY_conj(r,r); +#endif + +} + +/* Optimal R-ate double pairing e(P,Q).e(R,S) */ +void PAIR_ZZZ_double_ate(FP24_YYY *r,ECP4_ZZZ *P1,ECP_ZZZ *Q1,ECP4_ZZZ *R1,ECP_ZZZ *S1) +{ + BIG_XXX x,n,n3; + FP_YYY Qx,Qy,Sx,Sy; + int i,nb,bt; + ECP4_ZZZ A,B,NP,NR,P,R; + ECP_ZZZ Q,S; + FP24_YYY lv; + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + BIG_XXX_copy(n,x); + + BIG_XXX_pmul(n3,n,3); + BIG_XXX_norm(n3); + + ECP4_ZZZ_copy(&P,P1); + ECP_ZZZ_copy(&Q,Q1); + + ECP4_ZZZ_affine(&P); + ECP_ZZZ_affine(&Q); + + ECP4_ZZZ_copy(&R,R1); + ECP_ZZZ_copy(&S,S1); + + ECP4_ZZZ_affine(&R); + ECP_ZZZ_affine(&S); + + + FP_YYY_copy(&Qx,&(Q.x)); + FP_YYY_copy(&Qy,&(Q.y)); + + FP_YYY_copy(&Sx,&(S.x)); + FP_YYY_copy(&Sy,&(S.y)); + + ECP4_ZZZ_copy(&A,&P); + ECP4_ZZZ_copy(&B,&R); + ECP4_ZZZ_copy(&NP,&P); ECP4_ZZZ_neg(&NP); + ECP4_ZZZ_copy(&NR,&R); ECP4_ZZZ_neg(&NR); + + + FP24_YYY_one(r); + nb=BIG_XXX_nbits(n3); + + /* Main Miller Loop */ + for (i=nb-2; i>=1; i--) + { + FP24_YYY_sqr(r,r); + PAIR_ZZZ_line(&lv,&A,&A,&Qx,&Qy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + PAIR_ZZZ_line(&lv,&B,&B,&Sx,&Sy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + bt=BIG_XXX_bit(n3,i)-BIG_XXX_bit(n,i); + if (bt==1) + { + PAIR_ZZZ_line(&lv,&A,&P,&Qx,&Qy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + PAIR_ZZZ_line(&lv,&B,&R,&Sx,&Sy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + if (bt==-1) + { + PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + PAIR_ZZZ_line(&lv,&B,&NR,&Sx,&Sy); + FP24_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + } + + + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP24_YYY_conj(r,r); +#endif + +} + +/* final exponentiation - keep separate for multi-pairings and to avoid thrashing stack */ + +void PAIR_ZZZ_fexp(FP24_YYY *r) +{ + FP2_YYY X; + BIG_XXX x; + FP_YYY a,b; + FP24_YYY t0,t1,t2,t3,t4,t5,t6,t7; // could lose one of these - r=t3 + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + FP_YYY_rcopy(&a,Fra_YYY); + FP_YYY_rcopy(&b,Frb_YYY); + FP2_YYY_from_FPs(&X,&a,&b); + + /* Easy part of final exp - r^(p^12-1)(p^4+1)*/ + + FP24_YYY_inv(&t0,r); + FP24_YYY_conj(r,r); + + FP24_YYY_mul(r,&t0); + FP24_YYY_copy(&t0,r); + + FP24_YYY_frob(r,&X,4); + + FP24_YYY_mul(r,&t0); + +// Ghamman & Fouotsa Method - (completely garbled in https://eprint.iacr.org/2016/130) + + FP24_YYY_usqr(&t7,r); // t7=f^2 + FP24_YYY_pow(&t1,&t7,x); // t1=t7^u + + BIG_XXX_fshr(x,1); + FP24_YYY_pow(&t2,&t1,x); // t2=t1^(u/2) + BIG_XXX_fshl(x,1); // x must be even + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP24_YYY_conj(&t1,&t1); +#endif + + FP24_YYY_conj(&t3,&t1); // t3=1/t1 + FP24_YYY_mul(&t2,&t3); // t2=t1*t3 + FP24_YYY_mul(&t2,r); // t2=t2*f + + + FP24_YYY_pow(&t3,&t2,x); // t3=t2^u + FP24_YYY_pow(&t4,&t3,x); // t4=t3^u + FP24_YYY_pow(&t5,&t4,x); // t5=t4^u + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP24_YYY_conj(&t3,&t3); + FP24_YYY_conj(&t5,&t5); +#endif + + FP24_YYY_frob(&t3,&X,6); + FP24_YYY_frob(&t4,&X,5); + + FP24_YYY_mul(&t3,&t4); // t3=t3.t4 + + + FP24_YYY_pow(&t6,&t5,x); // t6=t5^u +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP24_YYY_conj(&t6,&t6); +#endif + + + FP24_YYY_frob(&t5,&X,4); + FP24_YYY_mul(&t3,&t5); // ?? + + + FP24_YYY_conj(&t0,&t2); // t0=1/t2 + FP24_YYY_mul(&t6,&t0); // t6=t6*t0 + + FP24_YYY_copy(&t5,&t6); + FP24_YYY_frob(&t5,&X,3); + + FP24_YYY_mul(&t3,&t5); // t3=t3*t5 + FP24_YYY_pow(&t5,&t6,x); // t5=t6^x + FP24_YYY_pow(&t6,&t5,x); // t6=t5^x + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP24_YYY_conj(&t5,&t5); +#endif + + FP24_YYY_copy(&t0,&t5); + FP24_YYY_frob(&t0,&X,2); + FP24_YYY_mul(&t3,&t0); // t3=t3*t0 + FP24_YYY_copy(&t0,&t6); // + FP24_YYY_frob(&t0,&X,1); + + FP24_YYY_mul(&t3,&t0); // t3=t3*t0 + FP24_YYY_pow(&t5,&t6,x); // t5=t6*x + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP24_YYY_conj(&t5,&t5); +#endif + + FP24_YYY_frob(&t2,&X,7); + + FP24_YYY_mul(&t5,&t7); // t5=t5*t7 + FP24_YYY_mul(&t3,&t2); // t3=t3*t2 + FP24_YYY_mul(&t3,&t5); // t3=t3*t5 + + FP24_YYY_mul(r,&t3); + FP24_YYY_reduce(r); + +} + +#ifdef USE_GLV_ZZZ +/* GLV method */ +static void glv(BIG_XXX u[2],BIG_XXX e) +{ + +// -(x^4).P = (Beta.x,y) + + BIG_XXX x,x2,q; + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + BIG_XXX_smul(x2,x,x); + BIG_XXX_smul(x,x2,x2); + BIG_XXX_copy(u[0],e); + BIG_XXX_mod(u[0],x); + BIG_XXX_copy(u[1],e); + BIG_XXX_sdiv(u[1],x); + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + BIG_XXX_sub(u[1],q,u[1]); + + + return; +} +#endif // USE_GLV + +/* Galbraith & Scott Method */ +static void gs(BIG_XXX u[8],BIG_XXX e) +{ + int i; + + BIG_XXX x,w,q; + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + BIG_XXX_copy(w,e); + + for (i=0; i<7; i++) + { + BIG_XXX_copy(u[i],w); + BIG_XXX_mod(u[i],x); + BIG_XXX_sdiv(w,x); + } + BIG_XXX_copy(u[7],w); + +/* */ +#if SIGN_OF_X_ZZZ==NEGATIVEX + BIG_XXX_modneg(u[1],u[1],q); + BIG_XXX_modneg(u[3],u[3],q); + BIG_XXX_modneg(u[5],u[5],q); + BIG_XXX_modneg(u[7],u[7],q); +#endif + + + return; +} + +/* Multiply P by e in group G1 */ +void PAIR_ZZZ_G1mul(ECP_ZZZ *P,BIG_XXX e) +{ +#ifdef USE_GLV_ZZZ /* Note this method is patented */ + int np,nn; + ECP_ZZZ Q; + FP_YYY cru; + BIG_XXX t,q; + BIG_XXX u[2]; + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + glv(u,e); + + ECP_ZZZ_copy(&Q,P); ECP_ZZZ_affine(&Q); + FP_YYY_rcopy(&cru,CURVE_Cru_ZZZ); + FP_YYY_mul(&(Q.x),&(Q.x),&cru); + + /* note that -a.B = a.(-B). Use a or -a depending on which is smaller */ + + np=BIG_XXX_nbits(u[0]); + BIG_XXX_modneg(t,u[0],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[0],t); + ECP_ZZZ_neg(P); + } + + np=BIG_XXX_nbits(u[1]); + BIG_XXX_modneg(t,u[1],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[1],t); + ECP_ZZZ_neg(&Q); + } + BIG_XXX_norm(u[0]); + BIG_XXX_norm(u[1]); + ECP_ZZZ_mul2(P,&Q,u[0],u[1]); + +#else + ECP_ZZZ_mul(P,e); +#endif +} + +/* Multiply P by e in group G2 */ +void PAIR_ZZZ_G2mul(ECP4_ZZZ *P,BIG_XXX e) +{ +#ifdef USE_GS_G2_ZZZ /* Well I didn't patent it :) */ + int i,np,nn; + ECP4_ZZZ Q[8]; + FP2_YYY X[3]; + BIG_XXX x,y,u[8]; + + ECP4_ZZZ_frob_constants(X); + + BIG_XXX_rcopy(y,CURVE_Order_ZZZ); + gs(u,e); + + ECP4_ZZZ_copy(&Q[0],P); + for (i=1; i<8; i++) + { + ECP4_ZZZ_copy(&Q[i],&Q[i-1]); + ECP4_ZZZ_frob(&Q[i],X,1); + } + + for (i=0; i<8; i++) + { + np=BIG_XXX_nbits(u[i]); + BIG_XXX_modneg(x,u[i],y); + nn=BIG_XXX_nbits(x); + if (nn<np) + { + BIG_XXX_copy(u[i],x); + ECP4_ZZZ_neg(&Q[i]); + } + BIG_XXX_norm(u[i]); + } + + ECP4_ZZZ_mul8(P,Q,u); + +#else + ECP4_ZZZ_mul(P,e); +#endif +} + +/* f=f^e */ +void PAIR_ZZZ_GTpow(FP24_YYY *f,BIG_XXX e) +{ +#ifdef USE_GS_GT_ZZZ /* Note that this option requires a lot of RAM! Maybe better to use compressed XTR method, see FP8.c */ + int i,np,nn; + FP24_YYY g[8]; + FP2_YYY X; + BIG_XXX t,q; + FP_YYY fx,fy; + BIG_XXX u[8]; + + FP_YYY_rcopy(&fx,Fra_YYY); + FP_YYY_rcopy(&fy,Frb_YYY); + FP2_YYY_from_FPs(&X,&fx,&fy); + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + gs(u,e); + + FP24_YYY_copy(&g[0],f); + for (i=1; i<8; i++) + { + FP24_YYY_copy(&g[i],&g[i-1]); + FP24_YYY_frob(&g[i],&X,1); + } + + for (i=0; i<8; i++) + { + np=BIG_XXX_nbits(u[i]); + BIG_XXX_modneg(t,u[i],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[i],t); + FP24_YYY_conj(&g[i],&g[i]); + } + BIG_XXX_norm(u[i]); + } + FP24_YYY_pow8(f,g,u); + +#else + FP24_YYY_pow(f,f,e); +#endif +} + + +#ifdef HAS_MAIN + +using namespace std; +using namespace ZZZ; + + +// g++ -O2 pair192_BLS24.cpp ecp4_BLS24.cpp fp24_BLS24.cpp fp8_BLS24.cpp fp4_BLS24.cpp fp2_BLS24.cpp ecp_BLS24.cpp fp_BLS24.cpp big_XXX.cpp rom_curve_BLS24.cpp rom_field_BLS24.cpp rand.cpp hash.cpp oct.cpp -o pair192_BLS24.exe + +int main() +{ + int i; + char byt[32]; + csprng rng; + BIG_XXX xa,xb,ya,yb,w,a,b,t1,q,u[2],v[4],m,r,xx,x2,x4,p; + ECP4_ZZZ P,G; + ECP_ZZZ Q,R; + FP24 g,gp; + FP8_YYY t,c,cp,cpm1,cpm2; + FP4_YYY X,Y; + FP2_YYY x,y,f,Aa,Bb; + FP_YYY cru; + + for (i=0;i<32;i++) + byt[i]=i+9; + RAND_seed(&rng,32,byt); + + BIG_XXX_rcopy(r,CURVE_Order); + BIG_XXX_rcopy(p,Modulus); + + + BIG_XXX_rcopy(xa,CURVE_Gx); + BIG_XXX_rcopy(ya,CURVE_Gy); + + ECP_set(&Q,xa,ya); + if (Q.inf) printf("Failed to set - point not on curve\n"); + else printf("G1 set success\n"); + + printf("Q= "); + ECP_output(&Q); + printf("\n"); + + ECP4_ZZZ_generator(&P); + + if (P.inf) printf("Failed to set - point not on curve\n"); + else printf("G2 set success\n"); + + BIG_XXX_rcopy(a,Fra); + BIG_XXX_rcopy(b,Frb); + FP2_YYY from_BIGs(&f,a,b); + + PAIR_ate(&g,&P,&Q); + + printf("gb= "); + FP24_output(&g); + printf("\n"); + PAIR_fexp(&g); + + printf("g= "); + FP24_output(&g); + printf("\n"); + + ECP_copy(&R,&Q); + ECP4_ZZZ_copy(&G,&P); + + ECP4_ZZZ_dbl(&G); + ECP_dbl(&R); + ECP_affine(&R); + + PAIR_ate(&g,&G,&Q); + PAIR_fexp(&g); + + printf("g1= "); + FP24_output(&g); + printf("\n"); + + PAIR_ate(&g,&P,&R); + PAIR_fexp(&g); + + printf("g2= "); + FP24_output(&g); + printf("\n"); + + + PAIR_G1mul(&Q,r); + printf("rQ= ");ECP_output(&Q); printf("\n"); + + PAIR_G2mul(&P,r); + printf("rP= ");ECP4_ZZZ_output(&P); printf("\n"); + + BIG_XXX_randomnum(w,r,&rng); + + FP24_copy(&gp,&g); + + PAIR_GTpow(&g,w); + + FP24_trace(&t,&g); + + printf("g^r= ");FP8_output(&t); printf("\n"); + + FP24_compow(&t,&gp,w,r); + + printf("t(g)= "); FP8_output(&t); printf("\n"); + +} + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pair192.h ---------------------------------------------------------------------- diff --git a/version3/c/pair192.h b/version3/c/pair192.h new file mode 100644 index 0000000..2e50d51 --- /dev/null +++ b/version3/c/pair192.h @@ -0,0 +1,77 @@ +#ifndef PAIR192_ZZZ_H +#define PAIR192_ZZZ_H + +#include "fp24_YYY.h" +#include "ecp4_ZZZ.h" +#include "ecp_ZZZ.h" + + +/* Pairing constants */ + +extern const BIG_XXX CURVE_Bnx_ZZZ; /**< BN curve x parameter */ +extern const BIG_XXX CURVE_Cru_ZZZ; /**< BN curve Cube Root of Unity */ + +extern const BIG_XXX CURVE_W_ZZZ[2]; /**< BN curve constant for GLV decomposition */ +extern const BIG_XXX CURVE_SB_ZZZ[2][2]; /**< BN curve constant for GLV decomposition */ +extern const BIG_XXX CURVE_WB_ZZZ[4]; /**< BN curve constant for GS decomposition */ +extern const BIG_XXX CURVE_BB_ZZZ[4][4]; /**< BN curve constant for GS decomposition */ + +/* Pairing function prototypes */ +/** @brief Calculate Miller loop for Optimal ATE pairing e(P,Q) + * + @param r FP24 result of the pairing calculation e(P,Q) + @param P ECP4 instance, an element of G2 + @param Q ECP instance, an element of G1 + + */ +extern void PAIR_ZZZ_ate(FP24_YYY *r,ECP4_ZZZ *P,ECP_ZZZ *Q); +/** @brief Calculate Miller loop for Optimal ATE double-pairing e(P,Q).e(R,S) + * + Faster than calculating two separate pairings + @param r FP24 result of the pairing calculation e(P,Q).e(R,S), an element of GT + @param P ECP4 instance, an element of G2 + @param Q ECP instance, an element of G1 + @param R ECP4 instance, an element of G2 + @param S ECP instance, an element of G1 + */ +extern void PAIR_ZZZ_double_ate(FP24_YYY *r,ECP4_ZZZ *P,ECP_ZZZ *Q,ECP4_ZZZ *R,ECP_ZZZ *S); +/** @brief Final exponentiation of pairing, converts output of Miller loop to element in GT + * + Here p is the internal modulus, and r is the group order + @param x FP24, on exit = x^((p^12-1)/r) + */ +extern void PAIR_ZZZ_fexp(FP24_YYY *x); +/** @brief Fast point multiplication of a member of the group G1 by a BIG number + * + May exploit endomorphism for speed. + @param Q ECP member of G1. + @param b BIG multiplier + + */ +extern void PAIR_ZZZ_G1mul(ECP_ZZZ *Q,BIG_XXX b); +/** @brief Fast point multiplication of a member of the group G2 by a BIG number + * + May exploit endomorphism for speed. + @param P ECP4 member of G1. + @param b BIG multiplier + + */ +extern void PAIR_ZZZ_G2mul(ECP4_ZZZ *P,BIG_XXX b); +/** @brief Fast raising of a member of GT to a BIG power + * + May exploit endomorphism for speed. + @param x FP24 member of GT. + @param b BIG exponent + + */ +extern void PAIR_ZZZ_GTpow(FP24_YYY *x,BIG_XXX b); +/** @brief Tests FP24 for membership of GT + * + @param x FP24 instance + @return 1 if x is in GT, else return 0 + + */ +extern int PAIR_ZZZ_GTmember(FP24_YYY *x); + + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pair256.c ---------------------------------------------------------------------- diff --git a/version3/c/pair256.c b/version3/c/pair256.c new file mode 100644 index 0000000..2f71691 --- /dev/null +++ b/version3/c/pair256.c @@ -0,0 +1,746 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* AMCL BLS Curve pairing functions */ + +//#define HAS_MAIN + +#include "pair256_ZZZ.h" + +/* Line function */ +static void PAIR_ZZZ_line(FP48_YYY *v,ECP8_ZZZ *A,ECP8_ZZZ *B,FP_YYY *Qx,FP_YYY *Qy) +{ + FP8_YYY X1,Y1,T1,T2; + FP8_YYY XX,YY,ZZ,YZ; + FP16_YYY a,b,c; + + if (A==B) + { + /* doubling */ + FP8_YYY_copy(&XX,&(A->x)); //FP8_YYY XX=new FP8_YYY(A.getx()); //X + FP8_YYY_copy(&YY,&(A->y)); //FP8_YYY YY=new FP8_YYY(A.gety()); //Y + FP8_YYY_copy(&ZZ,&(A->z)); //FP8_YYY ZZ=new FP8_YYY(A.getz()); //Z + + + FP8_YYY_copy(&YZ,&YY); //FP8_YYY YZ=new FP8_YYY(YY); //Y + FP8_YYY_mul(&YZ,&YZ,&ZZ); //YZ.mul(ZZ); //YZ + FP8_YYY_sqr(&XX,&XX); //XX.sqr(); //X^2 + FP8_YYY_sqr(&YY,&YY); //YY.sqr(); //Y^2 + FP8_YYY_sqr(&ZZ,&ZZ); //ZZ.sqr(); //Z^2 + + FP8_YYY_imul(&YZ,&YZ,4); //YZ.imul(4); + FP8_YYY_neg(&YZ,&YZ); //YZ.neg(); + FP8_YYY_norm(&YZ); //YZ.norm(); //-4YZ + + FP8_YYY_imul(&XX,&XX,6); //6X^2 + FP8_YYY_tmul(&XX,&XX,Qx); //6X^2.Xs + + FP8_YYY_imul(&ZZ,&ZZ,3*CURVE_B_I_ZZZ); //3Bz^2 + FP8_YYY_tmul(&YZ,&YZ,Qy); //-4YZ.Ys + +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP8_YYY_div_2i(&ZZ); //6(b/i)z^2 +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP8_YYY_times_i(&ZZ); + FP8_YYY_add(&ZZ,&ZZ,&ZZ); // 6biz^2 + FP8_YYY_times_i(&YZ); + FP8_YYY_norm(&YZ); +#endif + FP8_YYY_norm(&ZZ); // 6bi.Z^2 + + FP8_YYY_add(&YY,&YY,&YY); // 2y^2 + FP8_YYY_sub(&ZZ,&ZZ,&YY); // + FP8_YYY_norm(&ZZ); // 6b.Z^2-2Y^2 + + FP16_YYY_from_FP8s(&a,&YZ,&ZZ); // -4YZ.Ys | 6b.Z^2-2Y^2 | 6X^2.Xs +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP16_YYY_from_FP8(&b,&XX); + FP16_YYY_zero(&c); +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP16_YYY_zero(&b); + FP16_YYY_from_FP8H(&c,&XX); +#endif + + ECP8_ZZZ_dbl(A); //A.dbl(); + } + else + { + /* addition */ + + FP8_YYY_copy(&X1,&(A->x)); //FP8_YYY X1=new FP8_YYY(A.getx()); // X1 + FP8_YYY_copy(&Y1,&(A->y)); //FP8_YYY Y1=new FP8_YYY(A.gety()); // Y1 + FP8_YYY_copy(&T1,&(A->z)); //FP8_YYY T1=new FP8_YYY(A.getz()); // Z1 + + FP8_YYY_copy(&T2,&T1); //FP8_YYY T2=new FP8_YYY(A.getz()); // Z1 + + FP8_YYY_mul(&T1,&T1,&(B->y)); //T1.mul(B.gety()); // T1=Z1.Y2 + FP8_YYY_mul(&T2,&T2,&(B->x)); //T2.mul(B.getx()); // T2=Z1.X2 + + FP8_YYY_sub(&X1,&X1,&T2); //X1.sub(T2); + FP8_YYY_norm(&X1); //X1.norm(); // X1=X1-Z1.X2 + FP8_YYY_sub(&Y1,&Y1,&T1); //Y1.sub(T1); + FP8_YYY_norm(&Y1); //Y1.norm(); // Y1=Y1-Z1.Y2 + + FP8_YYY_copy(&T1,&X1); //T1.copy(X1); // T1=X1-Z1.X2 + FP8_YYY_tmul(&X1,&X1,Qy); //X1.pmul(Qy); // X1=(X1-Z1.X2).Ys +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP8_YYY_times_i(&X1); + FP8_YYY_norm(&X1); +#endif + + FP8_YYY_mul(&T1,&T1,&(B->y)); //T1.mul(B.gety()); // T1=(X1-Z1.X2).Y2 + + FP8_YYY_copy(&T2,&Y1); //T2.copy(Y1); // T2=Y1-Z1.Y2 + FP8_YYY_mul(&T2,&T2,&(B->x)); //T2.mul(B.getx()); // T2=(Y1-Z1.Y2).X2 + FP8_YYY_sub(&T2,&T2,&T1); //T2.sub(T1); + FP8_YYY_norm(&T2); //T2.norm(); // T2=(Y1-Z1.Y2).X2 - (X1-Z1.X2).Y2 + FP8_YYY_tmul(&Y1,&Y1,Qx); //Y1.pmul(Qx); + FP8_YYY_neg(&Y1,&Y1); //Y1.neg(); + FP8_YYY_norm(&Y1); //Y1.norm(); // Y1=-(Y1-Z1.Y2).Xs + + FP16_YYY_from_FP8s(&a,&X1,&T2); // (X1-Z1.X2).Ys | (Y1-Z1.Y2).X2 - (X1-Z1.X2).Y2 | - (Y1-Z1.Y2).Xs +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP16_YYY_from_FP8(&b,&Y1); //b=new FP4(Y1); + FP16_YYY_zero(&c); +#endif +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP16_YYY_zero(&b); + FP16_YYY_from_FP8H(&c,&Y1); //b=new FP4(Y1); +#endif + ECP8_ZZZ_add(A,B); // A.add(B); + } + + FP48_YYY_from_FP16s(v,&a,&b,&c); +} + +/* Optimal R-ate pairing r=e(P,Q) */ +void PAIR_ZZZ_ate(FP48_YYY *r,ECP8_ZZZ *P1,ECP_ZZZ *Q1) +{ + BIG_XXX x,n,n3; + FP_YYY Qx,Qy; + int i,j,nb,bt; + ECP8_ZZZ A,NP,P; + ECP_ZZZ Q; + FP48_YYY lv; + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + + BIG_XXX_copy(n,x); + + BIG_XXX_pmul(n3,n,3); + BIG_XXX_norm(n3); + + ECP8_ZZZ_copy(&P,P1); + ECP_ZZZ_copy(&Q,Q1); + + ECP8_ZZZ_affine(&P); + ECP_ZZZ_affine(&Q); + + + FP_YYY_copy(&Qx,&(Q.x)); + FP_YYY_copy(&Qy,&(Q.y)); + + ECP8_ZZZ_copy(&A,&P); + ECP8_ZZZ_copy(&NP,&P); ECP8_ZZZ_neg(&NP); + + FP48_YYY_one(r); + nb=BIG_XXX_nbits(n3); // n3 + + j=0; + /* Main Miller Loop */ + for (i=nb-2; i>=1; i--) + { + j++; + FP48_YYY_sqr(r,r); + PAIR_ZZZ_line(&lv,&A,&A,&Qx,&Qy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + bt= BIG_XXX_bit(n3,i)-BIG_XXX_bit(n,i); + if (bt==1) + { + PAIR_ZZZ_line(&lv,&A,&P,&Qx,&Qy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + if (bt==-1) + { + PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + + } + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(r,r); +#endif + +} + +/* Optimal R-ate double pairing e(P,Q).e(R,S) */ +void PAIR_ZZZ_double_ate(FP48_YYY *r,ECP8_ZZZ *P1,ECP_ZZZ *Q1,ECP8_ZZZ *R1,ECP_ZZZ *S1) +{ + BIG_XXX x,n,n3; + FP_YYY Qx,Qy,Sx,Sy; + int i,nb,bt; + ECP8_ZZZ A,B,NP,NR,P,R; + ECP_ZZZ Q,S; + FP48_YYY lv; + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + BIG_XXX_copy(n,x); + + BIG_XXX_pmul(n3,n,3); + BIG_XXX_norm(n3); + + ECP8_ZZZ_copy(&P,P1); + ECP_ZZZ_copy(&Q,Q1); + + ECP8_ZZZ_affine(&P); + ECP_ZZZ_affine(&Q); + + ECP8_ZZZ_copy(&R,R1); + ECP_ZZZ_copy(&S,S1); + + ECP8_ZZZ_affine(&R); + ECP_ZZZ_affine(&S); + + FP_YYY_copy(&Qx,&(Q.x)); + FP_YYY_copy(&Qy,&(Q.y)); + + FP_YYY_copy(&Sx,&(S.x)); + FP_YYY_copy(&Sy,&(S.y)); + + ECP8_ZZZ_copy(&A,&P); + ECP8_ZZZ_copy(&B,&R); + ECP8_ZZZ_copy(&NP,&P); ECP8_ZZZ_neg(&NP); + ECP8_ZZZ_copy(&NR,&R); ECP8_ZZZ_neg(&NR); + + + FP48_YYY_one(r); + nb=BIG_XXX_nbits(n3); + + /* Main Miller Loop */ + for (i=nb-2; i>=1; i--) + { + FP48_YYY_sqr(r,r); + PAIR_ZZZ_line(&lv,&A,&A,&Qx,&Qy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + PAIR_ZZZ_line(&lv,&B,&B,&Sx,&Sy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + bt=BIG_XXX_bit(n3,i)-BIG_XXX_bit(n,i); + if (bt==1) + { + PAIR_ZZZ_line(&lv,&A,&P,&Qx,&Qy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + + PAIR_ZZZ_line(&lv,&B,&R,&Sx,&Sy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + if (bt==-1) + { + PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + PAIR_ZZZ_line(&lv,&B,&NR,&Sx,&Sy); + FP48_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); + } + } + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(r,r); +#endif + +} + +/* final exponentiation - keep separate for multi-pairings and to avoid thrashing stack */ + +void PAIR_ZZZ_fexp(FP48_YYY *r) +{ + FP2_YYY X; + BIG_XXX x; + FP_YYY a,b; + FP48_YYY t1,t2,t3,t7; + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + FP_YYY_rcopy(&a,Fra_YYY); + FP_YYY_rcopy(&b,Frb_YYY); + FP2_YYY_from_FPs(&X,&a,&b); + + /* Easy part of final exp - r^(p^24-1)(p^8+1)*/ + + FP48_YYY_inv(&t7,r); + FP48_YYY_conj(r,r); + + FP48_YYY_mul(r,&t7); + FP48_YYY_copy(&t7,r); + + FP48_YYY_frob(r,&X,8); + + FP48_YYY_mul(r,&t7); + +// f^e0.f^e1^p.f^e2^p^2.. .. f^e14^p^14.f^e15^p^15 + + FP48_YYY_usqr(&t7,r); // t7=f^2 + FP48_YYY_pow(&t1,&t7,x); // t1=f^2u + + BIG_XXX_fshr(x,1); + FP48_YYY_pow(&t2,&t1,x); // t2=f^2u^(u/2) = f^u^2 + BIG_XXX_fshl(x,1); // x must be even + +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + + FP48_YYY_conj(&t3,&t1); // t3=f^-2u + FP48_YYY_mul(&t2,&t3); // t2=f^u^2.f^-2u + FP48_YYY_mul(&t2,r); // t2=f^u^2.f^-2u.f = f^(u^2-2u+1) = f^e15 + + FP48_YYY_mul(r,&t7); // f^3 + + FP48_YYY_pow(&t1,&t2,x); // f^e15^u = f^(u.e15) = f^(u^3-2u^2+u) = f^(e14) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,14); // f^(u^3-2u^2+u)^p^14 + FP48_YYY_mul(r,&t3); // f^3.f^(u^3-2u^2+u)^p^14 + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e14) = f^(u^4-2u^3+u^2) = f^(e13) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,13); // f^(e13)^p^13 + FP48_YYY_mul(r,&t3); // f^3.f^(u^3-2u^2+u)^p^14.f^(u^4-2u^3+u^2)^p^13 + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e13) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,12); // f^(e12)^p^12 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e12) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,11); // f^(e11)^p^11 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e11) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,10); // f^(e10)^p^10 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e10) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,9); // f^(e9)^p^9 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e9) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,8); // f^(e8)^p^8 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e8) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_conj(&t3,&t2); + FP48_YYY_mul(&t1,&t3); // f^(u.e8).f^-e15 + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,7); // f^(e7)^p^7 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e7) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,6); // f^(e6)^p^6 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e6) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,5); // f^(e5)^p^5 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e5) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,4); // f^(e4)^p^4 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e4) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,3); // f^(e3)^p^3 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e3) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,2); // f^(e2)^p^2 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e2) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_copy(&t3,&t1); + FP48_YYY_frob(&t3,&X,1); // f^(e1)^p^1 + FP48_YYY_mul(r,&t3); + + FP48_YYY_pow(&t1,&t1,x); // f^(u.e1) +#if SIGN_OF_X_ZZZ==NEGATIVEX + FP48_YYY_conj(&t1,&t1); +#endif + FP48_YYY_mul(r,&t1); // r.f^e0 + + FP48_YYY_frob(&t2,&X,15); // f^(e15.p^15) + FP48_YYY_mul(r,&t2); + + + FP48_YYY_reduce(r); + +} + +#ifdef USE_GLV_ZZZ +/* GLV method */ +static void glv(BIG_XXX u[2],BIG_XXX e) +{ + +// -(x^8).P = (Beta.x,y) + + BIG_XXX x,x2,q; + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + + BIG_XXX_smul(x2,x,x); + BIG_XXX_smul(x,x2,x2); + BIG_XXX_smul(x2,x,x); + + BIG_XXX_copy(u[0],e); + BIG_XXX_mod(u[0],x2); + BIG_XXX_copy(u[1],e); + BIG_XXX_sdiv(u[1],x2); + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + BIG_XXX_sub(u[1],q,u[1]); + + + return; +} +#endif // USE_GLV + +/* Galbraith & Scott Method */ +static void gs(BIG_XXX u[16],BIG_XXX e) +{ + int i; + + BIG_XXX x,w,q; + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + BIG_XXX_copy(w,e); + + for (i=0; i<15; i++) + { + BIG_XXX_copy(u[i],w); + BIG_XXX_mod(u[i],x); + BIG_XXX_sdiv(w,x); + } + BIG_XXX_copy(u[15],w); + +/* */ +#if SIGN_OF_X_ZZZ==NEGATIVEX + BIG_XXX_modneg(u[1],u[1],q); + BIG_XXX_modneg(u[3],u[3],q); + BIG_XXX_modneg(u[5],u[5],q); + BIG_XXX_modneg(u[7],u[7],q); + BIG_XXX_modneg(u[9],u[9],q); + BIG_XXX_modneg(u[11],u[11],q); + BIG_XXX_modneg(u[13],u[13],q); + BIG_XXX_modneg(u[15],u[15],q); +#endif + + + return; +} + +/* Multiply P by e in group G1 */ +void PAIR_ZZZ_G1mul(ECP_ZZZ *P,BIG_XXX e) +{ +#ifdef USE_GLV_ZZZ /* Note this method is patented */ + int np,nn; + ECP_ZZZ Q; + FP_YYY cru; + BIG_XXX t,q; + BIG_XXX u[2]; + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + glv(u,e); + + ECP_ZZZ_copy(&Q,P); ECP_ZZZ_affine(&Q); + FP_YYY_rcopy(&cru,CURVE_Cru_ZZZ); + FP_YYY_mul(&(Q.x),&(Q.x),&cru); + + /* note that -a.B = a.(-B). Use a or -a depending on which is smaller */ + + np=BIG_XXX_nbits(u[0]); + BIG_XXX_modneg(t,u[0],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[0],t); + ECP_ZZZ_neg(P); + } + + np=BIG_XXX_nbits(u[1]); + BIG_XXX_modneg(t,u[1],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[1],t); + ECP_ZZZ_neg(&Q); + } + BIG_XXX_norm(u[0]); + BIG_XXX_norm(u[1]); + ECP_ZZZ_mul2(P,&Q,u[0],u[1]); + +#else + ECP_ZZZ_mul(P,e); +#endif +} + +/* Multiply P by e in group G2 */ +void PAIR_ZZZ_G2mul(ECP8_ZZZ *P,BIG_XXX e) +{ +#ifdef USE_GS_G2_ZZZ /* Well I didn't patent it :) */ + int i,np,nn; + ECP8_ZZZ Q[16]; + FP2_YYY X[3]; + BIG_XXX x,y,u[16]; + + ECP8_ZZZ_frob_constants(X); + + BIG_XXX_rcopy(y,CURVE_Order_ZZZ); + gs(u,e); + + ECP8_ZZZ_copy(&Q[0],P); + for (i=1; i<16; i++) + { + ECP8_ZZZ_copy(&Q[i],&Q[i-1]); + ECP8_ZZZ_frob(&Q[i],X,1); + } + + for (i=0; i<16; i++) + { + np=BIG_XXX_nbits(u[i]); + BIG_XXX_modneg(x,u[i],y); + nn=BIG_XXX_nbits(x); + if (nn<np) + { + BIG_XXX_copy(u[i],x); + ECP8_ZZZ_neg(&Q[i]); + } + BIG_XXX_norm(u[i]); + } + + ECP8_ZZZ_mul16(P,Q,u); + +#else + ECP8_ZZZ_mul(P,e); +#endif +} + +/* f=f^e */ +void PAIR_ZZZ_GTpow(FP48_YYY *f,BIG_XXX e) +{ +#ifdef USE_GS_GT_ZZZ /* Note that this option requires a lot of RAM! Maybe better to use compressed XTR method, see FP16.cpp */ + int i,np,nn; + FP48_YYY g[16]; + FP2_YYY X; + BIG_XXX t,q; + FP_YYY fx,fy; + BIG_XXX u[16]; + + FP_YYY_rcopy(&fx,Fra_YYY); + FP_YYY_rcopy(&fy,Frb_YYY); + FP2_YYY_from_FPs(&X,&fx,&fy); + + BIG_XXX_rcopy(q,CURVE_Order_ZZZ); + gs(u,e); + + FP48_YYY_copy(&g[0],f); + for (i=1; i<16; i++) + { + FP48_YYY_copy(&g[i],&g[i-1]); + FP48_YYY_frob(&g[i],&X,1); + } + + for (i=0; i<16; i++) + { + np=BIG_XXX_nbits(u[i]); + BIG_XXX_modneg(t,u[i],q); + nn=BIG_XXX_nbits(t); + if (nn<np) + { + BIG_XXX_copy(u[i],t); + FP48_YYY_conj(&g[i],&g[i]); + } + BIG_XXX_norm(u[i]); + } + FP48_YYY_pow16(f,g,u); + +#else + FP48_YYY_pow(f,f,e); +#endif +} + +#ifdef HAS_MAIN + +using namespace std; +using namespace ZZZ; + + +// g++ -O2 pair256_BLS48.cpp ecp8_BLS48.cpp fp48_BLS48.cpp fp16_BLS48.cpp fp8_BLS48.cpp fp4_BLS48.cpp fp2_BLS48.cpp ecp_BLS48.cpp fp_BLS48.cpp big_B560_29.cpp rom_curve_BLS48.cpp rom_field_BLS48.cpp rand.cpp hash.cpp oct.cpp -o pair256_BLS48.exe + +int main() +{ + int i; + char byt[32]; + csprng rng; + BIG xa,xb,ya,yb,w,a,b,t1,q,u[2],v[4],m,r,xx,x2,x4,p; + ECP8 P,G; + ECP Q,R; + FP48 g,gp; + FP16 t,c,cp,cpm1,cpm2; + FP8 X,Y; + FP2 x,y,f,Aa,Bb; + FP cru; + + for (i=0;i<32;i++) + byt[i]=i+9; + RAND_seed(&rng,32,byt); + + BIG_rcopy(r,CURVE_Order); + BIG_rcopy(p,Modulus); + + + BIG_rcopy(xa,CURVE_Gx_ZZZ); + BIG_rcopy(ya,CURVE_Gy_ZZZ); + + ECP_ZZZ_set(&Q,xa,ya); + if (Q.inf) printf("Failed to set - point not on curve\n"); + else printf("G1 set success\n"); + + printf("Q= "); + ECP_ZZZ_output(&Q); + printf("\n"); + + ECP8_generator(&P); + + if (P.inf) printf("Failed to set - point not on curve\n"); + else printf("G2 set success\n"); + + BIG_rcopy(a,Fra); + BIG_rcopy(b,Frb); + FP2_from_BIGs(&f,a,b); + + PAIR_ZZZ_ate(&g,&P,&Q); + + printf("gb= "); + FP48_output(&g); + printf("\n"); + PAIR_ZZZ_fexp(&g); + + printf("g= "); + FP48_output(&g); + printf("\n"); + + ECP_ZZZ_copy(&R,&Q); + ECP8_copy(&G,&P); + + ECP8_dbl(&G); + ECP_dbl(&R); + ECP_affine(&R); + + PAIR_ZZZ_ate(&g,&G,&Q); + PAIR_ZZZ_fexp(&g); + + printf("g1= "); + FP48_output(&g); + printf("\n"); + + PAIR_ZZZ_ate(&g,&P,&R); + PAIR_ZZZ_fexp(&g); + + printf("g2= "); + FP48_output(&g); + printf("\n"); + + + PAIR_ZZZ_G1mul(&Q,r); + printf("rQ= ");ECP_output(&Q); printf("\n"); + + PAIR_ZZZ_G2mul(&P,r); + printf("rP= ");ECP8_output(&P); printf("\n"); + + PAIR_ZZZ_GTpow(&g,r); + printf("g^r= ");FP48_output(&g); printf("\n"); + + + BIG_randomnum(w,r,&rng); + + FP48_copy(&gp,&g); + + PAIR_ZZZ_GTpow(&g,w); + + FP48_trace(&t,&g); + + printf("g^r= ");FP16_output(&t); printf("\n"); + + FP48_compow(&t,&gp,w,r); + + printf("t(g)= "); FP16_output(&t); printf("\n"); + +} + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pair256.h ---------------------------------------------------------------------- diff --git a/version3/c/pair256.h b/version3/c/pair256.h new file mode 100644 index 0000000..d270f76 --- /dev/null +++ b/version3/c/pair256.h @@ -0,0 +1,77 @@ +#ifndef PAIR256_ZZZ_H +#define PAIR256_ZZZ_H + +#include "fp48_YYY.h" +#include "ecp8_ZZZ.h" +#include "ecp_ZZZ.h" + + +/* Pairing constants */ + +extern const BIG_XXX CURVE_Bnx_ZZZ; /**< BN curve x parameter */ +extern const BIG_XXX CURVE_Cru_ZZZ; /**< BN curve Cube Root of Unity */ + +extern const BIG_XXX CURVE_W_ZZZ[2]; /**< BN curve constant for GLV decomposition */ +extern const BIG_XXX CURVE_SB_ZZZ[2][2]; /**< BN curve constant for GLV decomposition */ +extern const BIG_XXX CURVE_WB_ZZZ[4]; /**< BN curve constant for GS decomposition */ +extern const BIG_XXX CURVE_BB_ZZZ[4][4]; /**< BN curve constant for GS decomposition */ + +/* Pairing function prototypes */ +/** @brief Calculate Miller loop for Optimal ATE pairing e(P,Q) + * + @param r FP48 result of the pairing calculation e(P,Q) + @param P ECP8 instance, an element of G2 + @param Q ECP instance, an element of G1 + + */ +extern void PAIR_ZZZ_ate(FP48_YYY *r,ECP8_ZZZ *P,ECP_ZZZ *Q); +/** @brief Calculate Miller loop for Optimal ATE double-pairing e(P,Q).e(R,S) + * + Faster than calculating two separate pairings + @param r FP48 result of the pairing calculation e(P,Q).e(R,S), an element of GT + @param P ECP8 instance, an element of G2 + @param Q ECP instance, an element of G1 + @param R ECP8 instance, an element of G2 + @param S ECP instance, an element of G1 + */ +extern void PAIR_ZZZ_double_ate(FP48_YYY *r,ECP8_ZZZ *P,ECP_ZZZ *Q,ECP8_ZZZ *R,ECP_ZZZ *S); +/** @brief Final exponentiation of pairing, converts output of Miller loop to element in GT + * + Here p is the internal modulus, and r is the group order + @param x FP48, on exit = x^((p^12-1)/r) + */ +extern void PAIR_ZZZ_fexp(FP48_YYY *x); +/** @brief Fast point multiplication of a member of the group G1 by a BIG number + * + May exploit endomorphism for speed. + @param Q ECP member of G1. + @param b BIG multiplier + + */ +extern void PAIR_ZZZ_G1mul(ECP_ZZZ *Q,BIG_XXX b); +/** @brief Fast point multiplication of a member of the group G2 by a BIG number + * + May exploit endomorphism for speed. + @param P ECP8 member of G1. + @param b BIG multiplier + + */ +extern void PAIR_ZZZ_G2mul(ECP8_ZZZ *P,BIG_XXX b); +/** @brief Fast raising of a member of GT to a BIG power + * + May exploit endomorphism for speed. + @param x FP48 member of GT. + @param b BIG exponent + + */ +extern void PAIR_ZZZ_GTpow(FP48_YYY *x,BIG_XXX b); +/** @brief Tests FP48 for membership of GT + * + @param x FP48 instance + @return 1 if x is in GT, else return 0 + + */ +extern int PAIR_ZZZ_GTmember(FP48_YYY *x); + + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pbc_support.c ---------------------------------------------------------------------- diff --git a/version3/c/pbc_support.c b/version3/c/pbc_support.c new file mode 100644 index 0000000..3639fb7 --- /dev/null +++ b/version3/c/pbc_support.c @@ -0,0 +1,180 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* Symmetric crypto support functions Functions */ + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> + +#include "pbc_support.h" + +/* general purpose hash function w=hash(p|n|x|y) */ +void mhashit(int sha,int n,octet *x,octet *w) +{ + int i,c[4],hlen; + hash256 sha256; + hash512 sha512; + char hh[64]; + + switch (sha) + { + case SHA256: + HASH256_init(&sha256); + break; + case SHA384: + HASH384_init(&sha512); + break; + case SHA512: + HASH512_init(&sha512); + break; + } + + hlen=sha; + + if (n>0) + { + c[0]=(n>>24)&0xff; + c[1]=(n>>16)&0xff; + c[2]=(n>>8)&0xff; + c[3]=(n)&0xff; + for (i=0; i<4; i++) + { + switch(sha) + { + case SHA256: + HASH256_process(&sha256,c[i]); + break; + case SHA384: + HASH384_process(&sha512,c[i]); + break; + case SHA512: + HASH512_process(&sha512,c[i]); + break; + } + } + } + + if (x!=NULL) for (i=0; i<x->len; i++) + { + switch(sha) + { + case SHA256: + HASH256_process(&sha256,x->val[i]); + + break; + case SHA384: + HASH384_process(&sha512,x->val[i]); + break; + case SHA512: + HASH512_process(&sha512,x->val[i]); + break; + } + } + + for (i=0; i<hlen; i++) hh[i]=0; + switch (sha) + { + case SHA256: + HASH256_hash(&sha256,hh); + break; + case SHA384: + HASH384_hash(&sha512,hh); + break; + case SHA512: + HASH512_hash(&sha512,hh); + break; + } + + OCT_empty(w); + + if (hlen>=w->max) + OCT_jbytes(w,hh,w->max); + else + { + OCT_jbyte(w,0,w->max-hlen); + OCT_jbytes(w,hh,hlen); + +// OCT_jbytes(w,hh,hlen); +// OCT_jbyte(w,0,w->max-hlen); + } +} + +unsign32 today(void) +{ + /* return time in slots since epoch */ + unsign32 ti=(unsign32)time(NULL); + return (uint32_t)(ti/(60*TIME_SLOT_MINUTES)); +} + +/* Hash the M-Pin transcript - new */ + +void HASH_ALL(int sha,octet *HID,octet *xID,octet *xCID,octet *SEC,octet *Y,octet *R,octet *W,octet *H) +{ + char t[1284]; // assumes max modulus of 1024-bits + octet T= {0,sizeof(t),t}; + + OCT_joctet(&T,HID); + if (xCID!=NULL) OCT_joctet(&T,xCID); + else OCT_joctet(&T,xID); + OCT_joctet(&T,SEC); + OCT_joctet(&T,Y); + OCT_joctet(&T,R); + OCT_joctet(&T,W); + + mhashit(sha,0,&T,H); +} + +void HASH_ID(int sha,octet *ID,octet *HID) +{ + mhashit(sha,0,ID,HID); +} + +unsign32 GET_TIME(void) +{ + return (unsign32)time(NULL); +} + +/* AES-GCM Encryption of octets, K is key, H is header, + P is plaintext, C is ciphertext, T is authentication tag */ +void AES_GCM_ENCRYPT(octet *K,octet *IV,octet *H,octet *P,octet *C,octet *T) +{ + gcm g; + GCM_init(&g,K->len,K->val,IV->len,IV->val); + GCM_add_header(&g,H->val,H->len); + GCM_add_plain(&g,C->val,P->val,P->len); + C->len=P->len; + GCM_finish(&g,T->val); + T->len=16; +} + +/* AES-GCM Decryption of octets, K is key, H is header, + P is plaintext, C is ciphertext, T is authentication tag */ +void AES_GCM_DECRYPT(octet *K,octet *IV,octet *H,octet *C,octet *P,octet *T) +{ + gcm g; + GCM_init(&g,K->len,K->val,IV->len,IV->val); + GCM_add_header(&g,H->val,H->len); + GCM_add_cipher(&g,P->val,C->val,C->len); + P->len=C->len; + GCM_finish(&g,T->val); + T->len=16; +} + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/pbc_support.h ---------------------------------------------------------------------- diff --git a/version3/c/pbc_support.h b/version3/c/pbc_support.h new file mode 100644 index 0000000..4fe82d9 --- /dev/null +++ b/version3/c/pbc_support.h @@ -0,0 +1,96 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/** + * @file pbc_support.h + * @author Mike Scott + * @brief Auxiliary functions for Pairing-based protocols + * + * + */ + +#ifndef PBC_SUPPORT_H +#define PBC_SUPPORT_H + +#include "amcl.h" + +#define TIME_SLOT_MINUTES 1440 /**< Time Slot = 1 day */ + +/** @brief general purpose hash function w=hash(n|x) + * + @param sha is the hash type + @param n integer involved in the hash + @param x octect involved in the h ash + @param w output + */ +extern void mhashit(int sha,int n,octet *x,octet *w); + +/** @brief Supply today's date as days from the epoch + * + @return today's date, as number of days elapsed since the epoch + */ +unsign32 today(void); +/** @brief Hash the session transcript + @param h is the hash type + @param I is the hashed input client ID = H(ID) + @param U is the client output = x.H(ID) + @param CU is the client output = x.(H(ID)+H(T|H(ID))) + @param Y is the server challenge + @param V is the client part response + @param R is the client part response + @param W is the server part response + @param H the output is the hash of all of the above that apply +*/ +void HASH_ALL(int h,octet *I,octet *U,octet *CU,octet *Y,octet *V,octet *R,octet *W,octet *H); +/** @brief Hash an M-Pin Identity to an octet string + * + @param h is the hash type + @param ID an octet containing the identity + @param HID an octet containing the hashed identity + */ +void HASH_ID(int h,octet *ID,octet *HID); +/** @brief Get epoch time as unsigned integer + * + @return current epoch time in seconds + */ +unsign32 GET_TIME(void); +/** @brief AES-GCM Encryption + * + @param K AES key + @param IV Initialization vector + @param H Header + @param P Plaintext + @param C Ciphertext + @param T Checksum + */ +void AES_GCM_ENCRYPT(octet *K,octet *IV,octet *H,octet *P,octet *C,octet *T); + +/** @brief AES-GCM Decryption + * + @param K AES key + @param IV Initialization vector + @param H Header + @param P Plaintext + @param C Ciphertext + @param T Checksum + */ +void AES_GCM_DECRYPT(octet *K,octet *IV,octet *H,octet *C,octet *P,octet *T); + + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/rand.c ---------------------------------------------------------------------- diff --git a/version3/c/rand.c b/version3/c/rand.c new file mode 100644 index 0000000..4a2cd0a --- /dev/null +++ b/version3/c/rand.c @@ -0,0 +1,172 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* + * Cryptographic strong random number generator + * + * Unguessable seed -> SHA -> PRNG internal state -> SHA -> random numbers + * Slow - but secure + * + * See ftp://ftp.rsasecurity.com/pub/pdfs/bull-1.pdf for a justification + */ +/* SU=m, m is Stack Usage */ + +#include "amcl.h" + +/* SU= 20 */ +static unsign32 sbrand(csprng *rng) +{ + /* Marsaglia & Zaman random number generator */ + int i,k; + unsign32 pdiff,t; + rng->rndptr++; + if (rng->rndptr<NK) return rng->ira[rng->rndptr]; + rng->rndptr=0; + for (i=0,k=NK-NJ; i<NK; i++,k++) + { + /* calculate next NK values */ + if (k==NK) k=0; + t=rng->ira[k]; + pdiff=t - rng->ira[i] - rng->borrow; + + if (pdiff<t) rng->borrow=0; + if (pdiff>t) rng->borrow=1; + rng->ira[i]=pdiff; + } + return rng->ira[0]; +} + +/* SU= 20 */ +static void sirand(csprng* rng,unsign32 seed) +{ + /* initialise random number system */ + /* modified so that a subsequent call "stirs" in another seed value */ + /* in this way as many seed bits as desired may be used */ + int i,in; + unsign32 t,m=1; + rng->borrow=0L; + rng->rndptr=0; + rng->ira[0]^=seed; + for (i=1; i<NK; i++) + { + /* fill initialisation vector */ + in=(NV*i)%NK; + rng->ira[in]^=m; /* note XOR */ + t=m; + m=seed-m; + seed=t; + } + for (i=0; i<10000; i++) sbrand(rng ); /* "warm-up" & stir the generator */ +} + +/* SU= 312 */ +static void fill_pool(csprng *rng) +{ + /* hash down output of RNG to re-fill the pool */ + int i; + hash256 sh; + HASH256_init(&sh); + for (i=0; i<128; i++) HASH256_process(&sh,sbrand(rng)); + HASH256_hash(&sh,rng->pool); + rng->pool_ptr=0; +} + +static unsign32 pack(const uchar *b) +{ + /* pack bytes into a 32-bit Word */ + return ((unsign32)b[3]<<24)|((unsign32)b[2]<<16)|((unsign32)b[1]<<8)|(unsign32)b[0]; +} + +/* SU= 360 */ +/* Initialize RNG with some real entropy from some external source */ +void RAND_seed(csprng *rng,int rawlen,char *raw) +{ + /* initialise from at least 128 byte string of raw * + * random (keyboard?) input, and 32-bit time-of-day */ + int i; + char digest[32]; + uchar b[4]; + hash256 sh; + rng->pool_ptr=0; + for (i=0; i<NK; i++) rng->ira[i]=0; + if (rawlen>0) + { + HASH256_init(&sh); + for (i=0; i<rawlen; i++) + HASH256_process(&sh,raw[i]); + HASH256_hash(&sh,digest); + + /* initialise PRNG from distilled randomness */ + + for (i=0; i<8; i++) + { + b[0]=digest[4*i]; + b[1]=digest[4*i+1]; + b[2]=digest[4*i+2]; + b[3]=digest[4*i+3]; + // printf("%08x\n",pack(b)); + sirand(rng,pack(b)); + } + } + fill_pool(rng); +} + +/* Terminate and clean up */ +void RAND_clean(csprng *rng) +{ + /* kill internal state */ + int i; + rng->pool_ptr=rng->rndptr=0; + for (i=0; i<32; i++) rng->pool[i]=0; + for (i=0; i<NK; i++) rng->ira[i]=0; + rng->borrow=0; +} + +/* get random byte */ +/* SU= 8 */ +int RAND_byte(csprng *rng) +{ + int r; + r=rng->pool[rng->pool_ptr++]; + if (rng->pool_ptr>=32) fill_pool(rng); + return (r&0xff); +} + +/* test main program */ +/* +#include <stdio.h> +#include <string.h> + +void main() +{ + int i; + char raw[256]; + csprng rng; + + RAND_clean(&rng); + + + for (i=0;i<256;i++) raw[i]=(char)i; + RAND_seed(&rng,256,raw); + + for (i=0;i<1000;i++) + printf("%02x ",(unsigned char)RAND_byte(&rng)); +} + +*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/randapi.c ---------------------------------------------------------------------- diff --git a/version3/c/randapi.c b/version3/c/randapi.c new file mode 100644 index 0000000..9b32efb --- /dev/null +++ b/version3/c/randapi.c @@ -0,0 +1,15 @@ +#include "randapi.h" + +/* Initialise a Cryptographically Strong Random Number Generator from + an octet of raw random data */ + +void CREATE_CSPRNG(csprng *RNG,octet *RAW) +{ + RAND_seed(RNG,RAW->len,RAW->val); +} + +void KILL_CSPRNG(csprng *RNG) +{ + RAND_clean(RNG); +} + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/randapi.h ---------------------------------------------------------------------- diff --git a/version3/c/randapi.h b/version3/c/randapi.h new file mode 100644 index 0000000..9a6807e --- /dev/null +++ b/version3/c/randapi.h @@ -0,0 +1,46 @@ +/* + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, + software distributed under the License is distributed on an + "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + KIND, either express or implied. See the License for the + specific language governing permissions and limitations + under the License. +*/ + +/** + * @file randapi.h + * @author Mike Scott + * @brief PRNG API File + * + */ + +#ifndef RANDOM_H +#define RANDOM_H + +#include "amcl.h" + +/** @brief Initialise a random number generator + * + @param R is a pointer to a cryptographically secure random number generator + @param S is an input truly random seed value + */ +extern void CREATE_CSPRNG(csprng *R,octet *S); +/** @brief Kill a random number generator + * + Deletes all internal state + @param R is a pointer to a cryptographically secure random number generator + */ +extern void KILL_CSPRNG(csprng *R); + +#endif + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/readme.txt ---------------------------------------------------------------------- diff --git a/version3/c/readme.txt b/version3/c/readme.txt new file mode 100644 index 0000000..36f143f --- /dev/null +++ b/version3/c/readme.txt @@ -0,0 +1,91 @@ +Namespaces are sinulated to separate different curves. + +To this end the BIG type is renamed to BIG_XXX, where XXX can be changed to +describe the size and layout of the BIG variable. Similarily the FP type +is renamed FP_YYY, where YYY reflects the modulus used. Also the ECP type +is renamed ECP_ZZZ, where ZZZ describes the actual curve. Function names +are also decorated in the same way. + +So for example to support both ED25519 and the NIST P256 curve on a 64-bit +processor, we would need to create BIG_256_56, FP_25519, ECP_ED25519 and +BIG_256_56, FP_NIST256, ECP_NIST256. Note that both curves could be built +on top of BIG_256_56, as both require support for 256-bit numbers using +an internal number base of 2^56. + +Separate ROM files provide the constants required for each curve. The +associated header files (big.h, fp.h and ecp.h) also specify +certain constants that must be set for the particular curve. + +-------------------------------------- + +To build the library and see it in action, copy all of the files in this +directory to a fresh directory. Then execute the python3 script config32.py +for a 32-bit build, or config64.py for a 64-bit build, and select the curves +that you wish to support. Note that support for 16-bit builds is currently +somewhat limited - see config16.py. A library is built automatically +including all of the modules that you will need. + +The configuration files assume the gcc compiler. For clang edit the +config32.py and config64.py files and substitute "clang" for "gcc". +Note that clang is about 10-15% faster.* + +NOTE: In the file config_curve.h a couple of methods with possible IP issues +are commented out. For faster pairing code, edit this file. + +As a quick example execute + +py config32.py + +or + +python3 config32.py + +Then select options 1, 3, 7, 18, 20, 25, 26 and 27, which are fixed for the example +program. (For a 16-bit build select 1,3 and 5). Select 0 then to exit. + +Then compile + +gcc -O2 -std=c99 testall.c amcl.a -o testall.exe + +if using MINGW in Windows. Or for Linux + +gcc -O2 -std=c99 testall.c amcl.a -o testall + +The test program exercises 3 different ordinary elliptic curves, a +pairing friendly curve and RSA, all in the one binary. + +The correct PIN is 1234 + + +Next compile + +gcc -O2 -std=c99 testbls.c amcl.a -o testbls.exe + +if using MINGW in Windows. Or for Linux + +gcc -O2 -std=c99 testbls.c amcl.a -o testbls + +This program implements the pairing-based BLS signature + + +Next compile + +gcc -O2 -std=c99 benchtest_all.c amcl.a -o benchtest_all.exe + +if using MINGW in Windows. Or for Linux + +gcc -O2 -std=c99 benchtest_all.c amcl.a -o benchtest_all + +This program provides some timings. + +Finally + +gcc -O2 -std=c99 testnhs.c amcl.a -o testnhs + + + +*Using clang on Windows +Download latest clang from http://releases.llvm.org/download.html +Choose Clang for Windows (64-bit) (.sig) +Install a free version of Microsoft Visual C++ https://www.visualstudio.com/downloads/ +Now use "clang" wherever "gcc" was used before. http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/rom_curve_ANSSI.c ---------------------------------------------------------------------- diff --git a/version3/c/rom_curve_ANSSI.c b/version3/c/rom_curve_ANSSI.c new file mode 100644 index 0000000..535a697 --- /dev/null +++ b/version3/c/rom_curve_ANSSI.c @@ -0,0 +1,33 @@ +#include "arch.h" +#include "ecp_ANSSI.h" + +/* ANSSI Curve */ + +#if CHUNK==16 + +#error Not supported + +#endif + +#if CHUNK==32 +const int CURVE_Cof_I_ANNSI= 1; +const BIG_256_28 CURVE_Cof_ANSSI= {0x1,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0}; +const int CURVE_A_ANSSI= -3; +const int CURVE_B_I_ANSSI= 0; +const BIG_256_28 CURVE_B_ANSSI= {0xB7BB73F,0x75ED967,0x1A18030,0xC9AE4B,0xFDFEC,0x754A44C,0xD4ABA,0x5428A93,0xE353FCA,0xE}; +const BIG_256_28 CURVE_Order_ANSSI= {0x6D655E1,0xFDD459C,0x2BF941F,0x67E140D,0x35B53DC,0xE8CE424,0xF10126D,0xB3AD58,0x1FD178C,0xF}; +const BIG_256_28 CURVE_Gx_ANSSI= {0x98F5CFF,0xC97A2DD,0x8B70164,0xD2DCAF9,0x3958C27,0x4749D42,0xB31183D,0x56C139E,0x6B3D4C3,0xB}; +const BIG_256_28 CURVE_Gy_ANSSI= {0x4062CFB,0x115A155,0x4C9E183,0xC307E8E,0xF8C2701,0xF0F3ECE,0x11F9271,0xC8B2049,0x142E0F7,0x6}; +#endif + +#if CHUNK==64 +const int CURVE_Cof_I_ANNSI= 1; +const BIG_256_56 CURVE_Cof_ANSSI= {0x1L,0x0L,0x0L,0x0L,0x0L}; +const int CURVE_A_ANSSI= -3; +const int CURVE_B_I_ANSSI= 0; +const BIG_256_56 CURVE_B_ANSSI= {0x75ED967B7BB73FL,0xC9AE4B1A18030L,0x754A44C00FDFECL,0x5428A9300D4ABAL,0xEE353FCAL}; +const BIG_256_56 CURVE_Order_ANSSI= {0xFDD459C6D655E1L,0x67E140D2BF941FL,0xE8CE42435B53DCL,0xB3AD58F10126DL,0xF1FD178CL}; +const BIG_256_56 CURVE_Gx_ANSSI= {0xC97A2DD98F5CFFL,0xD2DCAF98B70164L,0x4749D423958C27L,0x56C139EB31183DL,0xB6B3D4C3L}; +const BIG_256_56 CURVE_Gy_ANSSI= {0x115A1554062CFBL,0xC307E8E4C9E183L,0xF0F3ECEF8C2701L,0xC8B204911F9271L,0x6142E0F7L}; +#endif +
