http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto-c/blob/8d28d2c3/src/big.c.in ---------------------------------------------------------------------- diff --git a/src/big.c.in b/src/big.c.in new file mode 100644 index 0000000..8d56f80 --- /dev/null +++ b/src/big.c.in @@ -0,0 +1,1438 @@ +/* + 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 basic functions for BIG type */ +/* SU=m, SU is Stack Usage */ + +#include "big_XXX.h" + +/* test a=0? */ +int BIG_XXX_iszilch(BIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + if (a[i]!=0) return 0; + return 1; +} + +/* test a=1? */ +int BIG_XXX_isunity(BIG_XXX a) +{ + int i; + for(i=1; i<NLEN_XXX; i++) + if (a[i]!=0) return 0; + if (a[0]!=1) return 0; + return 1; +} + +/* test a=0? */ +int BIG_XXX_diszilch(DBIG_XXX a) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + if (a[i]!=0) return 0; + return 1; +} + +/* SU= 56 */ +/* output a */ +void BIG_XXX_output(BIG_XXX a) +{ + BIG_XXX b; + int i,len; + len=BIG_XXX_nbits(a); + if (len%4==0) len/=4; + else + { + len/=4; + len++; + } + if (len<MODBYTES_XXX*2) len=MODBYTES_XXX*2; + + for (i=len-1; i>=0; i--) + { + BIG_XXX_copy(b,a); + BIG_XXX_shr(b,i*4); + printf("%01x",(unsigned int) b[0]&15); + } +} + +/* SU= 16 */ +void BIG_XXX_rawoutput(BIG_XXX a) +{ + int i; + printf("("); + for (i=0; i<NLEN_XXX-1; i++) +#if CHUNK==64 + printf("%"PRIxMAX",",(uintmax_t) a[i]); + printf("%"PRIxMAX")",(uintmax_t) a[NLEN_XXX-1]); +#else + printf("%x,",(unsigned int) a[i]); + printf("%x)",(unsigned int) a[NLEN_XXX-1]); +#endif +} + +/* Swap a and b if d=1 */ +void BIG_XXX_cswap(BIG_XXX a,BIG_XXX b,int d) +{ + int i; + chunk t,c=d; + c=~(c-1); +#ifdef DEBUG_NORM + for (i=0; i<NLEN_XXX+2; i++) +#else + for (i=0; i<NLEN_XXX; i++) +#endif + { + t=c&(a[i]^b[i]); + a[i]^=t; + b[i]^=t; + } +} + +/* Move b to a if d=1 */ +void BIG_XXX_cmove(BIG_XXX f,BIG_XXX g,int d) +{ + int i; + chunk b=(chunk)-d; +#ifdef DEBUG_NORM + for (i=0; i<NLEN_XXX+2; i++) +#else + for (i=0; i<NLEN_XXX; i++) +#endif + { + f[i]^=(f[i]^g[i])&b; + } +} + +/* Move g to f if d=1 */ +void BIG_XXX_dcmove(DBIG_XXX f,DBIG_XXX g,int d) +{ + int i; + chunk b=(chunk)-d; +#ifdef DEBUG_NORM + for (i=0; i<DNLEN_XXX+2; i++) +#else + for (i=0; i<DNLEN_XXX; i++) +#endif + { + f[i]^=(f[i]^g[i])&b; + } +} + +/* convert BIG to/from bytes */ +/* SU= 64 */ +void BIG_XXX_toBytes(char *b,BIG_XXX a) +{ + int i; + BIG_XXX c; + BIG_XXX_norm(a); + BIG_XXX_copy(c,a); + for (i=MODBYTES_XXX-1; i>=0; i--) + { + b[i]=c[0]&0xff; + BIG_XXX_fshr(c,8); + } +} + +/* SU= 16 */ +void BIG_XXX_fromBytes(BIG_XXX a,char *b) +{ + int i; + BIG_XXX_zero(a); + for (i=0; i<MODBYTES_XXX; i++) + { + BIG_XXX_fshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[MPV_XXX]=1; + a[MNV_XXX]=0; +#endif +} + +void BIG_XXX_fromBytesLen(BIG_XXX a,char *b,int s) +{ + int i,len=s; + BIG_XXX_zero(a); + + if (len>MODBYTES_XXX) len=MODBYTES_XXX; + for (i=0; i<len; i++) + { + BIG_XXX_fshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[MPV_XXX]=1; + a[MNV_XXX]=0; +#endif +} + + + +/* SU= 88 */ +void BIG_XXX_doutput(DBIG_XXX a) +{ + DBIG_XXX b; + int i,len; + BIG_XXX_dnorm(a); + len=BIG_XXX_dnbits(a); + if (len%4==0) len/=4; + else + { + len/=4; + len++; + } + + for (i=len-1; i>=0; i--) + { + BIG_XXX_dcopy(b,a); + BIG_XXX_dshr(b,i*4); + printf("%01x",(unsigned int) b[0]&15); + } +} + + +void BIG_XXX_drawoutput(DBIG_XXX a) +{ + int i; + printf("("); + for (i=0; i<DNLEN_XXX-1; i++) +#if CHUNK==64 + printf("%"PRIxMAX",",(uintmax_t) a[i]); + printf("%"PRIxMAX")",(uintmax_t) a[DNLEN_XXX-1]); +#else + printf("%x,",(unsigned int) a[i]); + printf("%x)",(unsigned int) a[DNLEN_XXX-1]); +#endif +} + +/* Copy b=a */ +void BIG_XXX_copy(BIG_XXX b,BIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[MPV_XXX]=a[MPV_XXX]; + b[MNV_XXX]=a[MNV_XXX]; +#endif +} + +/* Copy from ROM b=a */ +void BIG_XXX_rcopy(BIG_XXX b,const BIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[MPV_XXX]=1; + b[MNV_XXX]=0; +#endif +} + +/* double length DBIG copy b=a */ +void BIG_XXX_dcopy(DBIG_XXX b,DBIG_XXX a) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[DMPV_XXX]=a[DMPV_XXX]; + b[DMNV_XXX]=a[DMNV_XXX]; +#endif +} + +/* Copy BIG to bottom half of DBIG */ +void BIG_XXX_dscopy(DBIG_XXX b,BIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX-1; i++) + b[i]=a[i]; + + b[NLEN_XXX-1]=a[NLEN_XXX-1]&BMASK_XXX; /* top word normalized */ + b[NLEN_XXX]=a[NLEN_XXX-1]>>BASEBITS_XXX; + + for (i=NLEN_XXX+1; i<DNLEN_XXX; i++) b[i]=0; +#ifdef DEBUG_NORM + b[DMPV_XXX]=a[MPV_XXX]; + b[DMNV_XXX]=a[MNV_XXX]; +#endif +} + +/* Copy BIG to top half of DBIG */ +void BIG_XXX_dsucopy(DBIG_XXX b,BIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=0; + for (i=NLEN_XXX; i<DNLEN_XXX; i++) + b[i]=a[i-NLEN_XXX]; +#ifdef DEBUG_NORM + b[DMPV_XXX]=a[MPV_XXX]; + b[DMNV_XXX]=a[MNV_XXX]; +#endif +} + +/* Copy bottom half of DBIG to BIG */ +void BIG_XXX_sdcopy(BIG_XXX b,DBIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i]; +#ifdef DEBUG_NORM + b[MPV_XXX]=a[DMPV_XXX]; + b[MNV_XXX]=a[DMNV_XXX]; +#endif +} + +/* Copy top half of DBIG to BIG */ +void BIG_XXX_sducopy(BIG_XXX b,DBIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + b[i]=a[i+NLEN_XXX]; +#ifdef DEBUG_NORM + b[MPV_XXX]=a[DMPV_XXX]; + b[MNV_XXX]=a[DMNV_XXX]; + +#endif +} + +/* Set a=0 */ +void BIG_XXX_zero(BIG_XXX a) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + a[i]=0; +#ifdef DEBUG_NORM + a[MPV_XXX]=a[MNV_XXX]=0; +#endif +} + +void BIG_XXX_dzero(DBIG_XXX a) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + a[i]=0; +#ifdef DEBUG_NORM + a[DMPV_XXX]=a[DMNV_XXX]=0; +#endif +} + +/* set a=1 */ +void BIG_XXX_one(BIG_XXX a) +{ + int i; + a[0]=1; + for (i=1; i<NLEN_XXX; i++) + a[i]=0; +#ifdef DEBUG_NORM + a[MPV_XXX]=1; + a[MNV_XXX]=0; +#endif +} + + + +/* Set c=a+b */ +/* SU= 8 */ +void BIG_XXX_add(BIG_XXX c,BIG_XXX a,BIG_XXX b) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + c[i]=a[i]+b[i]; +#ifdef DEBUG_NORM + c[MPV_XXX]=a[MPV_XXX]+b[MPV_XXX]; + c[MNV_XXX]=a[MNV_XXX]+b[MNV_XXX]; + if (c[MPV_XXX]>NEXCESS_XXX) printf("add problem - positive digit overflow %d\n",c[MPV_XXX]); + if (c[MNV_XXX]>NEXCESS_XXX) printf("add problem - negative digit overflow %d\n",c[MNV_XXX]); + +#endif +} + +/* Set c=a or b */ +void BIG_XXX_or(BIG_XXX c,BIG_XXX a,BIG_XXX b) +{ + int i; + BIG_XXX_norm(a); + BIG_XXX_norm(b); + for (i=0; i<NLEN_XXX; i++) + c[i]=a[i]|b[i]; +#ifdef DEBUG_NORM + c[MPV_XXX]=1; + c[MNV_XXX]=0; +#endif +} + + +/* Set c=c+d */ +void BIG_XXX_inc(BIG_XXX c,int d) +{ + BIG_XXX_norm(c); + c[0]+=(chunk)d; +#ifdef DEBUG_NORM + c[MPV_XXX]+=1; +#endif +} + +/* Set c=a-b */ +/* SU= 8 */ +void BIG_XXX_sub(BIG_XXX c,BIG_XXX a,BIG_XXX b) +{ + int i; + for (i=0; i<NLEN_XXX; i++) + c[i]=a[i]-b[i]; +#ifdef DEBUG_NORM + c[MPV_XXX]=a[MPV_XXX]+b[MNV_XXX]; + c[MNV_XXX]=a[MNV_XXX]+b[MPV_XXX]; + if (c[MPV_XXX]>NEXCESS_XXX) printf("sub problem - positive digit overflow %d\n",c[MPV_XXX]); + if (c[MNV_XXX]>NEXCESS_XXX) printf("sub problem - negative digit overflow %d\n",c[MNV_XXX]); + +#endif +} + +/* SU= 8 */ + +void BIG_XXX_dsub(DBIG_XXX c,DBIG_XXX a,DBIG_XXX b) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + c[i]=a[i]-b[i]; +#ifdef DEBUG_NORM + c[DMPV_XXX]=a[DMPV_XXX]+b[DMNV_XXX]; + c[DMNV_XXX]=a[DMNV_XXX]+b[DMPV_XXX]; + if (c[DMPV_XXX]>NEXCESS_XXX) printf("double sub problem - positive digit overflow %d\n",c[DMPV_XXX]); + if (c[DMNV_XXX]>NEXCESS_XXX) printf("double sub problem - negative digit overflow %d\n",c[DMNV_XXX]); +#endif +} + +void BIG_XXX_dadd(DBIG_XXX c,DBIG_XXX a,DBIG_XXX b) +{ + int i; + for (i=0; i<DNLEN_XXX; i++) + c[i]=a[i]+b[i]; +#ifdef DEBUG_NORM + c[DMPV_XXX]=a[DMPV_XXX]+b[DMNV_XXX]; + c[DMNV_XXX]=a[DMNV_XXX]+b[DMPV_XXX]; + if (c[DMPV_XXX]>NEXCESS_XXX) printf("double add problem - positive digit overflow %d\n",c[DMPV_XXX]); + if (c[DMNV_XXX]>NEXCESS_XXX) printf("double add problem - negative digit overflow %d\n",c[DMNV_XXX]); +#endif +} + +/* Set c=c-1 */ +void BIG_XXX_dec(BIG_XXX c,int d) +{ + BIG_XXX_norm(c); + c[0]-=(chunk)d; +#ifdef DEBUG_NORM + c[MNV_XXX]+=1; +#endif +} + +/* multiplication r=a*c by c<=NEXCESS_XXX */ +void BIG_XXX_imul(BIG_XXX r,BIG_XXX a,int c) +{ + int i; + for (i=0; i<NLEN_XXX; i++) r[i]=a[i]*c; +#ifdef DEBUG_NORM + r[MPV_XXX]=a[MPV_XXX]*c; + r[MNV_XXX]=a[MNV_XXX]*c; + if (r[MPV_XXX]>NEXCESS_XXX) printf("int mul problem - positive digit overflow %d\n",r[MPV_XXX]); + if (r[MNV_XXX]>NEXCESS_XXX) printf("int mul problem - negative digit overflow %d\n",r[MNV_XXX]); + +#endif +} + +/* multiplication r=a*c by larger integer - c<=FEXCESS */ +/* SU= 24 */ +chunk BIG_XXX_pmul(BIG_XXX r,BIG_XXX a,int c) +{ + int i; + chunk ak,carry=0; + for (i=0; i<NLEN_XXX; i++) + { + ak=a[i]; + r[i]=0; + carry=muladd_XXX(ak,(chunk)c,carry,&r[i]); + } +#ifdef DEBUG_NORM + r[MPV_XXX]=1; + r[MNV_XXX]=0; +#endif + return carry; +} + +/* r/=3 */ +/* SU= 16 */ +int BIG_XXX_div3(BIG_XXX r) +{ + int i; + chunk ak,base,carry=0; + BIG_XXX_norm(r); + base=((chunk)1<<BASEBITS_XXX); + for (i=NLEN_XXX-1; i>=0; i--) + { + ak=(carry*base+r[i]); + r[i]=ak/3; + carry=ak%3; + } + return (int)carry; +} + +/* multiplication c=a*b by even larger integer b>FEXCESS, resulting in DBIG */ +/* SU= 24 */ +void BIG_XXX_pxmul(DBIG_XXX c,BIG_XXX a,int b) +{ + int j; + chunk carry; + BIG_XXX_dzero(c); + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd_XXX(a[j],(chunk)b,carry,&c[j]); + c[NLEN_XXX]=carry; +#ifdef DEBUG_NORM + c[DMPV_XXX]=1; + c[DMNV_XXX]=0; +#endif +} + +/* .. if you know the result will fit in a BIG, c must be distinct from a and b */ +/* SU= 40 */ +void BIG_XXX_smul(BIG_XXX c,BIG_XXX a,BIG_XXX b) +{ + int i,j; + chunk carry; + + BIG_XXX_zero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=0; j<NLEN_XXX; j++) + { + if (i+j<NLEN_XXX) + carry=muladd_XXX(a[i],b[j],carry,&c[i+j]); + } + } +#ifdef DEBUG_NORM + c[MPV_XXX]=1; + c[MNV_XXX]=0; +#endif + +} + +/* Set c=a*b */ +/* SU= 72 */ +void BIG_XXX_mul(DBIG_XXX c,BIG_XXX a,BIG_XXX b) +{ + int i; +#ifdef dchunk + dchunk t,co; + dchunk s; + dchunk d[NLEN_XXX]; + int k; +#endif + +#ifdef DEBUG_NORM + if ((a[MPV_XXX]!=1 && a[MPV_XXX]!=0) || a[MNV_XXX]!=0) printf("First input to mul not normed\n"); + if ((b[MPV_XXX]!=1 && b[MPV_XXX]!=0) || b[MNV_XXX]!=0) printf("Second input to mul not normed\n"); +#endif + + /* Faster to Combafy it.. Let the compiler unroll the loops! */ + +#ifdef COMBA + + /* faster psuedo-Karatsuba method */ +#ifdef UNWOUND + + /* Insert output of faster.c here */ + +#else + for (i=0; i<NLEN_XXX; i++) + d[i]=(dchunk)a[i]*b[i]; + + s=d[0]; + t=s; + c[0]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + + for (k=1; k<NLEN_XXX; k++) + { + s+=d[k]; + t=co+s; + for (i=k; i>=1+k/2; i--) t+=(dchunk)(a[i]-a[k-i])*(b[k-i]-b[i]); + c[k]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + } + for (k=NLEN_XXX; k<2*NLEN_XXX-1; k++) + { + s-=d[k-NLEN_XXX]; + t=co+s; + for (i=NLEN_XXX-1; i>=1+k/2; i--) t+=(dchunk)(a[i]-a[k-i])*(b[k-i]-b[i]); + c[k]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + } + c[2*NLEN_XXX-1]=(chunk)co; + +#endif + +#else + int j; + chunk carry; + BIG_XXX_dzero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd_XXX(a[i],b[j],carry,&c[i+j]); + + c[NLEN_XXX+i]=carry; + } + +#endif + +#ifdef DEBUG_NORM + c[DMPV_XXX]=1; + c[DMNV_XXX]=0; +#endif +} + +/* Set c=a*a */ +/* SU= 80 */ +void BIG_XXX_sqr(DBIG_XXX c,BIG_XXX a) +{ + int i,j; +#ifdef dchunk + dchunk t,co; +#endif + +#ifdef DEBUG_NORM + if ((a[MPV_XXX]!=1 && a[MPV_XXX]!=0) || a[MNV_XXX]!=0) printf("Input to sqr not normed\n"); +#endif + /* Note 2*a[i] in loop below and extra addition */ + +#ifdef COMBA + +#ifdef UNWOUND + + /* Insert output of faster.c here */ + +#else + + + t=(dchunk)a[0]*a[0]; + c[0]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + + for (j=1; j<NLEN_XXX-1; ) + { + t=(dchunk)a[j]*a[0]; + for (i=1; i<(j+1)/2; i++) + { + t+=(dchunk)a[j-i]*a[i]; + } + t+=t; + t+=co; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + t=(dchunk)a[j]*a[0]; + for (i=1; i<(j+1)/2; i++) + { + t+=(dchunk)a[j-i]*a[i]; + } + t+=t; + t+=co; + t+=(dchunk)a[j/2]*a[j/2]; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + } + + for (j=NLEN_XXX-1+NLEN_XXX%2; j<DNLEN_XXX-3; ) + { + t=(dchunk)a[NLEN_XXX-1]*a[j-NLEN_XXX+1]; + for (i=j-NLEN_XXX+2; i<(j+1)/2; i++) + { + t+=(dchunk)a[j-i]*a[i]; + } + t+=t; + t+=co; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + t=(dchunk)a[NLEN_XXX-1]*a[j-NLEN_XXX+1]; + for (i=j-NLEN_XXX+2; i<(j+1)/2; i++) + { + t+=(dchunk)a[j-i]*a[i]; + } + t+=t; + t+=co; + t+=(dchunk)a[j/2]*a[j/2]; + c[j]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + j++; + } + + t=(dchunk)a[NLEN_XXX-2]*a[NLEN_XXX-1]; + t+=t; + t+=co; + c[DNLEN_XXX-3]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + + t=(dchunk)a[NLEN_XXX-1]*a[NLEN_XXX-1]+co; + c[DNLEN_XXX-2]=(chunk)t&BMASK_XXX; + co=t>>BASEBITS_XXX; + c[DNLEN_XXX-1]=(chunk)co; + + +#endif + +#else + chunk carry; + BIG_XXX_dzero(c); + for (i=0; i<NLEN_XXX; i++) + { + carry=0; + for (j=i+1; j<NLEN_XXX; j++) + carry=muladd_XXX(a[i],a[j],carry,&c[i+j]); + c[NLEN_XXX+i]=carry; + } + + for (i=0; i<DNLEN_XXX; i++) c[i]*=2; + + for (i=0; i<NLEN_XXX; i++) + c[2*i+1]+=muladd_XXX(a[i],a[i],0,&c[2*i]); + + BIG_XXX_dnorm(c); +#endif + + +#ifdef DEBUG_NORM + c[DMPV_XXX]=1; + c[DMNV_XXX]=0; +#endif + +} + +/* Montgomery reduction */ +void BIG_XXX_monty(BIG_XXX a,BIG_XXX md,chunk MC,DBIG_XXX d) +{ + int i,k; + +#ifdef dchunk + dchunk t,c,s; + dchunk dd[NLEN_XXX]; + chunk v[NLEN_XXX]; +#endif + +#ifdef COMBA + +#ifdef UNWOUND + + /* Insert output of faster.c here */ + +#else + + t=d[0]; + v[0]=((chunk)t*MC)&BMASK_XXX; + t+=(dchunk)v[0]*md[0]; + c=(t>>BASEBITS_XXX)+d[1]; + s=0; + + for (k=1; k<NLEN_XXX; k++) + { + t=c+s+(dchunk)v[0]*md[k]; + for (i=k-1; i>k/2; i--) t+=(dchunk)(v[k-i]-v[i])*(md[i]-md[k-i]); + v[k]=((chunk)t*MC)&BMASK_XXX; + t+=(dchunk)v[k]*md[0]; + c=(t>>BASEBITS_XXX)+d[k+1]; + dd[k]=(dchunk)v[k]*md[k]; + s+=dd[k]; + } + for (k=NLEN_XXX; k<2*NLEN_XXX-1; k++) + { + t=c+s; + for (i=NLEN_XXX-1; i>=1+k/2; i--) t+=(dchunk)(v[k-i]-v[i])*(md[i]-md[k-i]); + a[k-NLEN_XXX]=(chunk)t&BMASK_XXX; + c=(t>>BASEBITS_XXX)+d[k+1]; + s-=dd[k-NLEN_XXX+1]; + } + a[NLEN_XXX-1]=(chunk)c&BMASK_XXX; + +#endif + + + +#else + int j; + chunk m,carry; + for (i=0; i<NLEN_XXX; i++) + { + if (MC==-1) m=(-d[i])&BMASK_XXX; + else + { + if (MC==1) m=d[i]; + else m=(MC*d[i])&BMASK_XXX; + } + carry=0; + for (j=0; j<NLEN_XXX; j++) + carry=muladd_XXX(m,md[j],carry,&d[i+j]); + d[NLEN_XXX+i]+=carry; + } + BIG_XXX_sducopy(a,d); + BIG_XXX_norm(a); + +#endif + +#ifdef DEBUG_NORM + a[MPV_XXX]=1; + a[MNV_XXX]=0; +#endif +} + +/* General shift left of a by n bits */ +/* a MUST be normalised */ +/* SU= 32 */ +void BIG_XXX_shl(BIG_XXX a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + + a[NLEN_XXX-1]=((a[NLEN_XXX-1-m]<<n)); + if (NLEN_XXX>=m+2) a[NLEN_XXX-1]|=(a[NLEN_XXX-m-2]>>(BASEBITS_XXX-n)); + + for (i=NLEN_XXX-2; i>m; i--) + a[i]=((a[i-m]<<n)&BMASK_XXX)|(a[i-m-1]>>(BASEBITS_XXX-n)); + a[m]=(a[0]<<n)&BMASK_XXX; + for (i=0; i<m; i++) a[i]=0; + +} + +/* Fast shift left of a by n bits, where n less than a word, Return excess (but store it as well) */ +/* a MUST be normalised */ +/* SU= 16 */ +int BIG_XXX_fshl(BIG_XXX a,int n) +{ + int i; + + a[NLEN_XXX-1]=((a[NLEN_XXX-1]<<n))|(a[NLEN_XXX-2]>>(BASEBITS_XXX-n)); /* top word not masked */ + for (i=NLEN_XXX-2; i>0; i--) + a[i]=((a[i]<<n)&BMASK_XXX)|(a[i-1]>>(BASEBITS_XXX-n)); + a[0]=(a[0]<<n)&BMASK_XXX; + + return (int)(a[NLEN_XXX-1]>>((8*MODBYTES_XXX)%BASEBITS_XXX)); /* return excess - only used in ff.c */ +} + +/* double length left shift of a by k bits - k can be > BASEBITS , a MUST be normalised */ +/* SU= 32 */ +void BIG_XXX_dshl(DBIG_XXX a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + + a[DNLEN_XXX-1]=((a[DNLEN_XXX-1-m]<<n))|(a[DNLEN_XXX-m-2]>>(BASEBITS_XXX-n)); + + for (i=DNLEN_XXX-2; i>m; i--) + a[i]=((a[i-m]<<n)&BMASK_XXX)|(a[i-m-1]>>(BASEBITS_XXX-n)); + a[m]=(a[0]<<n)&BMASK_XXX; + for (i=0; i<m; i++) a[i]=0; + +} + +/* General shift rightof a by k bits */ +/* a MUST be normalised */ +/* SU= 32 */ +void BIG_XXX_shr(BIG_XXX a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + for (i=0; i<NLEN_XXX-m-1; i++) + a[i]=(a[m+i]>>n)|((a[m+i+1]<<(BASEBITS_XXX-n))&BMASK_XXX); + if (NLEN_XXX>m) a[NLEN_XXX-m-1]=a[NLEN_XXX-1]>>n; + for (i=NLEN_XXX-m; i<NLEN_XXX; i++) a[i]=0; + +} + +/* Faster shift right of a by k bits. Return shifted out part */ +/* a MUST be normalised */ +/* SU= 16 */ +int BIG_XXX_fshr(BIG_XXX a,int k) +{ + int i; + chunk r=a[0]&(((chunk)1<<k)-1); /* shifted out part */ + for (i=0; i<NLEN_XXX-1; i++) + a[i]=(a[i]>>k)|((a[i+1]<<(BASEBITS_XXX-k))&BMASK_XXX); + a[NLEN_XXX-1]=a[NLEN_XXX-1]>>k; + return (int)r; +} + +/* double length right shift of a by k bits - can be > BASEBITS */ +/* SU= 32 */ +void BIG_XXX_dshr(DBIG_XXX a,int k) +{ + int i; + int n=k%BASEBITS_XXX; + int m=k/BASEBITS_XXX; + for (i=0; i<DNLEN_XXX-m-1; i++) + a[i]=(a[m+i]>>n)|((a[m+i+1]<<(BASEBITS_XXX-n))&BMASK_XXX); + a[DNLEN_XXX-m-1]=a[DNLEN_XXX-1]>>n; + for (i=DNLEN_XXX-m; i<DNLEN_XXX; i++ ) a[i]=0; +} + +/* Split DBIG d into two BIGs t|b. Split happens at n bits, where n falls into NLEN word */ +/* d MUST be normalised */ +/* SU= 24 */ +chunk BIG_XXX_split(BIG_XXX t,BIG_XXX b,DBIG_XXX d,int n) +{ + int i; + chunk nw,carry=0; + int m=n%BASEBITS_XXX; + + if (m==0) + { + for (i=0; i<NLEN_XXX; i++) b[i]=d[i]; + if (t!=b) + { + for (i=NLEN_XXX; i<2*NLEN_XXX; i++) t[i-NLEN_XXX]=d[i]; + carry=t[NLEN_XXX-1]>>BASEBITS_XXX; + t[NLEN_XXX-1]=t[NLEN_XXX-1]&BMASK_XXX; /* top word normalized */ + } + return carry; + } + + for (i=0; i<NLEN_XXX-1; i++) b[i]=d[i]; + + b[NLEN_XXX-1]=d[NLEN_XXX-1]&(((chunk)1<<m)-1); + + if (t!=b) + { + carry=(d[DNLEN_XXX-1]<<(BASEBITS_XXX-m)); + for (i=DNLEN_XXX-2; i>=NLEN_XXX-1; i--) + { + nw=(d[i]>>m)|carry; + carry=(d[i]<<(BASEBITS_XXX-m))&BMASK_XXX; + t[i-NLEN_XXX+1]=nw; + } + } +#ifdef DEBUG_NORM + t[MPV_XXX]=1; + t[MNV_XXX]=0; + b[MPV_XXX]=1; + b[MNV_XXX]=0; +#endif + return carry; +} + +/* you gotta keep the sign of carry! Look - no branching! */ +/* Note that sign bit is needed to disambiguate between +ve and -ve values */ +/* normalise BIG - force all digits < 2^BASEBITS */ +chunk BIG_XXX_norm(BIG_XXX a) +{ + int i; + chunk d,carry=0; + for (i=0; i<NLEN_XXX-1; i++) + { + d=a[i]+carry; + a[i]=d&BMASK_XXX; + carry=d>>BASEBITS_XXX; + } + a[NLEN_XXX-1]=(a[NLEN_XXX-1]+carry); + +#ifdef DEBUG_NORM + a[MPV_XXX]=1; + a[MNV_XXX]=0; +#endif + return (a[NLEN_XXX-1]>>((8*MODBYTES_XXX)%BASEBITS_XXX)); /* only used in ff.c */ +} + +void BIG_XXX_dnorm(DBIG_XXX a) +{ + int i; + chunk d,carry=0; + for (i=0; i<DNLEN_XXX-1; i++) + { + d=a[i]+carry; + a[i]=d&BMASK_XXX; + carry=d>>BASEBITS_XXX; + } + a[DNLEN_XXX-1]=(a[DNLEN_XXX-1]+carry); +#ifdef DEBUG_NORM + a[DMPV_XXX]=1; + a[DMNV_XXX]=0; +#endif +} + +/* Compare a and b. Return 1 for a>b, -1 for a<b, 0 for a==b */ +/* a and b MUST be normalised before call */ +int BIG_XXX_comp(BIG_XXX a,BIG_XXX b) +{ + int i; + for (i=NLEN_XXX-1; i>=0; i--) + { + if (a[i]==b[i]) continue; + if (a[i]>b[i]) return 1; + else return -1; + } + return 0; +} + +int BIG_XXX_dcomp(DBIG_XXX a,DBIG_XXX b) +{ + int i; + for (i=DNLEN_XXX-1; i>=0; i--) + { + if (a[i]==b[i]) continue; + if (a[i]>b[i]) return 1; + else return -1; + } + return 0; +} + +/* return number of bits in a */ +/* SU= 8 */ +int BIG_XXX_nbits(BIG_XXX a) +{ + int bts,k=NLEN_XXX-1; + chunk c; + BIG_XXX_norm(a); + while (k>=0 && a[k]==0) k--; + if (k<0) return 0; + bts=BASEBITS_XXX*k; + c=a[k]; + while (c!=0) + { + c/=2; + bts++; + } + return bts; +} + +/* SU= 8, Calculate number of bits in a DBIG - output normalised */ +int BIG_XXX_dnbits(DBIG_XXX a) +{ + int bts,k=DNLEN_XXX-1; + chunk c; + BIG_XXX_dnorm(a); + while (k>=0 && a[k]==0) k--; + if (k<0) return 0; + bts=BASEBITS_XXX*k; + c=a[k]; + while (c!=0) + { + c/=2; + bts++; + } + return bts; +} + + +/* Set b=b mod c */ +/* SU= 16 */ +void BIG_XXX_mod(BIG_XXX b,BIG_XXX c) +{ + int k=0; + BIG_XXX r; /**/ + + BIG_XXX_norm(b); + if (BIG_XXX_comp(b,c)<0) + return; + do + { + BIG_XXX_fshl(c,1); + k++; + } + while (BIG_XXX_comp(b,c)>=0); + + while (k>0) + { + BIG_XXX_fshr(c,1); + + // constant time... + BIG_XXX_sub(r,b,c); + BIG_XXX_norm(r); + BIG_XXX_cmove(b,r,1-((r[NLEN_XXX-1]>>(CHUNK-1))&1)); + k--; + } +} + +/* Set a=b mod c, b is destroyed. Slow but rarely used. */ +/* SU= 96 */ +void BIG_XXX_dmod(BIG_XXX a,DBIG_XXX b,BIG_XXX c) +{ + int k=0; + DBIG_XXX m,r; + BIG_XXX_dnorm(b); + BIG_XXX_dscopy(m,c); + + if (BIG_XXX_dcomp(b,m)<0) + { + BIG_XXX_sdcopy(a,b); + return; + } + + do + { + BIG_XXX_dshl(m,1); + k++; + } + while (BIG_XXX_dcomp(b,m)>=0); + + while (k>0) + { + BIG_XXX_dshr(m,1); + // constant time... + BIG_XXX_dsub(r,b,m); + BIG_XXX_dnorm(r); + BIG_XXX_dcmove(b,r,1-((r[DNLEN_XXX-1]>>(CHUNK-1))&1)); + + k--; + } + BIG_XXX_sdcopy(a,b); +} + +/* Set a=b/c, b is destroyed. Slow but rarely used. */ +/* SU= 136 */ +void BIG_XXX_ddiv(BIG_XXX a,DBIG_XXX b,BIG_XXX c) +{ + int d,k=0; + DBIG_XXX m,dr; + BIG_XXX e,r; + BIG_XXX_dnorm(b); + BIG_XXX_dscopy(m,c); + + BIG_XXX_zero(a); + BIG_XXX_zero(e); + BIG_XXX_inc(e,1); + + while (BIG_XXX_dcomp(b,m)>=0) + { + BIG_XXX_fshl(e,1); + BIG_XXX_dshl(m,1); + k++; + } + + while (k>0) + { + BIG_XXX_dshr(m,1); + BIG_XXX_fshr(e,1); + + BIG_XXX_dsub(dr,b,m); + BIG_XXX_dnorm(dr); + d=1-((dr[DNLEN_XXX-1]>>(CHUNK-1))&1); + BIG_XXX_dcmove(b,dr,d); + + BIG_XXX_add(r,a,e); + BIG_XXX_norm(r); + BIG_XXX_cmove(a,r,d); + + k--; + } +} + +/* SU= 136 */ + +void BIG_XXX_sdiv(BIG_XXX a,BIG_XXX c) +{ + int d,k=0; + BIG_XXX m,e,b,r; + BIG_XXX_norm(a); + BIG_XXX_copy(b,a); + BIG_XXX_copy(m,c); + + BIG_XXX_zero(a); + BIG_XXX_zero(e); + BIG_XXX_inc(e,1); + + while (BIG_XXX_comp(b,m)>=0) + { + BIG_XXX_fshl(e,1); + BIG_XXX_fshl(m,1); + k++; + } + + while (k>0) + { + BIG_XXX_fshr(m,1); + BIG_XXX_fshr(e,1); + + BIG_XXX_sub(r,b,m); + BIG_XXX_norm(r); + d=1-((r[NLEN_XXX-1]>>(CHUNK-1))&1); + BIG_XXX_cmove(b,r,d); + + BIG_XXX_add(r,a,e); + BIG_XXX_norm(r); + BIG_XXX_cmove(a,r,d); + k--; + } +} + +/* return LSB of a */ +int BIG_XXX_parity(BIG_XXX a) +{ + return a[0]%2; +} + +/* return n-th bit of a */ +/* SU= 16 */ +int BIG_XXX_bit(BIG_XXX a,int n) +{ + if (a[n/BASEBITS_XXX]&((chunk)1<<(n%BASEBITS_XXX))) return 1; + else return 0; +} + +/* return last n bits of a, where n is small < BASEBITS */ +/* SU= 16 */ +int BIG_XXX_lastbits(BIG_XXX a,int n) +{ + int msk=(1<<n)-1; + BIG_XXX_norm(a); + return ((int)a[0])&msk; +} + +/* get 8*MODBYTES size random number */ +void BIG_XXX_random(BIG_XXX m,csprng *rng) +{ + int i,b,j=0,r=0; + int len=8*MODBYTES_XXX; + + BIG_XXX_zero(m); + /* generate random BIG */ + for (i=0; i<len; i++) + { + if (j==0) r=RAND_byte(rng); + else r>>=1; + b=r&1; + BIG_XXX_shl(m,1); + m[0]+=b; + j++; + j&=7; + } + +#ifdef DEBUG_NORM + m[MPV_XXX]=1; + m[MNV_XXX]=0; +#endif +} + +/* get random BIG from rng, modulo q. Done one bit at a time, so its portable */ +void BIG_XXX_randomnum(BIG_XXX m,BIG_XXX q,csprng *rng) +{ + int i,b,j=0,r=0; + DBIG_XXX d; + BIG_XXX_dzero(d); + /* generate random DBIG */ + for (i=0; i<2*BIG_XXX_nbits(q); i++) + { + if (j==0) r=RAND_byte(rng); + else r>>=1; + b=r&1; + BIG_XXX_dshl(d,1); + d[0]+=b; + j++; + j&=7; + } + /* reduce modulo a BIG. Removes bias */ + BIG_XXX_dmod(m,d,q); +#ifdef DEBUG_NORM + m[MPV_XXX]=1; + m[MNV_XXX]=0; +#endif +} + +/* Set r=a*b mod m */ +/* SU= 96 */ +void BIG_XXX_modmul(BIG_XXX r,BIG_XXX a,BIG_XXX b,BIG_XXX m) +{ + DBIG_XXX d; + BIG_XXX_mod(a,m); + BIG_XXX_mod(b,m); + + BIG_XXX_mul(d,a,b); + BIG_XXX_dmod(r,d,m); +} + +/* Set a=a*a mod m */ +/* SU= 88 */ +void BIG_XXX_modsqr(BIG_XXX r,BIG_XXX a,BIG_XXX m) +{ + DBIG_XXX d; + BIG_XXX_mod(a,m); + BIG_XXX_sqr(d,a); + BIG_XXX_dmod(r,d,m); +} + +/* Set r=-a mod m */ +/* SU= 16 */ +void BIG_XXX_modneg(BIG_XXX r,BIG_XXX a,BIG_XXX m) +{ + BIG_XXX_mod(a,m); + BIG_XXX_sub(r,m,a); +} + +/* Set a=a/b mod m */ +/* SU= 136 */ +void BIG_XXX_moddiv(BIG_XXX r,BIG_XXX a,BIG_XXX b,BIG_XXX m) +{ + DBIG_XXX d; + BIG_XXX z; + BIG_XXX_mod(a,m); + BIG_XXX_invmodp(z,b,m); + + BIG_XXX_mul(d,a,z); + BIG_XXX_dmod(r,d,m); +} + +/* Get jacobi Symbol (a/p). Returns 0, 1 or -1 */ +/* SU= 216 */ +int BIG_XXX_jacobi(BIG_XXX a,BIG_XXX p) +{ + int n8,k,m=0; + BIG_XXX t,x,n,zilch,one; + BIG_XXX_one(one); + BIG_XXX_zero(zilch); + if (BIG_XXX_parity(p)==0 || BIG_XXX_comp(a,zilch)==0 || BIG_XXX_comp(p,one)<=0) return 0; + BIG_XXX_norm(a); + BIG_XXX_copy(x,a); + BIG_XXX_copy(n,p); + BIG_XXX_mod(x,p); + + while (BIG_XXX_comp(n,one)>0) + { + if (BIG_XXX_comp(x,zilch)==0) return 0; + n8=BIG_XXX_lastbits(n,3); + k=0; + while (BIG_XXX_parity(x)==0) + { + k++; + BIG_XXX_shr(x,1); + } + if (k%2==1) m+=(n8*n8-1)/8; + m+=(n8-1)*(BIG_XXX_lastbits(x,2)-1)/4; + BIG_XXX_copy(t,n); + + BIG_XXX_mod(t,x); + BIG_XXX_copy(n,x); + BIG_XXX_copy(x,t); + m%=2; + + } + if (m==0) return 1; + else return -1; +} + +/* Set r=1/a mod p. Binary method */ +/* SU= 240 */ +void BIG_XXX_invmodp(BIG_XXX r,BIG_XXX a,BIG_XXX p) +{ + BIG_XXX u,v,x1,x2,t,one; + BIG_XXX_mod(a,p); + BIG_XXX_copy(u,a); + BIG_XXX_copy(v,p); + BIG_XXX_one(one); + BIG_XXX_copy(x1,one); + BIG_XXX_zero(x2); + + while (BIG_XXX_comp(u,one)!=0 && BIG_XXX_comp(v,one)!=0) + { + while (BIG_XXX_parity(u)==0) + { + BIG_XXX_fshr(u,1); + if (BIG_XXX_parity(x1)!=0) + { + BIG_XXX_add(x1,p,x1); + BIG_XXX_norm(x1); + } + BIG_XXX_fshr(x1,1); + } + while (BIG_XXX_parity(v)==0) + { + BIG_XXX_fshr(v,1); + if (BIG_XXX_parity(x2)!=0) + { + BIG_XXX_add(x2,p,x2); + BIG_XXX_norm(x2); + } + BIG_XXX_fshr(x2,1); + } + if (BIG_XXX_comp(u,v)>=0) + { + BIG_XXX_sub(u,u,v); + BIG_XXX_norm(u); + if (BIG_XXX_comp(x1,x2)>=0) BIG_XXX_sub(x1,x1,x2); + else + { + BIG_XXX_sub(t,p,x2); + BIG_XXX_add(x1,x1,t); + } + BIG_XXX_norm(x1); + } + else + { + BIG_XXX_sub(v,v,u); + BIG_XXX_norm(v); + if (BIG_XXX_comp(x2,x1)>=0) BIG_XXX_sub(x2,x2,x1); + else + { + BIG_XXX_sub(t,p,x1); + BIG_XXX_add(x2,x2,t); + } + BIG_XXX_norm(x2); + } + } + if (BIG_XXX_comp(u,one)==0) + BIG_XXX_copy(r,x1); + else + BIG_XXX_copy(r,x2); +} + +/* set x = x mod 2^m */ +void BIG_XXX_mod2m(BIG_XXX x,int m) +{ + int i,wd,bt; + chunk msk; + BIG_XXX_norm(x); + wd=m/BASEBITS_XXX; + bt=m%BASEBITS_XXX; + msk=((chunk)1<<bt)-1; + x[wd]&=msk; + for (i=wd+1; i<NLEN_XXX; i++) x[i]=0; +} + +// new +/* Convert to DBIG number from byte array of given length */ +void BIG_XXX_dfromBytesLen(DBIG_XXX a,char *b,int s) +{ + int i,len=s; + BIG_XXX_dzero(a); + + for (i=0; i<len; i++) + { + BIG_XXX_dshl(a,8); + a[0]+=(int)(unsigned char)b[i]; + } +#ifdef DEBUG_NORM + a[DMPV_XXX]=1; + a[DMNV_XXX]=0; +#endif +}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto-c/blob/8d28d2c3/src/ecdh.c.in ---------------------------------------------------------------------- diff --git a/src/ecdh.c.in b/src/ecdh.c.in new file mode 100644 index 0000000..360fa85 --- /dev/null +++ b/src/ecdh.c.in @@ -0,0 +1,408 @@ +/* +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" + +/* 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 ECP_ZZZ_KEY_PAIR_GENERATE(csprng *RNG,octet* S,octet *W) +{ + BIG_XXX r,gx,s; + ECP_ZZZ G; + int res=0; + + ECP_ZZZ_generator(&G); + + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + if (RNG!=NULL) + { + BIG_XXX_randomnum(s,r,RNG); + } + else + { + BIG_XXX_fromBytes(s,S->val); + BIG_XXX_mod(s,r); + } + +#ifdef AES_S + BIG_XXX_mod2m(s,2*AES_S); +#endif + + ECP_ZZZ_mul(&G,s); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX gy; + ECP_ZZZ_get(gx,gy,&G); +#else + ECP_ZZZ_get(gx,&G); + +#endif + + S->len=EGS_ZZZ; + BIG_XXX_toBytes(S->val,s); + +#if CURVETYPE_ZZZ!=MONTGOMERY + W->len=2*EFS_ZZZ+1; + W->val[0]=4; + BIG_XXX_toBytes(&(W->val[1]),gx); + BIG_XXX_toBytes(&(W->val[EFS_ZZZ+1]),gy); +#else + W->len=EFS_ZZZ+1; + W->val[0]=2; + BIG_XXX_toBytes(&(W->val[1]),gx); +#endif + + return res; +} + +/* validate public key. Set full=true for fuller check */ +int ECP_ZZZ_PUBLIC_KEY_VALIDATE(octet *W) +{ + BIG_XXX q,r,wx,k; + ECP_ZZZ WP; + int valid,nb; + int res=0; + + BIG_XXX_rcopy(q,Modulus_YYY); + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + + BIG_XXX_fromBytes(wx,&(W->val[1])); + if (BIG_XXX_comp(wx,q)>=0) res=ECDH_INVALID_PUBLIC_KEY; +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX wy; + BIG_XXX_fromBytes(wy,&(W->val[EFS_ZZZ+1])); + if (BIG_XXX_comp(wy,q)>=0) res=ECDH_INVALID_PUBLIC_KEY; +#endif + if (res==0) + { + +#if CURVETYPE_ZZZ!=MONTGOMERY + valid=ECP_ZZZ_set(&WP,wx,wy); +#else + valid=ECP_ZZZ_set(&WP,wx); +#endif + if (!valid || ECP_ZZZ_isinf(&WP)) res=ECDH_INVALID_PUBLIC_KEY; + if (res==0 ) + { + /* Check point is not in wrong group */ + nb=BIG_XXX_nbits(q); + BIG_XXX_one(k); + BIG_XXX_shl(k,(nb+4)/2); + BIG_XXX_add(k,q,k); + BIG_XXX_sdiv(k,r); /* get co-factor */ + + while (BIG_XXX_parity(k)==0) + { + ECP_ZZZ_dbl(&WP); + BIG_XXX_fshr(k,1); + } + + if (!BIG_XXX_isunity(k)) ECP_ZZZ_mul(&WP,k); + if (ECP_ZZZ_isinf(&WP)) res=ECDH_INVALID_PUBLIC_KEY; + } + } + + return res; +} + +/* IEEE-1363 Diffie-Hellman online calculation Z=S.WD */ +int ECP_ZZZ_SVDP_DH(octet *S,octet *WD,octet *Z) +{ + BIG_XXX r,s,wx; + int valid; + ECP_ZZZ W; + int res=0; + + BIG_XXX_fromBytes(s,S->val); + + BIG_XXX_fromBytes(wx,&(WD->val[1])); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX wy; + BIG_XXX_fromBytes(wy,&(WD->val[EFS_ZZZ+1])); + valid=ECP_ZZZ_set(&W,wx,wy); +#else + valid=ECP_ZZZ_set(&W,wx); +#endif + if (!valid) res=ECDH_ERROR; + if (res==0) + { + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + BIG_XXX_mod(s,r); + + ECP_ZZZ_mul(&W,s); + if (ECP_ZZZ_isinf(&W)) res=ECDH_ERROR; + else + { +#if CURVETYPE_ZZZ!=MONTGOMERY + ECP_ZZZ_get(wx,wx,&W); +#else + ECP_ZZZ_get(wx,&W); +#endif + Z->len=MODBYTES_XXX; + BIG_XXX_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 ECP_ZZZ_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_XXX r,s,f,c,d,u,vx,w; + ECP_ZZZ G,V; + + ehashit(sha,F,-1,NULL,&H,sha); + + ECP_ZZZ_generator(&G); + + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + + BIG_XXX_fromBytes(s,S->val); + + int hlen=H.len; + if (H.len>MODBYTES_XXX) hlen=MODBYTES_XXX; + BIG_XXX_fromBytesLen(f,H.val,hlen); + + if (RNG!=NULL) + { + do + { + + BIG_XXX_randomnum(u,r,RNG); + BIG_XXX_randomnum(w,r,RNG); /* randomize calculation */ + +#ifdef AES_S + BIG_XXX_mod2m(u,2*AES_S); +#endif + ECP_ZZZ_copy(&V,&G); + ECP_ZZZ_mul(&V,u); + + ECP_ZZZ_get(vx,vx,&V); + + BIG_XXX_copy(c,vx); + BIG_XXX_mod(c,r); + if (BIG_XXX_iszilch(c)) continue; + + BIG_XXX_modmul(u,u,w,r); + + BIG_XXX_invmodp(u,u,r); + BIG_XXX_modmul(d,s,c,r); + + BIG_XXX_add(d,f,d); + + BIG_XXX_modmul(d,d,w,r); + + BIG_XXX_modmul(d,u,d,r); + } + while (BIG_XXX_iszilch(d)); + } + else + { + BIG_XXX_fromBytes(u,K->val); + BIG_XXX_mod(u,r); + +#ifdef AES_S + BIG_XXX_mod2m(u,2*AES_S); +#endif + ECP_ZZZ_copy(&V,&G); + ECP_ZZZ_mul(&V,u); + + ECP_ZZZ_get(vx,vx,&V); + + BIG_XXX_copy(c,vx); + BIG_XXX_mod(c,r); + if (BIG_XXX_iszilch(c)) return ECDH_ERROR; + + + BIG_XXX_invmodp(u,u,r); + BIG_XXX_modmul(d,s,c,r); + + BIG_XXX_add(d,f,d); + + BIG_XXX_modmul(d,u,d,r); + if (BIG_XXX_iszilch(d)) return ECDH_ERROR; + } + + C->len=D->len=EGS_ZZZ; + + BIG_XXX_toBytes(C->val,c); + BIG_XXX_toBytes(D->val,d); + + return 0; +} + +/* IEEE1363 ECDSA Signature Verification. Signature C and D on F is verified using public key W */ +int ECP_ZZZ_VP_DSA(int sha,octet *W,octet *F, octet *C,octet *D) +{ + char h[128]; + octet H= {0,sizeof(h),h}; + + BIG_XXX r,wx,wy,f,c,d,h2; + int res=0; + ECP_ZZZ G,WP; + int valid; + + ehashit(sha,F,-1,NULL,&H,sha); + + ECP_ZZZ_generator(&G); + + BIG_XXX_rcopy(r,CURVE_Order_ZZZ); + + OCT_shl(C,C->len-MODBYTES_XXX); + OCT_shl(D,D->len-MODBYTES_XXX); + + BIG_XXX_fromBytes(c,C->val); + BIG_XXX_fromBytes(d,D->val); + + int hlen=H.len; + if (hlen>MODBYTES_XXX) hlen=MODBYTES_XXX; + + BIG_XXX_fromBytesLen(f,H.val,hlen); + + if (BIG_XXX_iszilch(c) || BIG_XXX_comp(c,r)>=0 || BIG_XXX_iszilch(d) || BIG_XXX_comp(d,r)>=0) + res=ECDH_INVALID; + + if (res==0) + { + BIG_XXX_invmodp(d,d,r); + BIG_XXX_modmul(f,f,d,r); + BIG_XXX_modmul(h2,c,d,r); + + BIG_XXX_fromBytes(wx,&(W->val[1])); + BIG_XXX_fromBytes(wy,&(W->val[EFS_ZZZ+1])); + + valid=ECP_ZZZ_set(&WP,wx,wy); + + if (!valid) res=ECDH_ERROR; + else + { + ECP_ZZZ_mul2(&WP,&G,h2,f); + + if (ECP_ZZZ_isinf(&WP)) res=ECDH_INVALID; + else + { + ECP_ZZZ_get(d,d,&WP); + BIG_XXX_mod(d,r); + if (BIG_XXX_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 ECP_ZZZ_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_ZZZ_KEY_PAIR_GENERATE(RNG,&U,V)!=0) return; + if (ECP_ZZZ_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 ECP_ZZZ_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_ZZZ_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_comp(T,&TAG)) return 0; + + return 1; + +} + +#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto-c/blob/8d28d2c3/src/ecdh_support.c ---------------------------------------------------------------------- diff --git a/src/ecdh_support.c b/src/ecdh_support.c new file mode 100644 index 0000000..0693c16 --- /dev/null +++ b/src/ecdh_support.c @@ -0,0 +1,329 @@ +/* +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" + +#define ROUNDUP(a,b) ((a)-1)/(b)+1 + +/* general purpose hash function w=hash(p|n|x|y) */ +/* pad or truncate ouput to length pad if pad!=0 */ +void 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 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 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) 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; +} + +/* Key Derivation Functions */ +/* Input octet z */ +/* Output key of length olen */ +void 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 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 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 */ + amcl_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 AES_CBC_IV0_DECRYPT(octet *k,octet *c,octet *m) +{ + /* padding is removed */ + amcl_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-c/blob/8d28d2c3/src/ecp.c.in ---------------------------------------------------------------------- diff --git a/src/ecp.c.in b/src/ecp.c.in new file mode 100644 index 0000000..f042cbb --- /dev/null +++ b/src/ecp.c.in @@ -0,0 +1,1265 @@ +/* +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 +} + +/* Set P=(x,y) */ + +#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) +{ + if (ECP_ZZZ_isinf(P)) return -1; + ECP_ZZZ_affine(P); + FP_YYY_redc(x,&(P->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 ECP_ZZZ_get(BIG_XXX x,BIG_XXX y,ECP_ZZZ *P) +{ + int s; + + if (ECP_ZZZ_isinf(P)) return -1; + + ECP_ZZZ_affine(P); + + FP_YYY_redc(y,&(P->y)); + s=BIG_XXX_parity(y); + + FP_YYY_redc(x,&(P->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); + ECP_ZZZ_affine(P); + return; + } + if (cf==8) + { + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + ECP_ZZZ_dbl(P); + ECP_ZZZ_affine(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; + 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) +{ +#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); + W->len=2*MODBYTES_XXX+1; + W->val[0]=4; + 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; + BIG_XXX_fromBytes(x,&(W->val[1])); + BIG_XXX_fromBytes(y,&(W->val[MODBYTES_XXX+1])); + if (ECP_ZZZ_set(P,x,y)) 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_neg(Q); + ECP_ZZZ_add(P,Q); + ECP_ZZZ_neg(Q); +} + +#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_affine(P); + + 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); + } + + /* 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; + + ECP_ZZZ_affine(P); + ECP_ZZZ_affine(Q); + + 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; + BIG_XXX_rcopy(x,CURVE_Gx_ZZZ); +#if CURVETYPE_ZZZ!=MONTGOMERY + BIG_XXX y; + 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); + printf("r= "); + BIG_XXX_output(r); + printf("\n"); + + ECP_ZZZ_copy(&P,&G); + + ECP_ZZZ_mul(&P,r); + + ECP_ZZZ_output(&P); + 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
