http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/big.c ---------------------------------------------------------------------- diff --git a/c/big.c b/c/big.c deleted file mode 100755 index b26abc2..0000000 --- a/c/big.c +++ /dev/null @@ -1,1210 +0,0 @@ -/* -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 "amcl.h" - -/* Calculates x*y+c+*r */ - -#ifdef dchunk - -/* Method required to calculate x*y+c+r, bottom half in r, top half returned */ -chunk muladd(chunk x,chunk y,chunk c,chunk *r) -{ - dchunk prod=(dchunk)x*y+c+*r; - *r=(chunk)prod&MASK; - return (chunk)(prod>>BASEBITS); -} - -#else - -/* No integer type available that can store double the wordlength */ -/* accumulate partial products */ - -chunk muladd(chunk x,chunk y,chunk c,chunk *r) -{ - chunk x0,x1,y0,y1; - chunk bot,top,mid,carry; - x0=x&HMASK; - x1=(x>>HBITS); - y0=y&HMASK; - y1=(y>>HBITS); - bot=x0*y0; - top=x1*y1; - mid=x0*y1+x1*y0; - x0=mid&HMASK1; - x1=(mid>>HBITS1); - bot+=x0<<HBITS; bot+=*r; bot+=c; - -#if HDIFF==1 - bot+=(top&HDIFF)<<(BASEBITS-1); - top>>=HDIFF; -#endif - - top+=x1; - carry=bot>>BASEBITS; - bot&=MASK; - top+=carry; - - *r=bot; - return top; -} - -#endif - -/* test a=0? */ -int BIG_iszilch(BIG a) -{ - int i; - for (i=0;i<NLEN;i++) - if (a[i]!=0) return 0; - return 1; -} - -/* test a=0? */ -int BIG_diszilch(DBIG a) -{ - int i; - for (i=0;i<DNLEN;i++) - if (a[i]!=0) return 0; - return 1; -} - -/* SU= 56 */ -/* output a */ -void BIG_output(BIG a) -{ - BIG b; - int i,len; - len=BIG_nbits(a); - if (len%4==0) len/=4; - else {len/=4; len++;} - if (len<MODBYTES*2) len=MODBYTES*2; - - for (i=len-1;i>=0;i--) - { - BIG_copy(b,a); - BIG_shr(b,i*4); - printf("%01x",(unsigned int) b[0]&15); - } -} - -/* SU= 16 */ -void BIG_rawoutput(BIG a) -{ - int i; - printf("("); - for (i=0;i<NLEN-1;i++) - printf("%llx,",(long long unsigned int) a[i]); - printf("%llx)",(long long unsigned int) a[NLEN-1]); -} - -/* Swap a and b if d=1 */ -void BIG_cswap(BIG a,BIG b,int d) -{ - int i; - chunk t,c=d; - c=~(c-1); -#ifdef DEBUG_NORM - for (i=0;i<=NLEN;i++) -#else - for (i=0;i<NLEN;i++) -#endif - { - t=c&(a[i]^b[i]); - a[i]^=t; - b[i]^=t; - } -} - -/* Move b to a if d=1 */ -void BIG_cmove(BIG f,BIG g,int d) -{ - int i; - chunk b=(chunk)-d; -#ifdef DEBUG_NORM - for (i=0;i<=NLEN;i++) -#else - for (i=0;i<NLEN;i++) -#endif - { - f[i]^=(f[i]^g[i])&b; - } -} - -/* convert BIG to/from bytes */ -/* SU= 64 */ -void BIG_toBytes(char *b,BIG a) -{ - int i; - BIG c; - BIG_norm(a); - BIG_copy(c,a); - for (i=MODBYTES-1;i>=0;i--) - { - b[i]=c[0]&0xff; - BIG_fshr(c,8); - } -} - -/* SU= 16 */ -void BIG_fromBytes(BIG a,char *b) -{ - int i; - BIG_zero(a); - for (i=0;i<MODBYTES;i++) - { - BIG_fshl(a,8); a[0]+=(int)(unsigned char)b[i]; - //BIG_inc(a,(int)(unsigned char)b[i]); BIG_norm(a); - } -#ifdef DEBUG_NORM - a[NLEN]=0; -#endif -} - -/* SU= 88 */ -void BIG_doutput(DBIG a) -{ - DBIG b; - int i,len; - BIG_dnorm(a); - len=BIG_dnbits(a); - if (len%4==0) len/=4; - else {len/=4; len++;} - - for (i=len-1;i>=0;i--) - { - BIG_dcopy(b,a); - BIG_dshr(b,i*4); - printf("%01x",(unsigned int) b[0]&15); - } -} - -/* Copy b=a */ -void BIG_copy(BIG b,BIG a) -{ - int i; - for (i=0;i<NLEN;i++) - b[i]=a[i]; -#ifdef DEBUG_NORM - b[NLEN]=a[NLEN]; -#endif -} - -/* Copy from ROM b=a */ -void BIG_rcopy(BIG b,const BIG a) -{ - int i; - for (i=0;i<NLEN;i++) - b[i]=a[i]; -#ifdef DEBUG_NORM - b[NLEN]=0; -#endif -} - -/* double length DBIG copy b=a */ -void BIG_dcopy(DBIG b,DBIG a) -{ - int i; - for (i=0;i<DNLEN;i++) - b[i]=a[i]; -#ifdef DEBUG_NORM - b[DNLEN]=a[DNLEN]; -#endif -} - -/* Copy BIG to bottom half of DBIG */ -void BIG_dscopy(DBIG b,BIG a) -{ - int i; - for (i=0;i<NLEN-1;i++) - b[i]=a[i]; - - b[NLEN-1]=a[NLEN-1]&MASK; /* top word normalized */ - b[NLEN]=a[NLEN-1]>>BASEBITS; - - for (i=NLEN+1;i<DNLEN;i++) b[i]=0; -#ifdef DEBUG_NORM - b[DNLEN]=a[NLEN]; -#endif -} - -/* Copy BIG to top half of DBIG */ -void BIG_dsucopy(DBIG b,BIG a) -{ - int i; - for (i=0;i<NLEN;i++) - b[i]=0; - for (i=NLEN;i<DNLEN;i++) - b[i]=a[i-NLEN]; -#ifdef DEBUG_NORM - b[DNLEN]=a[NLEN]; -#endif -} - -/* Copy bottom half of DBIG to BIG */ -void BIG_sdcopy(BIG b,DBIG a) -{ - int i; - for (i=0;i<NLEN;i++) - b[i]=a[i]; -#ifdef DEBUG_NORM - b[NLEN]=a[DNLEN]; -#endif -} - -/* Copy top half of DBIG to BIG */ -void BIG_sducopy(BIG b,DBIG a) -{ - int i; - for (i=0;i<NLEN;i++) - b[i]=a[i+NLEN]; -#ifdef DEBUG_NORM - b[NLEN]=a[DNLEN]; -#endif -} - -/* Set a=0 */ -void BIG_zero(BIG a) -{ - int i; - for (i=0;i<NLEN;i++) - a[i]=0; -#ifdef DEBUG_NORM - a[NLEN]=0; -#endif -} - -void BIG_dzero(DBIG a) -{ - int i; - for (i=0;i<DNLEN;i++) - a[i]=0; -#ifdef DEBUG_NORM - a[DNLEN]=0; -#endif -} - -/* set a=1 */ -void BIG_one(BIG a) -{ - int i; - a[0]=1; - for (i=1;i<NLEN;i++) - a[i]=0; -#ifdef DEBUG_NORM - a[NLEN]=0; -#endif -} - - - -/* Set c=a+b */ -/* SU= 8 */ -void BIG_add(BIG c,BIG a,BIG b) -{ - int i; - for (i=0;i<NLEN;i++) - c[i]=a[i]+b[i]; -#ifdef DEBUG_NORM - c[NLEN]=a[NLEN]+b[NLEN]+1; - if (c[NLEN]>=NEXCESS) printf("add problem - digit overflow %d\n",c[NLEN]); -#endif -} - -/* Set c=c+d */ -void BIG_inc(BIG c,int d) -{ - BIG_norm(c); - c[0]+=(chunk)d; -#ifdef DEBUG_NORM - c[NLEN]=1; -#endif -} - -/* Set c=a-b */ -/* SU= 8 */ -void BIG_sub(BIG c,BIG a,BIG b) -{ - int i; - for (i=0;i<NLEN;i++) - c[i]=a[i]-b[i]; -#ifdef DEBUG_NORM - c[NLEN]=a[NLEN]+b[NLEN]+1; - if (c[NLEN]>=NEXCESS) printf("sub problem - digit overflow %d\n",c[NLEN]); -#endif -} - -/* SU= 8 */ - -void BIG_dsub(DBIG c,DBIG a,DBIG b) -{ - int i; - for (i=0;i<DNLEN;i++) - c[i]=a[i]-b[i]; -#ifdef DEBUG_NORM - c[DNLEN]=a[DNLEN]+b[DNLEN]+1; - if (c[DNLEN]>=NEXCESS) printf("sub problem - digit overflow %d\n",c[DNLEN]); -#endif -} - - -/* Set c=c-1 */ -void BIG_dec(BIG c,int d) -{ - BIG_norm(c); - c[0]-=(chunk)d; -#ifdef DEBUG_NORM - c[NLEN]=1; -#endif -} - -/* multiplication r=a*c by c<=NEXCESS */ -void BIG_imul(BIG r,BIG a,int c) -{ - int i; - for (i=0;i<NLEN;i++) r[i]=a[i]*c; -#ifdef DEBUG_NORM - r[NLEN]=(a[NLEN]+1)*c-1; - if (r[NLEN]>=NEXCESS) printf("int mul problem - digit overflow %d\n",r[NLEN]); -#endif -} - -/* multiplication r=a*c by larger integer - c<=FEXCESS */ -/* SU= 24 */ -chunk BIG_pmul(BIG r,BIG a,int c) -{ - int i; - chunk ak,carry=0; - BIG_norm(a); - for (i=0;i<NLEN;i++) - { - ak=a[i]; - r[i]=0; - carry=muladd(ak,(chunk)c,carry,&r[i]); - } -#ifdef DEBUG_NORM - r[NLEN]=0; -#endif - return carry; -} - -/* r/=3 */ -/* SU= 16 */ -int BIG_div3(BIG r) -{ - int i; - chunk ak,base,carry=0; - BIG_norm(r); - base=((chunk)1<<BASEBITS); - for (i=NLEN-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_pxmul(DBIG c,BIG a,int b) -{ - int j; - chunk carry; - BIG_dzero(c); - carry=0; - for (j=0;j<NLEN;j++) - carry=muladd(a[j],(chunk)b,carry,&c[j]); - c[NLEN]=carry; -#ifdef DEBUG_NORM - c[DNLEN]=0; -#endif -} - -/* Set c=a*b */ -/* SU= 72 */ -void BIG_mul(DBIG c,BIG a,BIG b) -{ - int i,j; - chunk carry; -#ifdef dchunk - dchunk t,co; -#endif - - BIG_norm(a); /* needed here to prevent overflow from addition of partial products */ - BIG_norm(b); - -/* Faster to Combafy it.. Let the compiler unroll the loops! */ - -#ifdef COMBA - - t=(dchunk)a[0]*b[0]; - c[0]=(chunk)t&MASK; co=t>>BASEBITS; - t=(dchunk)a[1]*b[0]+(dchunk)a[0]*b[1]+co; - c[1]=(chunk)t&MASK; co=t>>BASEBITS; - - for (j=2;j<NLEN;j++) - { - t=co; for (i=0;i<=j;i++) t+=(dchunk)a[j-i]*b[i]; - c[j]=(chunk)t&MASK; co=t>>BASEBITS; - } - - for (j=NLEN;j<DNLEN-2;j++) - { - t=co; for (i=j-NLEN+1;i<NLEN;i++) t+=(dchunk)a[j-i]*b[i]; - c[j]=(chunk)t&MASK; co=t>>BASEBITS; - } - - t=(dchunk)a[NLEN-1]*b[NLEN-1]+co; - c[DNLEN-2]=(chunk)t&MASK; co=t>>BASEBITS; - c[DNLEN-1]=(chunk)co; -#else - BIG_dzero(c); - for (i=0;i<NLEN;i++) - { - carry=0; - for (j=0;j<NLEN;j++) - carry=muladd(a[i],b[j],carry,&c[i+j]); - c[NLEN+i]=carry; - } -#endif - -#ifdef DEBUG_NORM - c[DNLEN]=0; -#endif -} - -/* .. if you know the result will fit in a BIG, c must be distinct from a and b */ -/* SU= 40 */ -void BIG_smul(BIG c,BIG a,BIG b) -{ - int i,j; - chunk carry; - BIG_norm(a); - BIG_norm(b); - - BIG_zero(c); - for (i=0;i<NLEN;i++) - { - carry=0; - for (j=0;j<NLEN;j++) - if (i+j<NLEN) carry=muladd(a[i],b[j],carry,&c[i+j]); - } -#ifdef DEBUG_NORM - c[NLEN]=0; -#endif - -} - -/* Set c=a*a */ -/* SU= 80 */ -void BIG_sqr(DBIG c,BIG a) -{ - int i,j; - chunk carry; -#ifdef dchunk - dchunk t,co; -#endif - - BIG_norm(a); - -/* Note 2*a[i] in loop below and extra addition */ - -#ifdef COMBA - - t=(dchunk)a[0]*a[0]; - c[0]=(chunk)t&MASK; co=t>>BASEBITS; - t=(dchunk)a[1]*a[0]; t+=t; t+=co; - c[1]=(chunk)t&MASK; co=t>>BASEBITS; - -#if NLEN%2==1 - for (j=2;j<NLEN-1;j+=2) - { - 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&MASK; co=t>>BASEBITS; - t=(dchunk)a[j+1]*a[0]; for (i=1;i<(j+2)/2;i++) t+=(dchunk)a[j+1-i]*a[i]; t+=t; t+=co; - c[j+1]=(chunk)t&MASK; co=t>>BASEBITS; - } - j=NLEN-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; t+=(dchunk)a[j/2]*a[j/2]; - c[j]=(chunk)t&MASK; co=t>>BASEBITS; - -#else - for (j=2;j<NLEN;j+=2) - { - 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&MASK; co=t>>BASEBITS; - t=(dchunk)a[j+1]*a[0]; for (i=1;i<(j+2)/2;i++) t+=(dchunk)a[j+1-i]*a[i]; t+=t; t+=co; - c[j+1]=(chunk)t&MASK; co=t>>BASEBITS; - } - -#endif - -#if NLEN%2==1 - j=NLEN; - t=(dchunk)a[NLEN-1]*a[j-NLEN+1]; for (i=j-NLEN+2;i<(j+1)/2;i++) t+=(dchunk)a[j-i]*a[i]; t+=t; t+=co; - c[j]=(chunk)t&MASK; co=t>>BASEBITS; - for (j=NLEN+1;j<DNLEN-2;j+=2) - { - t=(dchunk)a[NLEN-1]*a[j-NLEN+1]; for (i=j-NLEN+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&MASK; co=t>>BASEBITS; - t=(dchunk)a[NLEN-1]*a[j-NLEN+2]; for (i=j-NLEN+3;i<(j+2)/2;i++) t+=(dchunk)a[j+1-i]*a[i]; t+=t; t+=co; - c[j+1]=(chunk)t&MASK; co=t>>BASEBITS; - } -#else - for (j=NLEN;j<DNLEN-2;j+=2) - { - t=(dchunk)a[NLEN-1]*a[j-NLEN+1]; for (i=j-NLEN+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&MASK; co=t>>BASEBITS; - t=(dchunk)a[NLEN-1]*a[j-NLEN+2]; for (i=j-NLEN+3;i<(j+2)/2;i++) t+=(dchunk)a[j+1-i]*a[i]; t+=t; t+=co; - c[j+1]=(chunk)t&MASK; co=t>>BASEBITS; - } - -#endif - - t=(dchunk)a[NLEN-1]*a[NLEN-1]+co; - c[DNLEN-2]=(chunk)t&MASK; co=t>>BASEBITS; - c[DNLEN-1]=(chunk)co; - -#else - BIG_dzero(c); - for (i=0;i<NLEN;i++) - { - carry=0; - for (j=i+1;j<NLEN;j++) - carry=muladd(a[i],a[j],carry,&c[i+j]); - c[NLEN+i]=carry; - } - - for (i=0;i<DNLEN;i++) c[i]*=2; - - for (i=0;i<NLEN;i++) - c[2*i+1]+=muladd(a[i],a[i],0,&c[2*i]); - - BIG_dnorm(c); -#endif - - -#ifdef DEBUG_NORM - c[DNLEN]=0; -#endif - -} - -/* General shift left of a by n bits */ -/* a MUST be normalised */ -/* SU= 32 */ -void BIG_shl(BIG a,int k) -{ - int i; - int n=k%BASEBITS; - int m=k/BASEBITS; - - a[NLEN-1]=((a[NLEN-1-m]<<n))|(a[NLEN-m-2]>>(BASEBITS-n)); - - for (i=NLEN-2;i>m;i--) - a[i]=((a[i-m]<<n)&MASK)|(a[i-m-1]>>(BASEBITS-n)); - a[m]=(a[0]<<n)&MASK; - 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 */ -chunk BIG_fshl(BIG a,int n) -{ - int i; - - a[NLEN-1]=((a[NLEN-1]<<n))|(a[NLEN-2]>>(BASEBITS-n)); /* top word not masked */ - for (i=NLEN-2;i>0;i--) - a[i]=((a[i]<<n)&MASK)|(a[i-1]>>(BASEBITS-n)); - a[0]=(a[0]<<n)&MASK; - - return (a[NLEN-1]>>((8*MODBYTES)%BASEBITS)); /* 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_dshl(DBIG a,int k) -{ - int i; - int n=k%BASEBITS; - int m=k/BASEBITS; - - a[DNLEN-1]=((a[DNLEN-1-m]<<n))|(a[DNLEN-m-2]>>(BASEBITS-n)); - - for (i=DNLEN-2;i>m;i--) - a[i]=((a[i-m]<<n)&MASK)|(a[i-m-1]>>(BASEBITS-n)); - a[m]=(a[0]<<n)&MASK; - for (i=0;i<m;i++) a[i]=0; - -} - -/* General shift rightof a by k bits */ -/* a MUST be normalised */ -/* SU= 32 */ -void BIG_shr(BIG a,int k) -{ - int i; - int n=k%BASEBITS; - int m=k/BASEBITS; - for (i=0;i<NLEN-m-1;i++) - a[i]=(a[m+i]>>n)|((a[m+i+1]<<(BASEBITS-n))&MASK); - a[NLEN-m-1]=a[NLEN-1]>>n; - for (i=NLEN-m;i<NLEN;i++) a[i]=0; - -} - -/* Faster shift right of a by k bits. Return shifted out part */ -/* a MUST be normalised */ -/* SU= 16 */ -chunk BIG_fshr(BIG a,int k) -{ - int i; - chunk r=a[0]&(((chunk)1<<k)-1); /* shifted out part */ - for (i=0;i<NLEN-1;i++) - a[i]=(a[i]>>k)|((a[i+1]<<(BASEBITS-k))&MASK); - a[NLEN-1]=a[NLEN-1]>>k; - return r; -} - -/* double length right shift of a by k bits - can be > BASEBITS */ -/* SU= 32 */ -void BIG_dshr(DBIG a,int k) -{ - int i; - int n=k%BASEBITS; - int m=k/BASEBITS; - for (i=0;i<DNLEN-m-1;i++) - a[i]=(a[m+i]>>n)|((a[m+i+1]<<(BASEBITS-n))&MASK); - a[DNLEN-m-1]=a[DNLEN-1]>>n; - for (i=DNLEN-m;i<DNLEN;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 */ -void BIG_split(BIG t,BIG b,DBIG d,int n) -{ - int i; - chunk nw,carry; - int m=n%BASEBITS; -// BIG_dnorm(d); - - for (i=0;i<NLEN-1;i++) b[i]=d[i]; - - b[NLEN-1]=d[NLEN-1]&(((chunk)1<<m)-1); - - if (t!=b) - { - carry=(d[DNLEN-1]<<(BASEBITS-m)); - for (i=DNLEN-2;i>=NLEN-1;i--) - { - nw=(d[i]>>m)|carry; - carry=(d[i]<<(BASEBITS-m))&MASK; - t[i-NLEN+1]=nw; - } - } -#ifdef DEBUG_NORM - t[NLEN]=0; - b[NLEN]=0; -#endif - -} - -/* 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_norm(BIG a) -{ - int i; - chunk d,carry=0; - for (i=0;i<NLEN-1;i++) - { - d=a[i]+carry; - a[i]=d&MASK; - carry=d>>BASEBITS; - } - a[NLEN-1]=(a[NLEN-1]+carry); - -#ifdef DEBUG_NORM - a[NLEN]=0; -#endif - return (a[NLEN-1]>>((8*MODBYTES)%BASEBITS)); /* only used in ff.c */ -} - -void BIG_dnorm(DBIG a) -{ - int i; - chunk d,carry=0;; - for (i=0;i<DNLEN-1;i++) - { - d=a[i]+carry; - a[i]=d&MASK; - carry=d>>BASEBITS; - } - a[DNLEN-1]=(a[DNLEN-1]+carry); -#ifdef DEBUG_NORM - a[DNLEN]=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_comp(BIG a,BIG b) -{ - int i; - for (i=NLEN-1;i>=0;i--) - { - if (a[i]==b[i]) continue; - if (a[i]>b[i]) return 1; - else return -1; - } - return 0; -} - -int BIG_dcomp(DBIG a,DBIG b) -{ - int i; - for (i=DNLEN-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_nbits(BIG a) -{ - int bts,k=NLEN-1; - chunk c; - BIG_norm(a); - while (k>=0 && a[k]==0) k--; - if (k<0) return 0; - bts=BASEBITS*k; - c=a[k]; - while (c!=0) {c/=2; bts++;} - return bts; -} - -/* SU= 8 */ -int BIG_dnbits(BIG a) -{ - int bts,k=DNLEN-1; - chunk c; - BIG_dnorm(a); - while (a[k]==0 && k>=0) k--; - if (k<0) return 0; - bts=BASEBITS*k; - c=a[k]; - while (c!=0) {c/=2; bts++;} - return bts; -} - - -/* Set b=b mod c */ -/* SU= 16 */ -void BIG_mod(BIG b,BIG c) -{ - int k=0; - - BIG_norm(b); - if (BIG_comp(b,c)<0) - return; - do - { - BIG_fshl(c,1); - k++; - } while (BIG_comp(b,c)>=0); - - while (k>0) - { - BIG_fshr(c,1); - if (BIG_comp(b,c)>=0) - { - BIG_sub(b,b,c); - BIG_norm(b); - } - k--; - } -} - -/* Set a=b mod c, b is destroyed. Slow but rarely used. */ -/* SU= 96 */ -void BIG_dmod(BIG a,DBIG b,BIG c) -{ - int k=0; - DBIG m; - BIG_dnorm(b); - BIG_dscopy(m,c); - - if (BIG_dcomp(b,m)<0) - { - BIG_sdcopy(a,b); - return; - } - - do - { - BIG_dshl(m,1); - k++; - } while (BIG_dcomp(b,m)>=0); - - while (k>0) - { - BIG_dshr(m,1); - if (BIG_dcomp(b,m)>=0) - { - BIG_dsub(b,b,m); - BIG_dnorm(b); - } - k--; - } - BIG_sdcopy(a,b); -} - -/* Set a=b/c, b is destroyed. Slow but rarely used. */ -/* SU= 136 */ -void BIG_ddiv(BIG a,DBIG b,BIG c) -{ - int k=0; - DBIG m; - BIG e; - BIG_dnorm(b); - BIG_dscopy(m,c); - - BIG_zero(a); - BIG_zero(e); BIG_inc(e,1); - - while (BIG_dcomp(b,m)>=0) - { - BIG_fshl(e,1); - BIG_dshl(m,1); - k++; - } - - while (k>0) - { - BIG_dshr(m,1); - BIG_fshr(e,1); - if (BIG_dcomp(b,m)>=0) - { - BIG_add(a,a,e); - BIG_norm(a); - BIG_dsub(b,b,m); - BIG_dnorm(b); - } - k--; - } -} - -/* SU= 136 */ - -void BIG_sdiv(BIG a,BIG c) -{ - int k=0; - BIG m,e,b; - BIG_norm(a); - BIG_copy(b,a); - BIG_copy(m,c); - - BIG_zero(a); - BIG_zero(e); BIG_inc(e,1); - - while (BIG_comp(b,m)>=0) - { - BIG_fshl(e,1); - BIG_fshl(m,1); - k++; - } - - while (k>0) - { - BIG_fshr(m,1); - BIG_fshr(e,1); - if (BIG_comp(b,m)>=0) - { - BIG_add(a,a,e); - BIG_norm(a); - BIG_sub(b,b,m); - BIG_norm(b); - } - k--; - } -} - -/* return LSB of a */ -int BIG_parity(BIG a) -{ - return a[0]%2; -} - -/* return n-th bit of a */ -/* SU= 16 */ -int BIG_bit(BIG a,int n) -{ - if (a[n/BASEBITS]&((chunk)1<<(n%BASEBITS))) return 1; - else return 0; -} - -/* return NAF value as +/- 1, 3 or 5. x and x3 should be normed. -nbs is number of bits processed, and nzs is number of trailing 0s detected */ -/* SU= 32 */ -int BIG_nafbits(BIG x,BIG x3,int i,int *nbs,int *nzs) -{ - int j,r,nb; - - nb=BIG_bit(x3,i)-BIG_bit(x,i); - *nbs=1; - *nzs=0; - if (nb==0) return 0; - if (i==0) return nb; - - if (nb>0) r=1; - else r=(-1); - - for (j=i-1;j>0;j--) - { - (*nbs)++; - r*=2; - nb=BIG_bit(x3,j)-BIG_bit(x,j); - if (nb>0) r+=1; - if (nb<0) r-=1; - if (abs(r)>5) break; - } - - if (r%2!=0 && j!=0) - { /* backtrack */ - if (nb>0) r=(r-1)/2; - if (nb<0) r=(r+1)/2; - (*nbs)--; - } - - while (r%2==0) - { /* remove trailing zeros */ - r/=2; - (*nzs)++; - (*nbs)--; - } - return r; -} - -/* return last n bits of a, where n is small < BASEBITS */ -/* SU= 16 */ -int BIG_lastbits(BIG a,int n) -{ - int msk=(1<<n)-1; - BIG_norm(a); - return ((int)a[0])&msk; -} - -/* get 8*MODBYTES size random number */ -void BIG_random(BIG m,csprng *rng) -{ - int i,b,j=0,r=0; - - BIG_zero(m); -/* generate random BIG */ - for (i=0;i<8*MODBYTES;i++) - { - if (j==0) r=RAND_byte(rng); - else r>>=1; - b=r&1; - BIG_shl(m,1); m[0]+=b; - j++; j&=7; - } - -#ifdef DEBUG_NORM - m[NLEN]=0; -#endif -} - -/* get random BIG from rng, modulo q. Done one bit at a time, so its portable */ - -void BIG_randomnum(BIG m,BIG q,csprng *rng) -{ - int i,b,j=0,r=0; - DBIG d; - BIG_dzero(d); -/* generate random DBIG */ - for (i=0;i<2*MODBITS;i++) - { - if (j==0) r=RAND_byte(rng); - else r>>=1; - b=r&1; - BIG_dshl(d,1); d[0]+=b; - j++; j&=7; - } -/* reduce modulo a BIG. Removes bias */ - BIG_dmod(m,d,q); -#ifdef DEBUG_NORM - m[NLEN]=0; -#endif -} - -/* Set r=a*b mod m */ -/* SU= 96 */ -void BIG_modmul(BIG r,BIG a,BIG b,BIG m) -{ - DBIG d; - BIG_mod(a,m); - BIG_mod(b,m); - BIG_mul(d,a,b); - BIG_dmod(r,d,m); -} - -/* Set a=a*a mod m */ -/* SU= 88 */ -void BIG_modsqr(BIG r,BIG a,BIG m) -{ - DBIG d; - BIG_mod(a,m); - BIG_sqr(d,a); - BIG_dmod(r,d,m); -} - -/* Set r=-a mod m */ -/* SU= 16 */ -void BIG_modneg(BIG r,BIG a,BIG m) -{ - BIG_mod(a,m); - BIG_sub(r,m,a); -} - -/* Set a=a/b mod m */ -/* SU= 136 */ -void BIG_moddiv(BIG r,BIG a,BIG b,BIG m) -{ - DBIG d; - BIG z; - BIG_mod(a,m); - BIG_invmodp(z,b,m); - BIG_mul(d,a,z); - BIG_dmod(r,d,m); -} - -/* Get jacobi Symbol (a/p). Returns 0, 1 or -1 */ -/* SU= 216 */ -int BIG_jacobi(BIG a,BIG p) -{ - int n8,k,m=0; - BIG t,x,n,zilch,one; - BIG_one(one); - BIG_zero(zilch); - if (BIG_parity(p)==0 || BIG_comp(a,zilch)==0 || BIG_comp(p,one)<=0) return 0; - BIG_norm(a); - BIG_copy(x,a); - BIG_copy(n,p); - BIG_mod(x,p); - - while (BIG_comp(n,one)>0) - { - if (BIG_comp(x,zilch)==0) return 0; - n8=BIG_lastbits(n,3); - k=0; - while (BIG_parity(x)==0) - { - k++; - BIG_shr(x,1); - } - if (k%2==1) m+=(n8*n8-1)/8; - m+=(n8-1)*(BIG_lastbits(x,2)-1)/4; - BIG_copy(t,n); - - BIG_mod(t,x); - BIG_copy(n,x); - BIG_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_invmodp(BIG r,BIG a,BIG p) -{ - BIG u,v,x1,x2,t,one; - BIG_mod(a,p); - BIG_copy(u,a); - BIG_copy(v,p); - BIG_one(one); - BIG_copy(x1,one); - BIG_zero(x2); - - while (BIG_comp(u,one)!=0 && BIG_comp(v,one)!=0) - { - while (BIG_parity(u)==0) - { - BIG_shr(u,1); - if (BIG_parity(x1)!=0) - { - BIG_add(x1,p,x1); - BIG_norm(x1); - } - BIG_shr(x1,1); - } - while (BIG_parity(v)==0) - { - BIG_shr(v,1); - if (BIG_parity(x2)!=0) - { - BIG_add(x2,p,x2); - BIG_norm(x2); - } - BIG_shr(x2,1); - } - if (BIG_comp(u,v)>=0) - { - BIG_sub(u,u,v); - BIG_norm(u); - if (BIG_comp(x1,x2)>=0) BIG_sub(x1,x1,x2); - else - { - BIG_sub(t,p,x2); - BIG_add(x1,x1,t); - } - BIG_norm(x1); - } - else - { - BIG_sub(v,v,u); - BIG_norm(v); - if (BIG_comp(x2,x1)>=0) BIG_sub(x2,x2,x1); - else - { - BIG_sub(t,p,x1); - BIG_add(x2,x2,t); - } - BIG_norm(x2); - } - } - if (BIG_comp(u,one)==0) - BIG_copy(r,x1); - else - BIG_copy(r,x2); -}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/build_ec ---------------------------------------------------------------------- diff --git a/c/build_ec b/c/build_ec deleted file mode 100644 index 5b364d0..0000000 --- a/c/build_ec +++ /dev/null @@ -1,24 +0,0 @@ -cp amcl_.h amcl.h - -gcc -std=c99 -c -O3 big.c -gcc -std=c99 -c -O3 fp.c -gcc -std=c99 -c -O3 ecp.c -gcc -std=c99 -c -O3 hash.c -gcc -std=c99 -c -O3 rand.c -gcc -std=c99 -c -O3 aes.c -gcc -std=c99 -c -O3 gcm.c -gcc -std=c99 -c -O3 oct.c -gcc -std=c99 -c -O3 rom.c - -gcc -std=c99 -c -O3 ff.c - -rm amcl.a -ar rc amcl.a big.o fp.o ecp.o hash.o ff.o -ar r amcl.a rand.o aes.o gcm.o oct.o rom.o - -gcc -std=c99 -O3 testecm.c ecdh.c amcl.a -o testecm -gcc -std=c99 -O3 testecdh.c ecdh.c amcl.a -o testecdh -gcc -std=c99 -O3 testrsa.c rsa.c amcl.a -o testrsa - -rm amcl.h -rm *.o http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/build_ec.bat ---------------------------------------------------------------------- diff --git a/c/build_ec.bat b/c/build_ec.bat deleted file mode 100644 index c302beb..0000000 --- a/c/build_ec.bat +++ /dev/null @@ -1,24 +0,0 @@ -copy amcl_.h amcl.h - -gcc -std=c99 -c -O3 big.c -gcc -std=c99 -c -O3 fp.c -gcc -std=c99 -c -O3 ecp.c -gcc -std=c99 -c -O3 hash.c -gcc -std=c99 -c -O3 rand.c -gcc -std=c99 -c -O3 aes.c -gcc -std=c99 -c -O3 gcm.c -gcc -std=c99 -c -O3 oct.c -gcc -std=c99 -c -O3 rom.c - -gcc -std=c99 -c -O3 ff.c - -del amcl.a -ar rc amcl.a big.o fp.o ecp.o hash.o ff.o -ar r amcl.a rand.o aes.o gcm.o oct.o rom.o - -gcc -std=c99 -O3 testecm.c ecdh.c amcl.a -o testecm.exe -gcc -std=c99 -O3 testecdh.c ecdh.c amcl.a -o testecdh.exe -gcc -std=c99 -O3 testrsa.c rsa.c amcl.a -o testrsa.exe - -del amcl.h -del *.o http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/build_pair ---------------------------------------------------------------------- diff --git a/c/build_pair b/c/build_pair deleted file mode 100644 index 7232c27..0000000 --- a/c/build_pair +++ /dev/null @@ -1,28 +0,0 @@ -cp amcl_.h amcl.h - -gcc -std=c99 -c -O3 big.c -gcc -std=c99 -c -O3 fp.c -gcc -std=c99 -c -O3 ecp.c -gcc -std=c99 -c -O3 hash.c -gcc -std=c99 -c -O3 rand.c -gcc -std=c99 -c -O3 aes.c -gcc -std=c99 -c -O3 gcm.c -gcc -std=c99 -c -O3 oct.c -gcc -std=c99 -c -O3 rom.c - -gcc -std=c99 -c -O3 fp2.c -gcc -std=c99 -c -O3 ecp2.c -gcc -std=c99 -c -O3 fp4.c -gcc -std=c99 -c -O3 fp12.c -gcc -std=c99 -c -O3 pair.c - -rm amcl.a -ar rc amcl.a big.o fp.o ecp.o hash.o -ar r amcl.a rand.o aes.o gcm.o oct.o rom.o - -ar r amcl.a pair.o fp2.o ecp2.o fp4.o fp12.o - -gcc -std=c99 -O3 testmpin.c mpin.c amcl.a -o testmpin - -rm amcl.h -rm *.o http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/build_pair.bat ---------------------------------------------------------------------- diff --git a/c/build_pair.bat b/c/build_pair.bat deleted file mode 100644 index 05d1c24..0000000 --- a/c/build_pair.bat +++ /dev/null @@ -1,28 +0,0 @@ -copy amcl_.h amcl.h - -gcc -std=c99 -c -O3 big.c -gcc -std=c99 -c -O3 fp.c -gcc -std=c99 -c -O3 ecp.c -gcc -std=c99 -c -O3 hash.c -gcc -std=c99 -c -O3 rand.c -gcc -std=c99 -c -O3 aes.c -gcc -std=c99 -c -O3 gcm.c -gcc -std=c99 -c -O3 oct.c -gcc -std=c99 -c -O3 rom.c - -gcc -std=c99 -c -O3 fp2.c -gcc -std=c99 -c -O3 ecp2.c -gcc -std=c99 -c -O3 fp4.c -gcc -std=c99 -c -O3 fp12.c -gcc -std=c99 -c -O3 pair.c - -del amcl.a -ar rc amcl.a big.o fp.o ecp.o hash.o -ar r amcl.a rand.o aes.o gcm.o oct.o rom.o - -ar r amcl.a pair.o fp2.o ecp2.o fp4.o fp12.o - -gcc -std=c99 -O3 testmpin.c mpin.c amcl.a -o testmpin.exe - -del amcl.h -del *.o http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/build_pair_ms.bat ---------------------------------------------------------------------- diff --git a/c/build_pair_ms.bat b/c/build_pair_ms.bat deleted file mode 100644 index 96b6234..0000000 --- a/c/build_pair_ms.bat +++ /dev/null @@ -1,28 +0,0 @@ -copy amcl_.h amcl.h - -cl /c /O2 big.c -cl /c /O2 fp.c -cl /c /O2 ecp.c -cl /c /O2 hash.c -cl /c /O2 rand.c -cl /c /O2 aes.c -cl /c /O2 gcm.c -cl /c /O2 oct.c -cl /c /O2 rom.c -cl /c /O2 fp.c -cl /c /O2 fp2.c -cl /c /O2 ecp2.c -cl /c /O2 fp4.c -cl /c /O2 fp12.c -cl /c /O2 pair.c - -del amcl.lib -lib /OUT:amcl.lib big.obj fp.obj ecp.obj hash.obj -lib /OUT:amcl.lib amcl.lib rand.obj aes.obj gcm.obj oct.obj rom.obj - -lib /OUT:amcl.lib amcl.lib pair.obj fp2.obj ecp2.obj fp4.obj fp12.obj - -cl /O2 testmpin.c mpin.c amcl.lib - -del amcl.h -del *.obj http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/ecdh.c ---------------------------------------------------------------------- diff --git a/c/ecdh.c b/c/ecdh.c deleted file mode 100755 index 56152da..0000000 --- a/c/ecdh.c +++ /dev/null @@ -1,576 +0,0 @@ -/* -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.h" - -#define ROUNDUP(a,b) ((a)-1)/(b)+1 - -/* general purpose hash function w=hash(p|n|x|y) */ -static void hashit(octet *p,int n,octet *x,octet *y,octet *w) -{ - int i,c[4]; - hash sha; - char hh[32]; - - HASH_init(&sha); - if (p!=NULL) - for (i=0;i<p->len;i++) HASH_process(&sha,p->val[i]); - 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++) HASH_process(&sha,c[i]); - } - if (x!=NULL) - for (i=0;i<x->len;i++) HASH_process(&sha,x->val[i]); - if (y!=NULL) - for (i=0;i<y->len;i++) HASH_process(&sha,y->val[i]); - - - HASH_hash(&sha,hh); - - OCT_empty(w); - OCT_jbytes(w,hh,32); - for (i=0;i<32;i++) hh[i]=0; -} - -/* Hash octet p to octet w */ -void ECP_HASH(octet *p,octet *w) -{ - hashit(p,-1,NULL,NULL,w); -} - -/* Initialise a Cryptographically Strong Random Number Generator from - an octet of raw random data */ -void ECP_CREATE_CSPRNG(csprng *RNG,octet *RAW) -{ - RAND_seed(RNG,RAW->len,RAW->val); -} - -void ECP_KILL_CSPRNG(csprng *RNG) -{ - RAND_clean(RNG); -} - -/* Calculate HMAC of m using key k. HMAC is tag of length olen */ -int ECP_HMAC(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[32],k0[64]; - octet H={0,sizeof(h),h}; - octet K0={0,sizeof(k0),k0}; - - hlen=32; b=64; - if (olen<4 || olen>hlen) return 0; - - if (k->len > b) hashit(k,-1,NULL,NULL,&K0); - else OCT_copy(&K0,k); - - OCT_jbyte(&K0,0,b-K0.len); - - OCT_xorbyte(&K0,0x36); - - hashit(&K0,-1,m,NULL,&H); - - OCT_xorbyte(&K0,0x6a); /* 0x6a = 0x36 ^ 0x5c */ - hashit(&K0,-1,&H,NULL,&H); - - OCT_empty(tag); - OCT_jbytes(tag,H.val,olen); - - return 1; -} - -/* Key Derivation Functions */ -/* Input octet z */ -/* Output key of length olen */ -/* -void KDF1(octet *z,int olen,octet *key) -{ - char h[32]; - octet H={0,sizeof(h),h}; - int counter,cthreshold; - int hlen=32; - - OCT_empty(key); - - cthreshold=ROUNDUP(olen,hlen); - - for (counter=0;counter<cthreshold;counter++) - { - hashit(z,counter,NULL,NULL,&H); - if (key->len+hlen>olen) OCT_jbytes(key,H.val,olen%hlen); - else OCT_joctet(key,&H); - } -} -*/ -void ECP_KDF2(octet *z,octet *p,int olen,octet *key) -{ -/* NOTE: the parameter olen is the length of the output k in bytes */ - char h[32]; - octet H={0,sizeof(h),h}; - int counter,cthreshold; - int hlen=32; - - OCT_empty(key); - - cthreshold=ROUNDUP(olen,hlen); - - for (counter=1;counter<=cthreshold;counter++) - { - hashit(z,counter,p,NULL,&H); - 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 ECP_PBKDF2(octet *p,octet *s,int rep,int olen,octet *key) -{ - int i,j,len,d=ROUNDUP(olen,32); - char f[EFS],u[EFS]; - 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); - ECP_HMAC(s,p,EFS,&F); - s->len=len; - OCT_copy(&U,&F); - for (j=2;j<=rep;j++) - { - ECP_HMAC(&U,p,EFS,&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 ECP_AES_CBC_IV0_ENCRYPT(octet *k,octet *m,octet *c) -{ /* AES CBC encryption, with Null IV and key k */ - /* Input is from an octet string m, output is to an octet string c */ - /* Input is padded as necessary to make up a full final block */ - aes a; - int fin; - int i,j,ipt,opt; - char buff[16]; - int padlen; - - OCT_clear(c); - if (m->len==0) return; - AES_init(&a,CBC,k->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 ECP_AES_CBC_IV0_DECRYPT(octet *k,octet *c,octet *m) -{ /* padding is removed */ - aes a; - int i,ipt,opt,ch; - char buff[16]; - int fin,bad; - int padlen; - ipt=opt=0; - - OCT_clear(m); - if (c->len==0) return 1; - ch=c->val[ipt++]; - - AES_init(&a,CBC,k->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; -} - -/* 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_KEY_PAIR_GENERATE(csprng *RNG,octet* S,octet *W) -{ - BIG r,gx,gy,s; - ECP G; - int res=0; - BIG_rcopy(gx,CURVE_Gx); - -#if CURVETYPE!=MONTGOMERY - BIG_rcopy(gy,CURVE_Gy); - ECP_set(&G,gx,gy); -#else - ECP_set(&G,gx); -#endif - - BIG_rcopy(r,CURVE_Order); - if (RNG!=NULL) - BIG_randomnum(s,r,RNG); - else - { - BIG_fromBytes(s,S->val); - BIG_mod(s,r); - } - - ECP_mul(&G,s); -#if CURVETYPE!=MONTGOMERY - ECP_get(gx,gy,&G); -#else - ECP_get(gx,&G); -#endif - if (RNG!=NULL) - { - S->len=EGS; - BIG_toBytes(S->val,s); - } -#if CURVETYPE!=MONTGOMERY - W->len=2*EFS+1; W->val[0]=4; - BIG_toBytes(&(W->val[1]),gx); - BIG_toBytes(&(W->val[EFS+1]),gy); -#else - W->len=EFS+1; W->val[0]=2; - BIG_toBytes(&(W->val[1]),gx); -#endif - - return res; -} - -/* validate public key. Set full=true for fuller check */ -int ECP_PUBLIC_KEY_VALIDATE(int full,octet *W) -{ - BIG q,r,wx,wy; - ECP WP; - int valid; - int res=0; - - BIG_rcopy(q,Modulus); - BIG_rcopy(r,CURVE_Order); - - BIG_fromBytes(wx,&(W->val[1])); - if (BIG_comp(wx,q)>=0) res=ECDH_INVALID_PUBLIC_KEY; -#if CURVETYPE!=MONTGOMERY - BIG_fromBytes(wy,&(W->val[EFS+1])); - if (BIG_comp(wy,q)>=0) res=ECDH_INVALID_PUBLIC_KEY; -#endif - if (res==0) - { -#if CURVETYPE!=MONTGOMERY - valid=ECP_set(&WP,wx,wy); -#else - valid=ECP_set(&WP,wx); -#endif - if (!valid || ECP_isinf(&WP)) res=ECDH_INVALID_PUBLIC_KEY; - if (res==0 && full) - { - ECP_mul(&WP,r); - if (!ECP_isinf(&WP)) res=ECDH_INVALID_PUBLIC_KEY; - } - } - - return res; -} - -/* IEEE-1363 Diffie-Hellman online calculation Z=S.WD */ -int ECP_SVDP_DH(octet *S,octet *WD,octet *Z) -{ - BIG r,s,wx,wy; - int valid; - ECP W; - int res=0; - - BIG_fromBytes(s,S->val); - - BIG_fromBytes(wx,&(WD->val[1])); -#if CURVETYPE!=MONTGOMERY - BIG_fromBytes(wy,&(WD->val[EFS+1])); - valid=ECP_set(&W,wx,wy); -#else - valid=ECP_set(&W,wx); -#endif - if (!valid) res=ECDH_ERROR; - if (res==0) - { - BIG_rcopy(r,CURVE_Order); - BIG_mod(s,r); - - ECP_mul(&W,s); - if (ECP_isinf(&W)) res=ECDH_ERROR; - else - { -#if CURVETYPE!=MONTGOMERY - ECP_get(wx,wx,&W); -#else - ECP_get(wx,&W); -#endif - Z->len=32; - BIG_toBytes(Z->val,wx); - } - } - return res; -} - -#if CURVETYPE!=MONTGOMERY - -/* IEEE ECDSA Signature, C and D are signature on F using private key S */ -int ECP_SP_DSA(csprng *RNG,octet *S,octet *F,octet *C,octet *D) -{ - char h[32]; - octet H={0,sizeof(h),h}; - - BIG gx,gy,r,s,f,c,d,u,vx; - ECP G,V; - - hashit(F,-1,NULL,NULL,&H); - - BIG_rcopy(gx,CURVE_Gx); - BIG_rcopy(gy,CURVE_Gy); - BIG_rcopy(r,CURVE_Order); - - BIG_fromBytes(s,S->val); - BIG_fromBytes(f,H.val); - - ECP_set(&G,gx,gy); - - do { - BIG_randomnum(u,r,RNG); - ECP_copy(&V,&G); - ECP_mul(&V,u); - - ECP_get(vx,vx,&V); - - BIG_copy(c,vx); - BIG_mod(c,r); - if (BIG_iszilch(c)) continue; - - BIG_invmodp(u,u,r); - BIG_modmul(d,s,c,r); - - BIG_add(d,f,d); - - BIG_modmul(d,u,d,r); - - } while (BIG_iszilch(d)); - - C->len=D->len=EGS; - - BIG_toBytes(C->val,c); - BIG_toBytes(D->val,d); - - return 0; -} - -/* IEEE1363 ECDSA Signature Verification. Signature C and D on F is verified using public key W */ -int ECP_VP_DSA(octet *W,octet *F, octet *C,octet *D) -{ - char h[32]; - octet H={0,sizeof(h),h}; - - BIG r,gx,gy,wx,wy,f,c,d,h2; - int res=0; - ECP G,WP; - int valid; - - hashit(F,-1,NULL,NULL,&H); - - BIG_rcopy(gx,CURVE_Gx); - BIG_rcopy(gy,CURVE_Gy); - BIG_rcopy(r,CURVE_Order); - - BIG_fromBytes(c,C->val); - BIG_fromBytes(d,D->val); - BIG_fromBytes(f,H.val); - - if (BIG_iszilch(c) || BIG_comp(c,r)>=0 || BIG_iszilch(d) || BIG_comp(d,r)>=0) - res=ECDH_INVALID; - - if (res==0) - { - BIG_invmodp(d,d,r); - BIG_modmul(f,f,d,r); - BIG_modmul(h2,c,d,r); - - ECP_set(&G,gx,gy); - - BIG_fromBytes(wx,&(W->val[1])); - BIG_fromBytes(wy,&(W->val[EFS+1])); - - valid=ECP_set(&WP,wx,wy); - - if (!valid) res=ECDH_ERROR; - else - { - ECP_mul2(&WP,&G,h2,f); - - if (ECP_isinf(&WP)) res=ECDH_INVALID; - else - { - ECP_get(d,d,&WP); - BIG_mod(d,r); - if (BIG_comp(d,c)!=0) res=ECDH_INVALID; - } - } - } - - return res; -} - -/* IEEE1363 ECIES encryption. Encryption of plaintext M uses public key W and produces ciphertext V,C,T */ -void ECP_ECIES_ENCRYPT(octet *P1,octet *P2,csprng *RNG,octet *W,octet *M,int tlen,octet *V,octet *C,octet *T) -{ - - int i,len; - char z[EFS],vz[3*EFS+2],k[32],k1[16],k2[16],l2[8],u[EFS]; - octet Z={0,sizeof(z),z}; - octet VZ={0,sizeof(vz),vz}; - octet K={0,sizeof(k),k}; - octet K1={0,sizeof(k1),k1}; - octet K2={0,sizeof(k2),k2}; - octet L2={0,sizeof(l2),l2}; - octet U={0,sizeof(u),u}; - - if (ECP_KEY_PAIR_GENERATE(RNG,&U,V)!=0) return; - if (ECP_SVDP_DH(&U,W,&Z)!=0) return; - - OCT_copy(&VZ,V); - OCT_joctet(&VZ,&Z); - - ECP_KDF2(&VZ,P1,EFS,&K); - - K1.len=K2.len=16; - for (i=0;i<16;i++) {K1.val[i]=K.val[i]; K2.val[i]=K.val[16+i];} - - ECP_AES_CBC_IV0_ENCRYPT(&K1,M,C); - - OCT_jint(&L2,P2->len,8); - - len=C->len; - OCT_joctet(C,P2); - OCT_joctet(C,&L2); - ECP_HMAC(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_ECIES_DECRYPT(octet *P1,octet *P2,octet *V,octet *C,octet *T,octet *U,octet *M) -{ - - int i,len; - char z[EFS],vz[3*EFS+2],k[32],k1[16],k2[16],l2[8],tag[32]; - octet Z={0,sizeof(z),z}; - octet VZ={0,sizeof(vz),vz}; - octet K={0,sizeof(k),k}; - octet K1={0,sizeof(k1),k1}; - octet K2={0,sizeof(k2),k2}; - octet L2={0,sizeof(l2),l2}; - octet TAG={0,sizeof(tag),tag}; - - if (ECP_SVDP_DH(U,V,&Z)!=0) return 0; - - OCT_copy(&VZ,V); - OCT_joctet(&VZ,&Z); - - ECP_KDF2(&VZ,P1,EFS,&K); - - K1.len=K2.len=16; - for (i=0;i<16;i++) {K1.val[i]=K.val[i]; K2.val[i]=K.val[16+i];} - - if (!ECP_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); - ECP_HMAC(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/blob/70e3a3a3/c/ecdh.h ---------------------------------------------------------------------- diff --git a/c/ecdh.h b/c/ecdh.h deleted file mode 100755 index 0dae41a..0000000 --- a/c/ecdh.h +++ /dev/null @@ -1,204 +0,0 @@ -/* -Licensed to the Apache Software Foundation (ASF) under one -or more contributor license agreements. See the NOTICE file -distributed with this work for additional information -regarding copyright ownership. The ASF licenses this file -to you under the Apache License, Version 2.0 (the -"License"); you may not use this file except in compliance -with the License. You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - -Unless required by applicable law or agreed to in writing, -software distributed under the License is distributed on an -"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY -KIND, either express or implied. See the License for the -specific language governing permissions and limitations -under the License. -*/ - -/** - * @file ecdh.h - * @author Mike Scott and Kealan McCusker - * @date 2nd June 2015 - * @brief ECDH Header file for implementation of standard EC protocols - * - * declares functions - * - */ - -#ifndef ECDH_H -#define ECDH_H - -#include "amcl.h" - -#define EAS 16 /**< Symmetric Key size - 128 bits */ -#define EGS 32 /**< ECC Group Size */ -#define EFS 32 /**< ECC Field Size */ - -#define ECDH_OK 0 /**< Function completed without error */ -/*#define ECDH_DOMAIN_ERROR -1*/ -#define ECDH_INVALID_PUBLIC_KEY -2 /**< Public Key is Invalid */ -#define ECDH_ERROR -3 /**< ECDH Internal Error */ -#define ECDH_INVALID -4 /**< ECDH Internal Error */ -/*#define ECDH_DOMAIN_NOT_FOUND -5 -#define ECDH_OUT_OF_MEMORY -6 -#define ECDH_DIV_BY_ZERO -7 -#define ECDH_BAD_ASSUMPTION -8*/ - -/* ECDH Auxiliary Functions */ - -/** @brief Initialise a random number generator - * - @param R is a pointer to a cryptographically secure random number generator - @param S is an input truly random seed value - */ -extern void ECP_CREATE_CSPRNG(csprng *R,octet *S); -/** @brief Kill a random number generator - * - Deletes all internal state - @param R is a pointer to a cryptographically secure random number generator - */ -extern void ECP_KILL_CSPRNG(csprng *R); -/** @brief hash an octet into another octet - * - @param I input octet - @param O output octet - H(I) - */ -extern void ECP_HASH(octet *I,octet *O); -/** @brief HMAC of message M using key K to create tag of length len in octet tag - * - IEEE-1363 MAC1 function. Uses SHA256 internally. - @param M input message octet - @param K input encryption key - @param len is output desired length of HMAC tag - @param tag is the output HMAC - @return 0 for bad parameters, else 1 - */ -extern int ECP_HMAC(octet *M,octet *K,int len,octet *tag); - -/*extern void KDF1(octet *,int,octet *);*/ - -/** @brief Key Derivation Function - generates key K from inputs Z and P - * - IEEE-1363 KDF2 Key Derivation Function. Uses SHA256 internally. - @param Z input octet - @param P input key derivation parameters - can be NULL - @param len is output desired length of key - @param K is the derived key - */ -extern void ECP_KDF2(octet *Z,octet *P,int len,octet *K); -/** @brief Password Based Key Derivation Function - generates key K from password, salt and repeat counter - * - PBKDF2 Password Based Key Derivation Function. Uses SHA256 internally. - @param P input password - @param S input salt - @param rep Number of times to be iterated. - @param len is output desired length of key - @param K is the derived key - */ -extern void ECP_PBKDF2(octet *P,octet *S,int rep,int len,octet *K); -/** @brief AES encrypts a plaintext to a ciphtertext - * - IEEE-1363 AES_CBC_IV0_ENCRYPT function. Encrypts in CBC mode with a zero IV, padding as necessary to create a full final block. - @param K AES key - @param P input plaintext octet - @param C output ciphertext octet - */ -extern void ECP_AES_CBC_IV0_ENCRYPT(octet *K,octet *P,octet *C); -/** @brief AES encrypts a plaintext to a ciphtertext - * - IEEE-1363 AES_CBC_IV0_DECRYPT function. Decrypts in CBC mode with a zero IV. - @param K AES key - @param C input ciphertext octet - @param P output plaintext octet - @return 0 if bad input, else 1 - */ -extern int ECP_AES_CBC_IV0_DECRYPT(octet *K,octet *C,octet *P); - -/* ECDH primitives - support functions */ -/** @brief Generate an ECC public/private key pair - * - @param R is a pointer to a cryptographically secure random number generator - @param s the private key, an output internally randomly generated if R!=NULL, otherwise must be provided as an input - @param W the output public key, which is s.G, where G is a fixed generator - @return 0 or an error code - */ -extern int ECP_KEY_PAIR_GENERATE(csprng *R,octet *s,octet *W); -/** @brief Validate an ECC public key - * - @param f if = 0 just does some simple checks, else tests that W is of the correct order - @param W the input public key to be validated - @return 0 if public key is OK, or an error code - */ -extern int ECP_PUBLIC_KEY_VALIDATE(int f,octet *W); - -/* ECDH primitives */ - -/** @brief Generate Diffie-Hellman shared key - * - IEEE-1363 Diffie-Hellman shared secret calculation - @param s is the input private key, - @param W the input public key of the other party - @param K the output shared key, in fact the x-coordinate of s.W - @return 0 or an error code - */ -extern int ECP_SVDP_DH(octet *s,octet *W,octet *K); -/*extern int ECPSVDP_DHC(octet *,octet *,int,octet *);*/ - -/*#if CURVETYPE!=MONTGOMERY */ -/* ECIES functions */ -/** @brief ECIES Encryption - * - IEEE-1363 ECIES Encryption - @param P1 input Key Derivation parameters - @param P2 input Encoding parameters - @param R is a pointer to a cryptographically secure random number generator - @param W the input public key of the recieving party - @param M is the plaintext message to be encrypted - @param len the length of the HMAC tag - @param V component of the output ciphertext - @param C the output ciphertext - @param T the output HMAC tag, part of the ciphertext - */ -extern void ECP_ECIES_ENCRYPT(octet *P1,octet *P2,csprng *R,octet *W,octet *M,int len,octet *V,octet *C,octet *T); -/** @brief ECIES Decryption - * - IEEE-1363 ECIES Decryption - @param P1 input Key Derivation parameters - @param P2 input Encoding parameters - @param V component of the input ciphertext - @param C the input ciphertext - @param T the input HMAC tag, part of the ciphertext - @param U the input private key for decryption - @param M the output plaintext message - @return 1 if successful, else 0 - */ -extern int ECP_ECIES_DECRYPT(octet *P1,octet *P2,octet *V,octet *C,octet *T,octet *U,octet *M); - -/* ECDSA functions */ -/** @brief ECDSA Signature - * - IEEE-1363 ECDSA Signature - @param R is a pointer to a cryptographically secure random number generator - @param s the input private signing key - @param M the input message to be signed - @param c component of the output signature - @param d component of the output signature - - */ -extern int ECP_SP_DSA(csprng *R,octet *s,octet *M,octet *c,octet *d); -/** @brief ECDSA Signature Verification - * - IEEE-1363 ECDSA Signature Verification - @param W the input public key - @param M the input message - @param c component of the input signature - @param d component of the input signature - @return 0 or an error code - */ -extern int ECP_VP_DSA(octet *W,octet *M,octet *c,octet *d); -/*#endif*/ - -#endif - http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/ecp.c ---------------------------------------------------------------------- diff --git a/c/ecp.c b/c/ecp.c deleted file mode 100755 index b7fdd10..0000000 --- a/c/ecp.c +++ /dev/null @@ -1,1091 +0,0 @@ -/* -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 "amcl.h" - -/* test for P=O point-at-infinity */ -int ECP_isinf(ECP *P) -{ -#if CURVETYPE==EDWARDS - FP_reduce(P->x); - FP_reduce(P->y); - FP_reduce(P->z); - return (BIG_iszilch(P->x) && BIG_comp(P->y,P->z)==0); -#else - return P->inf; -#endif -} - -/* Conditional swap of P and Q dependant on d */ -static void ECP_cswap(ECP *P,ECP *Q,int d) -{ - BIG_cswap(P->x,Q->x,d); -#if CURVETYPE!=MONTGOMERY - BIG_cswap(P->y,Q->y,d); -#endif - BIG_cswap(P->z,Q->z,d); -#if CURVETYPE!=EDWARDS - d=~(d-1); - d=d&(P->inf^Q->inf); - P->inf^=d; - Q->inf^=d; -#endif -} - -/* Conditional move Q to P dependant on d */ -static void ECP_cmove(ECP *P,ECP *Q,int d) -{ - BIG_cmove(P->x,Q->x,d); -#if CURVETYPE!=MONTGOMERY - BIG_cmove(P->y,Q->y,d); -#endif - BIG_cmove(P->z,Q->z,d); -#if CURVETYPE!=EDWARDS - d=~(d-1); - P->inf^=(P->inf^Q->inf)&d; -#endif -} - -/* return 1 if b==c, no branching */ -static int teq(sign32 b,sign32 c) -{ - sign32 x=b^c; - x-=1; // if x=0, x now -1 - return (int)((x>>31)&1); -} - -/* Constant time select from pre-computed table */ -static void ECP_select(ECP *P,ECP W[],sign32 b) -{ - ECP MP; - sign32 m=b>>31; - sign32 babs=(b^m)-m; - - babs=(babs-1)/2; - - ECP_cmove(P,&W[0],teq(babs,0)); // conditional move - ECP_cmove(P,&W[1],teq(babs,1)); - ECP_cmove(P,&W[2],teq(babs,2)); - ECP_cmove(P,&W[3],teq(babs,3)); - ECP_cmove(P,&W[4],teq(babs,4)); - ECP_cmove(P,&W[5],teq(babs,5)); - ECP_cmove(P,&W[6],teq(babs,6)); - ECP_cmove(P,&W[7],teq(babs,7)); - - ECP_copy(&MP,P); - ECP_neg(&MP); // minus P - ECP_cmove(P,&MP,(int)(m&1)); -} - -/* Test P == Q */ -/* SU=168 */ -int ECP_equals(ECP *P,ECP *Q) -{ -#if CURVETYPE==WEIERSTRASS - BIG pz2,qz2,a,b; - if (ECP_isinf(P) && ECP_isinf(Q)) return 1; - if (ECP_isinf(P) || ECP_isinf(Q)) return 0; - - FP_sqr(pz2,P->z); FP_sqr(qz2,Q->z); - - FP_mul(a,P->x,qz2); - FP_mul(b,Q->x,pz2); - FP_reduce(a); - FP_reduce(b); - if (BIG_comp(a,b)!=0) return 0; - - FP_mul(a,P->y,qz2); - FP_mul(a,a,Q->z); - FP_mul(b,Q->y,pz2); - FP_mul(b,b,P->z); - FP_reduce(a); - FP_reduce(b); - if (BIG_comp(a,b)!=0) return 0; - return 1; -#else - BIG a,b; - if (ECP_isinf(P) && ECP_isinf(Q)) return 1; - if (ECP_isinf(P) || ECP_isinf(Q)) return 0; - - FP_mul(a,P->x,Q->z); - FP_mul(b,Q->x,P->z); - FP_reduce(a); - FP_reduce(b); - if (BIG_comp(a,b)!=0) return 0; - -#if CURVETYPE==EDWARDS - FP_mul(a,P->y,Q->z); - FP_mul(b,Q->y,P->z); - FP_reduce(a); - FP_reduce(b); - if (BIG_comp(a,b)!=0) return 0; -#endif - - return 1; -#endif -} - -/* Set P=Q */ -/* SU=16 */ -void ECP_copy(ECP *P,ECP *Q) -{ -#if CURVETYPE!=EDWARDS - P->inf=Q->inf; -#endif - BIG_copy(P->x,Q->x); -#if CURVETYPE!=MONTGOMERY - BIG_copy(P->y,Q->y); -#endif - BIG_copy(P->z,Q->z); -} - -/* Set P=-Q */ -#if CURVETYPE!=MONTGOMERY -/* SU=8 */ -void ECP_neg(ECP *P) -{ - if (ECP_isinf(P)) return; -#if CURVETYPE==WEIERSTRASS - FP_neg(P->y,P->y); - BIG_norm(P->y); -#else - FP_neg(P->x,P->x); - BIG_norm(P->x); -#endif - -} -#endif - -/* Set P=O */ -void ECP_inf(ECP *P) -{ -#if CURVETYPE==EDWARDS - BIG_zero(P->x); FP_one(P->y); FP_one(P->z); -#else - P->inf=1; -#endif -} - -/* Calculate right Hand Side of curve equation y^2=RHS */ -/* SU=56 */ -void ECP_rhs(BIG v,BIG x) -{ -#if CURVETYPE==WEIERSTRASS -/* x^3+Ax+B */ - BIG t; - FP_sqr(t,x); - FP_mul(t,t,x); - - if (CURVE_A==-3) - { - FP_neg(v,x); - BIG_norm(v); - BIG_imul(v,v,-CURVE_A); - BIG_norm(v); - FP_add(v,t,v); - } - else BIG_copy(v,t); - - BIG_rcopy(t,CURVE_B); - FP_nres(t); - FP_add(v,t,v); - FP_reduce(v); -#endif - -#if CURVETYPE==EDWARDS -/* (Ax^2-1)/(Bx^2-1) */ - BIG t,m,one; - BIG_rcopy(m,Modulus); - FP_sqr(v,x); - FP_one(one); - BIG_rcopy(t,CURVE_B); FP_nres(t); - FP_mul(t,v,t); FP_sub(t,t,one); - if (CURVE_A==1) FP_sub(v,v,one); - - if (CURVE_A==-1) - { - FP_add(v,v,one); - FP_neg(v,v); - } - FP_redc(v); FP_redc(t); - BIG_moddiv(v,v,t,m); - FP_nres(v); -#endif - -#if CURVETYPE==MONTGOMERY -/* x^3+Ax^2+x */ - BIG x2,x3; - FP_sqr(x2,x); - FP_mul(x3,x2,x); - BIG_copy(v,x); - FP_imul(x2,x2,CURVE_A); - FP_add(v,v,x2); - FP_add(v,v,x3); - FP_reduce(v); -#endif -} - -/* Set P=(x,y) */ - -#if CURVETYPE==MONTGOMERY - -/* Set P=(x,{y}) */ - -int ECP_set(ECP *P,BIG x) -{ - BIG m,rhs; - BIG_rcopy(m,Modulus); - BIG_copy(rhs,x); - FP_nres(rhs); - ECP_rhs(rhs,rhs); - FP_redc(rhs); - - if (BIG_jacobi(rhs,m)!=1) - { - ECP_inf(P); - return 0; - } - P->inf=0; - BIG_copy(P->x,x); FP_nres(P->x); - FP_one(P->z); - return 1; -} - -/* Extract x coordinate as BIG */ -int ECP_get(BIG x,ECP *P) -{ - if (ECP_isinf(P)) return -1; - ECP_affine(P); - BIG_copy(x,P->x); - FP_redc(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_get(BIG x,BIG y,ECP *P) -{ - int s; -#if CURVETYPE!=EDWARDS - if (ECP_isinf(P)) return -1; -#endif - ECP_affine(P); - - BIG_copy(y,P->y); - FP_redc(y); - - s=BIG_parity(y); - - BIG_copy(x,P->x); - FP_redc(x); - - return s; -} - -/* Set P=(x,{y}) */ -/* SU=96 */ -int ECP_set(ECP *P,BIG x,BIG y) -{ - BIG rhs,y2; - BIG_copy(y2,y); - - FP_nres(y2); - - FP_sqr(y2,y2); - FP_reduce(y2); - - BIG_copy(rhs,x); - FP_nres(rhs); - - ECP_rhs(rhs,rhs); - - if (BIG_comp(y2,rhs)!=0) - { - ECP_inf(P); - return 0; - } -#if CURVETYPE==WEIERSTRASS - P->inf=0; -#endif - BIG_copy(P->x,x); FP_nres(P->x); - BIG_copy(P->y,y); FP_nres(P->y); - FP_one(P->z); - return 1; -} - -/* Set P=(x,y), where y is calculated from x with sign s */ -/* SU=136 */ -int ECP_setx(ECP *P,BIG x,int s) -{ - BIG t,rhs,m; - BIG_rcopy(m,Modulus); - - BIG_copy(rhs,x); - FP_nres(rhs); - ECP_rhs(rhs,rhs); - BIG_copy(t,rhs); - FP_redc(t); - if (BIG_jacobi(t,m)!=1) - { - ECP_inf(P); - return 0; - } -#if CURVETYPE==WEIERSTRASS - P->inf=0; -#endif - BIG_copy(P->x,x); FP_nres(P->x); - - FP_sqrt(P->y,rhs); - BIG_copy(rhs,P->y); - FP_redc(rhs); - if (BIG_parity(rhs)!=s) - FP_neg(P->y,P->y); - FP_reduce(P->y); - FP_one(P->z); - return 1; -} - -#endif - -/* Convert P to Affine, from (x,y,z) to (x,y) */ -/* SU=160 */ -void ECP_affine(ECP *P) -{ - BIG one,iz,m; -#if CURVETYPE==WEIERSTRASS - BIG izn; - if (ECP_isinf(P)) return; - FP_one(one); - if (BIG_comp(P->z,one)==0) return; - BIG_rcopy(m,Modulus); - FP_redc(P->z); - - BIG_invmodp(iz,P->z,m); - FP_nres(iz); - - FP_sqr(izn,iz); - FP_mul(P->x,P->x,izn); - FP_mul(izn,izn,iz); - FP_mul(P->y,P->y,izn); - FP_reduce(P->y); - -#endif -#if CURVETYPE==EDWARDS - FP_one(one); - if (BIG_comp(P->z,one)==0) return; - BIG_rcopy(m,Modulus); - FP_redc(P->z); - - BIG_invmodp(iz,P->z,m); - FP_nres(iz); - - FP_mul(P->x,P->x,iz); - FP_mul(P->y,P->y,iz); - FP_reduce(P->y); - -#endif -#if CURVETYPE==MONTGOMERY - if (ECP_isinf(P)) return; - FP_one(one); - if (BIG_comp(P->z,one)==0) return; - - BIG_rcopy(m,Modulus); - FP_redc(P->z); - BIG_invmodp(iz,P->z,m); - FP_nres(iz); - - FP_mul(P->x,P->x,iz); - -#endif - FP_reduce(P->x); - BIG_copy(P->z,one); -} - -/* SU=120 */ -void ECP_outputxyz(ECP *P) -{ - BIG x,y,z; - if (ECP_isinf(P)) - { - printf("Infinity\n"); - return; - } - BIG_copy(x,P->x); FP_reduce(x); FP_redc(x); - BIG_copy(z,P->z); FP_reduce(z); FP_redc(z); - -#if CURVETYPE!=MONTGOMERY - BIG_copy(y,P->y); FP_reduce(y); FP_redc(y); - printf("(");BIG_output(x);printf(",");BIG_output(y);printf(",");BIG_output(z);printf(")\n"); - -#else - printf("(");BIG_output(x);printf(",");BIG_output(z);printf(")\n"); -#endif -} - -/* SU=16 */ -/* Output point P */ -void ECP_output(ECP *P) -{ - if (ECP_isinf(P)) - { - printf("Infinity\n"); - return; - } - ECP_affine(P); -#if CURVETYPE!=MONTGOMERY - FP_redc(P->x); FP_redc(P->y); - printf("(");BIG_output(P->x);printf(",");BIG_output(P->y);printf(")\n"); - FP_nres(P->x); FP_nres(P->y); -#else - FP_redc(P->x); - printf("(");BIG_output(P->x);printf(")\n"); - FP_nres(P->x); -#endif -} - - -/* SU=88 */ -/* Convert P to octet string */ -void ECP_toOctet(octet *W,ECP *P) -{ -#if CURVETYPE==MONTGOMERY - BIG x; - ECP_get(x,P); - W->len=MODBYTES+1; W->val[0]=6; - BIG_toBytes(&(W->val[1]),x); -#else - BIG x,y; - ECP_get(x,y,P); - W->len=2*MODBYTES+1; W->val[0]=4; - BIG_toBytes(&(W->val[1]),x); - BIG_toBytes(&(W->val[MODBYTES+1]),y); -#endif -} - -/* SU=88 */ -/* Restore P from octet string */ -int ECP_fromOctet(ECP *P,octet *W) -{ -#if CURVETYPE==MONTGOMERY - BIG x; - BIG_fromBytes(x,&(W->val[1])); - if (ECP_set(P,x)) return 1; - return 0; -#else - BIG x,y; - BIG_fromBytes(x,&(W->val[1])); - BIG_fromBytes(y,&(W->val[MODBYTES+1])); - if (ECP_set(P,x,y)) return 1; - return 0; -#endif -} - - -/* Set P=2P */ -/* SU=272 */ -void ECP_dbl(ECP *P) -{ -#if CURVETYPE==WEIERSTRASS - int i; - BIG one,s1,s2; - BIG w1,w7,w8,w2,w3,w6; - if (ECP_isinf(P)) return; - - if (BIG_iszilch(P->y)) - { - P->inf=1; - return; - } - FP_one(one); - BIG_zero(w6); - - if (CURVE_A==-3) - { - if (BIG_comp(P->z,one)==0) BIG_copy(w6,one); - else FP_sqr(w6,P->z); - FP_neg(w1,w6); - FP_add(w3,P->x,w1); - FP_add(w8,P->x,w6); - FP_mul(w3,w3,w8); - BIG_imul(w8,w3,3); - } - else - { -/* assuming A=0 */ - FP_sqr(w1,P->x); - BIG_imul(w8,w1,3); - } - - FP_sqr(w2,P->y); - FP_mul(w3,P->x,w2); - - BIG_imul(w3,w3,4); - FP_neg(w1,w3); -#if CHUNK<64 - BIG_norm(w1); -#endif - FP_sqr(P->x,w8); - FP_add(P->x,P->x,w1); - FP_add(P->x,P->x,w1); - - BIG_norm(P->x); - - if (BIG_comp(P->z,one)==0) BIG_copy(P->z,P->y); - else FP_mul(P->z,P->z,P->y); - FP_add(P->z,P->z,P->z); - - - FP_add(w7,w2,w2); - FP_sqr(w2,w7); - - FP_add(w2,w2,w2); - FP_sub(w3,w3,P->x); - FP_mul(P->y,w8,w3); -//#if CHUNK<64 -// BIG_norm(w2); -//#endif - FP_sub(P->y,P->y,w2); - - BIG_norm(P->y); - BIG_norm(P->z); - -#endif - -#if CURVETYPE==EDWARDS -/* Not using square for multiplication swap, as (1) it needs more adds, and (2) it triggers more reductions */ - BIG B,C,D,E,F,H,J; - - FP_mul(B,P->x,P->y); FP_add(B,B,B); - FP_sqr(C,P->x); - FP_sqr(D,P->y); - if (CURVE_A==1) BIG_copy(E,C); - if (CURVE_A==-1) FP_neg(E,C); - FP_add(F,E,D); -#if CHUNK<64 - BIG_norm(F); -#endif - FP_sqr(H,P->z); - FP_add(H,H,H); FP_sub(J,F,H); - FP_mul(P->x,B,J); - FP_sub(E,E,D); - FP_mul(P->y,F,E); - FP_mul(P->z,F,J); - - BIG_norm(P->x); - BIG_norm(P->y); - BIG_norm(P->z); - -#endif - -#if CURVETYPE==MONTGOMERY - BIG t,A,B,AA,BB,C; - if (ECP_isinf(P)) return; - - FP_add(A,P->x,P->z); - FP_sqr(AA,A); - FP_sub(B,P->x,P->z); - FP_sqr(BB,B); - FP_sub(C,AA,BB); -//#if CHUNK<64 -// BIG_norm(C); -//#endif - - FP_mul(P->x,AA,BB); - FP_imul(A,C,(CURVE_A+2)/4); - FP_add(BB,BB,A); - FP_mul(P->z,BB,C); - - BIG_norm(P->x); - BIG_norm(P->z); -#endif -} - -#if CURVETYPE==MONTGOMERY - -/* Set P+=Q. W is difference between P and Q and is affine */ -void ECP_add(ECP *P,ECP *Q,ECP *W) -{ - BIG A,B,C,D,DA,CB; - - FP_add(A,P->x,P->z); - FP_sub(B,P->x,P->z); - - FP_add(C,Q->x,Q->z); - FP_sub(D,Q->x,Q->z); - - FP_mul(DA,D,A); - FP_mul(CB,C,B); - - FP_add(A,DA,CB); FP_sqr(A,A); - FP_sub(B,DA,CB); FP_sqr(B,B); - - BIG_copy(P->x,A); - FP_mul(P->z,W->x,B); - - FP_reduce(P->z); - if (BIG_iszilch(P->z)) P->inf=1; - else P->inf=0; - - BIG_norm(P->x); -} - - -#else - -/* Set P+=Q */ -/* SU=248 */ -void ECP_add(ECP *P,ECP *Q) -{ -#if CURVETYPE==WEIERSTRASS - int aff; - BIG one,B,D,E,C,A; - if (ECP_isinf(Q)) return; - if (ECP_isinf(P)) - { - ECP_copy(P,Q); - return; - } - - FP_one(one); - aff=1; - if (BIG_comp(Q->z,one)!=0) aff=0; - - if (!aff) - { - FP_sqr(A,Q->z); - FP_mul(C,A,Q->z); - - FP_sqr(B,P->z); - FP_mul(D,B,P->z); - - FP_mul(A,P->x,A); - FP_mul(C,P->y,C); - } - else - { - BIG_copy(A,P->x); - BIG_copy(C,P->y); - - FP_sqr(B,P->z); - FP_mul(D,B,P->z); - } - - FP_mul(B,Q->x,B); FP_sub(B,B,A); /* B=Qx.z^2-x.Qz^2 */ - FP_mul(D,Q->y,D); FP_sub(D,D,C); /* D=Qy.z^3-y.Qz^3 */ - - FP_reduce(B); - if (BIG_iszilch(B)) - { - FP_reduce(D); - if (BIG_iszilch(D)) - { - ECP_dbl(P); - return; - } - else - { - ECP_inf(P); - return; - } - } - if (!aff) FP_mul(P->z,P->z,Q->z); - FP_mul(P->z,P->z,B); - - FP_sqr(E,B); - FP_mul(B,B,E); - FP_mul(A,A,E); - - FP_add(E,A,A); - FP_add(E,E,B); - - FP_sqr(P->x,D); - FP_sub(P->x,P->x,E); - - FP_sub(A,A,P->x); - FP_mul(P->y,A,D); - FP_mul(C,C,B); - FP_sub(P->y,P->y,C); - - BIG_norm(P->x); - BIG_norm(P->y); - BIG_norm(P->z); - -#else - BIG b,A,B,C,D,E,F,G,H,I; - - BIG_rcopy(b,CURVE_B); FP_nres(b); - FP_mul(A,P->z,Q->z); - - FP_sqr(B,A); - FP_mul(C,P->x,Q->x); - FP_mul(D,P->y,Q->y); - FP_mul(E,C,D); FP_mul(E,E,b); - - FP_sub(F,B,E); - FP_add(G,B,E); - - FP_add(C,C,D); - - if (CURVE_A==1) FP_sub(E,D,C); - - FP_add(B,P->x,P->y); - FP_add(D,Q->x,Q->y); - FP_mul(B,B,D); - FP_sub(B,B,C); - FP_mul(B,B,F); - FP_mul(P->x,A,B); - - - if (CURVE_A==1) FP_mul(C,E,G); - if (CURVE_A==-1)FP_mul(C,C,G); - - FP_mul(P->y,A,C); - FP_mul(P->z,F,G); - - BIG_norm(P->x); - BIG_norm(P->y); - BIG_norm(P->z); - -#endif -} - -/* Set P-=Q */ -/* SU=16 */ -void ECP_sub(ECP *P,ECP *Q) -{ - ECP_neg(Q); - ECP_add(P,Q); - ECP_neg(Q); -} - -#endif - - -#if CURVETYPE==WEIERSTRASS -/* normalises array of points. Assumes P[0] is normalised already */ - -static void ECP_multiaffine(int m,ECP P[],BIG work[]) -{ - int i; - BIG t1,t2; - - FP_one(work[0]); - BIG_copy(work[1],P[0].z); - for (i=2;i<m;i++) - FP_mul(work[i],work[i-1],P[i-1].z); - - FP_mul(t1,work[m-1],P[m-1].z); - FP_inv(t1,t1); - - BIG_copy(t2,P[m-1].z); - FP_mul(work[m-1],work[m-1],t1); - - for (i=m-2;;i--) - { - if (i==0) - { - FP_mul(work[0],t1,t2); - break; - } - FP_mul(work[i],work[i],t2); - FP_mul(work[i],work[i],t1); - FP_mul(t2,P[i].z,t2); - } -/* now work[] contains inverses of all Z coordinates */ - - for (i=0;i<m;i++) - { - FP_one(P[i].z); - FP_sqr(t1,work[i]); - FP_mul(P[i].x,P[i].x,t1); - FP_mul(t1,work[i],t1); - FP_mul(P[i].y,P[i].y,t1); - } -} - -#endif - -#if CURVETYPE!=MONTGOMERY -/* constant time multiply by small integer of length bts - use ladder */ -void ECP_pinmul(ECP *P,int e,int bts) -{ - int nb,i,b; - ECP R0,R1; - - ECP_affine(P); - ECP_inf(&R0); - ECP_copy(&R1,P); - - for (i=bts-1;i>=0;i--) - { - b=(e>>i)&1; - ECP_copy(P,&R1); - ECP_add(P,&R0); - ECP_cswap(&R0,&R1,b); - ECP_copy(&R1,P); - ECP_dbl(&R0); - ECP_cswap(&R0,&R1,b); - } - ECP_copy(P,&R0); - ECP_affine(P); -} -#endif - -/* Set P=r*P */ -/* SU=424 */ -void ECP_mul(ECP *P,BIG e) -{ -#if CURVETYPE==MONTGOMERY -/* Montgomery ladder */ - int nb,i,b; - ECP R0,R1,D; - if (ECP_isinf(P)) return; - if (BIG_iszilch(e)) - { - ECP_inf(P); - return; - } - ECP_affine(P); - - ECP_copy(&R0,P); - ECP_copy(&R1,P); - ECP_dbl(&R1); - ECP_copy(&D,P); - - nb=BIG_nbits(e); - for (i=nb-2;i>=0;i--) - { - b=BIG_bit(e,i); - ECP_copy(P,&R1); - ECP_add(P,&R0,&D); - ECP_cswap(&R0,&R1,b); - ECP_copy(&R1,P); - ECP_dbl(&R0); - ECP_cswap(&R0,&R1,b); - } - ECP_copy(P,&R0); - -#else -/* fixed size windows */ - int i,b,nb,m,s,ns; - BIG mt,t; - ECP Q,W[8],C; - sign8 w[1+(NLEN*BASEBITS+3)/4]; -#if CURVETYPE==WEIERSTRASS - BIG work[8]; -#endif - if (ECP_isinf(P)) return; - if (BIG_iszilch(e)) - { - ECP_inf(P); - return; - } - - ECP_affine(P); - -/* precompute table */ - - ECP_copy(&Q,P); - ECP_dbl(&Q); - ECP_copy(&W[0],P); - - for (i=1;i<8;i++) - { - ECP_copy(&W[i],&W[i-1]); - ECP_add(&W[i],&Q); - } - -/* convert the table to affine */ -#if CURVETYPE==WEIERSTRASS - ECP_multiaffine(8,W,work); -#endif - -/* make exponent odd - add 2P if even, P if odd */ - BIG_copy(t,e); - s=BIG_parity(t); - BIG_inc(t,1); BIG_norm(t); ns=BIG_parity(t); BIG_copy(mt,t); BIG_inc(mt,1); BIG_norm(mt); - BIG_cmove(t,mt,s); - ECP_cmove(&Q,P,ns); - ECP_copy(&C,&Q); - - nb=1+(BIG_nbits(t)+3)/4; - -/* convert exponent to signed 4-bit window */ - for (i=0;i<nb;i++) - { - w[i]=BIG_lastbits(t,5)-16; - BIG_dec(t,w[i]); BIG_norm(t); - BIG_fshr(t,4); - } - w[nb]=BIG_lastbits(t,5); - - ECP_copy(P,&W[(w[nb]-1)/2]); - for (i=nb-1;i>=0;i--) - { - ECP_select(&Q,W,w[i]); - ECP_dbl(P); - ECP_dbl(P); - ECP_dbl(P); - ECP_dbl(P); - ECP_add(P,&Q); - } - ECP_sub(P,&C); /* apply correction */ -#endif - ECP_affine(P); -} - -#if CURVETYPE!=MONTGOMERY -/* Set P=eP+fQ double multiplication */ -/* constant time - as useful for GLV method in pairings */ -/* SU=456 */ - -void ECP_mul2(ECP *P,ECP *Q,BIG e,BIG f) -{ - BIG te,tf,mt; - ECP S,T,W[8],C; - sign8 w[1+(NLEN*BASEBITS+1)/2]; - int i,a,b,s,ns,nb; -#if CURVETYPE==WEIERSTRASS - BIG work[8]; -#endif - - ECP_affine(P); - ECP_affine(Q); - - BIG_copy(te,e); - BIG_copy(tf,f); - -/* precompute table */ - ECP_copy(&W[1],P); ECP_sub(&W[1],Q); /* P+Q */ - ECP_copy(&W[2],P); ECP_add(&W[2],Q); /* P-Q */ - ECP_copy(&S,Q); ECP_dbl(&S); /* S=2Q */ - ECP_copy(&W[0],&W[1]); ECP_sub(&W[0],&S); - ECP_copy(&W[3],&W[2]); ECP_add(&W[3],&S); - ECP_copy(&T,P); ECP_dbl(&T); /* T=2P */ - ECP_copy(&W[5],&W[1]); ECP_add(&W[5],&T); - ECP_copy(&W[6],&W[2]); ECP_add(&W[6],&T); - ECP_copy(&W[4],&W[5]); ECP_sub(&W[4],&S); - ECP_copy(&W[7],&W[6]); ECP_add(&W[7],&S); - -#if CURVETYPE==WEIERSTRASS - ECP_multiaffine(8,W,work); -#endif - -/* if multiplier is odd, add 2, else add 1 to multiplier, and add 2P or P to correction */ - - s=BIG_parity(te); - BIG_inc(te,1); BIG_norm(te); ns=BIG_parity(te); BIG_copy(mt,te); BIG_inc(mt,1); BIG_norm(mt); - BIG_cmove(te,mt,s); - ECP_cmove(&T,P,ns); - ECP_copy(&C,&T); - - s=BIG_parity(tf); - BIG_inc(tf,1); BIG_norm(tf); ns=BIG_parity(tf); BIG_copy(mt,tf); BIG_inc(mt,1); BIG_norm(mt); - BIG_cmove(tf,mt,s); - ECP_cmove(&S,Q,ns); - ECP_add(&C,&S); - - BIG_add(mt,te,tf); BIG_norm(mt); - nb=1+(BIG_nbits(mt)+1)/2; - -/* convert exponent to signed 2-bit window */ - for (i=0;i<nb;i++) - { - a=BIG_lastbits(te,3)-4; - BIG_dec(te,a); BIG_norm(te); - BIG_fshr(te,2); - b=BIG_lastbits(tf,3)-4; - BIG_dec(tf,b); BIG_norm(tf); - BIG_fshr(tf,2); - w[i]=4*a+b; - } - w[nb]=(4*BIG_lastbits(te,3)+BIG_lastbits(tf,3)); - - ECP_copy(P,&W[(w[nb]-1)/2]); - for (i=nb-1;i>=0;i--) - { - ECP_select(&T,W,w[i]); - ECP_dbl(P); - ECP_dbl(P); - ECP_add(P,&T); - } - ECP_sub(P,&C); /* apply correction */ - ECP_affine(P); -} - -#endif - -#ifdef HAS_MAIN - -int main() -{ - int i; - ECP G,P; - csprng RNG; - BIG r,s,x,y,b,m,w,q; - BIG_rcopy(x,CURVE_Gx); -#if CURVETYPE!=MONTGOMERY - BIG_rcopy(y,CURVE_Gy); -#endif - BIG_rcopy(m,Modulus); - - printf("x= ");BIG_output(x); printf("\n"); -#if CURVETYPE!=MONTGOMERY - printf("y= ");BIG_output(y); printf("\n"); -#endif - RNG_seed(&RNG,3,"abc"); - -#if CURVETYPE!=MONTGOMERY - ECP_set(&G,x,y); -#else - ECP_set(&G,x); -#endif - if (ECP_isinf(&G)) printf("Failed to set - point not on curve\n"); - else printf("set success\n"); - - ECP_output(&G); - - BIG_rcopy(r,CURVE_Order); //BIG_dec(r,7); - printf("r= ");BIG_output(r); printf("\n"); - - ECP_copy(&P,&G); - - ECP_mul(&P,r); - - ECP_output(&P); -//exit(0); - BIG_randomnum(w,&RNG); - BIG_mod(w,r); - - ECP_copy(&P,&G); - ECP_mul(&P,w); - - ECP_output(&P); - - return 0; -} - -#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/ecp2.c ---------------------------------------------------------------------- diff --git a/c/ecp2.c b/c/ecp2.c deleted file mode 100755 index 5ebc588..0000000 --- a/c/ecp2.c +++ /dev/null @@ -1,666 +0,0 @@ -/* -Licensed to the Apache Software Foundation (ASF) under one -or more contributor license agreements. See the NOTICE file -distributed with this work for additional information -regarding copyright ownership. The ASF licenses this file -to you under the Apache License, Version 2.0 (the -"License"); you may not use this file except in compliance -with the License. You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - -Unless required by applicable law or agreed to in writing, -software distributed under the License is distributed on an -"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY -KIND, either express or implied. See the License for the -specific language governing permissions and limitations -under the License. -*/ - -/* AMCL Weierstrass elliptic curve functions over FP2 */ -/* SU=m, m is Stack Usage */ - -#include "amcl.h" - -int ECP2_isinf(ECP2 *P) -{ - return P->inf; -} - -/* Set P=Q */ -/* SU= 16 */ -void ECP2_copy(ECP2 *P,ECP2 *Q) -{ - P->inf=Q->inf; - FP2_copy(&(P->x),&(Q->x)); - FP2_copy(&(P->y),&(Q->y)); - FP2_copy(&(P->z),&(Q->z)); -} - -/* set P to Infinity */ -/* SU= 8 */ -void ECP2_inf(ECP2 *P) -{ - P->inf=1; - FP2_zero(&(P->x)); FP2_zero(&(P->y)); FP2_zero(&(P->z)); -} - -/* Conditional move Q to P dependant on d */ -static void ECP2_cmove(ECP2 *P,ECP2 *Q,int d) -{ - FP2_cmove(&(P->x),&(Q->x),d); - FP2_cmove(&(P->y),&(Q->y),d); - FP2_cmove(&(P->z),&(Q->z),d); - d=~(d-1); - P->inf^=(P->inf^Q->inf)&d; -} - -/* return 1 if b==c, no branching */ -static int teq(sign32 b,sign32 c) -{ - sign32 x=b^c; - x-=1; // if x=0, x now -1 - return (int)((x>>31)&1); -} - -/* Constant time select from pre-computed table */ -static void ECP2_select(ECP2 *P,ECP2 W[],sign32 b) -{ - ECP2 MP; - sign32 m=b>>31; - sign32 babs=(b^m)-m; - - babs=(babs-1)/2; - - ECP2_cmove(P,&W[0],teq(babs,0)); // conditional move - ECP2_cmove(P,&W[1],teq(babs,1)); - ECP2_cmove(P,&W[2],teq(babs,2)); - ECP2_cmove(P,&W[3],teq(babs,3)); - ECP2_cmove(P,&W[4],teq(babs,4)); - ECP2_cmove(P,&W[5],teq(babs,5)); - ECP2_cmove(P,&W[6],teq(babs,6)); - ECP2_cmove(P,&W[7],teq(babs,7)); - - ECP2_copy(&MP,P); - ECP2_neg(&MP); // minus P - ECP2_cmove(P,&MP,(int)(m&1)); -} - -/* return 1 if P==Q, else 0 */ -/* SU= 312 */ -int ECP2_equals(ECP2 *P,ECP2 *Q) -{ - FP2 pz2,qz2,a,b; - if (P->inf && Q->inf) return 1; - if (P->inf || Q->inf) return 0; - - FP2_sqr(&pz2,&(P->z)); FP2_sqr(&qz2,&(Q->z)); - - FP2_mul(&a,&(P->x),&qz2); - FP2_mul(&b,&(Q->x),&pz2); - if (!FP2_equals(&a,&b)) return 0; - - FP2_mul(&a,&(P->y),&qz2); - FP2_mul(&a,&a,&(Q->z)); - FP2_mul(&b,&(Q->y),&pz2); - FP2_mul(&b,&b,&(P->z)); - if (!FP2_equals(&a,&b)) return 0; - return 1; -} - -/* Make P affine (so z=1) */ -/* SU= 232 */ -void ECP2_affine(ECP2 *P) -{ - FP2 one,iz,izn; - if (P->inf) return; - - FP2_one(&one); - if (FP2_isunity(&(P->z))) - { - FP2_reduce(&(P->x)); - FP2_reduce(&(P->y)); - return; - } - - FP2_inv(&iz,&(P->z)); - FP2_sqr(&izn,&iz); - FP2_mul(&(P->x),&(P->x),&izn); - FP2_mul(&izn,&izn,&iz); - FP2_mul(&(P->y),&(P->y),&izn); - - FP2_reduce(&(P->x)); - FP2_reduce(&(P->y)); - FP2_copy(&(P->z),&one); -} - -/* extract x, y from point P */ -/* SU= 16 */ -int ECP2_get(FP2 *x,FP2 *y,ECP2 *P) -{ - if (P->inf) return -1; - ECP2_affine(P); - FP2_copy(y,&(P->y)); - FP2_copy(x,&(P->x)); - return 0; -} - -/* SU= 152 */ -/* Output point P */ -void ECP2_output(ECP2 *P) -{ - FP2 x,y; - if (P->inf) - { - printf("Infinity\n"); - return; - } - ECP2_get(&x,&y,P); - printf("(");FP2_output(&x);printf(",");FP2_output(&y);printf(")\n"); -} - -/* SU= 232 */ -void ECP2_outputxyz(ECP2 *P) -{ - FP2 x,y,z; - ECP2 Q; - if (P->inf) - { - printf("Infinity\n"); - return; - } - ECP2_copy(&Q,P); - printf("(");FP2_output(&(Q.x));printf(",");FP2_output(&(Q.y));printf(",");FP2_output(&(Q.z)); printf(")\n"); -} - -/* SU= 168 */ -/* Convert Q to octet string */ -void ECP2_toOctet(octet *W,ECP2 *Q) -{ - FP2 qx,qy; - ECP2_get(&qx,&qy,Q); - FP_redc(qx.a); FP_redc(qx.b); FP_redc(qy.a); FP_redc(qy.b); - W->len=4*MODBYTES; - - BIG_toBytes(&(W->val[0]),qx.a); - BIG_toBytes(&(W->val[MODBYTES]),qx.b); - BIG_toBytes(&(W->val[2*MODBYTES]),qy.a); - BIG_toBytes(&(W->val[3*MODBYTES]),qy.b); -} - -/* SU= 176 */ -/* restore Q from octet string */ -int ECP2_fromOctet(ECP2 *Q,octet *W) -{ - FP2 qx,qy; - BIG_fromBytes(qx.a,&(W->val[0])); - BIG_fromBytes(qx.b,&(W->val[MODBYTES])); - BIG_fromBytes(qy.a,&(W->val[2*MODBYTES])); - BIG_fromBytes(qy.b,&(W->val[3*MODBYTES])); - FP_nres(qx.a); FP_nres(qx.b); FP_nres(qy.a); FP_nres(qy.b); - - if (ECP2_set(Q,&qx,&qy)) return 1; - return 0; -} - -/* SU= 128 */ -/* Calculate RHS of twisted curve equation x^3+B/i */ -void ECP2_rhs(FP2 *rhs,FP2 *x) -{ /* calculate RHS of elliptic curve equation */ - FP2 t; - BIG b; - FP2_sqr(&t,x); - - FP2_mul(rhs,&t,x); - -/* Assuming CURVE_A=0 */ - - BIG_rcopy(b,CURVE_B); - - FP2_from_BIG(&t,b); - - FP2_div_ip(&t); /* IMPORTANT - here we use the SEXTIC twist of the curve */ - - FP2_add(rhs,&t,rhs); - FP2_reduce(rhs); -} - - -/* Set P=(x,y). Return 1 if (x,y) is on the curve, else return 0*/ -/* SU= 232 */ -int ECP2_set(ECP2 *P,FP2 *x,FP2 *y) -{ - FP2 one,rhs,y2; - FP2_copy(&y2,y); - - FP2_sqr(&y2,&y2); - ECP2_rhs(&rhs,x); - - if (!FP2_equals(&y2,&rhs)) - { - - P->inf=1; - return 0; - } - - P->inf=0; - FP2_copy(&(P->x),x); - FP2_copy(&(P->y),y); - - FP2_one(&one); - FP2_copy(&(P->z),&one); - return 1; -} - -/* Set P=(x,y). Return 1 if (x,.) is on the curve, else return 0 */ -/* SU= 232 */ -int ECP2_setx(ECP2 *P,FP2 *x) -{ - FP2 y; - ECP2_rhs(&y,x); - - if (!FP2_sqrt(&y,&y)) - { - P->inf=1; - return 0; - } - - P->inf=0; - FP2_copy(&(P->x),x); - FP2_copy(&(P->y),&y); - FP2_one(&(P->z)); - return 1; -} - -/* Set P=-P */ -/* SU= 8 */ -void ECP2_neg(ECP2 *P) -{ - FP2_neg(&(P->y),&(P->y)); - FP2_norm(&(P->y)); -} - -/* R+=R */ -/* return -1 for Infinity, 0 for addition, 1 for doubling */ -/* SU= 448 */ -int ECP2_dbl(ECP2 *P) -{ - FP2 w1,w7,w8,w2,w3; - if (P->inf) return -1; - - if (FP2_iszilch(&(P->y))) - { - P->inf=1; - return -1; - } - -/* Assuming A=0 */ - FP2_sqr(&w1,&(P->x)); - FP2_imul(&w8,&w1,3); - - FP2_sqr(&w2,&(P->y)); - FP2_mul(&w3,&(P->x),&w2); - FP2_imul(&w3,&w3,4); - - FP2_neg(&w1,&w3); -#if CHUNK<64 - FP2_norm(&w1); -#endif - FP2_sqr(&(P->x),&w8); - FP2_add(&(P->x),&(P->x),&w1); - FP2_add(&(P->x),&(P->x),&w1); - - FP2_norm(&(P->x)); - - if (FP2_isunity(&(P->z))) FP2_copy(&(P->z),&(P->y)); - else FP2_mul(&(P->z),&(P->z),&(P->y)); - FP2_add(&(P->z),&(P->z),&(P->z)); - - FP2_add(&w7,&w2,&w2); - FP2_sqr(&w2,&w7); - - FP2_add(&w2,&w2,&w2); - FP2_sub(&w3,&w3,&(P->x)); - - FP2_mul(&(P->y),&w8,&w3); -//#if CHUNK<64 -// FP2_norm(&w2); -//#endif - FP2_sub(&(P->y),&(P->y),&w2); - - - FP2_norm(&(P->y)); - FP2_norm(&(P->z)); - - return 1; -} - -/* Set P+=Q */ -/* SU= 400 */ -int ECP2_add(ECP2 *P,ECP2 *Q) -{ - int aff; - FP2 B,D,E,C,A; - if (Q->inf) return 0; - if (P->inf) - { - ECP2_copy(P,Q); - return 0; - } - - aff=1; - if (!FP2_isunity(&(Q->z))) aff=0; - - if (!aff) - { - FP2_sqr(&A,&(Q->z)); - FP2_mul(&C,&A,&(Q->z)); - - FP2_sqr(&B,&(P->z)); - FP2_mul(&D,&B,&(P->z)); - - FP2_mul(&A,&(P->x),&A); - FP2_mul(&C,&(P->y),&C); - } - else - { - FP2_copy(&A,&(P->x)); - FP2_copy(&C,&(P->y)); - - FP2_sqr(&B,&(P->z)); - FP2_mul(&D,&B,&(P->z)); - } - - FP2_mul(&B,&(Q->x),&B); FP2_sub(&B,&B,&A); /* B=Qx.z^2-x.Qz^2 */ - FP2_mul(&D,&(Q->y),&D); FP2_sub(&D,&D,&C); /* D=Qy.z^3-y.Qz^3 */ - - if (FP2_iszilch(&B)) - { - if (FP2_iszilch(&D)) - { - ECP2_dbl(P); - return 1; - } - else - { - ECP2_inf(P); - return -1; - } - } - if (!aff) FP2_mul(&(P->z),&(P->z),&(Q->z)); - FP2_mul(&(P->z),&(P->z),&B); - - FP2_sqr(&E,&B); - FP2_mul(&B,&B,&E); - FP2_mul(&A,&A,&E); - - FP2_add(&E,&A,&A); - FP2_add(&E,&E,&B); - - FP2_sqr(&(P->x),&D); - FP2_sub(&(P->x),&(P->x),&E); - - FP2_sub(&A,&A,&(P->x)); - FP2_mul(&(P->y),&A,&D); - FP2_mul(&C,&C,&B); - FP2_sub(&(P->y),&(P->y),&C); - - FP2_norm(&(P->x)); - FP2_norm(&(P->y)); - FP2_norm(&(P->z)); - - return 0; -} - -/* Set P-=Q */ -/* SU= 16 */ -void ECP2_sub(ECP2 *P,ECP2 *Q) -{ - ECP2_neg(Q); - ECP2_add(P,Q); - ECP2_neg(Q); -} - -/* normalises m-array of ECP2 points. Requires work vector of m FP2s */ -/* SU= 200 */ -static void ECP2_multiaffine(int m,ECP2 *P,FP2 *work) -{ - int i; - FP2 t1,t2; - - FP2_one(&work[0]); - FP2_copy(&work[1],&(P[0].z)); - for (i=2;i<m;i++) - FP2_mul(&work[i],&work[i-1],&(P[i-1].z)); - FP2_mul(&t1,&work[m-1],&(P[m-1].z)); - - FP2_inv(&t1,&t1); - - FP2_copy(&t2,&(P[m-1].z)); - FP2_mul(&work[m-1],&work[m-1],&t1); - - for (i=m-2;;i--) - { - if (i==0) - { - FP2_mul(&work[0],&t1,&t2); - break; - } - FP2_mul(&work[i],&work[i],&t2); - FP2_mul(&work[i],&work[i],&t1); - FP2_mul(&t2,&(P[i].z),&t2); - } -/* now work[] contains inverses of all Z coordinates */ - - for (i=0;i<m;i++) - { - FP2_one(&(P[i].z)); - FP2_sqr(&t1,&work[i]); - FP2_mul(&(P[i].x),&(P[i].x),&t1); - FP2_mul(&t1,&work[i],&t1); - FP2_mul(&(P[i].y),&(P[i].y),&t1); - } -} - -/* P*=e */ -/* SU= 280 */ -void ECP2_mul(ECP2 *P,BIG e) -{ -/* fixed size windows */ - int i,b,nb,m,s,ns; - BIG mt,t,r; - ECP2 Q,W[8],C; - sign8 w[1+(NLEN*BASEBITS+3)/4]; - FP2 work[8]; - - if (ECP2_isinf(P)) return; - ECP2_affine(P); - - -/* precompute table */ - - ECP2_copy(&Q,P); - ECP2_dbl(&Q); - ECP2_copy(&W[0],P); - - for (i=1;i<8;i++) - { - ECP2_copy(&W[i],&W[i-1]); - ECP2_add(&W[i],&Q); - } - -/* convert the table to affine */ - - ECP2_multiaffine(8,W,work); - -/* make exponent odd - add 2P if even, P if odd */ - BIG_copy(t,e); - s=BIG_parity(t); - BIG_inc(t,1); BIG_norm(t); ns=BIG_parity(t); BIG_copy(mt,t); BIG_inc(mt,1); BIG_norm(mt); - BIG_cmove(t,mt,s); - ECP2_cmove(&Q,P,ns); - ECP2_copy(&C,&Q); - - nb=1+(BIG_nbits(t)+3)/4; - -/* convert exponent to signed 4-bit window */ - for (i=0;i<nb;i++) - { - w[i]=BIG_lastbits(t,5)-16; - BIG_dec(t,w[i]); BIG_norm(t); - BIG_fshr(t,4); - } - w[nb]=BIG_lastbits(t,5); - - ECP2_copy(P,&W[(w[nb]-1)/2]); - for (i=nb-1;i>=0;i--) - { - ECP2_select(&Q,W,w[i]); - ECP2_dbl(P); - ECP2_dbl(P); - ECP2_dbl(P); - ECP2_dbl(P); - ECP2_add(P,&Q); - } - ECP2_sub(P,&C); /* apply correction */ - ECP2_affine(P); -} - -/* Calculates q.P using Frobenius constant X */ -/* SU= 96 */ -void ECP2_frob(ECP2 *P,FP2 *X) -{ - FP2 X2; - if (P->inf) return; - FP2_sqr(&X2,X); - FP2_conj(&(P->x),&(P->x)); - FP2_conj(&(P->y),&(P->y)); - FP2_conj(&(P->z),&(P->z)); - FP2_reduce(&(P->z)); - - FP2_mul(&(P->x),&X2,&(P->x)); - FP2_mul(&(P->y),&X2,&(P->y)); - FP2_mul(&(P->y),X,&(P->y)); -} - -void ECP2_mul4(ECP2 *P,ECP2 Q[4],BIG u[4]) -{ - int i,j,a[4],nb; - ECP2 W[8],T,C; - BIG mt,t[4]; - FP2 work[8]; - sign8 w[NLEN*BASEBITS+1]; - - for (i=0;i<4;i++) - { - BIG_copy(t[i],u[i]); - ECP2_affine(&Q[i]); - } - -/* precompute table */ - - ECP2_copy(&W[0],&Q[0]); ECP2_sub(&W[0],&Q[1]); /* P-Q */ - ECP2_copy(&W[1],&W[0]); - ECP2_copy(&W[2],&W[0]); - ECP2_copy(&W[3],&W[0]); - ECP2_copy(&W[4],&Q[0]); ECP2_add(&W[4],&Q[1]); /* P+Q */ - ECP2_copy(&W[5],&W[4]); - ECP2_copy(&W[6],&W[4]); - ECP2_copy(&W[7],&W[4]); - - ECP2_copy(&T,&Q[2]); ECP2_sub(&T,&Q[3]); /* R-S */ - ECP2_sub(&W[1],&T); - ECP2_add(&W[2],&T); - ECP2_sub(&W[5],&T); - ECP2_add(&W[6],&T); - ECP2_copy(&T,&Q[2]); ECP2_add(&T,&Q[3]); /* R+S */ - ECP2_sub(&W[0],&T); - ECP2_add(&W[3],&T); - ECP2_sub(&W[4],&T); - ECP2_add(&W[7],&T); - - ECP2_multiaffine(8,W,work); - -/* if multiplier is even add 1 to multiplier, and add P to correction */ - ECP2_inf(&C); - - BIG_zero(mt); - for (i=0;i<4;i++) - { - if (BIG_parity(t[i])==0) - { - BIG_inc(t[i],1); BIG_norm(t[i]); - ECP2_add(&C,&Q[i]); - } - BIG_add(mt,mt,t[i]); BIG_norm(mt); - } - - nb=1+BIG_nbits(mt); - -/* convert exponent to signed 1-bit window */ - for (j=0;j<nb;j++) - { - for (i=0;i<4;i++) - { - a[i]=BIG_lastbits(t[i],2)-2; - BIG_dec(t[i],a[i]); BIG_norm(t[i]); - BIG_fshr(t[i],1); - } - w[j]=8*a[0]+4*a[1]+2*a[2]+a[3]; - } - w[nb]=8*BIG_lastbits(t[0],2)+4*BIG_lastbits(t[1],2)+2*BIG_lastbits(t[2],2)+BIG_lastbits(t[3],2); - - ECP2_copy(P,&W[(w[nb]-1)/2]); - for (i=nb-1;i>=0;i--) - { - ECP2_select(&T,W,w[i]); - ECP2_dbl(P); - ECP2_add(P,&T); - } - ECP2_sub(P,&C); /* apply correction */ - - ECP2_affine(P); -} - -/* - -int main() -{ - int i; - ECP2 G,P; - ECP2 *W; - FP2 x,y,w,z,f; - BIG r,xa,xb,ya,yb; - - BIG_rcopy(xa,CURVE_Pxa); - BIG_rcopy(xb,CURVE_Pxb); - BIG_rcopy(ya,CURVE_Pya); - BIG_rcopy(yb,CURVE_Pyb); - - FP2_from_BIGs(&x,xa,xb); - FP2_from_BIGs(&y,ya,yb); - ECP2_set(&G,&x,&y); - if (G.inf) printf("Failed to set - point not on curve\n"); - else printf("set success\n"); - - ECP2_output(&G); - -// BIG_copy(r,CURVE_Order); - BIG_rcopy(r,Modulus); - - ECP2_copy(&P,&G); - - ECP2_mul(&P,r); - - ECP2_output(&P); - - FP2_gfc(&f,12); - - ECP2_frob(&G,&f); - - ECP2_output(&G); - - return 0; -} - -*/
