http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/ecdh_support.h ---------------------------------------------------------------------- diff --git a/version3/c/ecdh_support.h b/version3/c/ecdh_support.h new file mode 100644 index 0000000..85b200d --- /dev/null +++ b/version3/c/ecdh_support.h @@ -0,0 +1,114 @@ +/* + 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 ecdh_support.h + * @author Mike Scott + * @brief ECDH Support Header File + * + */ + +#ifndef ECC_SUPPORT_H +#define ECC_SUPPORT_H + +#include "amcl.h" + +/* Auxiliary Functions */ + +/** @brief general purpose hash function w=hash(p|n|x|y) + * + @param sha is the hash type + @param p first octect involved in the hash + @param n integer involved in the hash + @param x second octect involved in the h ash + @param w output + @param pad padding + */ +extern void ehashit(int sha,octet *p,int n,octet *x,octet *w,int pad); + +/** @brief hash an octet into another octet + * + @param h is the hash type + @param I input octet + @param O output octet - H(I) + */ +extern void HASH(int h,octet *I,octet *O); +/** @brief HMAC of message M using key K to create tag of length len in octet tag + * + IEEE-1363 MAC1 function. Uses SHA256 internally. + @param h is the hash type + @param M input message octet + @param K input encryption key + @param len is output desired length of HMAC tag + @param tag is the output HMAC + @return 0 for bad parameters, else 1 + */ +extern int HMAC(int h,octet *M,octet *K,int len,octet *tag); + +/*extern void KDF1(octet *,int,octet *);*/ + +/** @brief Key Derivation Function - generates key K from inputs Z and P + * + IEEE-1363 KDF2 Key Derivation Function. Uses SHA256 internally. + @param h is the hash type + @param Z input octet + @param P input key derivation parameters - can be NULL + @param len is output desired length of key + @param K is the derived key + */ +extern void KDF2(int h,octet *Z,octet *P,int len,octet *K); +/** @brief Password Based Key Derivation Function - generates key K from password, salt and repeat counter + * + PBKDF2 Password Based Key Derivation Function. Uses SHA256 internally. + @param h is the hash type + @param P input password + @param S input salt + @param rep Number of times to be iterated. + @param len is output desired length + @param K is the derived key + */ +extern void PBKDF2(int h,octet *P,octet *S,int rep,int len,octet *K); +/** @brief AES encrypts a plaintext to a ciphtertext + * + IEEE-1363 AES_CBC_IV0_ENCRYPT function. Encrypts in CBC mode with a zero IV, padding as necessary to create a full final block. + @param K AES key + @param P input plaintext octet + @param C output ciphertext octet + */ +extern void AES_CBC_IV0_ENCRYPT(octet *K,octet *P,octet *C); +/** @brief AES encrypts a plaintext to a ciphtertext + * + IEEE-1363 AES_CBC_IV0_DECRYPT function. Decrypts in CBC mode with a zero IV. + @param K AES key + @param C input ciphertext octet + @param P output plaintext octet + @return 0 if bad input, else 1 + */ +extern int AES_CBC_IV0_DECRYPT(octet *K,octet *C,octet *P); + +/* ECDH primitives - support functions */ +/** @brief Generate an ECC public/private key pair + * + @param R is a pointer to a cryptographically secure random number generator + @param s the private key, an output internally randomly generated if R!=NULL, otherwise must be provided as an input + @param W the output public key, which is s.G, where G is a fixed generator + @return 0 or an error code + */ + +#endif
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/ecp.c ---------------------------------------------------------------------- diff --git a/version3/c/ecp.c b/version3/c/ecp.c new file mode 100644 index 0000000..60eddaa --- /dev/null +++ b/version3/c/ecp.c @@ -0,0 +1,1288 @@ +/* +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 Elliptic Curve Functions */ +/* SU=m, SU is Stack Usage (Weierstrass Curves) */ + +//#define HAS_MAIN + +#include "ecp_ZZZ.h" + +/* test for P=O point-at-infinity */ +int ECP_ZZZ_isinf(ECP_ZZZ *P) +{ + +#if CURVETYPE_ZZZ==EDWARDS + return (FP_YYY_iszilch(&(P->x)) && FP_YYY_equals(&(P->y),&(P->z))); +#endif +#if CURVETYPE_ZZZ==WEIERSTRASS + return (FP_YYY_iszilch(&(P->x)) && FP_YYY_iszilch(&(P->z))); +#endif +#if CURVETYPE_ZZZ==MONTGOMERY + return FP_YYY_iszilch(&(P->z)); +#endif + +} + +/* Conditional swap of P and Q dependant on d */ +static void ECP_ZZZ_cswap(ECP_ZZZ *P,ECP_ZZZ *Q,int d) +{ + FP_YYY_cswap(&(P->x),&(Q->x),d); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_YYY_cswap(&(P->y),&(Q->y),d); +#endif + FP_YYY_cswap(&(P->z),&(Q->z),d); +} + +#if CURVETYPE_ZZZ!=MONTGOMERY +/* Conditional move Q to P dependant on d */ +static void ECP_ZZZ_cmove(ECP_ZZZ *P,ECP_ZZZ *Q,int d) +{ + FP_YYY_cmove(&(P->x),&(Q->x),d); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_YYY_cmove(&(P->y),&(Q->y),d); +#endif + FP_YYY_cmove(&(P->z),&(Q->z),d); +} + +/* return 1 if b==c, no branching */ +static int teq(sign32 b,sign32 c) +{ + sign32 x=b^c; + x-=1; // if x=0, x now -1 + return (int)((x>>31)&1); +} +#endif // CURVETYPE_ZZZ!=MONTGOMERY + +#if CURVETYPE_ZZZ!=MONTGOMERY +/* Constant time select from pre-computed table */ +static void ECP_ZZZ_select(ECP_ZZZ *P,ECP_ZZZ W[],sign32 b) +{ + ECP_ZZZ MP; + sign32 m=b>>31; + sign32 babs=(b^m)-m; + + babs=(babs-1)/2; + + ECP_ZZZ_cmove(P,&W[0],teq(babs,0)); // conditional move + ECP_ZZZ_cmove(P,&W[1],teq(babs,1)); + ECP_ZZZ_cmove(P,&W[2],teq(babs,2)); + ECP_ZZZ_cmove(P,&W[3],teq(babs,3)); + ECP_ZZZ_cmove(P,&W[4],teq(babs,4)); + ECP_ZZZ_cmove(P,&W[5],teq(babs,5)); + ECP_ZZZ_cmove(P,&W[6],teq(babs,6)); + ECP_ZZZ_cmove(P,&W[7],teq(babs,7)); + + ECP_ZZZ_copy(&MP,P); + ECP_ZZZ_neg(&MP); // minus P + ECP_ZZZ_cmove(P,&MP,(int)(m&1)); +} +#endif + +/* Test P == Q */ +/* SU=168 */ +int ECP_ZZZ_equals(ECP_ZZZ *P,ECP_ZZZ *Q) +{ + FP_YYY a,b; + + FP_YYY_mul(&a,&(P->x),&(Q->z)); + FP_YYY_mul(&b,&(Q->x),&(P->z)); + if (!FP_YYY_equals(&a,&b)) return 0; + +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_YYY_mul(&a,&(P->y),&(Q->z)); + FP_YYY_mul(&b,&(Q->y),&(P->z)); + if (!FP_YYY_equals(&a,&b)) return 0; +#endif + + return 1; + +} + +/* Set P=Q */ +/* SU=16 */ +void ECP_ZZZ_copy(ECP_ZZZ *P,ECP_ZZZ *Q) +{ + FP_YYY_copy(&(P->x),&(Q->x)); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_YYY_copy(&(P->y),&(Q->y)); +#endif + FP_YYY_copy(&(P->z),&(Q->z)); +} + +/* Set P=-Q */ +#if CURVETYPE_ZZZ!=MONTGOMERY +/* SU=8 */ +void ECP_ZZZ_neg(ECP_ZZZ *P) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + FP_YYY_neg(&(P->y),&(P->y)); + FP_YYY_norm(&(P->y)); +#else + FP_YYY_neg(&(P->x),&(P->x)); + FP_YYY_norm(&(P->x)); +#endif + +} +#endif + +/* Set P=O */ +void ECP_ZZZ_inf(ECP_ZZZ *P) +{ + FP_YYY_zero(&(P->x)); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_YYY_one(&(P->y)); +#endif +#if CURVETYPE_ZZZ!=EDWARDS + FP_YYY_zero(&(P->z)); +#else + FP_YYY_one(&(P->z)); +#endif +} + +/* Calculate right Hand Side of curve equation y^2=RHS */ +/* SU=56 */ +void ECP_ZZZ_rhs(FP_YYY *v,FP_YYY *x) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + /* x^3+Ax+B */ + FP_YYY t; + FP_YYY_sqr(&t,x); + FP_YYY_mul(&t,&t,x); + + if (CURVE_A_ZZZ==-3) + { + FP_YYY_neg(v,x); + FP_YYY_norm(v); + FP_YYY_imul(v,v,-CURVE_A_ZZZ); + FP_YYY_norm(v); + FP_YYY_add(v,&t,v); + } + else FP_YYY_copy(v,&t); + + FP_YYY_rcopy(&t,CURVE_B_ZZZ); + + FP_YYY_add(v,&t,v); + FP_YYY_reduce(v); +#endif + +#if CURVETYPE_ZZZ==EDWARDS + /* (Ax^2-1)/(Bx^2-1) */ + FP_YYY t,one; + FP_YYY_sqr(v,x); + FP_YYY_one(&one); + FP_YYY_rcopy(&t,CURVE_B_ZZZ); + + FP_YYY_mul(&t,v,&t); + FP_YYY_sub(&t,&t,&one); + FP_YYY_norm(&t); + if (CURVE_A_ZZZ==1) FP_YYY_sub(v,v,&one); + + if (CURVE_A_ZZZ==-1) + { + FP_YYY_add(v,v,&one); + FP_YYY_norm(v); + FP_YYY_neg(v,v); + } + FP_YYY_norm(v); + FP_YYY_inv(&t,&t); + FP_YYY_mul(v,v,&t); + FP_YYY_reduce(v); +#endif + +#if CURVETYPE_ZZZ==MONTGOMERY + /* x^3+Ax^2+x */ + FP_YYY x2,x3; + FP_YYY_sqr(&x2,x); + FP_YYY_mul(&x3,&x2,x); + FP_YYY_copy(v,x); + FP_YYY_imul(&x2,&x2,CURVE_A_ZZZ); + FP_YYY_add(v,v,&x2); + FP_YYY_add(v,v,&x3); + FP_YYY_reduce(v); +#endif +} + +#if CURVETYPE_ZZZ==MONTGOMERY + +/* Set P=(x,{y}) */ + +int ECP_ZZZ_set(ECP_ZZZ *P,BIG_XXX x) +{ + BIG_XXX m,b; + FP_YYY rhs; + BIG_XXX_rcopy(m,Modulus_YYY); + + FP_YYY_nres(&rhs,x); + + ECP_ZZZ_rhs(&rhs,&rhs); + FP_YYY_redc(b,&rhs); + + if (BIG_XXX_jacobi(b,m)!=1) + { + ECP_ZZZ_inf(P); + return 0; + } + + FP_YYY_nres(&(P->x),x); + FP_YYY_one(&(P->z)); + return 1; +} + +/* Extract x coordinate as BIG */ +int ECP_ZZZ_get(BIG_XXX x,ECP_ZZZ *P) +{ + ECP_ZZZ W; + ECP_ZZZ_copy(&W,P); + ECP_ZZZ_affine(&W); + if (ECP_ZZZ_isinf(&W)) return -1; + FP_YYY_redc(x,&(Wx)); + return 0; +} + + +#else +/* Extract (x,y) and return sign of y. If x and y are the same return only x */ +/* SU=16 */ +int ECP_ZZZ_get(BIG_XXX x,BIG_XXX y,ECP_ZZZ *P) +{ + ECP_ZZZ W; + int s; + ECP_ZZZ_copy(&W,P); + ECP_ZZZ_affine(&W); + + if (ECP_ZZZ_isinf(&W)) return -1; + + FP_YYY_redc(y,&(W.y)); + s=BIG_XXX_parity(y); + + FP_YYY_redc(x,&(W.x)); + + return s; +} + +/* Set P=(x,{y}) */ +/* SU=96 */ +int ECP_ZZZ_set(ECP_ZZZ *P,BIG_XXX x,BIG_XXX y) +{ + FP_YYY rhs,y2; + + FP_YYY_nres(&y2,y); + FP_YYY_sqr(&y2,&y2); + FP_YYY_reduce(&y2); + + FP_YYY_nres(&rhs,x); + ECP_ZZZ_rhs(&rhs,&rhs); + + if (!FP_YYY_equals(&y2,&rhs)) + { + ECP_ZZZ_inf(P); + return 0; + } + + FP_YYY_nres(&(P->x),x); + FP_YYY_nres(&(P->y),y); + FP_YYY_one(&(P->z)); + return 1; +} + +/* Set P=(x,y), where y is calculated from x with sign s */ +/* SU=136 */ +int ECP_ZZZ_setx(ECP_ZZZ *P,BIG_XXX x,int s) +{ + FP_YYY rhs; + BIG_XXX t,m; + BIG_XXX_rcopy(m,Modulus_YYY); + + FP_YYY_nres(&rhs,x); + + ECP_ZZZ_rhs(&rhs,&rhs); + + FP_YYY_redc(t,&rhs); + if (BIG_XXX_jacobi(t,m)!=1) + { + ECP_ZZZ_inf(P); + return 0; + } + + FP_YYY_nres(&(P->x),x); + FP_YYY_sqrt(&(P->y),&rhs); + + FP_YYY_redc(t,&(P->y)); + + if (BIG_XXX_parity(t)!=s) + FP_YYY_neg(&(P->y),&(P->y)); + FP_YYY_reduce(&(P->y)); + FP_YYY_one(&(P->z)); + return 1; +} + +#endif + +void ECP_ZZZ_cfp(ECP_ZZZ *P) +{ /* multiply point by curves cofactor */ + BIG_XXX c; + int cf=CURVE_Cof_I_ZZZ; + if (cf==1) return; + if (cf==4) + { + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + return; + } + if (cf==8) + { + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + return; + } + BIG_XXX_rcopy(c,CURVE_Cof_ZZZ); + ECP_ZZZ_mul(P,c); + return; +} + +/* map BIG to point on curve of correct order */ +/* The BIG should be the output of some hash function */ + +void ECP_ZZZ_mapit(ECP_ZZZ *P,octet *W) +{ + BIG_XXX q,x; + BIG_XXX_fromBytes(x,W->val); + BIG_XXX_rcopy(q,Modulus_YYY); + BIG_XXX_mod(x,q); + + for (;;) + { + for (;;) + { +#if CURVETYPE_ZZZ!=MONTGOMERY + ECP_ZZZ_setx(P,x,0); +#else + ECP_ZZZ_set(P,x); +#endif + BIG_XXX_inc(x,1); BIG_XXX_norm(x); + if (!ECP_ZZZ_isinf(P)) break; + } + ECP_ZZZ_cfp(P); + if (!ECP_ZZZ_isinf(P)) break; + } +} + +/* Convert P to Affine, from (x,y,z) to (x,y) */ +/* SU=160 */ +void ECP_ZZZ_affine(ECP_ZZZ *P) +{ + FP_YYY one,iz; + BIG_XXX b; + if (ECP_ZZZ_isinf(P)) return; + FP_YYY_one(&one); + if (FP_YYY_equals(&(P->z),&one)) return; + + FP_YYY_inv(&iz,&(P->z)); + FP_YYY_mul(&(P->x),&(P->x),&iz); + +#if CURVETYPE_ZZZ==EDWARDS || CURVETYPE_ZZZ==WEIERSTRASS + + FP_YYY_mul(&(P->y),&(P->y),&iz); + FP_YYY_reduce(&(P->y)); + +#endif + + FP_YYY_reduce(&(P->x)); + FP_YYY_copy(&(P->z),&one); +} + +/* SU=120 */ +void ECP_ZZZ_outputxyz(ECP_ZZZ *P) +{ + BIG_XXX x,z; + if (ECP_ZZZ_isinf(P)) + { + printf("Infinity\n"); + return; + } + FP_YYY_reduce(&(P->x)); + FP_YYY_redc(x,&(P->x)); + FP_YYY_reduce(&(P->z)); + FP_YYY_redc(z,&(P->z)); + +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX y; + FP_YYY_reduce(&(P->y)); + FP_YYY_redc(y,&(P->y)); + printf("("); + BIG_XXX_output(x); + printf(","); + BIG_XXX_output(y); + printf(","); + BIG_XXX_output(z); + printf(")\n"); + +#else + printf("("); + BIG_XXX_output(x); + printf(","); + BIG_XXX_output(z); + printf(")\n"); +#endif +} + +/* SU=16 */ +/* Output point P */ +void ECP_ZZZ_output(ECP_ZZZ *P) +{ + BIG_XXX x; + if (ECP_ZZZ_isinf(P)) + { + printf("Infinity\n"); + return; + } + ECP_ZZZ_affine(P); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX y; + FP_YYY_redc(x,&(P->x)); + FP_YYY_redc(y,&(P->y)); + printf("("); + BIG_XXX_output(x); + printf(","); + BIG_XXX_output(y); + printf(")\n"); +#else + FP_YYY_redc(x,&(P->x)); + printf("("); + BIG_XXX_output(x); + printf(")\n"); +#endif +} + +/* SU=16 */ +/* Output point P */ +void ECP_ZZZ_rawoutput(ECP_ZZZ *P) +{ + BIG_XXX x,z; + +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX y; + FP_YYY_redc(x,&(P->x)); + FP_YYY_redc(y,&(P->y)); + FP_YYY_redc(z,&(P->z)); + printf("("); + BIG_XXX_output(x); + printf(","); + BIG_XXX_output(y); + printf(","); + BIG_XXX_output(z); + printf(")\n"); +#else + FP_YYY_redc(x,&(P->x)); + FP_YYY_redc(z,&(P->z)); + printf("("); + BIG_XXX_output(x); + printf(","); + BIG_XXX_output(z); + printf(")\n"); +#endif +} + +/* SU=88 */ +/* Convert P to octet string */ +void ECP_ZZZ_toOctet(octet *W,ECP_ZZZ *P,bool compress) +{ +#if CURVETYPE_ZZZ==MONTGOMERY + BIG_XXX x; + ECP_ZZZ_get(x,P); + W->len=MODBYTES_XXX+1; + W->val[0]=6; + BIG_XXX_toBytes(&(W->val[1]),x); +#else + BIG_XXX x,y; + ECP_ZZZ_get(x,y,P); + if (compress) + { + W->val[0]=0x02; + if (BIG_XXX_parity(y)==1) W->val[0]=0x03; + W->len=MODBYTES_XXX+1; + BIG_XXX_toBytes(&(W->val[1]),x); + } + else + { + W->val[0]=4; + W->len=2*MODBYTES_XXX+1; + BIG_XXX_toBytes(&(W->val[1]),x); + BIG_XXX_toBytes(&(W->val[MODBYTES_XXX+1]),y); + } +#endif +} + +/* SU=88 */ +/* Restore P from octet string */ +int ECP_ZZZ_fromOctet(ECP_ZZZ *P,octet *W) +{ +#if CURVETYPE_ZZZ==MONTGOMERY + BIG_XXX x; + BIG_XXX_fromBytes(x,&(W->val[1])); + if (ECP_ZZZ_set(P,x)) return 1; + return 0; +#else + BIG_XXX x,y; + int typ=W->val[0]; + BIG_XXX_fromBytes(x,&(W->val[1])); + if (typ==0x04) + { + BIG_XXX_fromBytes(y,&(W->val[MODBYTES_XXX+1])); + if (ECP_ZZZ_set(P,x,y)) return 1; + } + if (typ==0x02 || typ==0x03) + { + if (ECP_ZZZ_setx(P,x,typ&1)) return 1; + } + return 0; +#endif +} + + +/* Set P=2P */ +/* SU=272 */ +void ECP_ZZZ_dbl(ECP_ZZZ *P) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + FP_YYY t0,t1,t2,t3,x3,y3,z3,b; + + if (CURVE_A_ZZZ==0) + { + FP_YYY_sqr(&t0,&(P->y)); //t0.sqr(); + FP_YYY_mul(&t1,&(P->y),&(P->z)); //t1.mul(z); + + FP_YYY_sqr(&t2,&(P->z)); //t2.sqr(); + FP_YYY_add(&(P->z),&t0,&t0); //z.add(t0); + FP_YYY_norm(&(P->z)); //z.norm(); + FP_YYY_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP_YYY_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP_YYY_norm(&(P->z)); //z.norm(); + + FP_YYY_imul(&t2,&t2,3*CURVE_B_I_ZZZ); //t2.imul(3*ROM.CURVE_B_I); + FP_YYY_mul(&x3,&t2,&(P->z)); //x3.mul(z); + + FP_YYY_add(&y3,&t0,&t2); //y3.add(t2); + FP_YYY_norm(&y3); //y3.norm(); + FP_YYY_mul(&(P->z),&(P->z),&t1); //z.mul(t1); + + FP_YYY_add(&t1,&t2,&t2); //t1.add(t2); + FP_YYY_add(&t2,&t2,&t1); //t2.add(t1); + FP_YYY_sub(&t0,&t0,&t2); //t0.sub(t2); + FP_YYY_norm(&t0); //t0.norm(); + FP_YYY_mul(&y3,&y3,&t0); //y3.mul(t0); + FP_YYY_add(&y3,&y3,&x3); //y3.add(x3); + FP_YYY_mul(&t1,&(P->x),&(P->y)); //t1.mul(y); + + FP_YYY_norm(&t0); //x.norm(); + FP_YYY_mul(&(P->x),&t0,&t1); //x.mul(t1); + FP_YYY_add(&(P->x),&(P->x),&(P->x)); //x.add(x); + FP_YYY_norm(&(P->x)); //x.norm(); + FP_YYY_copy(&(P->y),&y3); //y.copy(y3); + FP_YYY_norm(&(P->y)); //y.norm(); + } + else // its -3 + { + + if (CURVE_B_I_ZZZ==0) //if (ROM.CURVE_B_I==0) + FP_YYY_rcopy(&b,CURVE_B_ZZZ); //b.copy(new FP(new BIG(ROM.CURVE_B))); + + FP_YYY_sqr(&t0,&(P->x)); //t0.sqr(); //1 x^2 + FP_YYY_sqr(&t1,&(P->y)); //t1.sqr(); //2 y^2 + FP_YYY_sqr(&t2,&(P->z)); //t2.sqr(); //3 + + FP_YYY_mul(&t3,&(P->x),&(P->y)); //t3.mul(y); //4 + FP_YYY_add(&t3,&t3,&t3); //t3.add(t3); + FP_YYY_norm(&t3); //t3.norm();//5 + + FP_YYY_mul(&z3,&(P->z),&(P->x)); //z3.mul(x); //6 + FP_YYY_add(&z3,&z3,&z3); //z3.add(z3); + FP_YYY_norm(&z3); //z3.norm();//7 + + if (CURVE_B_I_ZZZ==0) //if (ROM.CURVE_B_I==0) + FP_YYY_mul(&y3,&t2,&b); //y3.mul(b); //8 + else + FP_YYY_imul(&y3,&t2,CURVE_B_I_ZZZ); //y3.imul(ROM.CURVE_B_I); + + FP_YYY_sub(&y3,&y3,&z3); //y3.sub(z3); //y3.norm(); //9 *** + FP_YYY_add(&x3,&y3,&y3); //x3.add(y3); + FP_YYY_norm(&x3); //x3.norm();//10 + + FP_YYY_add(&y3,&y3,&x3); //y3.add(x3); //y3.norm();//11 + FP_YYY_sub(&x3,&t1,&y3); //x3.sub(y3); + FP_YYY_norm(&x3); //x3.norm();//12 + FP_YYY_add(&y3,&y3,&t1); //y3.add(t1); + FP_YYY_norm(&y3); //y3.norm();//13 + FP_YYY_mul(&y3,&y3,&x3); //y3.mul(x3); //14 + FP_YYY_mul(&x3,&x3,&t3); //x3.mul(t3); //15 + FP_YYY_add(&t3,&t2,&t2); //t3.add(t2); //16 + FP_YYY_add(&t2,&t2,&t3); //t2.add(t3); //17 + + if (CURVE_B_I_ZZZ==0) //if (ROM.CURVE_B_I==0) + FP_YYY_mul(&z3,&z3,&b); //z3.mul(b); //18 + else + FP_YYY_imul(&z3,&z3,CURVE_B_I_ZZZ); //z3.imul(ROM.CURVE_B_I); + + FP_YYY_sub(&z3,&z3,&t2); //z3.sub(t2); //z3.norm();//19 + FP_YYY_sub(&z3,&z3,&t0); //z3.sub(t0); + FP_YYY_norm(&z3); //z3.norm();//20 *** + FP_YYY_add(&t3,&z3,&z3); //t3.add(z3); //t3.norm();//21 + + FP_YYY_add(&z3,&z3,&t3); //z3.add(t3); + FP_YYY_norm(&z3); //z3.norm(); //22 + FP_YYY_add(&t3,&t0,&t0); //t3.add(t0); //t3.norm(); //23 + FP_YYY_add(&t0,&t0,&t3); //t0.add(t3); //t0.norm();//24 + FP_YYY_sub(&t0,&t0,&t2); //t0.sub(t2); + FP_YYY_norm(&t0); //t0.norm();//25 + + FP_YYY_mul(&t0,&t0,&z3); //t0.mul(z3);//26 + FP_YYY_add(&y3,&y3,&t0); //y3.add(t0); //y3.norm();//27 + FP_YYY_mul(&t0,&(P->y),&(P->z)); //t0.mul(z);//28 + FP_YYY_add(&t0,&t0,&t0); //t0.add(t0); + FP_YYY_norm(&t0); //t0.norm(); //29 + FP_YYY_mul(&z3,&z3,&t0); //z3.mul(t0);//30 + FP_YYY_sub(&(P->x),&x3,&z3); //x3.sub(z3); //x3.norm();//31 + FP_YYY_add(&t0,&t0,&t0); //t0.add(t0); + FP_YYY_norm(&t0); //t0.norm();//32 + FP_YYY_add(&t1,&t1,&t1); //t1.add(t1); + FP_YYY_norm(&t1); //t1.norm();//33 + FP_YYY_mul(&(P->z),&t0,&t1); //z3.mul(t1);//34 + + FP_YYY_norm(&(P->x)); //x.norm(); + FP_YYY_copy(&(P->y),&y3); //y.copy(y3); + FP_YYY_norm(&(P->y)); //y.norm(); + FP_YYY_norm(&(P->z)); //z.norm(); + } +#endif + +#if CURVETYPE_ZZZ==EDWARDS + /* Not using square for multiplication swap, as (1) it needs more adds, and (2) it triggers more reductions */ + + FP_YYY C,D,H,J; + + FP_YYY_sqr(&C,&(P->x)); //C.sqr(); + + FP_YYY_mul(&(P->x),&(P->x),&(P->y)); //x.mul(y); + FP_YYY_add(&(P->x),&(P->x),&(P->x)); //x.add(x); + FP_YYY_norm(&(P->x)); //x.norm(); + + FP_YYY_sqr(&D,&(P->y)); //D.sqr(); + + if (CURVE_A_ZZZ==-1) //if (ROM.CURVE_A==-1) + FP_YYY_neg(&C,&C); // C.neg(); + + FP_YYY_add(&(P->y),&C,&D); //y.add(D); + FP_YYY_norm(&(P->y)); //y.norm(); + FP_YYY_sqr(&H,&(P->z)); //H.sqr(); + FP_YYY_add(&H,&H,&H); //H.add(H); + + FP_YYY_sub(&J,&(P->y),&H); //J.sub(H); + FP_YYY_norm(&J); //J.norm(); + + FP_YYY_mul(&(P->x),&(P->x),&J); //x.mul(J); + FP_YYY_sub(&C,&C,&D); //C.sub(D); + FP_YYY_norm(&C); //C.norm(); + FP_YYY_mul(&(P->z),&(P->y),&J); //z.mul(J); + FP_YYY_mul(&(P->y),&(P->y),&C); //y.mul(C); + + +#endif + +#if CURVETYPE_ZZZ==MONTGOMERY + FP_YYY A,B,AA,BB,C; + + FP_YYY_add(&A,&(P->x),&(P->z)); //A.add(z); + FP_YYY_norm(&A); //A.norm(); + FP_YYY_sqr(&AA,&A); //AA.sqr(); + FP_YYY_sub(&B,&(P->x),&(P->z)); //B.sub(z); + FP_YYY_norm(&B); //B.norm(); + + FP_YYY_sqr(&BB,&B); //BB.sqr(); + FP_YYY_sub(&C,&AA,&BB); //C.sub(BB); + FP_YYY_norm(&C); //C.norm(); + FP_YYY_mul(&(P->x),&AA,&BB); //x.mul(BB); + FP_YYY_imul(&A,&C,(CURVE_A_ZZZ+2)/4); //A.imul((ROM.CURVE_A+2)/4); + + FP_YYY_add(&BB,&BB,&A); //BB.add(A); + FP_YYY_norm(&BB); //BB.norm(); + FP_YYY_mul(&(P->z),&BB,&C); //z.mul(C); + +#endif +} + +#if CURVETYPE_ZZZ==MONTGOMERY + +/* Set P+=Q. W is difference between P and Q and is affine */ +void ECP_ZZZ_add(ECP_ZZZ *P,ECP_ZZZ *Q,ECP_ZZZ *W) +{ + FP_YYY A,B,C,D,DA,CB; + + FP_YYY_add(&A,&(P->x),&(P->z)); //A.add(z); + FP_YYY_sub(&B,&(P->x),&(P->z)); //B.sub(z); + + FP_YYY_add(&C,&(Q->x),&(Q->z)); //C.add(Q.z); + + FP_YYY_sub(&D,&(Q->x),&(Q->z)); //D.sub(Q.z); + FP_YYY_norm(&A); //A.norm(); + + FP_YYY_norm(&D); //D.norm(); + FP_YYY_mul(&DA,&D,&A); //DA.mul(A); + + FP_YYY_norm(&C); //C.norm(); + FP_YYY_norm(&B); //B.norm(); + FP_YYY_mul(&CB,&C,&B); //CB.mul(B); + + FP_YYY_add(&A,&DA,&CB); //A.add(CB); + FP_YYY_norm(&A); //A.norm(); + FP_YYY_sqr(&(P->x),&A); //A.sqr(); + FP_YYY_sub(&B,&DA,&CB); //B.sub(CB); + FP_YYY_norm(&B); //B.norm(); + FP_YYY_sqr(&B,&B); //B.sqr(); + + FP_YYY_mul(&(P->z),&(W->x),&B); //z.mul(B); + +} + +#else + +/* Set P+=Q */ +/* SU=248 */ +void ECP_ZZZ_add(ECP_ZZZ *P,ECP_ZZZ *Q) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + + int b3; + FP_YYY t0,t1,t2,t3,t4,x3,y3,z3,b; + + if (CURVE_A_ZZZ==0) + { + b3=3*CURVE_B_I_ZZZ; //int b=3*ROM.CURVE_B_I; + FP_YYY_mul(&t0,&(P->x),&(Q->x)); //t0.mul(Q.x); + FP_YYY_mul(&t1,&(P->y),&(Q->y)); //t1.mul(Q.y); + FP_YYY_mul(&t2,&(P->z),&(Q->z)); //t2.mul(Q.z); + FP_YYY_add(&t3,&(P->x),&(P->y)); //t3.add(y); + FP_YYY_norm(&t3); //t3.norm(); + + FP_YYY_add(&t4,&(Q->x),&(Q->y)); //t4.add(Q.y); + FP_YYY_norm(&t4); //t4.norm(); + FP_YYY_mul(&t3,&t3,&t4); //t3.mul(t4); + FP_YYY_add(&t4,&t0,&t1); //t4.add(t1); + + FP_YYY_sub(&t3,&t3,&t4); //t3.sub(t4); + FP_YYY_norm(&t3); //t3.norm(); + FP_YYY_add(&t4,&(P->y),&(P->z)); //t4.add(z); + FP_YYY_norm(&t4); //t4.norm(); + FP_YYY_add(&x3,&(Q->y),&(Q->z)); //x3.add(Q.z); + FP_YYY_norm(&x3); //x3.norm(); + + FP_YYY_mul(&t4,&t4,&x3); //t4.mul(x3); + FP_YYY_add(&x3,&t1,&t2); //x3.add(t2); + + FP_YYY_sub(&t4,&t4,&x3); //t4.sub(x3); + FP_YYY_norm(&t4); //t4.norm(); + FP_YYY_add(&x3,&(P->x),&(P->z)); //x3.add(z); + FP_YYY_norm(&x3); //x3.norm(); + FP_YYY_add(&y3,&(Q->x),&(Q->z)); //y3.add(Q.z); + FP_YYY_norm(&y3); //y3.norm(); + FP_YYY_mul(&x3,&x3,&y3); //x3.mul(y3); + + FP_YYY_add(&y3,&t0,&t2); //y3.add(t2); + FP_YYY_sub(&y3,&x3,&y3); //y3.rsub(x3); + FP_YYY_norm(&y3); //y3.norm(); + FP_YYY_add(&x3,&t0,&t0); //x3.add(t0); + FP_YYY_add(&t0,&t0,&x3); //t0.add(x3); + FP_YYY_norm(&t0); //t0.norm(); + FP_YYY_imul(&t2,&t2,b3); //t2.imul(b); + + FP_YYY_add(&z3,&t1,&t2); //z3.add(t2); + FP_YYY_norm(&z3); //z3.norm(); + FP_YYY_sub(&t1,&t1,&t2); //t1.sub(t2); + FP_YYY_norm(&t1); //t1.norm(); + FP_YYY_imul(&y3,&y3,b3); //y3.imul(b); + + FP_YYY_mul(&x3,&y3,&t4); //x3.mul(t4); + FP_YYY_mul(&t2,&t3,&t1); //t2.mul(t1); + FP_YYY_sub(&(P->x),&t2,&x3); //x3.rsub(t2); + FP_YYY_mul(&y3,&y3,&t0); //y3.mul(t0); + FP_YYY_mul(&t1,&t1,&z3); //t1.mul(z3); + FP_YYY_add(&(P->y),&y3,&t1); //y3.add(t1); + FP_YYY_mul(&t0,&t0,&t3); //t0.mul(t3); + FP_YYY_mul(&z3,&z3,&t4); //z3.mul(t4); + FP_YYY_add(&(P->z),&z3,&t0); //z3.add(t0); + + FP_YYY_norm(&(P->x)); //x.norm(); + FP_YYY_norm(&(P->y)); //y.norm(); + FP_YYY_norm(&(P->z)); //z.norm(); + } + else + { + + if (CURVE_B_I_ZZZ==0) //if (ROM.CURVE_B_I==0) + FP_YYY_rcopy(&b,CURVE_B_ZZZ); //b.copy(new FP(new BIG(ROM.CURVE_B))); + + FP_YYY_mul(&t0,&(P->x),&(Q->x)); //t0.mul(Q.x); //1 + FP_YYY_mul(&t1,&(P->y),&(Q->y)); //t1.mul(Q.y); //2 + FP_YYY_mul(&t2,&(P->z),&(Q->z)); //t2.mul(Q.z); //3 + + FP_YYY_add(&t3,&(P->x),&(P->y)); //t3.add(y); + FP_YYY_norm(&t3); //t3.norm(); //4 + FP_YYY_add(&t4,&(Q->x),&(Q->y)); //t4.add(Q.y); + FP_YYY_norm(&t4); //t4.norm();//5 + FP_YYY_mul(&t3,&t3,&t4); //t3.mul(t4);//6 + + FP_YYY_add(&t4,&t0,&t1); //t4.add(t1); //t4.norm(); //7 + FP_YYY_sub(&t3,&t3,&t4); //t3.sub(t4); + FP_YYY_norm(&t3); //t3.norm(); //8 + FP_YYY_add(&t4,&(P->y),&(P->z)); //t4.add(z); + FP_YYY_norm(&t4); //t4.norm();//9 + FP_YYY_add(&x3,&(Q->y),&(Q->z)); //x3.add(Q.z); + FP_YYY_norm(&x3); //x3.norm();//10 + FP_YYY_mul(&t4,&t4,&x3); //t4.mul(x3); //11 + FP_YYY_add(&x3,&t1,&t2); //x3.add(t2); //x3.norm();//12 + + FP_YYY_sub(&t4,&t4,&x3); //t4.sub(x3); + FP_YYY_norm(&t4); //t4.norm();//13 + FP_YYY_add(&x3,&(P->x),&(P->z)); //x3.add(z); + FP_YYY_norm(&x3); //x3.norm(); //14 + FP_YYY_add(&y3,&(Q->x),&(Q->z)); //y3.add(Q.z); + FP_YYY_norm(&y3); //y3.norm();//15 + + FP_YYY_mul(&x3,&x3,&y3); //x3.mul(y3); //16 + FP_YYY_add(&y3,&t0,&t2); //y3.add(t2); //y3.norm();//17 + + FP_YYY_sub(&y3,&x3,&y3); //y3.rsub(x3); + FP_YYY_norm(&y3); //y3.norm(); //18 + + if (CURVE_B_I_ZZZ==0) //if (ROM.CURVE_B_I==0) + FP_YYY_mul(&z3,&t2,&b); //z3.mul(b); //18 + else + FP_YYY_imul(&z3,&t2,CURVE_B_I_ZZZ); //z3.imul(ROM.CURVE_B_I); + + FP_YYY_sub(&x3,&y3,&z3); //x3.sub(z3); + FP_YYY_norm(&x3); //x3.norm(); //20 + FP_YYY_add(&z3,&x3,&x3); //z3.add(x3); //z3.norm(); //21 + + FP_YYY_add(&x3,&x3,&z3); //x3.add(z3); //x3.norm(); //22 + FP_YYY_sub(&z3,&t1,&x3); //z3.sub(x3); + FP_YYY_norm(&z3); //z3.norm(); //23 + FP_YYY_add(&x3,&x3,&t1); //x3.add(t1); + FP_YYY_norm(&x3); //x3.norm(); //24 + + if (CURVE_B_I_ZZZ==0) //if (ROM.CURVE_B_I==0) + FP_YYY_mul(&y3,&y3,&b); //y3.mul(b); //18 + else + FP_YYY_imul(&y3,&y3,CURVE_B_I_ZZZ); //y3.imul(ROM.CURVE_B_I); + + FP_YYY_add(&t1,&t2,&t2); //t1.add(t2); //t1.norm();//26 + FP_YYY_add(&t2,&t2,&t1); //t2.add(t1); //t2.norm();//27 + + FP_YYY_sub(&y3,&y3,&t2); //y3.sub(t2); //y3.norm(); //28 + + FP_YYY_sub(&y3,&y3,&t0); //y3.sub(t0); + FP_YYY_norm(&y3); //y3.norm(); //29 + FP_YYY_add(&t1,&y3,&y3); //t1.add(y3); //t1.norm();//30 + FP_YYY_add(&y3,&y3,&t1); //y3.add(t1); + FP_YYY_norm(&y3); //y3.norm(); //31 + + FP_YYY_add(&t1,&t0,&t0); //t1.add(t0); //t1.norm(); //32 + FP_YYY_add(&t0,&t0,&t1); //t0.add(t1); //t0.norm();//33 + FP_YYY_sub(&t0,&t0,&t2); //t0.sub(t2); + FP_YYY_norm(&t0); //t0.norm();//34 + + FP_YYY_mul(&t1,&t4,&y3); //t1.mul(y3);//35 + FP_YYY_mul(&t2,&t0,&y3); //t2.mul(y3);//36 + FP_YYY_mul(&y3,&x3,&z3); //y3.mul(z3);//37 + FP_YYY_add(&(P->y),&y3,&t2); //y3.add(t2); //y3.norm();//38 + FP_YYY_mul(&x3,&x3,&t3); //x3.mul(t3);//39 + FP_YYY_sub(&(P->x),&x3,&t1); //x3.sub(t1);//40 + FP_YYY_mul(&z3,&z3,&t4); //z3.mul(t4);//41 + + FP_YYY_mul(&t1,&t3,&t0); //t1.mul(t0);//42 + FP_YYY_add(&(P->z),&z3,&t1); //z3.add(t1); + FP_YYY_norm(&(P->x)); //x.norm(); + + FP_YYY_norm(&(P->y)); //y.norm(); + FP_YYY_norm(&(P->z)); //z.norm(); + } + +#else + FP_YYY A,B,C,D,E,F,G,b; + + FP_YYY_mul(&A,&(P->z),&(Q->z)); //A.mul(Q.z); + FP_YYY_sqr(&B,&A); //B.sqr(); + FP_YYY_mul(&C,&(P->x),&(Q->x)); //C.mul(Q.x); + FP_YYY_mul(&D,&(P->y),&(Q->y)); //D.mul(Q.y); + FP_YYY_mul(&E,&C,&D); //E.mul(D); + + if (CURVE_B_I_ZZZ==0) //if (ROM.CURVE_B_I==0) + { + FP_YYY_rcopy(&b,CURVE_B_ZZZ); //FP b=new FP(new BIG(ROM.CURVE_B)); + FP_YYY_mul(&E,&E,&b); //E.mul(b); + } + else + FP_YYY_imul(&E,&E,CURVE_B_I_ZZZ); //E.imul(ROM.CURVE_B_I); + + FP_YYY_sub(&F,&B,&E); //F.sub(E); + FP_YYY_add(&G,&B,&E); //G.add(E); + + if (CURVE_A_ZZZ==1) //if (ROM.CURVE_A==1) + { + FP_YYY_sub(&E,&D,&C); //E.sub(C); + } + FP_YYY_add(&C,&C,&D); //C.add(D); + FP_YYY_add(&B,&(P->x),&(P->y)); //B.add(y); + + FP_YYY_add(&D,&(Q->x),&(Q->y)); //D.add(Q.y); + FP_YYY_norm(&B); //B.norm(); + FP_YYY_norm(&D); //D.norm(); + FP_YYY_mul(&B,&B,&D); //B.mul(D); + FP_YYY_sub(&B,&B,&C); //B.sub(C); + FP_YYY_norm(&B); //B.norm(); + FP_YYY_norm(&F); //F.norm(); + FP_YYY_mul(&B,&B,&F); //B.mul(F); + FP_YYY_mul(&(P->x),&A,&B); //x.mul(B); + FP_YYY_norm(&G); //G.norm(); + + if (CURVE_A_ZZZ==1) //if (ROM.CURVE_A==1) + { + FP_YYY_norm(&E); //E.norm(); + FP_YYY_mul(&C,&E,&G); //C.mul(G); + } + if (CURVE_A_ZZZ==-1) //if (ROM.CURVE_A==-1) + { + FP_YYY_norm(&C); //C.norm(); + FP_YYY_mul(&C,&C,&G); //C.mul(G); + } + FP_YYY_mul(&(P->y),&A,&C); //y.mul(C); + FP_YYY_mul(&(P->z),&F,&G); //z.mul(G); + +#endif +} + +/* Set P-=Q */ +/* SU=16 */ +void ECP_ZZZ_sub(ECP_ZZZ *P,ECP_ZZZ *Q) +{ + ECP_ZZZ NQ; + ECP_ZZZ_copy(&NQ,Q); + ECP_ZZZ_neg(&NQ); + ECP_ZZZ_add(P,&NQ); +} + +#endif + +#if CURVETYPE_ZZZ!=MONTGOMERY +/* constant time multiply by small integer of length bts - use ladder */ +void ECP_ZZZ_pinmul(ECP_ZZZ *P,int e,int bts) +{ + int i,b; + ECP_ZZZ R0,R1; + + ECP_ZZZ_affine(P); + ECP_ZZZ_inf(&R0); + ECP_ZZZ_copy(&R1,P); + + for (i=bts-1; i>=0; i--) + { + b=(e>>i)&1; + ECP_ZZZ_copy(P,&R1); + ECP_ZZZ_add(P,&R0); + ECP_ZZZ_cswap(&R0,&R1,b); + ECP_ZZZ_copy(&R1,P); + ECP_ZZZ_dbl(&R0); + ECP_ZZZ_cswap(&R0,&R1,b); + } + ECP_ZZZ_copy(P,&R0); + ECP_ZZZ_affine(P); +} +#endif + +/* Set P=r*P */ +/* SU=424 */ +void ECP_ZZZ_mul(ECP_ZZZ *P,BIG_XXX e) +{ +#if CURVETYPE_ZZZ==MONTGOMERY + /* Montgomery ladder */ + int nb,i,b; + ECP_ZZZ R0,R1,D; + if (ECP_ZZZ_isinf(P)) return; + if (BIG_XXX_iszilch(e)) + { + ECP_ZZZ_inf(P); + return; + } + + ECP_ZZZ_copy(&R0,P); + ECP_ZZZ_copy(&R1,P); + ECP_ZZZ_dbl(&R1); + + ECP_ZZZ_copy(&D,P); + ECP_ZZZ_affine(&D); + + nb=BIG_XXX_nbits(e); + for (i=nb-2; i>=0; i--) + { + b=BIG_XXX_bit(e,i); + ECP_ZZZ_copy(P,&R1); + ECP_ZZZ_add(P,&R0,&D); + ECP_ZZZ_cswap(&R0,&R1,b); + ECP_ZZZ_copy(&R1,P); + ECP_ZZZ_dbl(&R0); + + ECP_ZZZ_cswap(&R0,&R1,b); + } + + ECP_ZZZ_copy(P,&R0); + +#else + /* fixed size windows */ + int i,nb,s,ns; + BIG_XXX mt,t; + ECP_ZZZ Q,W[8],C; + sign8 w[1+(NLEN_XXX*BASEBITS_XXX+3)/4]; + + if (ECP_ZZZ_isinf(P)) return; + if (BIG_XXX_iszilch(e)) + { + ECP_ZZZ_inf(P); + return; + } + + ECP_ZZZ_affine(P); + + /* precompute table */ + + ECP_ZZZ_copy(&Q,P); + ECP_ZZZ_dbl(&Q); + + ECP_ZZZ_copy(&W[0],P); + + for (i=1; i<8; i++) + { + ECP_ZZZ_copy(&W[i],&W[i-1]); + ECP_ZZZ_add(&W[i],&Q); + } + +//printf("W[1]= ");ECP_output(&W[1]); printf("\n"); + + /* make exponent odd - add 2P if even, P if odd */ + BIG_XXX_copy(t,e); + s=BIG_XXX_parity(t); + BIG_XXX_inc(t,1); + BIG_XXX_norm(t); + ns=BIG_XXX_parity(t); + BIG_XXX_copy(mt,t); + BIG_XXX_inc(mt,1); + BIG_XXX_norm(mt); + BIG_XXX_cmove(t,mt,s); + ECP_ZZZ_cmove(&Q,P,ns); + ECP_ZZZ_copy(&C,&Q); + + nb=1+(BIG_XXX_nbits(t)+3)/4; + + /* convert exponent to signed 4-bit window */ + for (i=0; i<nb; i++) + { + w[i]=BIG_XXX_lastbits(t,5)-16; + BIG_XXX_dec(t,w[i]); + BIG_XXX_norm(t); + BIG_XXX_fshr(t,4); + } + w[nb]=BIG_XXX_lastbits(t,5); + + ECP_ZZZ_copy(P,&W[(w[nb]-1)/2]); + for (i=nb-1; i>=0; i--) + { + ECP_ZZZ_select(&Q,W,w[i]); + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + ECP_ZZZ_add(P,&Q); + } + ECP_ZZZ_sub(P,&C); /* apply correction */ +#endif + ECP_ZZZ_affine(P); +} + +#if CURVETYPE_ZZZ!=MONTGOMERY +/* Set P=eP+fQ double multiplication */ +/* constant time - as useful for GLV method in pairings */ +/* SU=456 */ + +void ECP_ZZZ_mul2(ECP_ZZZ *P,ECP_ZZZ *Q,BIG_XXX e,BIG_XXX f) +{ + BIG_XXX te,tf,mt; + ECP_ZZZ S,T,W[8],C; + sign8 w[1+(NLEN_XXX*BASEBITS_XXX+1)/2]; + int i,a,b,s,ns,nb; + + BIG_XXX_copy(te,e); + BIG_XXX_copy(tf,f); + + /* precompute table */ + ECP_ZZZ_copy(&W[1],P); + ECP_ZZZ_sub(&W[1],Q); /* P+Q */ + ECP_ZZZ_copy(&W[2],P); + ECP_ZZZ_add(&W[2],Q); /* P-Q */ + ECP_ZZZ_copy(&S,Q); + ECP_ZZZ_dbl(&S); /* S=2Q */ + ECP_ZZZ_copy(&W[0],&W[1]); + ECP_ZZZ_sub(&W[0],&S); + ECP_ZZZ_copy(&W[3],&W[2]); + ECP_ZZZ_add(&W[3],&S); + ECP_ZZZ_copy(&T,P); + ECP_ZZZ_dbl(&T); /* T=2P */ + ECP_ZZZ_copy(&W[5],&W[1]); + ECP_ZZZ_add(&W[5],&T); + ECP_ZZZ_copy(&W[6],&W[2]); + ECP_ZZZ_add(&W[6],&T); + ECP_ZZZ_copy(&W[4],&W[5]); + ECP_ZZZ_sub(&W[4],&S); + ECP_ZZZ_copy(&W[7],&W[6]); + ECP_ZZZ_add(&W[7],&S); + + /* if multiplier is odd, add 2, else add 1 to multiplier, and add 2P or P to correction */ + + s=BIG_XXX_parity(te); + BIG_XXX_inc(te,1); + BIG_XXX_norm(te); + ns=BIG_XXX_parity(te); + BIG_XXX_copy(mt,te); + BIG_XXX_inc(mt,1); + BIG_XXX_norm(mt); + BIG_XXX_cmove(te,mt,s); + ECP_ZZZ_cmove(&T,P,ns); + ECP_ZZZ_copy(&C,&T); + + s=BIG_XXX_parity(tf); + BIG_XXX_inc(tf,1); + BIG_XXX_norm(tf); + ns=BIG_XXX_parity(tf); + BIG_XXX_copy(mt,tf); + BIG_XXX_inc(mt,1); + BIG_XXX_norm(mt); + BIG_XXX_cmove(tf,mt,s); + ECP_ZZZ_cmove(&S,Q,ns); + ECP_ZZZ_add(&C,&S); + + BIG_XXX_add(mt,te,tf); + BIG_XXX_norm(mt); + nb=1+(BIG_XXX_nbits(mt)+1)/2; + + /* convert exponent to signed 2-bit window */ + for (i=0; i<nb; i++) + { + a=BIG_XXX_lastbits(te,3)-4; + BIG_XXX_dec(te,a); + BIG_XXX_norm(te); + BIG_XXX_fshr(te,2); + b=BIG_XXX_lastbits(tf,3)-4; + BIG_XXX_dec(tf,b); + BIG_XXX_norm(tf); + BIG_XXX_fshr(tf,2); + w[i]=4*a+b; + } + w[nb]=(4*BIG_XXX_lastbits(te,3)+BIG_XXX_lastbits(tf,3)); + + ECP_ZZZ_copy(P,&W[(w[nb]-1)/2]); + for (i=nb-1; i>=0; i--) + { + ECP_ZZZ_select(&T,W,w[i]); + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + ECP_ZZZ_add(P,&T); + } + ECP_ZZZ_sub(P,&C); /* apply correction */ + ECP_ZZZ_affine(P); +} + +#endif + +void ECP_ZZZ_generator(ECP_ZZZ *G) +{ + BIG_XXX x,y; + BIG_XXX_rcopy(x,CURVE_Gx_ZZZ); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX_rcopy(y,CURVE_Gy_ZZZ); + ECP_ZZZ_set(G,x,y); +#else + ECP_ZZZ_set(G,x); +#endif +} + +#ifdef HAS_MAIN + +int main() +{ + int i; + ECP_ZZZ G,P; + csprng RNG; + BIG_XXX r,s,x,y,b,m,w,q; + BIG_XXX_rcopy(x,CURVE_Gx); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX_rcopy(y,CURVE_Gy); +#endif + BIG_XXX_rcopy(m,Modulus_YYY); + + printf("x= "); + BIG_XXX_output(x); + printf("\n"); +#if CURVETYPE_ZZZ!=MONTGOMERY + printf("y= "); + BIG_XXX_output(y); + printf("\n"); +#endif + RNG_seed(&RNG,3,"abc"); + +#if CURVETYPE_ZZZ!=MONTGOMERY + ECP_ZZZ_set(&G,x,y); +#else + ECP_ZZZ_set(&G,x); +#endif + if (ECP_ZZZ_isinf(&G)) printf("Failed to set - point not on curve\n"); + else printf("set success\n"); + + ECP_ZZZ_output(&G); + + BIG_XXX_rcopy(r,CURVE_Order); //BIG_dec(r,7); + printf("r= "); + BIG_XXX_output(r); + printf("\n"); + + ECP_ZZZ_copy(&P,&G); + + ECP_ZZZ_mul(&P,r); + + ECP_ZZZ_output(&P); +//exit(0); + BIG_XXX_randomnum(w,&RNG); + BIG_XXX_mod(w,r); + + ECP_ZZZ_copy(&P,&G); + ECP_ZZZ_mul(&P,w); + + ECP_ZZZ_output(&P); + + return 0; +} + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/ecp.h ---------------------------------------------------------------------- diff --git a/version3/c/ecp.h b/version3/c/ecp.h new file mode 100644 index 0000000..01dac7c --- /dev/null +++ b/version3/c/ecp.h @@ -0,0 +1,314 @@ +/* + 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 ecp.h + * @author Mike Scott + * @brief ECP Header File + * + */ + +#ifndef ECP_ZZZ_H +#define ECP_ZZZ_H + +#include "fp_YYY.h" +#include "config_curve_ZZZ.h" + +/* Curve Params - see rom_zzz.c */ +extern const int CURVE_A_ZZZ; /**< Elliptic curve A parameter */ +extern const int CURVE_Cof_I_ZZZ; /**< Elliptic curve cofactor */ +extern const int CURVE_B_I_ZZZ; /**< Elliptic curve B_i parameter */ +extern const BIG_XXX CURVE_B_ZZZ; /**< Elliptic curve B parameter */ +extern const BIG_XXX CURVE_Order_ZZZ; /**< Elliptic curve group order */ +extern const BIG_XXX CURVE_Cof_ZZZ; /**< Elliptic curve cofactor */ + +/* Generator point on G1 */ +extern const BIG_XXX CURVE_Gx_ZZZ; /**< x-coordinate of generator point in group G1 */ +extern const BIG_XXX CURVE_Gy_ZZZ; /**< y-coordinate of generator point in group G1 */ + + +/* For Pairings only */ + +/* Generator point on G2 */ +extern const BIG_XXX CURVE_Pxa_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxb_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pya_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyb_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ + + +/*** needed for BLS24 curves ***/ + +extern const BIG_XXX CURVE_Pxaa_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxab_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxba_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxbb_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyaa_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyab_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyba_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pybb_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ + +/*** needed for BLS48 curves ***/ + +extern const BIG_XXX CURVE_Pxaaa_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxaab_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxaba_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxabb_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxbaa_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxbab_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxbba_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxbbb_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ + +extern const BIG_XXX CURVE_Pyaaa_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyaab_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyaba_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyabb_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pybaa_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pybab_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pybba_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pybbb_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ + + +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 Fra_YYY; /**< real part of BN curve Frobenius Constant */ +extern const BIG_XXX Frb_YYY; /**< imaginary part of BN curve Frobenius Constant */ + + +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 */ + + +/** + @brief ECP structure - Elliptic Curve Point over base field +*/ + +typedef struct +{ +// int inf; /**< Infinity Flag - not needed for Edwards representation */ + + FP_YYY x; /**< x-coordinate of point */ +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_YYY y; /**< y-coordinate of point. Not needed for Montgomery representation */ +#endif + FP_YYY z;/**< z-coordinate of point */ +} ECP_ZZZ; + + +/* ECP E(Fp) prototypes */ +/** @brief Tests for ECP point equal to infinity + * + @param P ECP point to be tested + @return 1 if infinity, else returns 0 + */ +extern int ECP_ZZZ_isinf(ECP_ZZZ *P); +/** @brief Tests for equality of two ECPs + * + @param P ECP instance to be compared + @param Q ECP instance to be compared + @return 1 if P=Q, else returns 0 + */ +extern int ECP_ZZZ_equals(ECP_ZZZ *P,ECP_ZZZ *Q); +/** @brief Copy ECP point to another ECP point + * + @param P ECP instance, on exit = Q + @param Q ECP instance to be copied + */ +extern void ECP_ZZZ_copy(ECP_ZZZ *P,ECP_ZZZ *Q); +/** @brief Negation of an ECP point + * + @param P ECP instance, on exit = -P + */ +extern void ECP_ZZZ_neg(ECP_ZZZ *P); +/** @brief Set ECP to point-at-infinity + * + @param P ECP instance to be set to infinity + */ +extern void ECP_ZZZ_inf(ECP_ZZZ *P); +/** @brief Calculate Right Hand Side of curve equation y^2=f(x) + * + Function f(x) depends on form of elliptic curve, Weierstrass, Edwards or Montgomery. + Used internally. + @param r BIG n-residue value of f(x) + @param x BIG n-residue x + */ +extern void ECP_ZZZ_rhs(FP_YYY *r,FP_YYY *x); + +#if CURVETYPE_ZZZ==MONTGOMERY +/** @brief Set ECP to point(x,[y]) given x + * + Point P set to infinity if no such point on the curve. Note that y coordinate is not needed. + @param P ECP instance to be set (x,[y]) + @param x BIG x coordinate of point + @return 1 if point exists, else 0 + */ +extern int ECP_ZZZ_set(ECP_ZZZ *P,BIG_XXX x); +/** @brief Extract x coordinate of an ECP point P + * + @param x BIG on exit = x coordinate of point + @param P ECP instance (x,[y]) + @return -1 if P is point-at-infinity, else 0 + */ +extern int ECP_ZZZ_get(BIG_XXX x,ECP_ZZZ *P); +/** @brief Adds ECP instance Q to ECP instance P, given difference D=P-Q + * + Differential addition of points on a Montgomery curve + @param P ECP instance, on exit =P+Q + @param Q ECP instance to be added to P + @param D Difference between P and Q + */ +extern void ECP_ZZZ_add(ECP_ZZZ *P,ECP_ZZZ *Q,ECP_ZZZ *D); +#else +/** @brief Set ECP to point(x,y) given x and y + * + Point P set to infinity if no such point on the curve. + @param P ECP instance to be set (x,y) + @param x BIG x coordinate of point + @param y BIG y coordinate of point + @return 1 if point exists, else 0 + */ +extern int ECP_ZZZ_set(ECP_ZZZ *P,BIG_XXX x,BIG_XXX y); +/** @brief Extract x and y coordinates of an ECP point P + * + If x=y, returns only x + @param x BIG on exit = x coordinate of point + @param y BIG on exit = y coordinate of point (unless x=y) + @param P ECP instance (x,y) + @return sign of y, or -1 if P is point-at-infinity + */ +extern int ECP_ZZZ_get(BIG_XXX x,BIG_XXX y,ECP_ZZZ *P); +/** @brief Adds ECP instance Q to ECP instance P + * + @param P ECP instance, on exit =P+Q + @param Q ECP instance to be added to P + */ +extern void ECP_ZZZ_add(ECP_ZZZ *P,ECP_ZZZ *Q); +/** @brief Subtracts ECP instance Q from ECP instance P + * + @param P ECP instance, on exit =P-Q + @param Q ECP instance to be subtracted from P + */ +extern void ECP_ZZZ_sub(ECP_ZZZ *P,ECP_ZZZ *Q); +/** @brief Set ECP to point(x,y) given just x and sign of y + * + Point P set to infinity if no such point on the curve. If x is on the curve then y is calculated from the curve equation. + The correct y value (plus or minus) is selected given its sign s. + @param P ECP instance to be set (x,[y]) + @param x BIG x coordinate of point + @param s an integer representing the "sign" of y, in fact its least significant bit. + */ +extern int ECP_ZZZ_setx(ECP_ZZZ *P,BIG_XXX x,int s); + +#endif + +/** @brief Multiplies Point by curve co-factor + * + @param Q ECP instance + */ +extern void ECP_ZZZ_cfp(ECP_ZZZ *Q); + +/** @brief Maps random BIG to curve point of correct order + * + @param Q ECP instance of correct order + @param w OCTET byte array to be mapped + */ +extern void ECP_ZZZ_mapit(ECP_ZZZ *Q,octet *w); + +/** @brief Converts an ECP point from Projective (x,y,z) coordinates to affine (x,y) coordinates + * + @param P ECP instance to be converted to affine form + */ +extern void ECP_ZZZ_affine(ECP_ZZZ *P); +/** @brief Formats and outputs an ECP point to the console, in projective coordinates + * + @param P ECP instance to be printed + */ +extern void ECP_ZZZ_outputxyz(ECP_ZZZ *P); +/** @brief Formats and outputs an ECP point to the console, converted to affine coordinates + * + @param P ECP instance to be printed + */ +extern void ECP_ZZZ_output(ECP_ZZZ * P); + +/** @brief Formats and outputs an ECP point to the console + * + @param P ECP instance to be printed + */ +extern void ECP_ZZZ_rawoutput(ECP_ZZZ * P); + +/** @brief Formats and outputs an ECP point to an octet string + The octet string is normally in the standard form 0x04|x|y + Here x (and y) are the x and y coordinates in left justified big-endian base 256 form. + For Montgomery curve it is 0x06|x + If c is true, only the x coordinate is provided as in 0x2|x if y is even, or 0x3|x if y is odd + @param c compression required, true or false + @param S output octet string + @param P ECP instance to be converted to an octet string + */ +extern void ECP_ZZZ_toOctet(octet *S,ECP_ZZZ *P,bool c); +/** @brief Creates an ECP point from an octet string + * + The octet string is normally in the standard form 0x04|x|y + Here x (and y) are the x and y coordinates in left justified big-endian base 256 form. + For Montgomery curve it is 0x06|x + If in compressed form only the x coordinate is provided as in 0x2|x if y is even, or 0x3|x if y is odd + @param P ECP instance to be created from the octet string + @param S input octet string + return 1 if octet string corresponds to a point on the curve, else 0 + */ +extern int ECP_ZZZ_fromOctet(ECP_ZZZ *P,octet *S); +/** @brief Doubles an ECP instance P + * + @param P ECP instance, on exit =2*P + */ +extern void ECP_ZZZ_dbl(ECP_ZZZ *P); +/** @brief Multiplies an ECP instance P by a small integer, side-channel resistant + * + @param P ECP instance, on exit =i*P + @param i small integer multiplier + @param b maximum number of bits in multiplier + */ +extern void ECP_ZZZ_pinmul(ECP_ZZZ *P,int i,int b); +/** @brief Multiplies an ECP instance P by a BIG, side-channel resistant + * + Uses Montgomery ladder for Montgomery curves, otherwise fixed sized windows. + @param P ECP instance, on exit =b*P + @param b BIG number multiplier + + */ +extern void ECP_ZZZ_mul(ECP_ZZZ *P,BIG_XXX b); +/** @brief Calculates double multiplication P=e*P+f*Q, side-channel resistant + * + @param P ECP instance, on exit =e*P+f*Q + @param Q ECP instance + @param e BIG number multiplier + @param f BIG number multiplier + */ +extern void ECP_ZZZ_mul2(ECP_ZZZ *P,ECP_ZZZ *Q,BIG_XXX e,BIG_XXX f); +/** @brief Get Group Generator from ROM + * + @param G ECP instance + */ +extern void ECP_ZZZ_generator(ECP_ZZZ *G); + + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/ecp2.c ---------------------------------------------------------------------- diff --git a/version3/c/ecp2.c b/version3/c/ecp2.c new file mode 100644 index 0000000..5463c37 --- /dev/null +++ b/version3/c/ecp2.c @@ -0,0 +1,724 @@ +/* +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 Weierstrass elliptic curve functions over FP2 */ +/* SU=m, m is Stack Usage */ + +#include "ecp2_ZZZ.h" + +int ECP2_ZZZ_isinf(ECP2_ZZZ *P) +{ + return (FP2_YYY_iszilch(&(P->x)) & FP2_YYY_iszilch(&(P->z))); +} + +/* Set P=Q */ +/* SU= 16 */ +void ECP2_ZZZ_copy(ECP2_ZZZ *P,ECP2_ZZZ *Q) +{ + FP2_YYY_copy(&(P->x),&(Q->x)); + FP2_YYY_copy(&(P->y),&(Q->y)); + FP2_YYY_copy(&(P->z),&(Q->z)); +} + +/* set P to Infinity */ +/* SU= 8 */ +void ECP2_ZZZ_inf(ECP2_ZZZ *P) +{ + FP2_YYY_zero(&(P->x)); + FP2_YYY_one(&(P->y)); + FP2_YYY_zero(&(P->z)); +} + +/* Conditional move Q to P dependant on d */ +static void ECP2_ZZZ_cmove(ECP2_ZZZ *P,ECP2_ZZZ *Q,int d) +{ + FP2_YYY_cmove(&(P->x),&(Q->x),d); + FP2_YYY_cmove(&(P->y),&(Q->y),d); + FP2_YYY_cmove(&(P->z),&(Q->z),d); +} + +/* return 1 if b==c, no branching */ +static int teq(sign32 b,sign32 c) +{ + sign32 x=b^c; + x-=1; // if x=0, x now -1 + return (int)((x>>31)&1); +} + +/* Constant time select from pre-computed table */ +static void ECP2_ZZZ_select(ECP2_ZZZ *P,ECP2_ZZZ W[],sign32 b) +{ + ECP2_ZZZ MP; + sign32 m=b>>31; + sign32 babs=(b^m)-m; + + babs=(babs-1)/2; + + ECP2_ZZZ_cmove(P,&W[0],teq(babs,0)); // conditional move + ECP2_ZZZ_cmove(P,&W[1],teq(babs,1)); + ECP2_ZZZ_cmove(P,&W[2],teq(babs,2)); + ECP2_ZZZ_cmove(P,&W[3],teq(babs,3)); + ECP2_ZZZ_cmove(P,&W[4],teq(babs,4)); + ECP2_ZZZ_cmove(P,&W[5],teq(babs,5)); + ECP2_ZZZ_cmove(P,&W[6],teq(babs,6)); + ECP2_ZZZ_cmove(P,&W[7],teq(babs,7)); + + ECP2_ZZZ_copy(&MP,P); + ECP2_ZZZ_neg(&MP); // minus P + ECP2_ZZZ_cmove(P,&MP,(int)(m&1)); +} + +/* return 1 if P==Q, else 0 */ +/* SU= 312 */ +int ECP2_ZZZ_equals(ECP2_ZZZ *P,ECP2_ZZZ *Q) +{ + FP2_YYY a,b; + + FP2_YYY_mul(&a,&(P->x),&(Q->z)); + FP2_YYY_mul(&b,&(Q->x),&(P->z)); + if (!FP2_YYY_equals(&a,&b)) return 0; + + FP2_YYY_mul(&a,&(P->y),&(Q->z)); + FP2_YYY_mul(&b,&(Q->y),&(P->z)); + if (!FP2_YYY_equals(&a,&b)) return 0; + return 1; +} + +/* Make P affine (so z=1) */ +/* SU= 232 */ +void ECP2_ZZZ_affine(ECP2_ZZZ *P) +{ + FP2_YYY one,iz; + if (ECP2_ZZZ_isinf(P)) return; + + FP2_YYY_one(&one); + if (FP2_YYY_isunity(&(P->z))) + { + FP2_YYY_reduce(&(P->x)); + FP2_YYY_reduce(&(P->y)); + return; + } + + FP2_YYY_inv(&iz,&(P->z)); + FP2_YYY_mul(&(P->x),&(P->x),&iz); + FP2_YYY_mul(&(P->y),&(P->y),&iz); + + FP2_YYY_reduce(&(P->x)); + FP2_YYY_reduce(&(P->y)); + FP2_YYY_copy(&(P->z),&one); +} + +/* extract x, y from point P */ +/* SU= 16 */ +int ECP2_ZZZ_get(FP2_YYY *x,FP2_YYY *y,ECP2_ZZZ *P) +{ + ECP2_ZZZ W; + ECP2_ZZZ_copy(&W,P); + ECP2_ZZZ_affine(&W); + if (ECP2_ZZZ_isinf(&W)) return -1; + FP2_YYY_copy(y,&(W.y)); + FP2_YYY_copy(x,&(W.x)); + return 0; +} + +/* SU= 152 */ +/* Output point P */ +void ECP2_ZZZ_output(ECP2_ZZZ *P) +{ + FP2_YYY x,y; + if (ECP2_ZZZ_isinf(P)) + { + printf("Infinity\n"); + return; + } + ECP2_ZZZ_get(&x,&y,P); + printf("("); + FP2_YYY_output(&x); + printf(","); + FP2_YYY_output(&y); + printf(")\n"); +} + +/* SU= 232 */ +void ECP2_ZZZ_outputxyz(ECP2_ZZZ *P) +{ + ECP2_ZZZ Q; + if (ECP2_ZZZ_isinf(P)) + { + printf("Infinity\n"); + return; + } + ECP2_ZZZ_copy(&Q,P); + printf("("); + FP2_YYY_output(&(Q.x)); + printf(","); + FP2_YYY_output(&(Q.y)); + printf(","); + FP2_YYY_output(&(Q.z)); + printf(")\n"); +} + +/* SU= 168 */ +/* Convert Q to octet string */ +void ECP2_ZZZ_toOctet(octet *W,ECP2_ZZZ *Q) +{ + BIG_XXX b; + FP2_YYY qx,qy; + ECP2_ZZZ_get(&qx,&qy,Q); + + FP_YYY_redc(b,&(qx.a)); + BIG_XXX_toBytes(&(W->val[0]),b); + FP_YYY_redc(b,&(qx.b)); + BIG_XXX_toBytes(&(W->val[MODBYTES_XXX]),b); + FP_YYY_redc(b,&(qy.a)); + BIG_XXX_toBytes(&(W->val[2*MODBYTES_XXX]),b); + FP_YYY_redc(b,&(qy.b)); + BIG_XXX_toBytes(&(W->val[3*MODBYTES_XXX]),b); + + W->len=4*MODBYTES_XXX; + +} + +/* SU= 176 */ +/* restore Q from octet string */ +int ECP2_ZZZ_fromOctet(ECP2_ZZZ *Q,octet *W) +{ + BIG_XXX b; + FP2_YYY qx,qy; + BIG_XXX_fromBytes(b,&(W->val[0])); + FP_YYY_nres(&(qx.a),b); + BIG_XXX_fromBytes(b,&(W->val[MODBYTES_XXX])); + FP_YYY_nres(&(qx.b),b); + BIG_XXX_fromBytes(b,&(W->val[2*MODBYTES_XXX])); + FP_YYY_nres(&(qy.a),b); + BIG_XXX_fromBytes(b,&(W->val[3*MODBYTES_XXX])); + FP_YYY_nres(&(qy.b),b); + + if (ECP2_ZZZ_set(Q,&qx,&qy)) return 1; + return 0; +} + +/* SU= 128 */ +/* Calculate RHS of twisted curve equation x^3+B/i or x^3+Bi*/ +void ECP2_ZZZ_rhs(FP2_YYY *rhs,FP2_YYY *x) +{ + /* calculate RHS of elliptic curve equation */ + FP2_YYY t; + BIG_XXX b; + FP2_YYY_sqr(&t,x); + + FP2_YYY_mul(rhs,&t,x); + + /* Assuming CURVE_A=0 */ + + BIG_XXX_rcopy(b,CURVE_B_ZZZ); + + FP2_YYY_from_BIG(&t,b); + +#if SEXTIC_TWIST_ZZZ == D_TYPE + FP2_YYY_div_ip(&t); /* IMPORTANT - here we use the correct SEXTIC twist of the curve */ +#endif + +#if SEXTIC_TWIST_ZZZ == M_TYPE + FP2_YYY_norm(&t); + FP2_YYY_mul_ip(&t); /* IMPORTANT - here we use the correct SEXTIC twist of the curve */ + FP2_YYY_norm(&t); + +#endif + + + FP2_YYY_add(rhs,&t,rhs); + FP2_YYY_reduce(rhs); +} + + +/* Set P=(x,y). Return 1 if (x,y) is on the curve, else return 0*/ +/* SU= 232 */ +int ECP2_ZZZ_set(ECP2_ZZZ *P,FP2_YYY *x,FP2_YYY *y) +{ + FP2_YYY rhs,y2; + + FP2_YYY_sqr(&y2,y); + ECP2_ZZZ_rhs(&rhs,x); + + if (!FP2_YYY_equals(&y2,&rhs)) + { + ECP2_ZZZ_inf(P); + return 0; + } + + FP2_YYY_copy(&(P->x),x); + FP2_YYY_copy(&(P->y),y); + + FP2_YYY_one(&(P->z)); + return 1; +} + +/* Set P=(x,y). Return 1 if (x,.) is on the curve, else return 0 */ +/* SU= 232 */ +int ECP2_ZZZ_setx(ECP2_ZZZ *P,FP2_YYY *x) +{ + FP2_YYY y; + ECP2_ZZZ_rhs(&y,x); + + if (!FP2_YYY_sqrt(&y,&y)) + { + ECP2_ZZZ_inf(P); + return 0; + } + + FP2_YYY_copy(&(P->x),x); + FP2_YYY_copy(&(P->y),&y); + FP2_YYY_one(&(P->z)); + return 1; +} + +/* Set P=-P */ +/* SU= 8 */ +void ECP2_ZZZ_neg(ECP2_ZZZ *P) +{ + FP2_YYY_norm(&(P->y)); + FP2_YYY_neg(&(P->y),&(P->y)); + FP2_YYY_norm(&(P->y)); +} + +/* R+=R */ +/* return -1 for Infinity, 0 for addition, 1 for doubling */ +/* SU= 448 */ +int ECP2_ZZZ_dbl(ECP2_ZZZ *P) +{ + FP2_YYY t0,t1,t2,iy,x3,y3; + + FP2_YYY_copy(&iy,&(P->y)); //FP2 iy=new FP2(y); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_YYY_mul_ip(&iy); //iy.mul_ip(); + FP2_YYY_norm(&iy); //iy.norm(); +#endif + FP2_YYY_sqr(&t0,&(P->y)); //t0.sqr(); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_YYY_mul_ip(&t0); //t0.mul_ip(); +#endif + FP2_YYY_mul(&t1,&iy,&(P->z)); //t1.mul(z); + FP2_YYY_sqr(&t2,&(P->z)); //t2.sqr(); + + FP2_YYY_add(&(P->z),&t0,&t0); //z.add(t0); + FP2_YYY_norm(&(P->z)); //z.norm(); + FP2_YYY_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP2_YYY_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP2_YYY_norm(&(P->z)); //z.norm(); + + FP2_YYY_imul(&t2,&t2,3*CURVE_B_I_ZZZ); //t2.imul(3*ROM.CURVE_B_I); +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_mul_ip(&t2); + FP2_YYY_norm(&t2); +#endif + + FP2_YYY_mul(&x3,&t2,&(P->z)); //x3.mul(z); + + FP2_YYY_add(&y3,&t0,&t2); //y3.add(t2); + FP2_YYY_norm(&y3); //y3.norm(); + FP2_YYY_mul(&(P->z),&(P->z),&t1); //z.mul(t1); + + FP2_YYY_add(&t1,&t2,&t2); //t1.add(t2); + FP2_YYY_add(&t2,&t2,&t1); //t2.add(t1); + FP2_YYY_norm(&t2); //t2.norm(); + FP2_YYY_sub(&t0,&t0,&t2); //t0.sub(t2); + FP2_YYY_norm(&t0); //t0.norm(); //y^2-9bz^2 + FP2_YYY_mul(&y3,&y3,&t0); //y3.mul(t0); + FP2_YYY_add(&(P->y),&y3,&x3); //y3.add(x3); //(y^2+3z*2)(y^2-9z^2)+3b.z^2.8y^2 + FP2_YYY_mul(&t1,&(P->x),&iy); //t1.mul(iy); // + FP2_YYY_norm(&t0); //x.norm(); + FP2_YYY_mul(&(P->x),&t0,&t1); //x.mul(t1); + FP2_YYY_add(&(P->x),&(P->x),&(P->x)); //x.add(x); //(y^2-9bz^2)xy2 + + FP2_YYY_norm(&(P->x)); //x.norm(); + FP2_YYY_norm(&(P->y)); //y.norm(); + + return 1; +} + +/* Set P+=Q */ +/* SU= 400 */ +int ECP2_ZZZ_add(ECP2_ZZZ *P,ECP2_ZZZ *Q) +{ + FP2_YYY t0,t1,t2,t3,t4,x3,y3,z3; + int b3=3*CURVE_B_I_ZZZ; + + FP2_YYY_mul(&t0,&(P->x),&(Q->x)); //t0.mul(Q.x); // x.Q.x + FP2_YYY_mul(&t1,&(P->y),&(Q->y)); //t1.mul(Q.y); // y.Q.y + + FP2_YYY_mul(&t2,&(P->z),&(Q->z)); //t2.mul(Q.z); + FP2_YYY_add(&t3,&(P->x),&(P->y)); //t3.add(y); + FP2_YYY_norm(&t3); //t3.norm(); //t3=X1+Y1 + + FP2_YYY_add(&t4,&(Q->x),&(Q->y)); //t4.add(Q.y); + FP2_YYY_norm(&t4); //t4.norm(); //t4=X2+Y2 + FP2_YYY_mul(&t3,&t3,&t4); //t3.mul(t4); //t3=(X1+Y1)(X2+Y2) + FP2_YYY_add(&t4,&t0,&t1); //t4.add(t1); //t4=X1.X2+Y1.Y2 + + FP2_YYY_sub(&t3,&t3,&t4); //t3.sub(t4); + FP2_YYY_norm(&t3); //t3.norm(); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_YYY_mul_ip(&t3); //t3.mul_ip(); + FP2_YYY_norm(&t3); //t3.norm(); //t3=(X1+Y1)(X2+Y2)-(X1.X2+Y1.Y2) = X1.Y2+X2.Y1 +#endif + FP2_YYY_add(&t4,&(P->y),&(P->z)); //t4.add(z); + FP2_YYY_norm(&t4); //t4.norm(); //t4=Y1+Z1 + FP2_YYY_add(&x3,&(Q->y),&(Q->z)); //x3.add(Q.z); + FP2_YYY_norm(&x3); //x3.norm(); //x3=Y2+Z2 + + FP2_YYY_mul(&t4,&t4,&x3); //t4.mul(x3); //t4=(Y1+Z1)(Y2+Z2) + FP2_YYY_add(&x3,&t1,&t2); //x3.add(t2); //X3=Y1.Y2+Z1.Z2 + + FP2_YYY_sub(&t4,&t4,&x3); //t4.sub(x3); + FP2_YYY_norm(&t4); //t4.norm(); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_YYY_mul_ip(&t4); //t4.mul_ip(); + FP2_YYY_norm(&t4); //t4.norm(); //t4=(Y1+Z1)(Y2+Z2) - (Y1.Y2+Z1.Z2) = Y1.Z2+Y2.Z1 +#endif + FP2_YYY_add(&x3,&(P->x),&(P->z)); //x3.add(z); + FP2_YYY_norm(&x3); //x3.norm(); // x3=X1+Z1 + FP2_YYY_add(&y3,&(Q->x),&(Q->z)); //y3.add(Q.z); + FP2_YYY_norm(&y3); //y3.norm(); // y3=X2+Z2 + FP2_YYY_mul(&x3,&x3,&y3); //x3.mul(y3); // x3=(X1+Z1)(X2+Z2) + FP2_YYY_add(&y3,&t0,&t2); //y3.add(t2); // y3=X1.X2+Z1+Z2 + FP2_YYY_sub(&y3,&x3,&y3); //y3.rsub(x3); + FP2_YYY_norm(&y3); //y3.norm(); // y3=(X1+Z1)(X2+Z2) - (X1.X2+Z1.Z2) = X1.Z2+X2.Z1 +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_YYY_mul_ip(&t0); //t0.mul_ip(); + FP2_YYY_norm(&t0); //t0.norm(); // x.Q.x + FP2_YYY_mul_ip(&t1); //t1.mul_ip(); + FP2_YYY_norm(&t1); //t1.norm(); // y.Q.y +#endif + FP2_YYY_add(&x3,&t0,&t0); //x3.add(t0); + FP2_YYY_add(&t0,&t0,&x3); //t0.add(x3); + FP2_YYY_norm(&t0); //t0.norm(); + FP2_YYY_imul(&t2,&t2,b3); //t2.imul(b); +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_mul_ip(&t2); + FP2_YYY_norm(&t2); +#endif + FP2_YYY_add(&z3,&t1,&t2); //z3.add(t2); + FP2_YYY_norm(&z3); //z3.norm(); + FP2_YYY_sub(&t1,&t1,&t2); //t1.sub(t2); + FP2_YYY_norm(&t1); //t1.norm(); + FP2_YYY_imul(&y3,&y3,b3); //y3.imul(b); +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_mul_ip(&y3); + FP2_YYY_norm(&y3); +#endif + FP2_YYY_mul(&x3,&y3,&t4); //x3.mul(t4); + FP2_YYY_mul(&t2,&t3,&t1); //t2.mul(t1); + FP2_YYY_sub(&(P->x),&t2,&x3); //x3.rsub(t2); + FP2_YYY_mul(&y3,&y3,&t0); //y3.mul(t0); + FP2_YYY_mul(&t1,&t1,&z3); //t1.mul(z3); + FP2_YYY_add(&(P->y),&y3,&t1); //y3.add(t1); + FP2_YYY_mul(&t0,&t0,&t3); //t0.mul(t3); + FP2_YYY_mul(&z3,&z3,&t4); //z3.mul(t4); + FP2_YYY_add(&(P->z),&z3,&t0); //z3.add(t0); + + FP2_YYY_norm(&(P->x)); //x.norm(); + FP2_YYY_norm(&(P->y)); //y.norm(); + FP2_YYY_norm(&(P->z)); //z.norm(); + + return 0; +} + +/* Set P-=Q */ +/* SU= 16 */ +void ECP2_ZZZ_sub(ECP2_ZZZ *P,ECP2_ZZZ *Q) +{ + ECP2_ZZZ NQ; + ECP2_ZZZ_copy(&NQ,Q); + ECP2_ZZZ_neg(&NQ); + ECP2_ZZZ_add(P,&NQ); +} + +/* P*=e */ +/* SU= 280 */ +void ECP2_ZZZ_mul(ECP2_ZZZ *P,BIG_XXX e) +{ + /* fixed size windows */ + int i,nb,s,ns; + BIG_XXX mt,t; + ECP2_ZZZ Q,W[8],C; + sign8 w[1+(NLEN_XXX*BASEBITS_XXX+3)/4]; + + if (ECP2_ZZZ_isinf(P)) return; + + /* precompute table */ + + ECP2_ZZZ_copy(&Q,P); + ECP2_ZZZ_dbl(&Q); + ECP2_ZZZ_copy(&W[0],P); + + for (i=1; i<8; i++) + { + ECP2_ZZZ_copy(&W[i],&W[i-1]); + ECP2_ZZZ_add(&W[i],&Q); + } + + /* make exponent odd - add 2P if even, P if odd */ + BIG_XXX_copy(t,e); + s=BIG_XXX_parity(t); + BIG_XXX_inc(t,1); + BIG_XXX_norm(t); + ns=BIG_XXX_parity(t); + BIG_XXX_copy(mt,t); + BIG_XXX_inc(mt,1); + BIG_XXX_norm(mt); + BIG_XXX_cmove(t,mt,s); + ECP2_ZZZ_cmove(&Q,P,ns); + ECP2_ZZZ_copy(&C,&Q); + + nb=1+(BIG_XXX_nbits(t)+3)/4; + + /* convert exponent to signed 4-bit window */ + for (i=0; i<nb; i++) + { + w[i]=BIG_XXX_lastbits(t,5)-16; + BIG_XXX_dec(t,w[i]); + BIG_XXX_norm(t); + BIG_XXX_fshr(t,4); + } + w[nb]=BIG_XXX_lastbits(t,5); + + ECP2_ZZZ_copy(P,&W[(w[nb]-1)/2]); + for (i=nb-1; i>=0; i--) + { + ECP2_ZZZ_select(&Q,W,w[i]); + ECP2_ZZZ_dbl(P); + ECP2_ZZZ_dbl(P); + ECP2_ZZZ_dbl(P); + ECP2_ZZZ_dbl(P); + ECP2_ZZZ_add(P,&Q); + } + ECP2_ZZZ_sub(P,&C); /* apply correction */ + ECP2_ZZZ_affine(P); +} + +/* Calculates q.P using Frobenius constant X */ +/* SU= 96 */ +void ECP2_ZZZ_frob(ECP2_ZZZ *P,FP2_YYY *X) +{ + FP2_YYY X2; + + FP2_YYY_sqr(&X2,X); + FP2_YYY_conj(&(P->x),&(P->x)); + FP2_YYY_conj(&(P->y),&(P->y)); + FP2_YYY_conj(&(P->z),&(P->z)); + FP2_YYY_reduce(&(P->z)); + + FP2_YYY_mul(&(P->x),&X2,&(P->x)); + FP2_YYY_mul(&(P->y),&X2,&(P->y)); + FP2_YYY_mul(&(P->y),X,&(P->y)); + +} + + +// Bos & Costello https://eprint.iacr.org/2013/458.pdf +// Faz-Hernandez & Longa & Sanchez https://eprint.iacr.org/2013/158.pdf +// Side channel attack secure + +void ECP2_ZZZ_mul4(ECP2_ZZZ *P,ECP2_ZZZ Q[4],BIG_XXX u[4]) +{ + int i,j,k,nb,pb,bt; + ECP2_ZZZ T[8],W; + BIG_XXX t[4],mt; + sign8 w[NLEN_XXX*BASEBITS_XXX+1]; + sign8 s[NLEN_XXX*BASEBITS_XXX+1]; + + for (i=0; i<4; i++) + { + BIG_XXX_copy(t[i],u[i]); + } + +// Precomputed table + ECP2_ZZZ_copy(&T[0],&Q[0]); // Q[0] + ECP2_ZZZ_copy(&T[1],&T[0]); + ECP2_ZZZ_add(&T[1],&Q[1]); // Q[0]+Q[1] + ECP2_ZZZ_copy(&T[2],&T[0]); + ECP2_ZZZ_add(&T[2],&Q[2]); // Q[0]+Q[2] + ECP2_ZZZ_copy(&T[3],&T[1]); + ECP2_ZZZ_add(&T[3],&Q[2]); // Q[0]+Q[1]+Q[2] + ECP2_ZZZ_copy(&T[4],&T[0]); + ECP2_ZZZ_add(&T[4],&Q[3]); // Q[0]+Q[3] + ECP2_ZZZ_copy(&T[5],&T[1]); + ECP2_ZZZ_add(&T[5],&Q[3]); // Q[0]+Q[1]+Q[3] + ECP2_ZZZ_copy(&T[6],&T[2]); + ECP2_ZZZ_add(&T[6],&Q[3]); // Q[0]+Q[2]+Q[3] + ECP2_ZZZ_copy(&T[7],&T[3]); + ECP2_ZZZ_add(&T[7],&Q[3]); // Q[0]+Q[1]+Q[2]+Q[3] + +// Make it odd + pb=1-BIG_XXX_parity(t[0]); + BIG_XXX_inc(t[0],pb); + BIG_XXX_norm(t[0]); + +// Number of bits + BIG_XXX_zero(mt); + for (i=0; i<4; i++) + { + BIG_XXX_or(mt,mt,t[i]); + } + nb=1+BIG_XXX_nbits(mt); + +// Sign pivot + s[nb-1]=1; + for (i=0;i<nb-1;i++) + { + BIG_XXX_fshr(t[0],1); + s[i]=2*BIG_XXX_parity(t[0])-1; + } + +// Recoded exponent + for (i=0; i<nb; i++) + { + w[i]=0; + k=1; + for (j=1; j<4; j++) + { + bt=s[i]*BIG_XXX_parity(t[j]); + BIG_XXX_fshr(t[j],1); + + BIG_XXX_dec(t[j],(bt>>1)); + BIG_XXX_norm(t[j]); + w[i]+=bt*k; + k*=2; + } + } + +// Main loop + ECP2_ZZZ_select(P,T,2*w[nb-1]+1); + for (i=nb-2; i>=0; i--) + { + ECP2_ZZZ_select(&W,T,2*w[i]+s[i]); + ECP2_ZZZ_dbl(P); + ECP2_ZZZ_add(P,&W); + } + +// apply correction + ECP2_ZZZ_copy(&W,P); + ECP2_ZZZ_sub(&W,&Q[0]); + ECP2_ZZZ_cmove(P,&W,pb); + + ECP2_ZZZ_affine(P); +} + +/* Map to hash value to point on G2 from random BIG */ +void ECP2_ZZZ_mapit(ECP2_ZZZ *Q,octet *W) +{ + BIG_XXX q,one,Fx,Fy,x,hv; + FP2_YYY X; +#if (PAIRING_FRIENDLY_ZZZ == BN) + ECP2_ZZZ T,K; +#elif (PAIRING_FRIENDLY_ZZZ == BLS) + ECP2_ZZZ xQ, x2Q; +#endif + BIG_XXX_fromBytes(hv,W->val); + BIG_XXX_rcopy(q,Modulus_ZZZ); + BIG_XXX_one(one); + BIG_XXX_mod(hv,q); + + for (;;) + { + FP2_YYY_from_BIGs(&X,one,hv); + if (ECP2_ZZZ_setx(Q,&X)) break; + BIG_XXX_inc(hv,1); + } + + BIG_XXX_rcopy(Fx,Fra_YYY); + BIG_XXX_rcopy(Fy,Frb_YYY); + FP2_YYY_from_BIGs(&X,Fx,Fy); + +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_YYY_inv(&X,&X); + FP2_YYY_norm(&X); +#endif + + BIG_XXX_rcopy(x,CURVE_Bnx_ZZZ); + +#if (PAIRING_FRIENDLY_ZZZ == BN) + + /* Faster Hashing to G2 - Fuentes-Castaneda, Knapp and Rodriguez-Henriquez */ + /* Q -> xQ + F(3xQ) + F(F(xQ)) + F(F(F(Q))). */ + ECP2_ZZZ_copy(&T,Q); + ECP2_ZZZ_mul(&T,x); +#if SIGN_OF_X_ZZZ==NEGATIVEX + ECP2_ZZZ_neg(&T); // our x is negative +#endif + ECP2_ZZZ_copy(&K,&T); + ECP2_ZZZ_dbl(&K); + ECP2_ZZZ_add(&K,&T); + + ECP2_ZZZ_frob(&K,&X); + ECP2_ZZZ_frob(Q,&X); + ECP2_ZZZ_frob(Q,&X); + ECP2_ZZZ_frob(Q,&X); + ECP2_ZZZ_add(Q,&T); + ECP2_ZZZ_add(Q,&K); + ECP2_ZZZ_frob(&T,&X); + ECP2_ZZZ_frob(&T,&X); + ECP2_ZZZ_add(Q,&T); + ECP2_ZZZ_affine(Q); + +#elif (PAIRING_FRIENDLY_ZZZ == BLS) + + /* Efficient hash maps to G2 on BLS curves - Budroni, Pintore */ + /* Q -> x2Q -xQ -Q +F(xQ -Q) +F(F(2Q)) */ + + ECP2_ZZZ_copy(&xQ,Q); + ECP2_ZZZ_mul(&xQ,x); + + ECP2_ZZZ_copy(&x2Q,&xQ); + ECP2_ZZZ_mul(&x2Q,x); + +#if SIGN_OF_X_ZZZ==NEGATIVEX + ECP2_ZZZ_neg(&xQ); +#endif + + ECP2_ZZZ_sub(&x2Q,&xQ); + ECP2_ZZZ_sub(&x2Q,Q); + + ECP2_ZZZ_sub(&xQ,Q); + ECP2_ZZZ_frob(&xQ,&X); + + ECP2_ZZZ_dbl(Q); + ECP2_ZZZ_frob(Q,&X); + ECP2_ZZZ_frob(Q,&X); + + ECP2_ZZZ_add(Q,&x2Q); + ECP2_ZZZ_add(Q,&xQ); + + ECP2_ZZZ_affine(Q); + +#endif +} + +void ECP2_ZZZ_generator(ECP2_ZZZ *G) +{ + FP2_YYY wx,wy; + + FP_YYY_rcopy(&(wx.a),CURVE_Pxa_ZZZ); + FP_YYY_rcopy(&(wx.b),CURVE_Pxb_ZZZ); + FP_YYY_rcopy(&(wy.a),CURVE_Pya_ZZZ); + FP_YYY_rcopy(&(wy.b),CURVE_Pyb_ZZZ); + + ECP2_ZZZ_set(G,&wx,&wy); +} http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/c/ecp2.h ---------------------------------------------------------------------- diff --git a/version3/c/ecp2.h b/version3/c/ecp2.h new file mode 100644 index 0000000..32c0420 --- /dev/null +++ b/version3/c/ecp2.h @@ -0,0 +1,220 @@ +/* + 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 ecp2.h + * @author Mike Scott + * @brief ECP2 Header File + * + */ + +#ifndef ECP2_ZZZ_H +#define ECP2_ZZZ_H + +#include "fp2_YYY.h" +#include "config_curve_ZZZ.h" + +/** + @brief ECP2 Structure - Elliptic Curve Point over quadratic extension field +*/ + +typedef struct +{ +// int inf; /**< Infinity Flag */ + FP2_YYY x; /**< x-coordinate of point */ + FP2_YYY y; /**< y-coordinate of point */ + FP2_YYY z; /**< z-coordinate of point */ +} ECP2_ZZZ; + + +/* Curve Params - see rom_zzz.c */ +extern const int CURVE_A_ZZZ; /**< Elliptic curve A parameter */ +extern const int CURVE_B_I_ZZZ; /**< Elliptic curve B parameter */ +extern const BIG_XXX CURVE_B_ZZZ; /**< Elliptic curve B parameter */ +extern const BIG_XXX CURVE_Order_ZZZ; /**< Elliptic curve group order */ +extern const BIG_XXX CURVE_Cof_ZZZ; /**< Elliptic curve cofactor */ +extern const BIG_XXX CURVE_Bnx_ZZZ; /**< Elliptic curve parameter */ + +extern const BIG_XXX Fra_YYY; /**< real part of BN curve Frobenius Constant */ +extern const BIG_XXX Frb_YYY; /**< imaginary part of BN curve Frobenius Constant */ + + +/* Generator point on G1 */ +extern const BIG_XXX CURVE_Gx_ZZZ; /**< x-coordinate of generator point in group G1 */ +extern const BIG_XXX CURVE_Gy_ZZZ; /**< y-coordinate of generator point in group G1 */ + +/* For Pairings only */ + +/* Generator point on G2 */ +extern const BIG_XXX CURVE_Pxa_ZZZ; /**< real part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pxb_ZZZ; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pya_ZZZ; /**< real part of y-coordinate of generator point in group G2 */ +extern const BIG_XXX CURVE_Pyb_ZZZ; /**< imaginary part of y-coordinate of generator point in group G2 */ + +/* ECP2 E(Fp2) prototypes */ +/** @brief Tests for ECP2 point equal to infinity + * + @param P ECP2 point to be tested + @return 1 if infinity, else returns 0 + */ +extern int ECP2_ZZZ_isinf(ECP2_ZZZ *P); +/** @brief Copy ECP2 point to another ECP2 point + * + @param P ECP2 instance, on exit = Q + @param Q ECP2 instance to be copied + */ +extern void ECP2_ZZZ_copy(ECP2_ZZZ *P,ECP2_ZZZ *Q); +/** @brief Set ECP2 to point-at-infinity + * + @param P ECP2 instance to be set to infinity + */ +extern void ECP2_ZZZ_inf(ECP2_ZZZ *P); +/** @brief Tests for equality of two ECP2s + * + @param P ECP2 instance to be compared + @param Q ECP2 instance to be compared + @return 1 if P=Q, else returns 0 + */ +extern int ECP2_ZZZ_equals(ECP2_ZZZ *P,ECP2_ZZZ *Q); +/** @brief Converts an ECP2 point from Projective (x,y,z) coordinates to affine (x,y) coordinates + * + @param P ECP2 instance to be converted to affine form + */ +extern void ECP2_ZZZ_affine(ECP2_ZZZ *P); +/** @brief Extract x and y coordinates of an ECP2 point P + * + If x=y, returns only x + @param x FP2 on exit = x coordinate of point + @param y FP2 on exit = y coordinate of point (unless x=y) + @param P ECP2 instance (x,y) + @return -1 if P is point-at-infinity, else 0 + */ +extern int ECP2_ZZZ_get(FP2_YYY *x,FP2_YYY *y,ECP2_ZZZ *P); +/** @brief Formats and outputs an ECP2 point to the console, converted to affine coordinates + * + @param P ECP2 instance to be printed + */ +extern void ECP2_ZZZ_output(ECP2_ZZZ *P); +/** @brief Formats and outputs an ECP2 point to the console, in projective coordinates + * + @param P ECP2 instance to be printed + */ +extern void ECP2_ZZZ_outputxyz(ECP2_ZZZ *P); +/** @brief Formats and outputs an ECP2 point to an octet string + * + The octet string is created in the form x|y. + Convert the real and imaginary parts of the x and y coordinates to big-endian base 256 form. + @param S output octet string + @param P ECP2 instance to be converted to an octet string + */ +extern void ECP2_ZZZ_toOctet(octet *S,ECP2_ZZZ *P); +/** @brief Creates an ECP2 point from an octet string + * + The octet string is in the form x|y + The real and imaginary parts of the x and y coordinates are in big-endian base 256 form. + @param P ECP2 instance to be created from the octet string + @param S input octet string + return 1 if octet string corresponds to a point on the curve, else 0 + */ +extern int ECP2_ZZZ_fromOctet(ECP2_ZZZ *P,octet *S); +/** @brief Calculate Right Hand Side of curve equation y^2=f(x) + * + Function f(x)=x^3+Ax+B + Used internally. + @param r FP2 value of f(x) + @param x FP2 instance + */ +extern void ECP2_ZZZ_rhs(FP2_YYY *r,FP2_YYY *x); +/** @brief Set ECP2 to point(x,y) given x and y + * + Point P set to infinity if no such point on the curve. + @param P ECP2 instance to be set (x,y) + @param x FP2 x coordinate of point + @param y FP2 y coordinate of point + @return 1 if point exists, else 0 + */ +extern int ECP2_ZZZ_set(ECP2_ZZZ *P,FP2_YYY *x,FP2_YYY *y); +/** @brief Set ECP to point(x,[y]) given x + * + Point P set to infinity if no such point on the curve. Otherwise y coordinate is calculated from x. + @param P ECP instance to be set (x,[y]) + @param x BIG x coordinate of point + @return 1 if point exists, else 0 + */ +extern int ECP2_ZZZ_setx(ECP2_ZZZ *P,FP2_YYY *x); +/** @brief Negation of an ECP2 point + * + @param P ECP2 instance, on exit = -P + */ +extern void ECP2_ZZZ_neg(ECP2_ZZZ *P); +/** @brief Doubles an ECP2 instance P + * + @param P ECP2 instance, on exit =2*P + */ +extern int ECP2_ZZZ_dbl(ECP2_ZZZ *P); +/** @brief Adds ECP2 instance Q to ECP2 instance P + * + @param P ECP2 instance, on exit =P+Q + @param Q ECP2 instance to be added to P + */ +extern int ECP2_ZZZ_add(ECP2_ZZZ *P,ECP2_ZZZ *Q); +/** @brief Subtracts ECP instance Q from ECP2 instance P + * + @param P ECP2 instance, on exit =P-Q + @param Q ECP2 instance to be subtracted from P + */ +extern void ECP2_ZZZ_sub(ECP2_ZZZ *P,ECP2_ZZZ *Q); +/** @brief Multiplies an ECP2 instance P by a BIG, side-channel resistant + * + Uses fixed sized windows. + @param P ECP2 instance, on exit =b*P + @param b BIG number multiplier + + */ +extern void ECP2_ZZZ_mul(ECP2_ZZZ *P,BIG_XXX b); +/** @brief Multiplies an ECP2 instance P by the internal modulus p, using precalculated Frobenius constant f + * + Fast point multiplication using Frobenius + @param P ECP2 instance, on exit = p*P + @param f FP2 precalculated Frobenius constant + + */ +extern void ECP2_ZZZ_frob(ECP2_ZZZ *P,FP2_YYY *f); +/** @brief Calculates P=b[0]*Q[0]+b[1]*Q[1]+b[2]*Q[2]+b[3]*Q[3] + * + @param P ECP2 instance, on exit = b[0]*Q[0]+b[1]*Q[1]+b[2]*Q[2]+b[3]*Q[3] + @param Q ECP2 array of 4 points + @param b BIG array of 4 multipliers + */ +extern void ECP2_ZZZ_mul4(ECP2_ZZZ *P,ECP2_ZZZ *Q,BIG_XXX *b); + +/** @brief Maps random BIG to curve point of correct order + * + @param P ECP2 instance of correct order + @param w OCTET byte array to be mapped + */ +extern void ECP2_ZZZ_mapit(ECP2_ZZZ *P,octet *w); + +/** @brief Get Group Generator from ROM + * + @param G ECP2 instance + */ +extern void ECP2_ZZZ_generator(ECP2_ZZZ *G); + +#endif
