http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/ecdh.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/ecdh.cpp b/version3/cpp/ecdh.cpp new file mode 100644 index 0000000..2d1075a --- /dev/null +++ b/version3/cpp/ecdh.cpp @@ -0,0 +1,377 @@ +/* +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. +*/ + +/* ECDH/ECIES/ECDSA Functions - see main program below */ + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> + +#include "ecdh_ZZZ.h" + +using namespace XXX; +using namespace YYY; + +/* Calculate a public/private EC GF(p) key pair. W=S.G mod EC(p), + * where S is the secret key and W is the public key + * and G is fixed generator. + * If RNG is NULL then the private key is provided externally in S + * otherwise it is generated randomly internally */ +int ZZZ::ECP_KEY_PAIR_GENERATE(csprng *RNG,octet* S,octet *W) +{ + BIG r,gx,gy,s; + ECP G; + int res=0; + + ECP_generator(&G); + + BIG_rcopy(r,CURVE_Order); + if (RNG!=NULL) + { + BIG_randomnum(s,r,RNG); + } + else + { + BIG_fromBytes(s,S->val); + BIG_mod(s,r); + } + +#ifdef AES_S + BIG_mod2m(s,2*AES_S); +#endif + + S->len=EGS_ZZZ; + BIG_toBytes(S->val,s); + + + ECP_mul(&G,s); + + ECP_toOctet(W,&G,false); // To use point compression on public keys, change to true + + return res; +} + +/* Validate public key */ +int ZZZ::ECP_PUBLIC_KEY_VALIDATE(octet *W) +{ + BIG q,r,wx,k; + ECP WP; + int valid,nb; + int res=0; + + BIG_rcopy(q,Modulus); + BIG_rcopy(r,CURVE_Order); + + valid=ECP_fromOctet(&WP,W); + if (!valid) res=ECDH_INVALID_PUBLIC_KEY; + + if (res==0) + { + + nb=BIG_nbits(q); + BIG_one(k); + BIG_shl(k,(nb+4)/2); + BIG_add(k,q,k); + BIG_sdiv(k,r); /* get co-factor */ + + while (BIG_parity(k)==0) + { + ECP_dbl(&WP); + BIG_fshr(k,1); + } + + if (!BIG_isunity(k)) ECP_mul(&WP,k); + if (ECP_isinf(&WP)) res=ECDH_INVALID_PUBLIC_KEY; + } + + return res; +} + +/* IEEE-1363 Diffie-Hellman online calculation Z=S.WD */ +int ZZZ::ECP_SVDP_DH(octet *S,octet *WD,octet *Z) +{ + BIG r,s,wx; + int valid; + ECP W; + int res=0; + + BIG_fromBytes(s,S->val); + + valid=ECP_fromOctet(&W,WD); + + if (!valid) res=ECDH_ERROR; + if (res==0) + { + BIG_rcopy(r,CURVE_Order); + BIG_mod(s,r); + + ECP_mul(&W,s); + if (ECP_isinf(&W)) res=ECDH_ERROR; + else + { +#if CURVETYPE_ZZZ!=MONTGOMERY + ECP_get(wx,wx,&W); +#else + ECP_get(wx,&W); +#endif + Z->len=MODBYTES_XXX; + BIG_toBytes(Z->val,wx); + } + } + return res; +} + +#if CURVETYPE_ZZZ!=MONTGOMERY + +/* IEEE ECDSA Signature, C and D are signature on F using private key S */ +int ZZZ::ECP_SP_DSA(int sha,csprng *RNG,octet *K,octet *S,octet *F,octet *C,octet *D) +{ + char h[128]; + octet H= {0,sizeof(h),h}; + + BIG r,s,f,c,d,u,vx,w; + ECP G,V; + + ehashit(sha,F,-1,NULL,&H,sha); + + ECP_generator(&G); + + BIG_rcopy(r,CURVE_Order); + + BIG_fromBytes(s,S->val); + + int hlen=H.len; + if (H.len>MODBYTES_XXX) hlen=MODBYTES_XXX; + BIG_fromBytesLen(f,H.val,hlen); + + + if (RNG!=NULL) + { + do + { + BIG_randomnum(u,r,RNG); + BIG_randomnum(w,r,RNG); /* side channel masking */ + +#ifdef AES_S + BIG_mod2m(u,2*AES_S); +#endif + ECP_copy(&V,&G); + ECP_mul(&V,u); + + ECP_get(vx,vx,&V); + + BIG_copy(c,vx); + BIG_mod(c,r); + if (BIG_iszilch(c)) continue; + + BIG_modmul(u,u,w,r); + + + BIG_invmodp(u,u,r); + BIG_modmul(d,s,c,r); + + BIG_add(d,f,d); + + BIG_modmul(d,d,w,r); + + BIG_modmul(d,u,d,r); + + } + while (BIG_iszilch(d)); + } + else + { + BIG_fromBytes(u,K->val); + BIG_mod(u,r); + +#ifdef AES_S + BIG_mod2m(u,2*AES_S); +#endif + ECP_copy(&V,&G); + ECP_mul(&V,u); + + ECP_get(vx,vx,&V); + + BIG_copy(c,vx); + BIG_mod(c,r); + if (BIG_iszilch(c)) return ECDH_ERROR; + + BIG_invmodp(u,u,r); + BIG_modmul(d,s,c,r); + + BIG_add(d,f,d); + + BIG_modmul(d,u,d,r); + if (BIG_iszilch(d)) return ECDH_ERROR; + + } + + C->len=D->len=EGS_ZZZ; + + BIG_toBytes(C->val,c); + BIG_toBytes(D->val,d); + + return 0; +} + +/* IEEE1363 ECDSA Signature Verification. Signature C and D on F is verified using public key W */ +int ZZZ::ECP_VP_DSA(int sha,octet *W,octet *F, octet *C,octet *D) +{ + char h[128]; + octet H= {0,sizeof(h),h}; + + BIG r,wx,wy,f,c,d,h2; + int res=0; + ECP G,WP; + int valid; + + ehashit(sha,F,-1,NULL,&H,sha); + + ECP_generator(&G); + + BIG_rcopy(r,CURVE_Order); + + OCT_shl(C,C->len-MODBYTES_XXX); + OCT_shl(D,D->len-MODBYTES_XXX); + + BIG_fromBytes(c,C->val); + BIG_fromBytes(d,D->val); + + int hlen=H.len; + if (hlen>MODBYTES_XXX) hlen=MODBYTES_XXX; + + BIG_fromBytesLen(f,H.val,hlen); + + //BIG_fromBytes(f,H.val); + + if (BIG_iszilch(c) || BIG_comp(c,r)>=0 || BIG_iszilch(d) || BIG_comp(d,r)>=0) + res=ECDH_INVALID; + + if (res==0) + { + BIG_invmodp(d,d,r); + BIG_modmul(f,f,d,r); + BIG_modmul(h2,c,d,r); + + valid=ECP_fromOctet(&WP,W); + + if (!valid) res=ECDH_ERROR; + else + { + ECP_mul2(&WP,&G,h2,f); + + if (ECP_isinf(&WP)) res=ECDH_INVALID; + else + { + ECP_get(d,d,&WP); + BIG_mod(d,r); + if (BIG_comp(d,c)!=0) res=ECDH_INVALID; + } + } + } + + return res; +} + +/* IEEE1363 ECIES encryption. Encryption of plaintext M uses public key W and produces ciphertext V,C,T */ +void ZZZ::ECP_ECIES_ENCRYPT(int sha,octet *P1,octet *P2,csprng *RNG,octet *W,octet *M,int tlen,octet *V,octet *C,octet *T) +{ + + int i,len; + char z[EFS_ZZZ],vz[3*EFS_ZZZ+1],k[2*AESKEY_ZZZ],k1[AESKEY_ZZZ],k2[AESKEY_ZZZ],l2[8],u[EFS_ZZZ]; + octet Z= {0,sizeof(z),z}; + octet VZ= {0,sizeof(vz),vz}; + octet K= {0,sizeof(k),k}; + octet K1= {0,sizeof(k1),k1}; + octet K2= {0,sizeof(k2),k2}; + octet L2= {0,sizeof(l2),l2}; + octet U= {0,sizeof(u),u}; + + if (ECP_KEY_PAIR_GENERATE(RNG,&U,V)!=0) return; + if (ECP_SVDP_DH(&U,W,&Z)!=0) return; + + OCT_copy(&VZ,V); + OCT_joctet(&VZ,&Z); + + KDF2(sha,&VZ,P1,2*AESKEY_ZZZ,&K); + + K1.len=K2.len=AESKEY_ZZZ; + for (i=0; i<AESKEY_ZZZ; i++) + { + K1.val[i]=K.val[i]; + K2.val[i]=K.val[AESKEY_ZZZ+i]; + } + + AES_CBC_IV0_ENCRYPT(&K1,M,C); + + OCT_jint(&L2,P2->len,8); + + len=C->len; + OCT_joctet(C,P2); + OCT_joctet(C,&L2); + HMAC(sha,C,&K2,tlen,T); + C->len=len; +} + +/* IEEE1363 ECIES decryption. Decryption of ciphertext V,C,T using private key U outputs plaintext M */ +int ZZZ::ECP_ECIES_DECRYPT(int sha,octet *P1,octet *P2,octet *V,octet *C,octet *T,octet *U,octet *M) +{ + + int i,len; + char z[EFS_ZZZ],vz[3*EFS_ZZZ+1],k[2*AESKEY_ZZZ],k1[AESKEY_ZZZ],k2[AESKEY_ZZZ],l2[8],tag[32]; + octet Z= {0,sizeof(z),z}; + octet VZ= {0,sizeof(vz),vz}; + octet K= {0,sizeof(k),k}; + octet K1= {0,sizeof(k1),k1}; + octet K2= {0,sizeof(k2),k2}; + octet L2= {0,sizeof(l2),l2}; + octet TAG= {0,sizeof(tag),tag}; + + if (ECP_SVDP_DH(U,V,&Z)!=0) return 0; + + OCT_copy(&VZ,V); + OCT_joctet(&VZ,&Z); + + KDF2(sha,&VZ,P1,2*AESKEY_ZZZ,&K); + + K1.len=K2.len=AESKEY_ZZZ; + for (i=0; i<AESKEY_ZZZ; i++) + { + K1.val[i]=K.val[i]; + K2.val[i]=K.val[AESKEY_ZZZ+i]; + } + + if (!AES_CBC_IV0_DECRYPT(&K1,C,M)) return 0; + + OCT_jint(&L2,P2->len,8); + + len=C->len; + OCT_joctet(C,P2); + OCT_joctet(C,&L2); + HMAC(sha,C,&K2,T->len,&TAG); + C->len=len; + + if (!OCT_ncomp(T,&TAG,T->len)) return 0; + + return 1; + +} + +#endif
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/ecdh.h ---------------------------------------------------------------------- diff --git a/version3/cpp/ecdh.h b/version3/cpp/ecdh.h new file mode 100644 index 0000000..f1f1873 --- /dev/null +++ b/version3/cpp/ecdh.h @@ -0,0 +1,154 @@ +/* +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.h + * @author Mike Scott and Kealan McCusker + * @date 2nd June 2015 + * @brief ECDH Header file for implementation of standard EC protocols + * + * declares functions + * + */ + +#ifndef ECDH_ZZZ_H +#define ECDH_ZZZ_H + +#include "ecp_ZZZ.h" +#include "ecdh_support.h" + +using namespace amcl; + + +/*** START OF USER CONFIGURABLE SECTION - ***/ + +/*** START OF USER CONFIGURABLE SECTION - ***/ + + +/*** END OF USER CONFIGURABLE SECTION ***/ + +#define EGS_ZZZ MODBYTES_XXX /**< ECC Group Size in bytes */ +#define EFS_ZZZ MODBYTES_XXX /**< ECC Field Size in bytes */ + +#define ECDH_OK 0 /**< Function completed without error */ +/*#define ECDH_DOMAIN_ERROR -1*/ +#define ECDH_INVALID_PUBLIC_KEY -2 /**< Public Key is Invalid */ +#define ECDH_ERROR -3 /**< ECDH Internal Error */ +#define ECDH_INVALID -4 /**< ECDH Internal Error */ +/*#define ECDH_DOMAIN_NOT_FOUND -5 +#define ECDH_OUT_OF_MEMORY -6 +#define ECDH_DIV_BY_ZERO -7 +#define ECDH_BAD_ASSUMPTION -8*/ + + +namespace ZZZ { + +/* ECDH primitives */ +/** @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 + */ +extern int ECP_KEY_PAIR_GENERATE(csprng *R,octet *s,octet *W); +/** @brief Validate an ECC public key + * + @param W the input public key to be validated + @return 0 if public key is OK, or an error code + */ +extern int ECP_PUBLIC_KEY_VALIDATE(octet *W); + +/* ECDH primitives */ + +/** @brief Generate Diffie-Hellman shared key + * + IEEE-1363 Diffie-Hellman shared secret calculation + @param s is the input private key, + @param W the input public key of the other party + @param K the output shared key, in fact the x-coordinate of s.W + @return 0 or an error code + */ +extern int ECP_SVDP_DH(octet *s,octet *W,octet *K); +/*extern int ECPSVDP_DHC(octet *,octet *,int,octet *);*/ + +/*#if CURVETYPE!=MONTGOMERY */ +/* ECIES functions */ +/*#if CURVETYPE!=MONTGOMERY */ +/* ECIES functions */ +/** @brief ECIES Encryption + * + IEEE-1363 ECIES Encryption + @param h is the hash type + @param P1 input Key Derivation parameters + @param P2 input Encoding parameters + @param R is a pointer to a cryptographically secure random number generator + @param W the input public key of the recieving party + @param M is the plaintext message to be encrypted + @param len the length of the HMAC tag + @param V component of the output ciphertext + @param C the output ciphertext + @param T the output HMAC tag, part of the ciphertext + */ +extern void ECP_ECIES_ENCRYPT(int h,octet *P1,octet *P2,csprng *R,octet *W,octet *M,int len,octet *V,octet *C,octet *T); +/** @brief ECIES Decryption + * + IEEE-1363 ECIES Decryption + @param h is the hash type + @param P1 input Key Derivation parameters + @param P2 input Encoding parameters + @param V component of the input ciphertext + @param C the input ciphertext + @param T the input HMAC tag, part of the ciphertext + @param U the input private key for decryption + @param M the output plaintext message + @return 1 if successful, else 0 + */ +extern int ECP_ECIES_DECRYPT(int h,octet *P1,octet *P2,octet *V,octet *C,octet *T,octet *U,octet *M); + +/* ECDSA functions */ +/** @brief ECDSA Signature + * + IEEE-1363 ECDSA Signature + @param h is the hash type + @param R is a pointer to a cryptographically secure random number generator + @param k Ephemeral key. This value is used when R=NULL + @param s the input private signing key + @param M the input message to be signed + @param c component of the output signature + @param d component of the output signature + + */ +extern int ECP_SP_DSA(int h,csprng *R,octet *k,octet *s,octet *M,octet *c,octet *d); +/** @brief ECDSA Signature Verification + * + IEEE-1363 ECDSA Signature Verification + @param h is the hash type + @param W the input public key + @param M the input message + @param c component of the input signature + @param d component of the input signature + @return 0 or an error code + */ +extern int ECP_VP_DSA(int h,octet *W,octet *M,octet *c,octet *d); +/*#endif*/ +} + +#endif + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/ecdh_support.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/ecdh_support.cpp b/version3/cpp/ecdh_support.cpp new file mode 100644 index 0000000..e282c07 --- /dev/null +++ b/version3/cpp/ecdh_support.cpp @@ -0,0 +1,328 @@ +/* +Licensed to the Apache Software Foundation (ASF) under one +or more contributor license agreements. See the NOTICE file +distributed with this work for additional information +regarding copyright ownership. The ASF licenses this file +to you under the Apache License, Version 2.0 (the +"License"); you may not use this file except in compliance +with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, +software distributed under the License is distributed on an +"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +KIND, either express or implied. See the License for the +specific language governing permissions and limitations +under the License. +*/ + +/* Symmetric crypto support functions Functions */ + +#include <stdio.h> +#include <string.h> +#include <stdlib.h> +#include <time.h> + +#include "ecdh_support.h" + +using namespace amcl; + +#define ROUNDUP(a,b) ((a)-1)/(b)+1 + +/* general purpose hash function w=hash(p|n|x|y) */ +/* pad or truncate output to length pad if pad!=0 */ +void amcl::ehashit(int sha,octet *p,int n,octet *x,octet *w,int pad) +{ + int i,c[4],hlen; + hash256 sha256; + hash512 sha512; + char hh[64]; + + switch (sha) + { + case SHA256: + HASH256_init(&sha256); + break; + case SHA384: + HASH384_init(&sha512); + break; + case SHA512: + HASH512_init(&sha512); + break; + } + + hlen=sha; + + for (i=0; i<p->len; i++) + { + switch(sha) + { + case SHA256: + HASH256_process(&sha256,p->val[i]); + break; + case SHA384: + HASH384_process(&sha512,p->val[i]); + break; + case SHA512: + HASH512_process(&sha512,p->val[i]); + break; + } + } + if (n>0) + { + c[0]=(n>>24)&0xff; + c[1]=(n>>16)&0xff; + c[2]=(n>>8)&0xff; + c[3]=(n)&0xff; + for (i=0; i<4; i++) + { + switch(sha) + { + case SHA256: + HASH256_process(&sha256,c[i]); + break; + case SHA384: + HASH384_process(&sha512,c[i]); + break; + case SHA512: + HASH512_process(&sha512,c[i]); + break; + } + } + } + if (x!=NULL) for (i=0; i<x->len; i++) + { + switch(sha) + { + case SHA256: + HASH256_process(&sha256,x->val[i]); + break; + case SHA384: + HASH384_process(&sha512,x->val[i]); + break; + case SHA512: + HASH512_process(&sha512,x->val[i]); + break; + } + } + + switch (sha) + { + case SHA256: + HASH256_hash(&sha256,hh); + break; + case SHA384: + HASH384_hash(&sha512,hh); + break; + case SHA512: + HASH512_hash(&sha512,hh); + break; + } + + OCT_empty(w); + if (!pad) + OCT_jbytes(w,hh,hlen); + else + { + if (pad<=hlen) + OCT_jbytes(w,hh,pad); + else + { + OCT_jbyte(w,0,pad-hlen); + OCT_jbytes(w,hh,hlen); + } + } + return; +} + +/* Hash octet p to octet w */ +void amcl::HASH(int sha,octet *p,octet *w) +{ + ehashit(sha,p,-1,NULL,w,0); +} + +/* Calculate HMAC of m using key k. HMAC is tag of length olen */ +int amcl::HMAC(int sha,octet *m,octet *k,int olen,octet *tag) +{ + /* Input is from an octet m * + * olen is requested output length in bytes. k is the key * + * The output is the calculated tag */ + int hlen,b; + char h[128],k0[128]; + octet H= {0,sizeof(h),h}; + octet K0= {0,sizeof(k0),k0}; + + hlen=sha; + if (hlen>32) b=128; + else b=64; + + if (olen<4 /*|| olen>hlen*/) return 0; + + if (k->len > b) ehashit(sha,k,-1,NULL,&K0,0); + else OCT_copy(&K0,k); + + OCT_jbyte(&K0,0,b-K0.len); + + OCT_xorbyte(&K0,0x36); + + ehashit(sha,&K0,-1,m,&H,0); + + OCT_xorbyte(&K0,0x6a); /* 0x6a = 0x36 ^ 0x5c */ + ehashit(sha,&K0,-1,&H,&H,olen); + + OCT_empty(tag); + + OCT_jbytes(tag,H.val,olen); + + return 1; +} + +void amcl::KDF2(int sha,octet *z,octet *p,int olen,octet *key) +{ + /* NOTE: the parameter olen is the length of the output k in bytes */ + char h[64]; + octet H= {0,sizeof(h),h}; + int counter,cthreshold; + int hlen=sha; + + OCT_empty(key); + + cthreshold=ROUNDUP(olen,hlen); + + for (counter=1; counter<=cthreshold; counter++) + { + ehashit(sha,z,counter,p,&H,0); + if (key->len+hlen>olen) OCT_jbytes(key,H.val,olen%hlen); + else OCT_joctet(key,&H); + } + +} + +/* Password based Key Derivation Function */ +/* Input password p, salt s, and repeat count */ +/* Output key of length olen */ +void amcl::PBKDF2(int sha,octet *p,octet *s,int rep,int olen,octet *key) +{ + int i,j,len,d=ROUNDUP(olen,sha); + char f[64],u[64]; + octet F= {0,sizeof(f),f}; + octet U= {0,sizeof(u),u}; + OCT_empty(key); + + for (i=1; i<=d; i++) + { + len=s->len; + OCT_jint(s,i,4); + + HMAC(sha,s,p,sha,&F); + + s->len=len; + OCT_copy(&U,&F); + for (j=2; j<=rep; j++) + { + HMAC(sha,&U,p,sha,&U); + OCT_xor(&F,&U); + } + + OCT_joctet(key,&F); + } + + OCT_chop(key,NULL,olen); +} + +/* AES encryption/decryption. Encrypt byte array M using key K and returns ciphertext */ +void amcl::AES_CBC_IV0_ENCRYPT(octet *k,octet *m,octet *c) +{ + /* AES CBC encryption, with Null IV and key k */ + /* Input is from an octet string m, output is to an octet string c */ + /* Input is padded as necessary to make up a full final block */ + aes a; + int fin; + int i,j,ipt,opt; + char buff[16]; + int padlen; + + OCT_clear(c); + if (m->len==0) return; + AES_init(&a,CBC,k->len,k->val,NULL); + + ipt=opt=0; + fin=0; + for(;;) + { + for (i=0; i<16; i++) + { + if (ipt<m->len) buff[i]=m->val[ipt++]; + else + { + fin=1; + break; + } + } + if (fin) break; + AES_encrypt(&a,buff); + for (i=0; i<16; i++) + if (opt<c->max) c->val[opt++]=buff[i]; + } + + /* last block, filled up to i-th index */ + + padlen=16-i; + for (j=i; j<16; j++) buff[j]=padlen; + AES_encrypt(&a,buff); + for (i=0; i<16; i++) + if (opt<c->max) c->val[opt++]=buff[i]; + AES_end(&a); + c->len=opt; +} + +/* decrypts and returns TRUE if all consistent, else returns FALSE */ +int amcl::AES_CBC_IV0_DECRYPT(octet *k,octet *c,octet *m) +{ + /* padding is removed */ + aes a; + int i,ipt,opt,ch; + char buff[16]; + int fin,bad; + int padlen; + ipt=opt=0; + + OCT_clear(m); + if (c->len==0) return 1; + ch=c->val[ipt++]; + + AES_init(&a,CBC,k->len,k->val,NULL); + fin=0; + + for(;;) + { + for (i=0; i<16; i++) + { + buff[i]=ch; + if (ipt>=c->len) + { + fin=1; + break; + } + else ch=c->val[ipt++]; + } + AES_decrypt(&a,buff); + if (fin) break; + for (i=0; i<16; i++) + if (opt<m->max) m->val[opt++]=buff[i]; + } + AES_end(&a); + bad=0; + padlen=buff[15]; + if (i!=15 || padlen<1 || padlen>16) bad=1; + if (padlen>=2 && padlen<=16) + for (i=16-padlen; i<16; i++) if (buff[i]!=padlen) bad=1; + + if (!bad) for (i=0; i<16-padlen; i++) + if (opt<m->max) m->val[opt++]=buff[i]; + + m->len=opt; + if (bad) return 0; + return 1; +} http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/ecdh_support.h ---------------------------------------------------------------------- diff --git a/version3/cpp/ecdh_support.h b/version3/cpp/ecdh_support.h new file mode 100644 index 0000000..65538e1 --- /dev/null +++ b/version3/cpp/ecdh_support.h @@ -0,0 +1,84 @@ +#ifndef ECC_SUPPORT_H +#define ECC_SUPPORT_H + +#include "amcl.h" + +namespace amcl { + +/* Auxiliary Functions */ + + +extern void ehashit(int ,octet *,int ,octet *,octet *,int); + +/** @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/cpp/ecp.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/ecp.cpp b/version3/cpp/ecp.cpp new file mode 100644 index 0000000..020c667 --- /dev/null +++ b/version3/cpp/ecp.cpp @@ -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" + +using namespace XXX; +using namespace YYY; + +/* test for P=O point-at-infinity */ +int ZZZ::ECP_isinf(ECP *P) +{ + +#if CURVETYPE_ZZZ==EDWARDS + return (FP_iszilch(&(P->x)) && FP_equals(&(P->y),&(P->z))); +#endif +#if CURVETYPE_ZZZ==WEIERSTRASS + return (FP_iszilch(&(P->x)) && FP_iszilch(&(P->z))); +#endif +#if CURVETYPE_ZZZ==MONTGOMERY + return FP_iszilch(&(P->z)); +#endif + +} + +/* Conditional swap of P and Q dependant on d */ +static void ECP_cswap(ZZZ::ECP *P,ZZZ::ECP *Q,int d) +{ + FP_cswap(&(P->x),&(Q->x),d); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_cswap(&(P->y),&(Q->y),d); +#endif + FP_cswap(&(P->z),&(Q->z),d); + +} + +#if CURVETYPE_ZZZ!=MONTGOMERY +/* Conditional move Q to P dependant on d */ +static void ECP_cmove(ZZZ::ECP *P,ZZZ::ECP *Q,int d) +{ + FP_cmove(&(P->x),&(Q->x),d); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_cmove(&(P->y),&(Q->y),d); +#endif + FP_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_select(ZZZ::ECP *P,ZZZ::ECP W[],sign32 b) +{ + ZZZ::ECP MP; + sign32 m=b>>31; + sign32 babs=(b^m)-m; + + babs=(babs-1)/2; + + ECP_cmove(P,&W[0],teq(babs,0)); // conditional move + ECP_cmove(P,&W[1],teq(babs,1)); + ECP_cmove(P,&W[2],teq(babs,2)); + ECP_cmove(P,&W[3],teq(babs,3)); + ECP_cmove(P,&W[4],teq(babs,4)); + ECP_cmove(P,&W[5],teq(babs,5)); + ECP_cmove(P,&W[6],teq(babs,6)); + ECP_cmove(P,&W[7],teq(babs,7)); + + ECP_copy(&MP,P); + ECP_neg(&MP); // minus P + ECP_cmove(P,&MP,(int)(m&1)); +} +#endif + +/* Test P == Q */ +/* SU=168 */ +int ZZZ::ECP_equals(ECP *P,ECP *Q) +{ + FP a,b; + + FP_mul(&a,&(P->x),&(Q->z)); + FP_mul(&b,&(Q->x),&(P->z)); + if (!FP_equals(&a,&b)) return 0; + +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_mul(&a,&(P->y),&(Q->z)); + FP_mul(&b,&(Q->y),&(P->z)); + if (!FP_equals(&a,&b)) return 0; +#endif + + return 1; + +} + +/* Set P=Q */ +/* SU=16 */ +void ZZZ::ECP_copy(ECP *P,ECP *Q) +{ + FP_copy(&(P->x),&(Q->x)); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_copy(&(P->y),&(Q->y)); +#endif + FP_copy(&(P->z),&(Q->z)); +} + +/* Set P=-Q */ +#if CURVETYPE_ZZZ!=MONTGOMERY +/* SU=8 */ +void ZZZ::ECP_neg(ECP *P) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + FP_neg(&(P->y),&(P->y)); + FP_norm(&(P->y)); +#else + FP_neg(&(P->x),&(P->x)); + FP_norm(&(P->x)); +#endif + +} +#endif + +/* Set P=O */ +void ZZZ::ECP_inf(ECP *P) +{ + FP_zero(&(P->x)); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_one(&(P->y)); +#endif +#if CURVETYPE_ZZZ!=EDWARDS + FP_zero(&(P->z)); +#else + FP_one(&(P->z)); +#endif +} + +/* Calculate right Hand Side of curve equation y^2=RHS */ +/* SU=56 */ +void ZZZ::ECP_rhs(FP *v,FP *x) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + /* x^3+Ax+B */ + FP t; + FP_sqr(&t,x); + FP_mul(&t,&t,x); + + if (CURVE_A==-3) + { + FP_neg(v,x); + FP_norm(v); + FP_imul(v,v,-CURVE_A); + FP_norm(v); + FP_add(v,&t,v); + } + else FP_copy(v,&t); + + FP_rcopy(&t,CURVE_B); + + FP_add(v,&t,v); + FP_reduce(v); +#endif + +#if CURVETYPE_ZZZ==EDWARDS + /* (Ax^2-1)/(Bx^2-1) */ + FP t,one; + FP_sqr(v,x); + FP_one(&one); + FP_rcopy(&t,CURVE_B); + + FP_mul(&t,v,&t); + FP_sub(&t,&t,&one); + FP_norm(&t); + if (CURVE_A==1) FP_sub(v,v,&one); + + if (CURVE_A==-1) + { + FP_add(v,v,&one); + FP_norm(v); + FP_neg(v,v); + } + FP_norm(v); + FP_inv(&t,&t); + FP_mul(v,v,&t); + FP_reduce(v); +#endif + +#if CURVETYPE_ZZZ==MONTGOMERY + /* x^3+Ax^2+x */ + FP x2,x3; + FP_sqr(&x2,x); + FP_mul(&x3,&x2,x); + FP_copy(v,x); + FP_imul(&x2,&x2,CURVE_A); + FP_add(v,v,&x2); + FP_add(v,v,&x3); + FP_reduce(v); +#endif +} + +/* Set P=(x,y) */ + +#if CURVETYPE_ZZZ==MONTGOMERY + +/* Set P=(x,{y}) */ + +int ZZZ::ECP_set(ECP *P,BIG x) +{ + BIG m,b; + FP rhs; + BIG_rcopy(m,Modulus); + + FP_nres(&rhs,x); + + ECP_rhs(&rhs,&rhs); + FP_redc(b,&rhs); + + if (BIG_jacobi(b,m)!=1) + { + ECP_inf(P); + return 0; + } + + FP_nres(&(P->x),x); + FP_one(&(P->z)); + return 1; +} + +/* Extract x coordinate as BIG */ +int ZZZ::ECP_get(BIG x,ECP *P) +{ + ECP W; + ECP_copy(&W,P); + ECP_affine(W); + if (ECP_isinf(&W)) return -1; + FP_redc(x,&(W.x)); + return 0; +} + + +#else +/* Extract (x,y) and return sign of y. If x and y are the same return only x */ +/* SU=16 */ +int ZZZ::ECP_get(BIG x,BIG y,ECP *P) +{ + int s; + ECP W; + ECP_copy(&W,P); + ECP_affine(&W); + if (ECP_isinf(&W)) return -1; + + FP_redc(y,&(W.y)); + s=BIG_parity(y); + + FP_redc(x,&(W.x)); + + return s; +} + +/* Set P=(x,{y}) */ +/* SU=96 */ +int ZZZ::ECP_set(ECP *P,BIG x,BIG y) +{ + FP rhs,y2; + + FP_nres(&y2,y); + FP_sqr(&y2,&y2); + FP_reduce(&y2); + + FP_nres(&rhs,x); + ECP_rhs(&rhs,&rhs); + + if (!FP_equals(&y2,&rhs)) + { + ECP_inf(P); + return 0; + } + + // P->inf=0; + + FP_nres(&(P->x),x); + FP_nres(&(P->y),y); + FP_one(&(P->z)); + return 1; +} + +/* Set P=(x,y), where y is calculated from x with sign s */ +/* SU=136 */ +int ZZZ::ECP_setx(ECP *P,BIG x,int s) +{ + FP rhs; + BIG t,m; + BIG_rcopy(m,Modulus); + + FP_nres(&rhs,x); + + ECP_rhs(&rhs,&rhs); + + FP_redc(t,&rhs); + if (BIG_jacobi(t,m)!=1) + { + ECP_inf(P); + return 0; + } + + FP_nres(&(P->x),x); + FP_sqrt(&(P->y),&rhs); + + FP_redc(t,&(P->y)); + + if (BIG_parity(t)!=s) + FP_neg(&(P->y),&(P->y)); + FP_reduce(&(P->y)); + FP_one(&(P->z)); + return 1; +} + +#endif + +/* Convert P to Affine, from (x,y,z) to (x,y) */ +/* SU=160 */ +void ZZZ::ECP_affine(ECP *P) +{ + FP one,iz; + BIG b; + if (ECP_isinf(P)) return; + FP_one(&one); + if (FP_equals(&(P->z),&one)) return; + + FP_inv(&iz,&(P->z)); + FP_mul(&(P->x),&(P->x),&iz); + +#if CURVETYPE_ZZZ==EDWARDS || CURVETYPE_ZZZ==WEIERSTRASS + + FP_mul(&(P->y),&(P->y),&iz); + FP_reduce(&(P->y)); + +#endif + + FP_reduce(&(P->x)); + FP_copy(&(P->z),&one); +} + +/* SU=120 */ +void ZZZ::ECP_outputxyz(ECP *P) +{ + BIG x,z; + if (ECP_isinf(P)) + { + printf("Infinity\n"); + return; + } + FP_reduce(&(P->x)); + FP_redc(x,&(P->x)); + FP_reduce(&(P->z)); + FP_redc(z,&(P->z)); + +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG y; + FP_reduce(&(P->y)); + FP_redc(y,&(P->y)); + printf("("); + BIG_output(x); + printf(","); + BIG_output(y); + printf(","); + BIG_output(z); + printf(")\n"); + +#else + printf("("); + BIG_output(x); + printf(","); + BIG_output(z); + printf(")\n"); +#endif +} + +/* SU=16 */ +/* Output point P */ +void ZZZ::ECP_output(ECP *P) +{ + BIG x,y; + if (ECP_isinf(P)) + { + printf("Infinity\n"); + return; + } + ECP_affine(P); +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_redc(x,&(P->x)); + FP_redc(y,&(P->y)); + printf("("); + BIG_output(x); + printf(","); + BIG_output(y); + printf(")\n"); +#else + FP_redc(x,&(P->x)); + printf("("); + BIG_output(x); + printf(")\n"); +#endif +} + +/* SU=16 */ +/* Output point P */ +void ZZZ::ECP_rawoutput(ECP *P) +{ + BIG x,y,z; + +#if CURVETYPE_ZZZ!=MONTGOMERY + FP_redc(x,&(P->x)); + FP_redc(y,&(P->y)); + FP_redc(z,&(P->z)); + printf("("); + BIG_output(x); + printf(","); + BIG_output(y); + printf(","); + BIG_output(z); + printf(")\n"); +#else + FP_redc(x,&(P->x)); + FP_redc(z,&(P->z)); + printf("("); + BIG_output(x); + printf(","); + BIG_output(z); + printf(")\n"); +#endif +} + +/* SU=88 */ +/* Convert P to octet string, compressing if desired */ +void ZZZ::ECP_toOctet(octet *W,ECP *P,bool compress) +{ +#if CURVETYPE_ZZZ==MONTGOMERY + BIG x; + ECP_get(x,P); + W->len=MODBYTES_XXX+1; + W->val[0]=0x06; + BIG_toBytes(&(W->val[1]),x); +#else + BIG x,y; + ECP_get(x,y,P); + if (compress) + { + W->val[0]=0x02; + if (BIG_parity(y)==1) W->val[0]=0x03; + W->len=MODBYTES_XXX+1; + BIG_toBytes(&(W->val[1]),x); + } + else + { + W->val[0]=0x04; + W->len=2*MODBYTES_XXX+1; + BIG_toBytes(&(W->val[1]),x); + BIG_toBytes(&(W->val[MODBYTES_XXX+1]),y); + } +#endif +} + +/* SU=88 */ +/* Restore P from octet string */ +int ZZZ::ECP_fromOctet(ECP *P,octet *W) +{ +#if CURVETYPE_ZZZ==MONTGOMERY + BIG x; + BIG_fromBytes(x,&(W->val[1])); + if (ECP_set(P,x)) return 1; + return 0; +#else + BIG x,y; + int typ=W->val[0]; + BIG_fromBytes(x,&(W->val[1])); + + if (typ==0x04) + { + BIG_fromBytes(y,&(W->val[MODBYTES_XXX+1])); + if (ECP_set(P,x,y)) return 1; + } + if (typ==0x02 || typ==0x03) + { + if (ECP_setx(P,x,typ&1)) return 1; + } + return 0; +#endif +} + + +/* Set P=2P */ +/* SU=272 */ +void ZZZ::ECP_dbl(ECP *P) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + FP t0,t1,t2,t3,x3,y3,z3,b; + +// if (ECP_isinf(P)) return; + + if (CURVE_A==0) + { // 2S + 6M + FP_sqr(&t0,&(P->y)); //t0.sqr(); + FP_mul(&t1,&(P->y),&(P->z)); //t1.mul(z); + + FP_sqr(&t2,&(P->z)); //t2.sqr(); + + FP_add(&(P->z),&t0,&t0); //z.add(t0); + FP_norm(&(P->z)); //z.norm(); + FP_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP_norm(&(P->z)); //z.norm(); + + FP_imul(&t2,&t2,3*CURVE_B_I); //t2.imul(3*ROM.CURVE_B_I); + FP_mul(&x3,&t2,&(P->z)); //x3.mul(z); + + FP_add(&y3,&t0,&t2); //y3.add(t2); + FP_norm(&y3); //y3.norm(); + FP_mul(&(P->z),&(P->z),&t1); //z.mul(t1); + + FP_add(&t1,&t2,&t2); //t1.add(t2); + FP_add(&t2,&t2,&t1); //t2.add(t1); + FP_sub(&t0,&t0,&t2); //t0.sub(t2); + FP_norm(&t0); //t0.norm(); + FP_mul(&y3,&y3,&t0); //y3.mul(t0); + FP_add(&y3,&y3,&x3); //y3.add(x3); + + FP_mul(&t1,&(P->x),&(P->y)); //t1.mul(y); + FP_norm(&t0); //x.norm(); + FP_mul(&(P->x),&t0,&t1); //x.mul(t1); + FP_add(&(P->x),&(P->x),&(P->x)); //x.add(x); + FP_norm(&(P->x)); //x.norm(); + FP_copy(&(P->y),&y3); //y.copy(y3); + FP_norm(&(P->y)); //y.norm(); + } + else // its -3 + { // 3S+10M + + if (CURVE_B_I==0) //if (ROM.CURVE_B_I==0) + FP_rcopy(&b,CURVE_B); //b.copy(new FP(new BIG(ROM.CURVE_B))); + + FP_sqr(&t0,&(P->x)); //t0.sqr(); //1 x^2 + FP_sqr(&t1,&(P->y)); //t1.sqr(); //2 y^2 + FP_sqr(&t2,&(P->z)); //t2.sqr(); //3 + + FP_mul(&t3,&(P->x),&(P->y)); //t3.mul(y); //4 + FP_add(&t3,&t3,&t3); //t3.add(t3); + FP_norm(&t3); //t3.norm();//5 + + FP_mul(&z3,&(P->z),&(P->x)); //z3.mul(x); //6 + FP_add(&z3,&z3,&z3); //z3.add(z3); + FP_norm(&z3); //z3.norm();//7 + + if (CURVE_B_I==0) //if (ROM.CURVE_B_I==0) + FP_mul(&y3,&t2,&b); //y3.mul(b); //8 + else + FP_imul(&y3,&t2,CURVE_B_I); //y3.imul(ROM.CURVE_B_I); + + FP_sub(&y3,&y3,&z3); //y3.sub(z3); //y3.norm(); //9 *** + FP_add(&x3,&y3,&y3); //x3.add(y3); + FP_norm(&x3); //x3.norm();//10 + + FP_add(&y3,&y3,&x3); //y3.add(x3); //y3.norm();//11 + FP_sub(&x3,&t1,&y3); //x3.sub(y3); + FP_norm(&x3); //x3.norm();//12 + FP_add(&y3,&y3,&t1); //y3.add(t1); + FP_norm(&y3); //y3.norm();//13 + FP_mul(&y3,&y3,&x3); //y3.mul(x3); //14 + FP_mul(&x3,&x3,&t3); //x3.mul(t3); //15 + FP_add(&t3,&t2,&t2); //t3.add(t2); //16 + FP_add(&t2,&t2,&t3); //t2.add(t3); //17 + + if (CURVE_B_I==0) //if (ROM.CURVE_B_I==0) + FP_mul(&z3,&z3,&b); //z3.mul(b); //18 + else + FP_imul(&z3,&z3,CURVE_B_I); //z3.imul(ROM.CURVE_B_I); + + FP_sub(&z3,&z3,&t2); //z3.sub(t2); //z3.norm();//19 + FP_sub(&z3,&z3,&t0); //z3.sub(t0); + FP_norm(&z3); //z3.norm();//20 *** + FP_add(&t3,&z3,&z3); //t3.add(z3); //t3.norm();//21 + + FP_add(&z3,&z3,&t3); //z3.add(t3); + FP_norm(&z3); //z3.norm(); //22 + FP_add(&t3,&t0,&t0); //t3.add(t0); //t3.norm(); //23 + FP_add(&t0,&t0,&t3); //t0.add(t3); //t0.norm();//24 + FP_sub(&t0,&t0,&t2); //t0.sub(t2); + FP_norm(&t0); //t0.norm();//25 + + FP_mul(&t0,&t0,&z3); //t0.mul(z3);//26 + FP_add(&y3,&y3,&t0); //y3.add(t0); //y3.norm();//27 + FP_mul(&t0,&(P->y),&(P->z)); //t0.mul(z);//28 + FP_add(&t0,&t0,&t0); //t0.add(t0); + FP_norm(&t0); //t0.norm(); //29 + FP_mul(&z3,&z3,&t0); //z3.mul(t0);//30 + FP_sub(&(P->x),&x3,&z3); //x3.sub(z3); //x3.norm();//31 + FP_add(&t0,&t0,&t0); //t0.add(t0); + FP_norm(&t0); //t0.norm();//32 + FP_add(&t1,&t1,&t1); //t1.add(t1); + FP_norm(&t1); //t1.norm();//33 + FP_mul(&(P->z),&t0,&t1); //z3.mul(t1);//34 + + FP_norm(&(P->x)); //x.norm(); + FP_copy(&(P->y),&y3); //y.copy(y3); + FP_norm(&(P->y)); //y.norm(); + FP_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 C,D,H,J; + + FP_sqr(&C,&(P->x)); //C.sqr(); + FP_mul(&(P->x),&(P->x),&(P->y)); //x.mul(y); + FP_add(&(P->x),&(P->x),&(P->x)); //x.add(x); + FP_norm(&(P->x)); //x.norm(); + + FP_sqr(&D,&(P->y)); //D.sqr(); + + if (CURVE_A==-1) //if (ROM.CURVE_A==-1) + FP_neg(&C,&C); // C.neg(); + + FP_add(&(P->y),&C,&D); //y.add(D); + FP_norm(&(P->y)); //y.norm(); + FP_sqr(&H,&(P->z)); //H.sqr(); + FP_add(&H,&H,&H); //H.add(H); + + FP_sub(&J,&(P->y),&H); //J.sub(H); + FP_norm(&J); //J.norm(); + + FP_mul(&(P->x),&(P->x),&J); //x.mul(J); + FP_sub(&C,&C,&D); //C.sub(D); + FP_norm(&C); //C.norm(); + FP_mul(&(P->z),&(P->y),&J); //z.mul(J); + FP_mul(&(P->y),&(P->y),&C); //y.mul(C); + + +#endif + +#if CURVETYPE_ZZZ==MONTGOMERY + FP A,B,AA,BB,C; + + FP_add(&A,&(P->x),&(P->z)); //A.add(z); + FP_norm(&A); //A.norm(); + FP_sqr(&AA,&A); //AA.sqr(); + FP_sub(&B,&(P->x),&(P->z)); //B.sub(z); + FP_norm(&B); //B.norm(); + FP_sqr(&BB,&B); //BB.sqr(); + FP_sub(&C,&AA,&BB); //C.sub(BB); + FP_norm(&C); //C.norm(); + FP_mul(&(P->x),&AA,&BB); //x.mul(BB); + + FP_imul(&A,&C,(CURVE_A+2)/4); //A.imul((ROM.CURVE_A+2)/4); + + FP_add(&BB,&BB,&A); //BB.add(A); + FP_norm(&BB); //BB.norm(); + FP_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 ZZZ::ECP_add(ECP *P,ECP *Q,ECP *W) +{ + FP A,B,C,D,DA,CB; + + FP_add(&A,&(P->x),&(P->z)); //A.add(z); + FP_sub(&B,&(P->x),&(P->z)); //B.sub(z); + + FP_add(&C,&(Q->x),&(Q->z)); //C.add(Q.z); + + FP_sub(&D,&(Q->x),&(Q->z)); //D.sub(Q.z); + FP_norm(&A); //A.norm(); + + FP_norm(&D); //D.norm(); + FP_mul(&DA,&D,&A); //DA.mul(A); + + FP_norm(&C); //C.norm(); + FP_norm(&B); //B.norm(); + FP_mul(&CB,&C,&B); //CB.mul(B); + + FP_add(&A,&DA,&CB); //A.add(CB); + FP_norm(&A); //A.norm(); + FP_sqr(&(P->x),&A); //A.sqr(); + FP_sub(&B,&DA,&CB); //B.sub(CB); + FP_norm(&B); //B.norm(); + FP_sqr(&B,&B); //B.sqr(); + + FP_mul(&(P->z),&(W->x),&B); //z.mul(B); +} + +#else + +/* Set P+=Q */ +/* SU=248 */ +void ZZZ::ECP_add(ECP *P,ECP *Q) +{ +#if CURVETYPE_ZZZ==WEIERSTRASS + + int b3; + FP t0,t1,t2,t3,t4,x3,y3,z3,b; + + if (CURVE_A==0) + { + b3=3*CURVE_B_I; //int b=3*ROM.CURVE_B_I; + FP_mul(&t0,&(P->x),&(Q->x)); //t0.mul(Q.x); + FP_mul(&t1,&(P->y),&(Q->y)); //t1.mul(Q.y); + FP_mul(&t2,&(P->z),&(Q->z)); //t2.mul(Q.z); + FP_add(&t3,&(P->x),&(P->y)); //t3.add(y); + FP_norm(&t3); //t3.norm(); + FP_add(&t4,&(Q->x),&(Q->y)); //t4.add(Q.y); + FP_norm(&t4); //t4.norm(); + FP_mul(&t3,&t3,&t4); //t3.mul(t4); + FP_add(&t4,&t0,&t1); //t4.add(t1); + + FP_sub(&t3,&t3,&t4); //t3.sub(t4); + FP_norm(&t3); //t3.norm(); + FP_add(&t4,&(P->y),&(P->z)); //t4.add(z); + FP_norm(&t4); //t4.norm(); + FP_add(&x3,&(Q->y),&(Q->z)); //x3.add(Q.z); + FP_norm(&x3); //x3.norm(); + + FP_mul(&t4,&t4,&x3); //t4.mul(x3); + FP_add(&x3,&t1,&t2); //x3.add(t2); + + FP_sub(&t4,&t4,&x3); //t4.sub(x3); + FP_norm(&t4); //t4.norm(); + FP_add(&x3,&(P->x),&(P->z)); //x3.add(z); + FP_norm(&x3); //x3.norm(); + FP_add(&y3,&(Q->x),&(Q->z)); //y3.add(Q.z); + FP_norm(&y3); //y3.norm(); + FP_mul(&x3,&x3,&y3); //x3.mul(y3); + FP_add(&y3,&t0,&t2); //y3.add(t2); + FP_sub(&y3,&x3,&y3); //y3.rsub(x3); + FP_norm(&y3); //y3.norm(); + FP_add(&x3,&t0,&t0); //x3.add(t0); + FP_add(&t0,&t0,&x3); //t0.add(x3); + FP_norm(&t0); //t0.norm(); + FP_imul(&t2,&t2,b3); //t2.imul(b); + + FP_add(&z3,&t1,&t2); //z3.add(t2); + FP_norm(&z3); //z3.norm(); + FP_sub(&t1,&t1,&t2); //t1.sub(t2); + FP_norm(&t1); //t1.norm(); + FP_imul(&y3,&y3,b3); //y3.imul(b); + + FP_mul(&x3,&y3,&t4); //x3.mul(t4); + FP_mul(&t2,&t3,&t1); //t2.mul(t1); + FP_sub(&(P->x),&t2,&x3); //x3.rsub(t2); + FP_mul(&y3,&y3,&t0); //y3.mul(t0); + FP_mul(&t1,&t1,&z3); //t1.mul(z3); + FP_add(&(P->y),&y3,&t1); //y3.add(t1); + FP_mul(&t0,&t0,&t3); //t0.mul(t3); + FP_mul(&z3,&z3,&t4); //z3.mul(t4); + FP_add(&(P->z),&z3,&t0); //z3.add(t0); + + FP_norm(&(P->x)); //x.norm(); + FP_norm(&(P->y)); //y.norm(); + FP_norm(&(P->z)); //z.norm(); + } + else + { + + if (CURVE_B_I==0) //if (ROM.CURVE_B_I==0) + FP_rcopy(&b,CURVE_B); //b.copy(new FP(new BIG(ROM.CURVE_B))); + + FP_mul(&t0,&(P->x),&(Q->x)); //t0.mul(Q.x); //1 + FP_mul(&t1,&(P->y),&(Q->y)); //t1.mul(Q.y); //2 + FP_mul(&t2,&(P->z),&(Q->z)); //t2.mul(Q.z); //3 + + FP_add(&t3,&(P->x),&(P->y)); //t3.add(y); + FP_norm(&t3); //t3.norm(); //4 + FP_add(&t4,&(Q->x),&(Q->y)); //t4.add(Q.y); + FP_norm(&t4); //t4.norm();//5 + FP_mul(&t3,&t3,&t4); //t3.mul(t4);//6 + FP_add(&t4,&t0,&t1); //t4.add(t1); //t4.norm(); //7 + FP_sub(&t3,&t3,&t4); //t3.sub(t4); + FP_norm(&t3); //t3.norm(); //8 + FP_add(&t4,&(P->y),&(P->z)); //t4.add(z); + FP_norm(&t4); //t4.norm();//9 + FP_add(&x3,&(Q->y),&(Q->z)); //x3.add(Q.z); + FP_norm(&x3); //x3.norm();//10 + FP_mul(&t4,&t4,&x3); //t4.mul(x3); //11 + FP_add(&x3,&t1,&t2); //x3.add(t2); //x3.norm();//12 + + FP_sub(&t4,&t4,&x3); //t4.sub(x3); + FP_norm(&t4); //t4.norm();//13 + FP_add(&x3,&(P->x),&(P->z)); //x3.add(z); + FP_norm(&x3); //x3.norm(); //14 + FP_add(&y3,&(Q->x),&(Q->z)); //y3.add(Q.z); + FP_norm(&y3); //y3.norm();//15 + + FP_mul(&x3,&x3,&y3); //x3.mul(y3); //16 + FP_add(&y3,&t0,&t2); //y3.add(t2); //y3.norm();//17 + + FP_sub(&y3,&x3,&y3); //y3.rsub(x3); + FP_norm(&y3); //y3.norm(); //18 + + if (CURVE_B_I==0) //if (ROM.CURVE_B_I==0) + FP_mul(&z3,&t2,&b); //z3.mul(b); //18 + else + FP_imul(&z3,&t2,CURVE_B_I); //z3.imul(ROM.CURVE_B_I); + + FP_sub(&x3,&y3,&z3); //x3.sub(z3); + FP_norm(&x3); //x3.norm(); //20 + FP_add(&z3,&x3,&x3); //z3.add(x3); //z3.norm(); //21 + + FP_add(&x3,&x3,&z3); //x3.add(z3); //x3.norm(); //22 + FP_sub(&z3,&t1,&x3); //z3.sub(x3); + FP_norm(&z3); //z3.norm(); //23 + FP_add(&x3,&x3,&t1); //x3.add(t1); + FP_norm(&x3); //x3.norm(); //24 + + if (CURVE_B_I==0) //if (ROM.CURVE_B_I==0) + FP_mul(&y3,&y3,&b); //y3.mul(b); //18 + else + FP_imul(&y3,&y3,CURVE_B_I); //y3.imul(ROM.CURVE_B_I); + + FP_add(&t1,&t2,&t2); //t1.add(t2); //t1.norm();//26 + FP_add(&t2,&t2,&t1); //t2.add(t1); //t2.norm();//27 + + FP_sub(&y3,&y3,&t2); //y3.sub(t2); //y3.norm(); //28 + + FP_sub(&y3,&y3,&t0); //y3.sub(t0); + FP_norm(&y3); //y3.norm(); //29 + FP_add(&t1,&y3,&y3); //t1.add(y3); //t1.norm();//30 + FP_add(&y3,&y3,&t1); //y3.add(t1); + FP_norm(&y3); //y3.norm(); //31 + + FP_add(&t1,&t0,&t0); //t1.add(t0); //t1.norm(); //32 + FP_add(&t0,&t0,&t1); //t0.add(t1); //t0.norm();//33 + FP_sub(&t0,&t0,&t2); //t0.sub(t2); + FP_norm(&t0); //t0.norm();//34 + FP_mul(&t1,&t4,&y3); //t1.mul(y3);//35 + FP_mul(&t2,&t0,&y3); //t2.mul(y3);//36 + FP_mul(&y3,&x3,&z3); //y3.mul(z3);//37 + FP_add(&(P->y),&y3,&t2); //y3.add(t2); //y3.norm();//38 + FP_mul(&x3,&x3,&t3); //x3.mul(t3);//39 + FP_sub(&(P->x),&x3,&t1); //x3.sub(t1);//40 + FP_mul(&z3,&z3,&t4); //z3.mul(t4);//41 + + FP_mul(&t1,&t3,&t0); //t1.mul(t0);//42 + FP_add(&(P->z),&z3,&t1); //z3.add(t1); + FP_norm(&(P->x)); //x.norm(); + FP_norm(&(P->y)); //y.norm(); + FP_norm(&(P->z)); //z.norm(); + } + +#else + FP A,B,C,D,E,F,G,b; + + FP_mul(&A,&(P->z),&(Q->z)); //A.mul(Q.z); + FP_sqr(&B,&A); //B.sqr(); + FP_mul(&C,&(P->x),&(Q->x)); //C.mul(Q.x); + FP_mul(&D,&(P->y),&(Q->y)); //D.mul(Q.y); + + FP_mul(&E,&C,&D); //E.mul(D); + + if (CURVE_B_I==0) //if (ROM.CURVE_B_I==0) + { + FP_rcopy(&b,CURVE_B); //FP b=new FP(new BIG(ROM.CURVE_B)); + FP_mul(&E,&E,&b); //E.mul(b); + } + else + FP_imul(&E,&E,CURVE_B_I); //E.imul(ROM.CURVE_B_I); + + FP_sub(&F,&B,&E); //F.sub(E); + FP_add(&G,&B,&E); //G.add(E); + + if (CURVE_A==1) //if (ROM.CURVE_A==1) + { + FP_sub(&E,&D,&C); //E.sub(C); + } + FP_add(&C,&C,&D); //C.add(D); + + FP_add(&B,&(P->x),&(P->y)); //B.add(y); + FP_add(&D,&(Q->x),&(Q->y)); //D.add(Q.y); + FP_norm(&B); //B.norm(); + FP_norm(&D); //D.norm(); + FP_mul(&B,&B,&D); //B.mul(D); + FP_sub(&B,&B,&C); //B.sub(C); + FP_norm(&B); //B.norm(); + FP_norm(&F); //F.norm(); + FP_mul(&B,&B,&F); //B.mul(F); + FP_mul(&(P->x),&A,&B); //x.mul(B); + FP_norm(&G); //G.norm(); + + if (CURVE_A==1) //if (ROM.CURVE_A==1) + { + FP_norm(&E); //E.norm(); + FP_mul(&C,&E,&G); //C.mul(G); + } + if (CURVE_A==-1) //if (ROM.CURVE_A==-1) + { + FP_norm(&C); //C.norm(); + FP_mul(&C,&C,&G); //C.mul(G); + } + FP_mul(&(P->y),&A,&C); //y.mul(C); + FP_mul(&(P->z),&F,&G); //z.mul(G); + +#endif +} + +/* Set P-=Q */ +/* SU=16 */ +void ZZZ::ECP_sub(ECP *P,ECP *Q) +{ + ECP NQ; + ECP_copy(&NQ,Q); + ECP_neg(&NQ); + ECP_add(P,&NQ); +} + +#endif + +#if CURVETYPE_ZZZ!=MONTGOMERY +/* constant time multiply by small integer of length bts - use ladder */ +void ZZZ::ECP_pinmul(ECP *P,int e,int bts) +{ + int i,b; + ECP R0,R1; + + ECP_affine(P); + ECP_inf(&R0); + ECP_copy(&R1,P); + + for (i=bts-1; i>=0; i--) + { + b=(e>>i)&1; + ECP_copy(P,&R1); + ECP_add(P,&R0); + ECP_cswap(&R0,&R1,b); + ECP_copy(&R1,P); + ECP_dbl(&R0); + ECP_cswap(&R0,&R1,b); + } + ECP_copy(P,&R0); + ECP_affine(P); +} +#endif + +/* Set P=r*P */ +/* SU=424 */ +void ZZZ::ECP_mul(ECP *P,BIG e) +{ +#if CURVETYPE_ZZZ==MONTGOMERY + /* Montgomery ladder */ + int nb,i,b; + ECP R0,R1,D; + if (ECP_isinf(P)) return; + if (BIG_iszilch(e)) + { + ECP_inf(P); + return; + } + + ECP_copy(&R0,P); + ECP_copy(&R1,P); + ECP_dbl(&R1); + + ECP_copy(&D,P); ECP_affine(&D); + + nb=BIG_nbits(e); + for (i=nb-2; i>=0; i--) + { + b=BIG_bit(e,i); + ECP_copy(P,&R1); + ECP_add(P,&R0,&D); + ECP_cswap(&R0,&R1,b); + ECP_copy(&R1,P); + ECP_dbl(&R0); + + ECP_cswap(&R0,&R1,b); + } + + ECP_copy(P,&R0); + +#else + /* fixed size windows */ + int i,nb,s,ns; + BIG mt,t; + ECP Q,W[8],C; + sign8 w[1+(NLEN_XXX*BASEBITS_XXX+3)/4]; + + if (ECP_isinf(P)) return; + if (BIG_iszilch(e)) + { + ECP_inf(P); + return; + } + + /* precompute table */ + + ECP_copy(&Q,P); + ECP_dbl(&Q); + + ECP_copy(&W[0],P); + + for (i=1; i<8; i++) + { + ECP_copy(&W[i],&W[i-1]); + ECP_add(&W[i],&Q); + } + + /* make exponent odd - add 2P if even, P if odd */ + BIG_copy(t,e); + s=BIG_parity(t); + BIG_inc(t,1); + BIG_norm(t); + ns=BIG_parity(t); + BIG_copy(mt,t); + BIG_inc(mt,1); + BIG_norm(mt); + BIG_cmove(t,mt,s); + ECP_cmove(&Q,P,ns); + ECP_copy(&C,&Q); + + nb=1+(BIG_nbits(t)+3)/4; + + /* convert exponent to signed 4-bit window */ + for (i=0; i<nb; i++) + { + w[i]=BIG_lastbits(t,5)-16; + BIG_dec(t,w[i]); + BIG_norm(t); + BIG_fshr(t,4); + } + w[nb]=BIG_lastbits(t,5); + + ECP_copy(P,&W[(w[nb]-1)/2]); + for (i=nb-1; i>=0; i--) + { + ECP_select(&Q,W,w[i]); + ECP_dbl(P); + ECP_dbl(P); + ECP_dbl(P); + ECP_dbl(P); + ECP_add(P,&Q); + } + ECP_sub(P,&C); /* apply correction */ +#endif + ECP_affine(P); +} + +#if CURVETYPE_ZZZ!=MONTGOMERY +/* Set P=eP+fQ double multiplication */ +/* constant time - as useful for GLV method in pairings */ +/* SU=456 */ + +void ZZZ::ECP_mul2(ECP *P,ECP *Q,BIG e,BIG f) +{ + BIG te,tf,mt; + ECP S,T,W[8],C; + sign8 w[1+(NLEN_XXX*BASEBITS_XXX+1)/2]; + int i,a,b,s,ns,nb; + + BIG_copy(te,e); + BIG_copy(tf,f); + + /* precompute table */ + ECP_copy(&W[1],P); + ECP_sub(&W[1],Q); /* P+Q */ + ECP_copy(&W[2],P); + ECP_add(&W[2],Q); /* P-Q */ + ECP_copy(&S,Q); + ECP_dbl(&S); /* S=2Q */ + ECP_copy(&W[0],&W[1]); + ECP_sub(&W[0],&S); + ECP_copy(&W[3],&W[2]); + ECP_add(&W[3],&S); + ECP_copy(&T,P); + ECP_dbl(&T); /* T=2P */ + ECP_copy(&W[5],&W[1]); + ECP_add(&W[5],&T); + ECP_copy(&W[6],&W[2]); + ECP_add(&W[6],&T); + ECP_copy(&W[4],&W[5]); + ECP_sub(&W[4],&S); + ECP_copy(&W[7],&W[6]); + ECP_add(&W[7],&S); + + /* if multiplier is odd, add 2, else add 1 to multiplier, and add 2P or P to correction */ + + s=BIG_parity(te); + BIG_inc(te,1); + BIG_norm(te); + ns=BIG_parity(te); + BIG_copy(mt,te); + BIG_inc(mt,1); + BIG_norm(mt); + BIG_cmove(te,mt,s); + ECP_cmove(&T,P,ns); + ECP_copy(&C,&T); + + s=BIG_parity(tf); + BIG_inc(tf,1); + BIG_norm(tf); + ns=BIG_parity(tf); + BIG_copy(mt,tf); + BIG_inc(mt,1); + BIG_norm(mt); + BIG_cmove(tf,mt,s); + ECP_cmove(&S,Q,ns); + ECP_add(&C,&S); + + BIG_add(mt,te,tf); + BIG_norm(mt); + nb=1+(BIG_nbits(mt)+1)/2; + + /* convert exponent to signed 2-bit window */ + for (i=0; i<nb; i++) + { + a=BIG_lastbits(te,3)-4; + BIG_dec(te,a); + BIG_norm(te); + BIG_fshr(te,2); + b=BIG_lastbits(tf,3)-4; + BIG_dec(tf,b); + BIG_norm(tf); + BIG_fshr(tf,2); + w[i]=4*a+b; + } + w[nb]=(4*BIG_lastbits(te,3)+BIG_lastbits(tf,3)); + + ECP_copy(P,&W[(w[nb]-1)/2]); + for (i=nb-1; i>=0; i--) + { + ECP_select(&T,W,w[i]); + ECP_dbl(P); + ECP_dbl(P); + ECP_add(P,&T); + } + ECP_sub(P,&C); /* apply correction */ + ECP_affine(P); +} + +#endif + +void ZZZ::ECP_cfp(ECP *P) +{ /* multiply point by curves cofactor */ + BIG c; + int cf=CURVE_Cof_I; + if (cf==1) return; + if (cf==4) + { + ECP_dbl(P); + ECP_dbl(P); + return; + } + if (cf==8) + { + ECP_dbl(P); + ECP_dbl(P); + ECP_dbl(P); + return; + } + BIG_rcopy(c,CURVE_Cof); + ECP_mul(P,c); + return; +} + +/* map BIG to point on curve of correct order */ +/* The BIG should be the output of some hash function */ + +void ZZZ::ECP_mapit(ECP *P,octet *W) +{ + BIG q,x; + BIG_fromBytes(x,W->val); + BIG_rcopy(q,Modulus); + BIG_mod(x,q); + + for (;;) + { + for (;;) + { +#if CURVETYPE_ZZZ!=MONTGOMERY + ECP_setx(P,x,0); +#else + ECP_set(P,x); +#endif + BIG_inc(x,1); BIG_norm(x); + if (!ECP_isinf(P)) break; + } + ECP_cfp(P); + if (!ECP_isinf(P)) break; + } +} + +void ZZZ::ECP_generator(ECP *G) +{ + BIG x,y; + BIG_rcopy(x,CURVE_Gx); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_rcopy(y,CURVE_Gy); + ECP_set(G,x,y); +#else + ECP_set(G,x); +#endif +} + +#ifdef HAS_MAIN + +using namespace ZZZ; + +int main() +{ + int i; + ECP G,P; + csprng RNG; + BIG r,s,x,y,b,m,w,q; + BIG_rcopy(x,CURVE_Gx); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_rcopy(y,CURVE_Gy); +#endif + BIG_rcopy(m,Modulus); + + printf("x= "); + BIG_output(x); + printf("\n"); +#if CURVETYPE_ZZZ!=MONTGOMERY + printf("y= "); + BIG_output(y); + printf("\n"); +#endif + RNG_seed(&RNG,3,"abc"); + +#if CURVETYPE_ZZZ!=MONTGOMERY + ECP_set(&G,x,y); +#else + ECP_set(&G,x); +#endif + if (ECP_isinf(&G)) printf("Failed to set - point not on curve\n"); + else printf("set success\n"); + + ECP_output(&G); + + BIG_rcopy(r,CURVE_Order); //BIG_dec(r,7); + printf("r= "); + BIG_output(r); + printf("\n"); + + ECP_copy(&P,&G); + + ECP_mul(&P,r); + + ECP_output(&P); + BIG_randomnum(w,&RNG); + BIG_mod(w,r); + + ECP_copy(&P,&G); + ECP_mul(&P,w); + + ECP_output(&P); + + return 0; +} + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/ecp.h ---------------------------------------------------------------------- diff --git a/version3/cpp/ecp.h b/version3/cpp/ecp.h new file mode 100644 index 0000000..fc7c901 --- /dev/null +++ b/version3/cpp/ecp.h @@ -0,0 +1,293 @@ +#ifndef ECP_ZZZ_H +#define ECP_ZZZ_H + +#include "fp_YYY.h" +#include "config_curve_ZZZ.h" + +using namespace amcl; + +namespace ZZZ { + +/* Curve Params - see rom.c */ +extern const int CURVE_A; /**< Elliptic curve A parameter */ +extern const int CURVE_B_I; +extern const int CURVE_Cof_I; +extern const XXX::BIG CURVE_B; /**< Elliptic curve B parameter */ +extern const XXX::BIG CURVE_Order; /**< Elliptic curve group order */ +extern const XXX::BIG CURVE_Cof; /**< Elliptic curve cofactor */ + +/* Generator point on G1 */ +extern const XXX::BIG CURVE_Gx; /**< x-coordinate of generator point in group G1 */ +extern const XXX::BIG CURVE_Gy; /**< y-coordinate of generator point in group G1 */ + + +/* For Pairings only */ + +/* Generator point on G2 */ +extern const XXX::BIG CURVE_Pxa; /**< real part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxb; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pya; /**< real part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pyb; /**< imaginary part of y-coordinate of generator point in group G2 */ + +/*** needed for BLS24 curves ***/ + +extern const XXX::BIG CURVE_Pxaa; /**< real part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxab; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxba; /**< real part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxbb; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pyaa; /**< real part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pyab; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pyba; /**< real part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pybb; /**< imaginary part of y-coordinate of generator point in group G2 */ + +/*** needed for BLS48 curves ***/ + +extern const XXX::BIG CURVE_Pxaaa; /**< real part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxaab; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxaba; /**< real part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxabb; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxbaa; /**< real part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxbab; /**< imaginary part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxbba; /**< real part of x-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pxbbb; /**< imaginary part of x-coordinate of generator point in group G2 */ + +extern const XXX::BIG CURVE_Pyaaa; /**< real part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pyaab; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pyaba; /**< real part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pyabb; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pybaa; /**< real part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pybab; /**< imaginary part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pybba; /**< real part of y-coordinate of generator point in group G2 */ +extern const XXX::BIG CURVE_Pybbb; /**< imaginary part of y-coordinate of generator point in group G2 */ + + + +extern const XXX::BIG CURVE_Bnx; /**< BN curve x parameter */ + +extern const XXX::BIG CURVE_Cru; /**< BN curve Cube Root of Unity */ + +extern const XXX::BIG Fra; /**< real part of BN curve Frobenius Constant */ +extern const XXX::BIG Frb; /**< imaginary part of BN curve Frobenius Constant */ + + +extern const XXX::BIG CURVE_W[2]; /**< BN curve constant for GLV decomposition */ +extern const XXX::BIG CURVE_SB[2][2]; /**< BN curve constant for GLV decomposition */ +extern const XXX::BIG CURVE_WB[4]; /**< BN curve constant for GS decomposition */ +extern const XXX::BIG CURVE_BB[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 */ + + YYY::FP x; /**< x-coordinate of point */ +#if CURVETYPE_ZZZ!=MONTGOMERY + YYY::FP y; /**< y-coordinate of point. Not needed for Montgomery representation */ +#endif + YYY::FP z;/**< z-coordinate of point */ +} ECP; + + +/* 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_isinf(ECP *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_equals(ECP *P,ECP *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_copy(ECP *P,ECP *Q); +/** @brief Negation of an ECP point + * + @param P ECP instance, on exit = -P + */ +extern void ECP_neg(ECP *P); +/** @brief Set ECP to point-at-infinity + * + @param P ECP instance to be set to infinity + */ +extern void ECP_inf(ECP *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_rhs(YYY::FP *r,YYY::FP *x); +/** @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_setx(ECP *P,XXX::BIG x,int s); + +#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_set(ECP *P,XXX::BIG 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_get(XXX::BIG x,ECP *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_add(ECP *P,ECP *Q,ECP *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_set(ECP *P,XXX::BIG x,XXX::BIG 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_get(XXX::BIG x,XXX::BIG y,ECP *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_add(ECP *P,ECP *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_sub(ECP *P,ECP *Q); +#endif +/** @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_affine(ECP *P); +/** @brief Formats and outputs an ECP point to the console, in projective coordinates + * + @param P ECP instance to be printed + */ +extern void ECP_outputxyz(ECP *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_output(ECP * P); + +/** @brief Formats and outputs an ECP point to the console + * + @param P ECP instance to be printed + */ +extern void ECP_rawoutput(ECP * 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_toOctet(octet *S,ECP *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_fromOctet(ECP *P,octet *S); +/** @brief Doubles an ECP instance P + * + @param P ECP instance, on exit =2*P + */ +extern void ECP_dbl(ECP *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_pinmul(ECP *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_mul(ECP *P,XXX::BIG 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_mul2(ECP *P,ECP *Q,XXX::BIG e,XXX::BIG f); + +/** @brief Multiplies random point by co-factor + * + @param Q ECP multiplied by co-factor + */ +extern void ECP_cfp(ECP *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_mapit(ECP *Q,octet *w); + +/** @brief Get Group Generator from ROM + * + @param G ECP instance + */ +extern void ECP_generator(ECP *G); + +} + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version3/cpp/ecp2.cpp ---------------------------------------------------------------------- diff --git a/version3/cpp/ecp2.cpp b/version3/cpp/ecp2.cpp new file mode 100644 index 0000000..1404854 --- /dev/null +++ b/version3/cpp/ecp2.cpp @@ -0,0 +1,734 @@ +/* +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" + +using namespace XXX; +using namespace YYY; + +int ZZZ::ECP2_isinf(ECP2 *P) +{ + return (FP2_iszilch(&(P->x)) & FP2_iszilch(&(P->z))); +} + +/* Set P=Q */ +/* SU= 16 */ +void ZZZ::ECP2_copy(ECP2 *P,ECP2 *Q) +{ + FP2_copy(&(P->x),&(Q->x)); + FP2_copy(&(P->y),&(Q->y)); + FP2_copy(&(P->z),&(Q->z)); +} + +/* set P to Infinity */ +/* SU= 8 */ +void ZZZ::ECP2_inf(ECP2 *P) +{ + FP2_zero(&(P->x)); + FP2_one(&(P->y)); + FP2_zero(&(P->z)); +} + +/* Conditional move Q to P dependant on d */ +static void ECP2_cmove(ZZZ::ECP2 *P,ZZZ::ECP2 *Q,int d) +{ + FP2_cmove(&(P->x),&(Q->x),d); + FP2_cmove(&(P->y),&(Q->y),d); + FP2_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_select(ZZZ::ECP2 *P,ZZZ::ECP2 W[],sign32 b) +{ + ZZZ::ECP2 MP; + sign32 m=b>>31; + sign32 babs=(b^m)-m; + + babs=(babs-1)/2; + + ECP2_cmove(P,&W[0],teq(babs,0)); // conditional move + ECP2_cmove(P,&W[1],teq(babs,1)); + ECP2_cmove(P,&W[2],teq(babs,2)); + ECP2_cmove(P,&W[3],teq(babs,3)); + ECP2_cmove(P,&W[4],teq(babs,4)); + ECP2_cmove(P,&W[5],teq(babs,5)); + ECP2_cmove(P,&W[6],teq(babs,6)); + ECP2_cmove(P,&W[7],teq(babs,7)); + + ECP2_copy(&MP,P); + ECP2_neg(&MP); // minus P + ECP2_cmove(P,&MP,(int)(m&1)); +} + +/* return 1 if P==Q, else 0 */ +/* SU= 312 */ +int ZZZ::ECP2_equals(ECP2 *P,ECP2 *Q) +{ + FP2 a,b; + + FP2_mul(&a,&(P->x),&(Q->z)); + FP2_mul(&b,&(Q->x),&(P->z)); + if (!FP2_equals(&a,&b)) return 0; + + FP2_mul(&a,&(P->y),&(Q->z)); + FP2_mul(&b,&(Q->y),&(P->z)); + if (!FP2_equals(&a,&b)) return 0; + return 1; +} + +/* Make P affine (so z=1) */ +/* SU= 232 */ +void ZZZ::ECP2_affine(ECP2 *P) +{ + FP2 one,iz; + if (ECP2_isinf(P)) return; + + FP2_one(&one); + if (FP2_isunity(&(P->z))) + { + FP2_reduce(&(P->x)); + FP2_reduce(&(P->y)); + return; + } + + FP2_inv(&iz,&(P->z)); + FP2_mul(&(P->x),&(P->x),&iz); + FP2_mul(&(P->y),&(P->y),&iz); + + FP2_reduce(&(P->x)); + FP2_reduce(&(P->y)); + FP2_copy(&(P->z),&one); +} + +/* extract x, y from point P */ +/* SU= 16 */ +int ZZZ::ECP2_get(FP2 *x,FP2 *y,ECP2 *P) +{ + ECP2 W; + ECP2_copy(&W,P); + ECP2_affine(&W); + if (ECP2_isinf(&W)) return -1; + + FP2_copy(y,&(W.y)); + FP2_copy(x,&(W.x)); + return 0; +} + +/* SU= 152 */ +/* Output point P */ +void ZZZ::ECP2_output(ECP2 *P) +{ + FP2 x,y; + if (ECP2_isinf(P)) + { + printf("Infinity\n"); + return; + } + ECP2_get(&x,&y,P); + printf("("); + FP2_output(&x); + printf(","); + FP2_output(&y); + printf(")\n"); +} + +/* SU= 232 */ +void ZZZ::ECP2_outputxyz(ECP2 *P) +{ + ECP2 Q; + if (ECP2_isinf(P)) + { + printf("Infinity\n"); + return; + } + ECP2_copy(&Q,P); + printf("("); + FP2_output(&(Q.x)); + printf(","); + FP2_output(&(Q.y)); + printf(","); + FP2_output(&(Q.z)); + printf(")\n"); +} + +/* SU= 168 */ +/* Convert Q to octet string */ +void ZZZ::ECP2_toOctet(octet *W,ECP2 *Q) +{ + BIG b; + FP2 qx,qy; + ECP2_get(&qx,&qy,Q); + + FP_redc(b,&(qx.a)); + BIG_toBytes(&(W->val[0]),b); + FP_redc(b,&(qx.b)); + BIG_toBytes(&(W->val[MODBYTES_XXX]),b); + FP_redc(b,&(qy.a)); + BIG_toBytes(&(W->val[2*MODBYTES_XXX]),b); + FP_redc(b,&(qy.b)); + BIG_toBytes(&(W->val[3*MODBYTES_XXX]),b); + + W->len=4*MODBYTES_XXX; + +} + +/* SU= 176 */ +/* restore Q from octet string */ +int ZZZ::ECP2_fromOctet(ECP2 *Q,octet *W) +{ + BIG b; + FP2 qx,qy; + BIG_fromBytes(b,&(W->val[0])); + FP_nres(&(qx.a),b); + BIG_fromBytes(b,&(W->val[MODBYTES_XXX])); + FP_nres(&(qx.b),b); + BIG_fromBytes(b,&(W->val[2*MODBYTES_XXX])); + FP_nres(&(qy.a),b); + BIG_fromBytes(b,&(W->val[3*MODBYTES_XXX])); + FP_nres(&(qy.b),b); + + if (ECP2_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 ZZZ::ECP2_rhs(FP2 *rhs,FP2 *x) +{ + /* calculate RHS of elliptic curve equation */ + FP2 t; + BIG b; + FP2_sqr(&t,x); + + FP2_mul(rhs,&t,x); + + /* Assuming CURVE_A=0 */ + + BIG_rcopy(b,CURVE_B); + + FP2_from_BIG(&t,b); + +#if SEXTIC_TWIST_ZZZ == D_TYPE + FP2_div_ip(&t); /* IMPORTANT - here we use the correct SEXTIC twist of the curve */ +#endif + +#if SEXTIC_TWIST_ZZZ == M_TYPE + FP2_norm(&t); + FP2_mul_ip(&t); /* IMPORTANT - here we use the correct SEXTIC twist of the curve */ + FP2_norm(&t); + +#endif + + + FP2_add(rhs,&t,rhs); + FP2_reduce(rhs); +} + + +/* Set P=(x,y). Return 1 if (x,y) is on the curve, else return 0*/ +/* SU= 232 */ +int ZZZ::ECP2_set(ECP2 *P,FP2 *x,FP2 *y) +{ + FP2 rhs,y2; + + FP2_sqr(&y2,y); + ECP2_rhs(&rhs,x); + + if (!FP2_equals(&y2,&rhs)) + { + ECP2_inf(P); + return 0; + } + + FP2_copy(&(P->x),x); + FP2_copy(&(P->y),y); + + FP2_one(&(P->z)); + return 1; +} + +/* Set P=(x,y). Return 1 if (x,.) is on the curve, else return 0 */ +/* SU= 232 */ +int ZZZ::ECP2_setx(ECP2 *P,FP2 *x) +{ + FP2 y; + ECP2_rhs(&y,x); + + if (!FP2_sqrt(&y,&y)) + { + ECP2_inf(P); + return 0; + } + + FP2_copy(&(P->x),x); + FP2_copy(&(P->y),&y); + FP2_one(&(P->z)); + return 1; +} + +/* Set P=-P */ +/* SU= 8 */ +void ZZZ::ECP2_neg(ECP2 *P) +{ + FP2_norm(&(P->y)); + FP2_neg(&(P->y),&(P->y)); + FP2_norm(&(P->y)); +} + +/* R+=R */ +/* return -1 for Infinity, 0 for addition, 1 for doubling */ +/* SU= 448 */ +int ZZZ::ECP2_dbl(ECP2 *P) +{ + FP2 t0,t1,t2,t3,iy,x3,y3; + + FP2_copy(&iy,&(P->y)); //FP2 iy=new FP2(y); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_mul_ip(&iy); //iy.mul_ip(); + FP2_norm(&iy); //iy.norm(); +#endif + FP2_sqr(&t0,&(P->y)); //t0.sqr(); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_mul_ip(&t0); //t0.mul_ip(); +#endif + FP2_mul(&t1,&iy,&(P->z)); //t1.mul(z); + FP2_sqr(&t2,&(P->z)); //t2.sqr(); + + FP2_add(&(P->z),&t0,&t0); //z.add(t0); + FP2_norm(&(P->z)); //z.norm(); + FP2_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP2_add(&(P->z),&(P->z),&(P->z)); //z.add(z); + FP2_norm(&(P->z)); //z.norm(); + + FP2_imul(&t2,&t2,3*CURVE_B_I); //t2.imul(3*ROM.CURVE_B_I); +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_mul_ip(&t2); + FP2_norm(&t2); +#endif + + FP2_mul(&x3,&t2,&(P->z)); //x3.mul(z); + + FP2_add(&y3,&t0,&t2); //y3.add(t2); + FP2_norm(&y3); //y3.norm(); + FP2_mul(&(P->z),&(P->z),&t1); //z.mul(t1); + + FP2_add(&t1,&t2,&t2); //t1.add(t2); + FP2_add(&t2,&t2,&t1); //t2.add(t1); + FP2_norm(&t2); //t2.norm(); + FP2_sub(&t0,&t0,&t2); //t0.sub(t2); + FP2_norm(&t0); //t0.norm(); //y^2-9bz^2 + FP2_mul(&y3,&y3,&t0); //y3.mul(t0); + FP2_add(&(P->y),&y3,&x3); //y3.add(x3); //(y^2+3z*2)(y^2-9z^2)+3b.z^2.8y^2 + FP2_mul(&t1,&(P->x),&iy); //t1.mul(iy); + + FP2_norm(&t0); //x.norm(); + FP2_mul(&(P->x),&t0,&t1); //x.mul(t1); + FP2_add(&(P->x),&(P->x),&(P->x)); //x.add(x); //(y^2-9bz^2)xy2 + + FP2_norm(&(P->x)); //x.norm(); + FP2_norm(&(P->y)); //y.norm(); + + return 1; +} + +/* Set P+=Q */ +/* SU= 400 */ +int ZZZ::ECP2_add(ECP2 *P,ECP2 *Q) +{ + FP2 t0,t1,t2,t3,t4,x3,y3,z3; + int b3=3*CURVE_B_I; + + FP2_mul(&t0,&(P->x),&(Q->x)); //t0.mul(Q.x); // x.Q.x + FP2_mul(&t1,&(P->y),&(Q->y)); //t1.mul(Q.y); // y.Q.y + + FP2_mul(&t2,&(P->z),&(Q->z)); //t2.mul(Q.z); + + FP2_add(&t3,&(P->x),&(P->y)); //t3.add(y); + FP2_norm(&t3); //t3.norm(); //t3=X1+Y1 + FP2_add(&t4,&(Q->x),&(Q->y)); //t4.add(Q.y); + FP2_norm(&t4); //t4.norm(); //t4=X2+Y2 + FP2_mul(&t3,&t3,&t4); //t3.mul(t4); //t3=(X1+Y1)(X2+Y2) + + FP2_add(&t4,&t0,&t1); //t4.add(t1); //t4=X1.X2+Y1.Y2 + + FP2_sub(&t3,&t3,&t4); //t3.sub(t4); + FP2_norm(&t3); //t3.norm(); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_mul_ip(&t3); //t3.mul_ip(); + FP2_norm(&t3); //t3.norm(); //t3=(X1+Y1)(X2+Y2)-(X1.X2+Y1.Y2) = X1.Y2+X2.Y1 +#endif + FP2_add(&t4,&(P->y),&(P->z)); //t4.add(z); + FP2_norm(&t4); //t4.norm(); //t4=Y1+Z1 + FP2_add(&x3,&(Q->y),&(Q->z)); //x3.add(Q.z); + FP2_norm(&x3); //x3.norm(); //x3=Y2+Z2 + + FP2_mul(&t4,&t4,&x3); //t4.mul(x3); //t4=(Y1+Z1)(Y2+Z2) + FP2_add(&x3,&t1,&t2); //x3.add(t2); //X3=Y1.Y2+Z1.Z2 + + FP2_sub(&t4,&t4,&x3); //t4.sub(x3); + FP2_norm(&t4); //t4.norm(); +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_mul_ip(&t4); //t4.mul_ip(); + FP2_norm(&t4); //t4.norm(); //t4=(Y1+Z1)(Y2+Z2) - (Y1.Y2+Z1.Z2) = Y1.Z2+Y2.Z1 +#endif + FP2_add(&x3,&(P->x),&(P->z)); //x3.add(z); + FP2_norm(&x3); //x3.norm(); // x3=X1+Z1 + FP2_add(&y3,&(Q->x),&(Q->z)); //y3.add(Q.z); + FP2_norm(&y3); //y3.norm(); // y3=X2+Z2 + FP2_mul(&x3,&x3,&y3); //x3.mul(y3); // x3=(X1+Z1)(X2+Z2) + FP2_add(&y3,&t0,&t2); //y3.add(t2); // y3=X1.X2+Z1+Z2 + FP2_sub(&y3,&x3,&y3); //y3.rsub(x3); + FP2_norm(&y3); //y3.norm(); // y3=(X1+Z1)(X2+Z2) - (X1.X2+Z1.Z2) = X1.Z2+X2.Z1 +#if SEXTIC_TWIST_ZZZ==D_TYPE + FP2_mul_ip(&t0); //t0.mul_ip(); + FP2_norm(&t0); //t0.norm(); // x.Q.x + FP2_mul_ip(&t1); //t1.mul_ip(); + FP2_norm(&t1); //t1.norm(); // y.Q.y +#endif + + FP2_add(&x3,&t0,&t0); //x3.add(t0); + FP2_add(&t0,&t0,&x3); //t0.add(x3); + FP2_norm(&t0); //t0.norm(); + FP2_imul(&t2,&t2,b3); //t2.imul(b); +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_mul_ip(&t2); + FP2_norm(&t2); +#endif + + FP2_add(&z3,&t1,&t2); //z3.add(t2); + FP2_norm(&z3); //z3.norm(); + FP2_sub(&t1,&t1,&t2); //t1.sub(t2); + FP2_norm(&t1); //t1.norm(); + + FP2_imul(&y3,&y3,b3); //y3.imul(b); +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_mul_ip(&y3); + FP2_norm(&y3); +#endif + + FP2_mul(&x3,&y3,&t4); //x3.mul(t4); + FP2_mul(&t2,&t3,&t1); //t2.mul(t1); + FP2_sub(&(P->x),&t2,&x3); //x3.rsub(t2); + FP2_mul(&y3,&y3,&t0); //y3.mul(t0); + FP2_mul(&t1,&t1,&z3); //t1.mul(z3); + FP2_add(&(P->y),&y3,&t1); //y3.add(t1); + + FP2_mul(&t0,&t0,&t3); //t0.mul(t3); + FP2_mul(&z3,&z3,&t4); //z3.mul(t4); + FP2_add(&(P->z),&z3,&t0); //z3.add(t0); + + FP2_norm(&(P->x)); //x.norm(); + FP2_norm(&(P->y)); //y.norm(); + FP2_norm(&(P->z)); //z.norm(); + + return 0; +} + +/* Set P-=Q */ +/* SU= 16 */ +void ZZZ::ECP2_sub(ECP2 *P,ECP2 *Q) +{ + ECP2 NQ; + ECP2_copy(&NQ,Q); + ECP2_neg(&NQ); + ECP2_add(P,&NQ); +} + +/* P*=e */ +/* SU= 280 */ +void ZZZ::ECP2_mul(ECP2 *P,BIG e) +{ + /* fixed size windows */ + int i,nb,s,ns; + BIG mt,t; + ECP2 Q,W[8],C; + sign8 w[1+(NLEN_XXX*BASEBITS_XXX+3)/4]; + + if (ECP2_isinf(P)) return; + + /* precompute table */ + + ECP2_copy(&Q,P); + ECP2_dbl(&Q); + ECP2_copy(&W[0],P); + + for (i=1; i<8; i++) + { + ECP2_copy(&W[i],&W[i-1]); + ECP2_add(&W[i],&Q); + } + + /* make exponent odd - add 2P if even, P if odd */ + BIG_copy(t,e); + s=BIG_parity(t); + BIG_inc(t,1); + BIG_norm(t); + ns=BIG_parity(t); + BIG_copy(mt,t); + BIG_inc(mt,1); + BIG_norm(mt); + BIG_cmove(t,mt,s); + ECP2_cmove(&Q,P,ns); + ECP2_copy(&C,&Q); + + nb=1+(BIG_nbits(t)+3)/4; + + /* convert exponent to signed 4-bit window */ + for (i=0; i<nb; i++) + { + w[i]=BIG_lastbits(t,5)-16; + BIG_dec(t,w[i]); + BIG_norm(t); + BIG_fshr(t,4); + } + w[nb]=BIG_lastbits(t,5); + + ECP2_copy(P,&W[(w[nb]-1)/2]); + for (i=nb-1; i>=0; i--) + { + ECP2_select(&Q,W,w[i]); + ECP2_dbl(P); + ECP2_dbl(P); + ECP2_dbl(P); + ECP2_dbl(P); + ECP2_add(P,&Q); + } + ECP2_sub(P,&C); /* apply correction */ + ECP2_affine(P); +} + +/* Calculates q.P using Frobenius constant X */ +/* SU= 96 */ +void ZZZ::ECP2_frob(ECP2 *P,FP2 *X) +{ + FP2 X2; + FP2_sqr(&X2,X); + FP2_conj(&(P->x),&(P->x)); + FP2_conj(&(P->y),&(P->y)); + FP2_conj(&(P->z),&(P->z)); + FP2_reduce(&(P->z)); + FP2_mul(&(P->x),&X2,&(P->x)); + FP2_mul(&(P->y),&X2,&(P->y)); + FP2_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 ZZZ::ECP2_mul4(ECP2 *P,ECP2 Q[4],BIG u[4]) +{ + int i,j,k,nb,pb,bt; + ECP2 T[8],W; + BIG t[4],mt; + sign8 w[NLEN_XXX*BASEBITS_XXX+1]; + sign8 s[NLEN_XXX*BASEBITS_XXX+1]; + + for (i=0; i<4; i++) + { + BIG_copy(t[i],u[i]); + } + +// Precomputed table + ECP2_copy(&T[0],&Q[0]); // Q[0] + ECP2_copy(&T[1],&T[0]); + ECP2_add(&T[1],&Q[1]); // Q[0]+Q[1] + ECP2_copy(&T[2],&T[0]); + ECP2_add(&T[2],&Q[2]); // Q[0]+Q[2] + ECP2_copy(&T[3],&T[1]); + ECP2_add(&T[3],&Q[2]); // Q[0]+Q[1]+Q[2] + ECP2_copy(&T[4],&T[0]); + ECP2_add(&T[4],&Q[3]); // Q[0]+Q[3] + ECP2_copy(&T[5],&T[1]); + ECP2_add(&T[5],&Q[3]); // Q[0]+Q[1]+Q[3] + ECP2_copy(&T[6],&T[2]); + ECP2_add(&T[6],&Q[3]); // Q[0]+Q[2]+Q[3] + ECP2_copy(&T[7],&T[3]); + ECP2_add(&T[7],&Q[3]); // Q[0]+Q[1]+Q[2]+Q[3] + +// Make it odd + pb=1-BIG_parity(t[0]); + BIG_inc(t[0],pb); + BIG_norm(t[0]); + +// Number of bits + BIG_zero(mt); + for (i=0; i<4; i++) + { + BIG_or(mt,mt,t[i]); + } + nb=1+BIG_nbits(mt); + +// Sign pivot + s[nb-1]=1; + for (i=0;i<nb-1;i++) + { + BIG_fshr(t[0],1); + s[i]=2*BIG_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_parity(t[j]); + BIG_fshr(t[j],1); + + BIG_dec(t[j],(bt>>1)); + BIG_norm(t[j]); + w[i]+=bt*k; + k*=2; + } + } + +// Main loop + ECP2_select(P,T,2*w[nb-1]+1); + for (i=nb-2; i>=0; i--) + { + ECP2_select(&W,T,2*w[i]+s[i]); + ECP2_dbl(P); + ECP2_add(P,&W); + } + +// apply correction + ECP2_copy(&W,P); + ECP2_sub(&W,&Q[0]); + ECP2_cmove(P,&W,pb); + + ECP2_affine(P); +} + + +/* Map to hash value to point on G2 from random BIG */ + +void ZZZ::ECP2_mapit(ECP2 *Q,octet *W) +{ + BIG q,one,x,hv; + FP Fx,Fy; + FP2 X; +#if (PAIRING_FRIENDLY_ZZZ == BN) + ECP2 T,K; +#elif (PAIRING_FRIENDLY_ZZZ == BLS) + ECP2 xQ, x2Q; +#endif + BIG_fromBytes(hv,W->val); + BIG_rcopy(q,Modulus); + BIG_one(one); + BIG_mod(hv,q); + + for (;;) + { + FP2_from_BIGs(&X,one,hv); + if (ECP2_setx(Q,&X)) break; + BIG_inc(hv,1); + } + + FP_rcopy(&Fx,Fra); + FP_rcopy(&Fy,Frb); + FP2_from_FPs(&X,&Fx,&Fy); + +#if SEXTIC_TWIST_ZZZ==M_TYPE + FP2_inv(&X,&X); + FP2_norm(&X); +#endif + + BIG_rcopy(x,CURVE_Bnx); + +#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_copy(&T,Q); + ECP2_mul(&T,x); +#if SIGN_OF_X_ZZZ==NEGATIVEX + ECP2_neg(&T); // our x is negative +#endif + ECP2_copy(&K,&T); + ECP2_dbl(&K); + ECP2_add(&K,&T); + + ECP2_frob(&K,&X); + ECP2_frob(Q,&X); + ECP2_frob(Q,&X); + ECP2_frob(Q,&X); + ECP2_add(Q,&T); + ECP2_add(Q,&K); + ECP2_frob(&T,&X); + ECP2_frob(&T,&X); + ECP2_add(Q,&T); + ECP2_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_copy(&xQ,Q); + ECP2_mul(&xQ,x); + ECP2_copy(&x2Q,&xQ); + ECP2_mul(&x2Q,x); + +#if SIGN_OF_X_ZZZ==NEGATIVEX + ECP2_neg(&xQ); +#endif + + ECP2_sub(&x2Q,&xQ); + ECP2_sub(&x2Q,Q); + + ECP2_sub(&xQ,Q); + ECP2_frob(&xQ,&X); + + ECP2_dbl(Q); + ECP2_frob(Q,&X); + ECP2_frob(Q,&X); + + ECP2_add(Q,&x2Q); + ECP2_add(Q,&xQ); + + ECP2_affine(Q); + +#endif +} + +void ZZZ::ECP2_generator(ECP2 *G) +{ + FP2 wx,wy; + + FP_rcopy(&(wx.a),CURVE_Pxa); + FP_rcopy(&(wx.b),CURVE_Pxb); + FP_rcopy(&(wy.a),CURVE_Pya); + FP_rcopy(&(wy.b),CURVE_Pyb); + ECP2_set(G,&wx,&wy); +} + +
