| /* |
| 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); |
| // FP12_YYY_norm(v); |
| } |
| |
| /* 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_affine(P); |
| // ECP_ZZZ_affine(Q); |
| |
| 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(n,i); |
| 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) |
| { |
| //ECP2_ZZZ_neg(P); |
| PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); |
| FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); |
| //ECP2_ZZZ_neg(P); |
| } |
| |
| // FP12_YYY_sqr(r,r); |
| } |
| |
| // PAIR_ZZZ_line(&lv,&A,&A,&Qx,&Qy); |
| // FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); |
| |
| // if (BIG_XXX_parity(n)) |
| // { |
| // PAIR_ZZZ_line(&lv,&A,P,&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); |
| // FP12_YYY_conj(r,r); |
| #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); |
| //bt=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) |
| { |
| //ECP2_ZZZ_neg(P); |
| PAIR_ZZZ_line(&lv,&A,&NP,&Qx,&Qy); |
| FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); |
| //ECP2_ZZZ_neg(P); |
| |
| //ECP2_ZZZ_neg(R); |
| PAIR_ZZZ_line(&lv,&B,&NR,&Sx,&Sy); |
| FP12_YYY_smul(r,&lv,SEXTIC_TWIST_ZZZ); |
| //ECP2_ZZZ_neg(R); |
| } |
| |
| //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); |
| |
| // if (BIG_XXX_parity(n)) |
| // { |
| // 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); |
| // } |
| |
| /* 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 |
| //FP12_YYY_conj(r,r); |
| 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); |
| |
| // Aranha et al method as described by Ghamman & Fouotsa |
| /* |
| FP12_YYY_usqr(&y0,r); // t0=f^2 |
| FP12_YYY_conj(&y3,&y0); // t0=f^-2 |
| FP12_YYY_pow(&t0,r,x); // t5=f^u |
| FP12_YYY_usqr(&y1,&t0); // t1=t5^2 |
| FP12_YYY_mul(&y3,&t0); // t3=t0*t5 |
| |
| FP12_YYY_pow(&y0,&y3,x); |
| |
| FP12_YYY_pow(&y2,&y0,x); |
| |
| FP12_YYY_pow(&y4,&y2,x); |
| |
| FP12_YYY_mul(&y4,&y1); |
| FP12_YYY_pow(&y1,&y4,x); |
| FP12_YYY_conj(&y3,&y3); |
| FP12_YYY_mul(&y1,&y3); |
| FP12_YYY_mul(&y1,r); |
| |
| FP12_YYY_conj(&y3,r); |
| FP12_YYY_mul(&y0,r); |
| FP12_YYY_frob(&y0,&X); FP12_YYY_frob(&y0,&X); FP12_YYY_frob(&y0,&X); |
| |
| FP12_YYY_mul(&y4,&y3); |
| FP12_YYY_frob(&y4,&X); |
| |
| FP12_YYY_mul(&t0,&y2); |
| FP12_YYY_frob(&t0,&X); FP12_YYY_frob(&t0,&X); |
| |
| FP12_YYY_mul(&t0,&y0); |
| FP12_YYY_mul(&t0,&y4); |
| FP12_YYY_mul(&t0,&y1); |
| FP12_YYY_copy(r,&t0); |
| FP12_YYY_reduce(r);*/ |
| |
| //----------------------------------- |
| /* |
| FP12_YYY_copy(&y0,r); // y0=r; |
| FP12_YYY_copy(&y1,r); // y1=r; |
| FP12_YYY_copy(&t0,r); FP12_YYY_frob(&t0,&X); // t0=Frobenius(r,X,1); |
| FP12_YYY_conj(&y3,&t0); FP12_YYY_mul(&y1,&y3); // y1*=inverse(t0); |
| FP12_YYY_frob(&t0,&X); FP12_YYY_frob(&t0,&X); // t0=Frobenius(t0,X,2); |
| FP12_YYY_mul(&y1,&t0); // y1*=t0; |
| |
| FP12_YYY_pow(r,r,x); // r=pow(r,x); |
| FP12_YYY_conj(&y3,r); FP12_YYY_mul(&y1,&y3); // y1*=inverse(r); |
| FP12_YYY_copy(&t0,r); FP12_YYY_frob(&t0,&X); // t0=Frobenius(r,X,1); |
| FP12_YYY_mul(&y0,&t0); // y0*=t0; |
| FP12_YYY_frob(&t0,&X); // t0=Frobenius(t0,X,1); |
| FP12_YYY_mul(&y1,&t0); // y1*=t0; |
| FP12_YYY_frob(&t0,&X); // t0=Frobenius(t0,X,1); |
| FP12_YYY_conj(&y3,&t0); FP12_YYY_mul(&y0,&y3); // y0*=inverse(t0); |
| |
| FP12_YYY_pow(r,r,x); // r=pow(r,x); |
| FP12_YYY_mul(&y0,r); // y0*=r; |
| FP12_YYY_copy(&t0,r); FP12_YYY_frob(&t0,&X); FP12_YYY_frob(&t0,&X); // t0=Frobenius(r,X,2); |
| FP12_YYY_conj(&y3,&t0); FP12_YYY_mul(&y0,&y3); // y0*=inverse(t0); |
| FP12_YYY_frob(&t0,&X); // t0=Frobenius(t0,X,1); |
| FP12_YYY_mul(&y1,&t0); // y1*=t0; |
| |
| FP12_YYY_pow(r,r,x); // r=pow(r,x); // r^x3 |
| FP12_YYY_copy(&t0,r); FP12_YYY_frob(&t0,&X); // t0=Frobenius(r,X,1); |
| FP12_YYY_conj(&y3,&t0); FP12_YYY_mul(&y0,&y3); // y0*=inverse(t0); |
| FP12_YYY_frob(&t0,&X); // t0=Frobenius(t0,X,1); |
| FP12_YYY_mul(&y1,&t0); // y1*=t0; |
| |
| FP12_YYY_pow(r,r,x); // r=pow(r,x); // r^x4 |
| FP12_YYY_conj(&y3,r); FP12_YYY_mul(&y0,&y3); // y0*=inverse(r); |
| FP12_YYY_copy(&t0,r); FP12_YYY_frob(&t0,&X); // t0=Frobenius(r,X,1); |
| FP12_YYY_mul(&y1,&t0); //y1*=t0; |
| |
| FP12_YYY_pow(r,r,x); // r=pow(r,x); // r^x5 |
| FP12_YYY_mul(&y1,r); // y1*=r; |
| |
| FP12_YYY_usqr(&y0,&y0); // r=y0*y0*y1; |
| FP12_YYY_mul(&y0,&y1); |
| FP12_YYY_copy(r,&y0); |
| 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_norm(t); BIG_XXX_norm(e); |
| 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_norm(t); BIG_XXX_norm(e); |
| 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_affine(P); |
| 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_affine(P); |
| |
| //printf("PPz= "); FP2_YYY_output(&(P->z)); printf("\n"); |
| |
| //printf("f= "); FP2_YYY_output(&X); printf("\n"); |
| |
| 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); |
| } |
| //printf("Q[0]= "); ECP2_ZZZ_output(&Q[0]); printf("\n"); |
| //printf("Q[1]= "); ECP2_ZZZ_output(&Q[1]); printf("\n"); |
| 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_affine(&Q[i]); |
| } |
| |
| |
| //printf("Q[2]= "); ECP2_ZZZ_output(&Q[2]); printf("\n"); |
| //printf("Q[3]= "); ECP2_ZZZ_output(&Q[3]); printf("\n"); |
| //exit(0); |
| |
| 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 |
| } |
| |
| /* test group membership test - no longer needed */ |
| /* with GT-Strong curve, now only check that m!=1, conj(m)*m==1, and m.m^{p^4}=m^{p^2} */ |
| |
| /* |
| int PAIR_ZZZ_GTmember(FP12_YYY *m) |
| { |
| BIG_XXX a,b; |
| FP2_YYY X; |
| FP12_YYY r,w; |
| if (FP12_YYY_isunity(m)) return 0; |
| FP12_YYY_conj(&r,m); |
| FP12_YYY_mul(&r,m); |
| if (!FP12_YYY_isunity(&r)) return 0; |
| |
| BIG_XXX_rcopy(a,CURVE_Fra); |
| BIG_XXX_rcopy(b,CURVE_Frb); |
| FP2_YYY_from_BIGs(&X,a,b); |
| |
| |
| FP12_YYY_copy(&r,m); FP12_YYY_frob(&r,&X); FP12_YYY_frob(&r,&X); |
| FP12_YYY_copy(&w,&r); FP12_YYY_frob(&w,&X); FP12_YYY_frob(&w,&X); |
| FP12_YYY_mul(&w,m); |
| |
| |
| #ifndef GT_STRONG |
| if (!FP12_YYY_equals(&w,&r)) return 0; |
| |
| BIG_XXX_rcopy(a,CURVE_Bnx); |
| |
| FP12_YYY_copy(&r,m); FP12_YYY_pow(&w,&r,a); FP12_YYY_pow(&w,&w,a); |
| FP12_YYY_sqr(&r,&w); FP12_YYY_mul(&r,&w); FP12_YYY_sqr(&r,&r); |
| |
| FP12_YYY_copy(&w,m); FP12_YYY_frob(&w,&X); |
| #endif |
| |
| return FP12_YYY_equals(&w,&r); |
| } |
| |
| */ |
| |
| |
| #ifdef HAS_MAIN |
| /* |
| #if CHOICE==BN254_T |
| |
| const BIG_XXX TEST_Gx={0x18AFF11A,0xF2EF406,0xAF68220,0x171F2E27,0x6BA0959,0x124C50E0,0x450BE27,0x7003EA8,0x8A914}; |
| const BIG_XXX TEST_Gy={0x6E010F4,0xA71D07E,0x7ECADA8,0x8260E8E,0x1F79C328,0x17A09412,0xBFAE690,0x1C57CBD1,0x17DF54}; |
| |
| const BIG_XXX TEST_Pxa={0x1047D566,0xD83CD71,0x10322E9D,0x991FA93,0xA282C48,0x18AEBEC8,0xCB05850,0x13B4F669,0x21794A}; |
| const BIG_XXX TEST_Pxb={0x1E305936,0x16885BF1,0x327060,0xE26F794,0x1547D870,0x1963E5B2,0x1BEBB96C,0x988A33C,0x1A9B47}; |
| const BIG_XXX TEST_Pya={0x20FF876,0x4427E67,0x18732211,0xE88E45E,0x174D1A7E,0x17D877ED,0x343AB37,0x97EB453,0xB00D5}; |
| const BIG_XXX TEST_Pyb={0x1D746B7B,0x732F4C2,0x122A49B0,0x16267985,0x235DF56,0x10B1E4D,0x14D8F210,0x17A05C3E,0x5ECF8}; |
| |
| #endif |
| |
| #if CHOICE==BN254_T2 |
| |
| const BIG_XXX TEST_Gx={0x15488765,0x46790D7,0xD9900A,0x1DFB43F,0x9F2D307,0xC4724E8,0x5678E51,0x15C3E3A7,0x1BEC8E}; |
| const BIG_XXX TEST_Gy={0x3D3273C,0x1AFA5FF,0x1880A139,0xACD34DF,0x17493067,0x10FA4103,0x1D4C9766,0x1A73F3DB,0x2D148}; |
| |
| const BIG_XXX TEST_Pxa={0xF8DC275,0xAC27FA,0x11815151,0x152691C8,0x5CDEBF1,0x7D5A965,0x1BF70CE3,0x679A1C8,0xD62CF}; |
| const BIG_XXX TEST_Pxb={0x1D17D7A8,0x6B28DF4,0x174A0389,0xFE67E5F,0x1FA97A3C,0x7F5F473,0xFFB5146,0x4BC19A5,0x227010}; |
| const BIG_XXX TEST_Pya={0x16CC1F90,0x5284627,0x171B91AB,0x11F843B9,0x1D468755,0x67E279C,0x19FE0EF8,0x1A0CAA6B,0x1CC6CB}; |
| const BIG_XXX TEST_Pyb={0x1FF0CF2A,0xBC83255,0x6DD6EE8,0xB8B752F,0x13E484EC,0x1809BE81,0x1A648AA1,0x8CEF3F3,0x86EE}; |
| |
| |
| #endif |
| |
| #if CHOICE==BN254 |
| |
| const BIG_XXX TEST_Gx={0x14BEC4670E4EB7,0xEA2973860F6861,0x35C14B2FC3C28F,0x4402A0B63B9473,0x2074A81D}; |
| const BIG_XXX TEST_Gy={0xC284846631CBEB,0x34A6E8D871B3B,0x89FB94A82B2006,0x87B20038771FC,0x6A41108}; |
| |
| const BIG_XXX TEST_Pxa={0xE4A00F52183C77,0x554E02DF4F8354,0xB65EB5CF1C2F89,0x8B71A87BFCFC9,0x49EEDB1}; |
| const BIG_XXX TEST_Pxb={0xCFB8FA9AA8845D,0x8A9CC76D966697,0x185BA05BF5EC08,0x76140E87D97226,0x1FB93AB6}; |
| const BIG_XXX TEST_Pya={0x3644CC1EDF208A,0xA637FB3FF8E257,0x4453DA2BB9E686,0xD14AD3CDF6A1FE,0xCD04A1E}; |
| const BIG_XXX TEST_Pyb={0x71BD7630A43C14,0x1CAA9F14EA264E,0x3C3C2DFC765DEF,0xCF59D1A1A7D6EE,0x11FF7795}; |
| |
| |
| #endif |
| */ |
| 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(r,CURVE_Order); BIG_XXX_dec(r,7); BIG_XXX_norm(r); |
| 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); |
| |
| // PAIR_ZZZ_GTpow(&g,xa); |
| |
| } |
| printf("g= "); |
| FP12_YYY_output(&g); |
| printf("\n"); |
| |
| } |
| |
| #endif |