You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@milagro.apache.org by br...@apache.org on 2018/11/08 00:13:00 UTC
[40/51] [partial] incubator-milagro-crypto-c git commit: update code
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