http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/ff.c ---------------------------------------------------------------------- diff --git a/c/ff.c b/c/ff.c deleted file mode 100755 index 684a8f3..0000000 --- a/c/ff.c +++ /dev/null @@ -1,1050 +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 Large Finite Field support */ - -#include "amcl.h" - -#define P_MBITS MODBYTES*8 -#define P_MB (P_MBITS%BASEBITS) -#define P_OMASK ((chunk)(-1)<<(P_MBITS%BASEBITS)) -#define P_EXCESS(a) ((a[NLEN-1]&P_OMASK)>>(P_MB)) -#define P_FEXCESS ((chunk)1<<(BASEBITS*NLEN-P_MBITS)) -#define P_TBITS (P_MBITS%BASEBITS) - -/* set x = x mod 2^m */ -static void BIG_mod2m(BIG x,int m) -{ - int i,wd,bt; - chunk msk; -// if (m>=MODBITS) return; - wd=m/BASEBITS; - bt=m%BASEBITS; - msk=((chunk)1<<bt)-1; - x[wd]&=msk; - for (i=wd+1;i<NLEN;i++) x[i]=0; -} - -/* Arazi and Qi inversion mod 256 */ -static int invmod256(int a) -{ - int i,m,U,t1,t2,b,c; - t1=0; - c=(a>>1)&1; - t1+=c; - t1&=1; - t1=2-t1; - t1<<=1; - U=t1+1; - -// i=2 - b=a&3; - t1=U*b; t1>>=2; - c=(a>>2)&3; - t2=(U*c)&3; - t1+=t2; - t1*=U; t1&=3; - t1=4-t1; - t1<<=2; - U+=t1; - -// i=4 - b=a&15; - t1=U*b; t1>>=4; - c=(a>>4)&15; - t2=(U*c)&15; - t1+=t2; - t1*=U; t1&=15; - t1=16-t1; - t1<<=4; - U+=t1; - - return U; -} - -/* a=1/a mod 2^256. This is very fast! */ -void BIG_invmod2m(BIG a) -{ - int i; - BIG U,t1,b,c; - BIG_zero(U); - BIG_inc(U,invmod256(BIG_lastbits(a,8))); - - for (i=8;i<256;i<<=1) - { - BIG_copy(b,a); BIG_mod2m(b,i); // bottom i bits of a - BIG_smul(t1,U,b); BIG_shr(t1,i); // top i bits of U*b - BIG_copy(c,a); BIG_shr(c,i); BIG_mod2m(c,i); // top i bits of a - BIG_smul(b,U,c); BIG_mod2m(b,i); // bottom i bits of U*c - BIG_add(t1,t1,b); - BIG_smul(b,t1,U); BIG_copy(t1,b); // (t1+b)*U - - BIG_mod2m(t1,i); // bottom i bits of (t1+b)*U - - BIG_one(b); BIG_shl(b,i); BIG_sub(t1,b,t1); BIG_norm(t1); - BIG_shl(t1,i); - BIG_add(U,U,t1); - } - BIG_copy(a,U); -} - -/* -void FF_rcopy(BIG x[],const BIG y[],int n) -{ - int i; - for (i=0;i<n;i++) - BIG_rcopy(x[i],y[i]); -} -*/ - -/* x=y */ -void FF_copy(BIG x[],BIG y[],int n) -{ - int i; - for (i=0;i<n;i++) - BIG_copy(x[i],y[i]); -} - -/* x=y<<n */ -static void FF_dsucopy(BIG x[],BIG y[],int n) -{ - int i; - for (i=0;i<n;i++) - { - BIG_copy(x[n+i],y[i]); - BIG_zero(x[i]); - } -} - -/* x=y */ -static void FF_dscopy(BIG x[],BIG y[],int n) -{ - int i; - for (i=0;i<n;i++) - { - BIG_copy(x[i],y[i]); - BIG_zero(x[n+i]); - } -} - -/* x=y>>n */ -static void FF_sducopy(BIG x[],BIG y[],int n) -{ - int i; - for (i=0;i<n;i++) - BIG_copy(x[i],y[n+i]); -} - -/* set to zero */ -void FF_zero(BIG x[],int n) -{ - int i; - for (i=0;i<n;i++) - BIG_zero(x[i]); -} - -/* test equals 0 */ -int FF_iszilch(BIG x[],int n) -{ - int i; - for (i=0;i<n;i++) - if (!BIG_iszilch(x[i])) return 0; - return 1; -} - -/* shift right by 256-bit words */ -static void FF_shrw(BIG a[],int n) -{ - int i; - for (i=0;i<n;i++) {BIG_copy(a[i],a[i+n]);BIG_zero(a[i+n]);} -} - -/* shift left by 256-bit words */ -static void FF_shlw(BIG a[],int n) -{ - int i; - for (i=0;i<n;i++) {BIG_copy(a[i+n],a[i]); BIG_zero(a[i]);} -} - -/* extract last bit */ -int FF_parity(BIG x[]) -{ - return BIG_parity(x[0]); -} - -/* extract last m bits */ -int FF_lastbits(BIG x[],int m) -{ - return BIG_lastbits(x[0],m); -} - -/* x=1 */ -void FF_one(BIG x[],int n) -{ - int i; - BIG_one(x[0]); - for (i=1;i<n;i++) - BIG_zero(x[i]); -} - -/* x=m, where m is 32-bit int */ -void FF_init(BIG x[],sign32 m,int n) -{ - int i; - BIG_zero(x[0]); -#if CHUNK<64 - x[0][0]=(chunk)(m&MASK); - x[0][1]=(chunk)(m>>BASEBITS); -#else - x[0][0]=(chunk)m; -#endif - for (i=1;i<n;i++) - BIG_zero(x[i]); -} - -/* compare x and y - must be normalised */ -int FF_comp(BIG x[],BIG y[],int n) -{ - int i,j; - for (i=n-1;i>=0;i--) - { - j=BIG_comp(x[i],y[i]); - if (j!=0) return j; - } - return 0; -} - -/* recursive add */ -static void FF_radd(BIG z[],int zp,BIG x[],int xp,BIG y[],int yp,int n) -{ - int i; - for (i=0;i<n;i++) - BIG_add(z[zp+i],x[xp+i],y[yp+i]); -} - -/* recursive inc */ -static void FF_rinc(BIG z[],int zp,BIG y[],int yp,int n) -{ - int i; - for (i=0;i<n;i++) - BIG_add(z[zp+i],z[zp+i],y[yp+i]); -} - -/* recursive sub */ -static void FF_rsub(BIG z[],int zp,BIG x[],int xp,BIG y[],int yp,int n) -{ - int i; - for (i=0;i<n;i++) - BIG_sub(z[zp+i],x[xp+i],y[yp+i]); -} - -/* recursive dec */ -static void FF_rdec(BIG z[],int zp,BIG y[],int yp,int n) -{ - int i; - for (i=0;i<n;i++) - BIG_sub(z[zp+i],z[zp+i],y[yp+i]); -} - -/* simple add */ -void FF_add(BIG z[],BIG x[],BIG y[],int n) -{ - int i; - for (i=0;i<n;i++) - BIG_add(z[i],x[i],y[i]); -} - -/* simple sub */ -void FF_sub(BIG z[],BIG x[],BIG y[],int n) -{ - int i; - for (i=0;i<n;i++) - BIG_sub(z[i],x[i],y[i]); -} - -/* increment/decrement by a small integer */ -void FF_inc(BIG x[],int m,int n) -{ - BIG_inc(x[0],m); - FF_norm(x,n); -} - -void FF_dec(BIG x[],int m,int n) -{ - BIG_dec(x[0],m); - FF_norm(x,n); -} - -/* normalise - but hold any overflow in top part unless n<0 */ -static void FF_rnorm(BIG z[],int zp,int n) -{ - int i,trunc=0; - chunk carry; - if (n<0) - { /* -v n signals to do truncation */ - n=-n; - trunc=1; - } - for (i=0;i<n-1;i++) - { - carry=BIG_norm(z[zp+i]); - z[zp+i][NLEN-1]^=carry<<P_TBITS; /* remove it */ - z[zp+i+1][0]+=carry; - } - carry=BIG_norm(z[zp+n-1]); - if (trunc) z[zp+n-1][NLEN-1]^=carry<<P_TBITS; -} - -void FF_norm(BIG z[],int n) -{ - FF_rnorm(z,0,n); -} - -/* shift left by one bit */ -void FF_shl(BIG x[],int n) -{ - int i; - chunk carry,delay_carry=0; - for (i=0;i<n-1;i++) - { - carry=BIG_fshl(x[i],1); - x[i][0]|=delay_carry; - x[i][NLEN-1]^=carry<<P_TBITS; - delay_carry=carry; - } - BIG_fshl(x[n-1],1); - x[n-1][0]|=delay_carry; -} - -/* shift right by one bit */ -void FF_shr(BIG x[],int n) -{ - int i; - chunk carry; - for (i=n-1;i>0;i--) - { - carry=BIG_fshr(x[i],1); - x[i-1][NLEN-1]|=carry<<P_TBITS; - } - BIG_fshr(x[0],1); -} - -void FF_output(BIG x[],int n) -{ - int i; - FF_norm(x,n); - for (i=n-1;i>=0;i--) - { - BIG_output(x[i]);// printf(" "); - } -} - -/* Convert FFs to/from octet strings */ -void FF_toOctet(octet *w,BIG x[],int n) -{ - int i; - w->len=n*MODBYTES; - for (i=0;i<n;i++) - { - BIG_toBytes(&(w->val[(n-i-1)*MODBYTES]),x[i]); - } -} - -void FF_fromOctet(BIG x[],octet *w,int n) -{ - int i; - for (i=0;i<n;i++) - { - BIG_fromBytes(x[i],&(w->val[(n-i-1)*MODBYTES])); - } -} - -/* in-place swapping using xor - side channel resistant */ -static void FF_cswap(BIG a[],BIG b[],int d,int n) -{ - int i; - for (i=0;i<n;i++) - BIG_cswap(a[i],b[i],d); - return; -} - -/* z=x*y, t is workspace */ -static void FF_karmul(BIG z[],int zp,BIG x[],int xp,BIG y[],int yp,BIG t[],int tp,int n) -{ - int nd2; - if (n==1) - { - BIG_mul(t[tp],x[xp],y[yp]); - BIG_split(z[zp+1],z[zp],t[tp],256); - return; - } - - nd2=n/2; - FF_radd(z,zp,x,xp,x,xp+nd2,nd2); -#if CHUNK<64 - FF_rnorm(z,zp,nd2); /* needs this if recursion level too deep */ -#endif - FF_radd(z,zp+nd2,y,yp,y,yp+nd2,nd2); -#if CHUNK<64 - FF_rnorm(z,zp+nd2,nd2); -#endif - FF_karmul(t,tp,z,zp,z,zp+nd2,t,tp+n,nd2); - FF_karmul(z,zp,x,xp,y,yp,t,tp+n,nd2); - FF_karmul(z,zp+n,x,xp+nd2,y,yp+nd2,t,tp+n,nd2); - FF_rdec(t,tp,z,zp,n); - FF_rdec(t,tp,z,zp+n,n); - FF_rinc(z,zp+nd2,t,tp,n); - FF_rnorm(z,zp,2*n); -} - -static void FF_karsqr(BIG z[],int zp,BIG x[],int xp,BIG t[],int tp,int n) -{ - int nd2; - if (n==1) - { - BIG_sqr(t[tp],x[xp]); - BIG_split(z[zp+1],z[zp],t[tp],256); - return; - } - nd2=n/2; - FF_karsqr(z,zp,x,xp,t,tp+n,nd2); - FF_karsqr(z,zp+n,x,xp+nd2,t,tp+n,nd2); - FF_karmul(t,tp,x,xp,x,xp+nd2,t,tp+n,nd2); - FF_rinc(z,zp+nd2,t,tp,n); - FF_rinc(z,zp+nd2,t,tp,n); - - FF_rnorm(z,zp+nd2,n); /* was FF_rnorm(z,zp,2*n) */ -} - -static void FF_karmul_lower(BIG z[],int zp,BIG x[],int xp,BIG y[],int yp,BIG t[],int tp,int n) -{ /* Calculates Least Significant bottom half of x*y */ - int nd2; - if (n==1) - { /* only calculate bottom half of product */ - // BIG_mul(d,x[xp],y[yp]); - // BIG_split(z[zp],z[zp],d,256); - BIG_smul(z[zp],x[xp],y[yp]); - return; - } - nd2=n/2; - - FF_karmul(z,zp,x,xp,y,yp,t,tp+n,nd2); - FF_karmul_lower(t,tp,x,xp+nd2,y,yp,t,tp+n,nd2); - FF_rinc(z,zp+nd2,t,tp,nd2); - FF_karmul_lower(t,tp,x,xp,y,yp+nd2,t,tp+n,nd2); - FF_rinc(z,zp+nd2,t,tp,nd2); - FF_rnorm(z,zp+nd2,-nd2); /* truncate it */ -} - -static void FF_karmul_upper(BIG z[],BIG x[],BIG y[],BIG t[],int n) -{ /* Calculates Most Significant upper half of x*y, given lower part */ - int i,nd2; - - nd2=n/2; - FF_radd(z,n,x,0,x,nd2,nd2); - FF_radd(z,n+nd2,y,0,y,nd2,nd2); - - FF_karmul(t,0,z,n+nd2,z,n,t,n,nd2); /* t = (a0+a1)(b0+b1) */ - FF_karmul(z,n,x,nd2,y,nd2,t,n,nd2); /* z[n]= a1*b1 */ - /* z[0-nd2]=l(a0b0) z[nd2-n]= h(a0b0)+l(t)-l(a0b0)-l(a1b1) */ - FF_rdec(t,0,z,n,n); /* t=t-a1b1 */ - FF_rinc(z,nd2,z,0,nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */ - FF_rdec(z,nd2,t,0,nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */ - FF_rnorm(z,0,-n); /* a0b0 now in z - truncate it */ - FF_rdec(t,0,z,0,n); /* (a0+a1)(b0+b1) - a0b0 */ - FF_rinc(z,nd2,t,0,n); - - FF_rnorm(z,nd2,n); -} - -/* z=x*y */ -void FF_mul(BIG z[],BIG x[],BIG y[],int n) -{ -#ifndef C99 - BIG t[2*FFLEN]; -#else - BIG t[2*n]; -#endif - FF_karmul(z,0,x,0,y,0,t,0,n); -} - -/* return low part of product */ -static void FF_lmul(BIG z[],BIG x[],BIG y[],int n) -{ -#ifndef C99 - BIG t[2*FFLEN]; -#else - BIG t[2*n]; -#endif - FF_karmul_lower(z,0,x,0,y,0,t,0,n); -} - -/* Set b=b mod c */ -void FF_mod(BIG b[],BIG c[],int n) -{ - int k=0; - - FF_norm(b,n); - if (FF_comp(b,c,n)<0) - return; - do - { - FF_shl(c,n); - k++; - } while (FF_comp(b,c,n)>=0); - - while (k>0) - { - FF_shr(c,n); - if (FF_comp(b,c,n)>=0) - { - FF_sub(b,b,c,n); - FF_norm(b,n); - } - k--; - } -} - -/* z=x^2 */ -void FF_sqr(BIG z[],BIG x[],int n) -{ -#ifndef C99 - BIG t[2*FFLEN]; -#else - BIG t[2*n]; -#endif - FF_karsqr(z,0,x,0,t,0,n); -} - -/* r=t mod modulus, N is modulus, ND is Montgomery Constant */ -static void FF_reduce(BIG r[],BIG T[],BIG N[],BIG ND[],int n) -{ /* fast karatsuba Montgomery reduction */ -#ifndef C99 - BIG t[2*FFLEN]; - BIG m[FFLEN]; -#else - BIG t[2*n]; - BIG m[n]; -#endif - FF_sducopy(r,T,n); /* keep top half of T */ - FF_karmul_lower(m,0,T,0,ND,0,t,0,n); /* m=T.(1/N) mod R */ - - FF_karmul_upper(T,N,m,t,n); /* T=mN */ - FF_sducopy(m,T,n); - - FF_add(r,r,N,n); - FF_sub(r,r,m,n); - FF_norm(r,n); -} - - -/* Set r=a mod b */ -/* a is of length - 2*n */ -/* r,b is of length - n */ -void FF_dmod(BIG r[],BIG a[],BIG b[],int n) -{ - int len,k; -#ifndef C99 - BIG m[2*FFLEN]; - BIG x[2*FFLEN]; -#else - BIG m[2*n]; - BIG x[2*n]; -#endif - FF_copy(x,a,2*n); - FF_norm(x,2*n); - FF_dsucopy(m,b,n); k=256*n; - - while (k>0) - { - // len=2*n-((256*n-k)/256); // reduce length as numbers get smaller? - FF_shr(m,2*n); - - if (FF_comp(x,m,2*n)>=0) - { - FF_sub(x,x,m,2*n); - FF_norm(x,2*n); - } - - k--; - } - FF_copy(r,x,n); - FF_mod(r,b,n); -} - -/* Set r=1/a mod p. Binary method - a<p on entry */ - -void FF_invmodp(BIG r[],BIG a[],BIG p[],int n) -{ -#ifndef C99 - BIG u[FFLEN],v[FFLEN],x1[FFLEN],x2[FFLEN],t[FFLEN],one[FFLEN]; -#else - BIG u[n],v[n],x1[n],x2[n],t[n],one[n]; -#endif - FF_copy(u,a,n); - FF_copy(v,p,n); - FF_one(one,n); - FF_copy(x1,one,n); - FF_zero(x2,n); - -// reduce n in here as well! - while (FF_comp(u,one,n)!=0 && FF_comp(v,one,n)!=0) - { - while (FF_parity(u)==0) - { - FF_shr(u,n); - if (FF_parity(x1)!=0) - { - FF_add(x1,p,x1,n); - FF_norm(x1,n); - } - FF_shr(x1,n); - } - while (FF_parity(v)==0) - { - FF_shr(v,n); - if (FF_parity(x2)!=0) - { - FF_add(x2,p,x2,n); - FF_norm(x2,n); - } - FF_shr(x2,n); - } - if (FF_comp(u,v,n)>=0) - { - - FF_sub(u,u,v,n); - FF_norm(u,n); - if (FF_comp(x1,x2,n)>=0) FF_sub(x1,x1,x2,n); - else - { - FF_sub(t,p,x2,n); - FF_add(x1,x1,t,n); - } - FF_norm(x1,n); - } - else - { - FF_sub(v,v,u,n); - FF_norm(v,n); - if (FF_comp(x2,x1,n)>=0) FF_sub(x2,x2,x1,n); - else - { - FF_sub(t,p,x1,n); - FF_add(x2,x2,t,n); - } - FF_norm(x2,n); - } - } - if (FF_comp(u,one,n)==0) - FF_copy(r,x1,n); - else - FF_copy(r,x2,n); -} - -/* nesidue mod m */ -static void FF_nres(BIG a[],BIG m[],int n) -{ -#ifndef C99 - BIG d[2*FFLEN]; -#else - BIG d[2*n]; -#endif - - FF_dsucopy(d,a,n); - FF_dmod(a,d,m,n); -} - -static void FF_redc(BIG a[],BIG m[],BIG ND[],int n) -{ -#ifndef C99 - BIG d[2*FFLEN]; -#else - BIG d[2*n]; -#endif - FF_mod(a,m,n); - FF_dscopy(d,a,n); - FF_reduce(a,d,m,ND,n); - FF_mod(a,m,n); -} - -/* U=1/a mod 2^m - Arazi & Qi */ -static void FF_invmod2m(BIG U[],BIG a[],int n) -{ - int i; -#ifndef C99 - BIG t1[FFLEN],b[FFLEN],c[FFLEN]; -#else - BIG t1[n],b[n],c[n]; -#endif - FF_zero(U,n); - BIG_copy(U[0],a[0]); - BIG_invmod2m(U[0]); - - for (i=1;i<n;i<<=1) - { - FF_copy(b,a,i); - FF_mul(t1,U,b,i); FF_shrw(t1,i); // top half to bottom half, top half=0 - - FF_copy(c,a,2*i); FF_shrw(c,i); // top half of c - FF_lmul(b,U,c,i); // should set top half of b=0 - FF_add(t1,t1,b,i); FF_norm(t1,2*i); - FF_lmul(b,t1,U,i); FF_copy(t1,b,i); - FF_one(b,i); FF_shlw(b,i); - FF_sub(t1,b,t1,2*i); FF_norm(t1,2*i); - FF_shlw(t1,i); - FF_add(U,U,t1,2*i); - } - FF_norm(U,n); -} - -void FF_random(BIG x[],csprng *rng,int n) -{ - int i; - for (i=0;i<n;i++) - { - BIG_random(x[i],rng); - } -/* make sure top bit is 1 */ - while (BIG_nbits(x[n-1])<MODBYTES*8) BIG_random(x[n-1],rng); -} - -/* generate random x mod p */ -void FF_randomnum(BIG x[],BIG p[],csprng *rng,int n) -{ - int i; -#ifndef C99 - BIG d[2*FFLEN]; -#else - BIG d[2*n]; -#endif - for (i=0;i<2*n;i++) - { - BIG_random(d[i],rng); - } - FF_dmod(x,d,p,n); -} - -static void FF_modmul(BIG z[],BIG x[],BIG y[],BIG p[],BIG ND[],int n) -{ -#ifndef C99 - BIG d[2*FFLEN]; -#else - BIG d[2*n]; -#endif - chunk ex=P_EXCESS(x[n-1]); - chunk ey=P_EXCESS(y[n-1]); - if ((ex+1)*(ey+1)+1>=P_FEXCESS) - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it %d %d\n",ex,ey); -#endif - FF_mod(x,p,n); - } - FF_mul(d,x,y,n); - FF_reduce(z,d,p,ND,n); -} - -static void FF_modsqr(BIG z[],BIG x[],BIG p[],BIG ND[],int n) -{ -#ifndef C99 - BIG d[2*FFLEN]; -#else - BIG d[2*n]; -#endif - chunk ex=P_EXCESS(x[n-1]); - if ((ex+1)*(ex+1)+1>=P_FEXCESS) - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it %d\n",ex); -#endif - FF_mod(x,p,n); - } - FF_sqr(d,x,n); - FF_reduce(z,d,p,ND,n); -} - -/* r=x^e mod p using side-channel resistant Montgomery Ladder, for large e */ -void FF_skpow(BIG r[],BIG x[],BIG e[],BIG p[],int n) -{ - int i,b; -#ifndef C99 - BIG R0[FFLEN],R1[FFLEN],ND[FFLEN]; -#else - BIG R0[n],R1[n],ND[n]; -#endif - FF_invmod2m(ND,p,n); - - FF_one(R0,n); - FF_copy(R1,x,n); - FF_nres(R0,p,n); - FF_nres(R1,p,n); - - for (i=8*MODBYTES*n-1;i>=0;i--) - { - b=BIG_bit(e[i/256],i%256); - FF_modmul(r,R0,R1,p,ND,n); - - FF_cswap(R0,R1,b,n); - FF_modsqr(R0,R0,p,ND,n); - - FF_copy(R1,r,n); - FF_cswap(R0,R1,b,n); - } - FF_copy(r,R0,n); - FF_redc(r,p,ND,n); -} - -/* r=x^e mod p using side-channel resistant Montgomery Ladder, for short e */ -void FF_skspow(BIG r[],BIG x[],BIG e,BIG p[],int n) -{ - int i,b; -#ifndef C99 - BIG R0[FFLEN],R1[FFLEN],ND[FFLEN]; -#else - BIG R0[n],R1[n],ND[n]; -#endif - FF_invmod2m(ND,p,n); - FF_one(R0,n); - FF_copy(R1,x,n); - FF_nres(R0,p,n); - FF_nres(R1,p,n); - for (i=8*MODBYTES-1;i>=0;i--) - { - b=BIG_bit(e,i); - FF_modmul(r,R0,R1,p,ND,n); - FF_cswap(R0,R1,b,n); - FF_modsqr(R0,R0,p,ND,n); - FF_copy(R1,r,n); - FF_cswap(R0,R1,b,n); - } - FF_copy(r,R0,n); - FF_redc(r,p,ND,n); -} - -/* raise to an integer power - right-to-left method */ -void FF_power(BIG r[],BIG x[],int e,BIG p[],int n) -{ - int i,b,f=1; -#ifndef C99 - BIG w[FFLEN],ND[FFLEN]; -#else - BIG w[n],ND[n]; -#endif - FF_invmod2m(ND,p,n); - - FF_copy(w,x,n); - FF_nres(w,p,n); - - if (e==2) - { - FF_modsqr(r,w,p,ND,n); - } - else for (;;) - { - if (e%2==1) - { - if (f) FF_copy(r,w,n); - else FF_modmul(r,r,w,p,ND,n); - f=0; - } - e>>=1; - if (e==0) break; - FF_modsqr(w,w,p,ND,n); - } - - FF_redc(r,p,ND,n); -} - -/* r=x^e mod p, faster but not side channel resistant */ -void FF_pow(BIG r[],BIG x[],BIG e[],BIG p[],int n) -{ - int i,b; -#ifndef C99 - BIG w[FFLEN],ND[FFLEN]; -#else - BIG w[n],ND[n]; -#endif - FF_invmod2m(ND,p,n); - FF_copy(w,x,n); - FF_one(r,n); - FF_nres(r,p,n); - FF_nres(w,p,n); - for (i=8*MODBYTES*n-1;i>=0;i--) - { - FF_modsqr(r,r,p,ND,n); - b=BIG_bit(e[i/256],i%256); - if (b==1) FF_modmul(r,r,w,p,ND,n); - } - FF_redc(r,p,ND,n); -} - -/* double exponentiation r=x^e.y^f mod p */ -void FF_pow2(BIG r[],BIG x[],BIG e,BIG y[],BIG f,BIG p[],int n) -{ - int i,eb,fb; -#ifndef C99 - BIG xn[FFLEN],yn[FFLEN],xy[FFLEN],ND[FFLEN]; -#else - BIG xn[n],yn[n],xy[n],ND[n]; -#endif - FF_invmod2m(ND,p,n); - FF_copy(xn,x,n); - FF_copy(yn,y,n); - FF_nres(xn,p,n); - FF_nres(yn,p,n); - FF_modmul(xy,xn,yn,p,ND,n); - FF_one(r,n); - FF_nres(r,p,n); - - for (i=8*MODBYTES-1;i>=0;i--) - { - eb=BIG_bit(e,i); - fb=BIG_bit(f,i); - FF_modsqr(r,r,p,ND,n); - if (eb==1) - { - if (fb==1) FF_modmul(r,r,xy,p,ND,n); - else FF_modmul(r,r,xn,p,ND,n); - } - else - { - if (fb==1) FF_modmul(r,r,yn,p,ND,n); - } - } - FF_redc(r,p,ND,n); -} - -static sign32 igcd(sign32 x,sign32 y) -{ /* integer GCD, returns GCD of x and y */ - sign32 r; - if (y==0) return x; - while ((r=x%y)!=0) - x=y,y=r; - return y; -} - -/* quick and dirty check for common factor with s */ -int FF_cfactor(BIG w[],sign32 s,int n) -{ - int r; - sign32 g; -#ifndef C99 - BIG x[FFLEN],y[FFLEN]; -#else - BIG x[n],y[n]; -#endif - FF_init(y,s,n); - FF_copy(x,w,n); - FF_norm(x,n); - -// if (FF_parity(x)==0) return 1; - do - { - FF_sub(x,x,y,n); - FF_norm(x,n); - while (!FF_iszilch(x,n) && FF_parity(x)==0) FF_shr(x,n); - } - while (FF_comp(x,y,n)>0); -#if CHUNK<32 - g=x[0][0]+((sign32)(x[0][1])<<BASEBITS); -#else - g=(sign32)x[0][0]; -#endif - r=igcd(s,g); -//printf("r= %d\n",r); - if (r>1) return 1; - return 0; -} - -/* Miller-Rabin test for primality. Slow. */ -int FF_prime(BIG p[],csprng *rng,int n) -{ - int i,j,loop,s=0; -#ifndef C99 - BIG d[FFLEN],x[FFLEN],unity[FFLEN],nm1[FFLEN]; -#else - BIG d[n],x[n],unity[n],nm1[n]; -#endif - sign32 sf=4849845;/* 3*5*.. *19 */ - - FF_norm(p,n); - if (FF_cfactor(p,sf,n)) return 0; - - FF_one(unity,n); - FF_sub(nm1,p,unity,n); - FF_norm(nm1,n); - FF_copy(d,nm1,n); - - while (FF_parity(d)==0) - { - FF_shr(d,n); - s++; - } - if (s==0) return 0; - - for (i=0;i<10;i++) - { - FF_randomnum(x,p,rng,n); - FF_pow(x,x,d,p,n); - if (FF_comp(x,unity,n)==0 || FF_comp(x,nm1,n)==0) continue; - loop=0; - for (j=1;j<s;j++) - { - FF_power(x,x,2,p,n); - if (FF_comp(x,unity,n)==0) return 0; - if (FF_comp(x,nm1,n)==0 ) {loop=1; break;} - } - if (loop) continue; - return 0; - } - return 1; -} - -/* -BIG P[4]= {{0x1670957,0x1568CD3C,0x2595E5,0xEED4F38,0x1FC9A971,0x14EF7E62,0xA503883,0x9E1E05E,0xBF59E3},{0x1844C908,0x1B44A798,0x3A0B1E7,0xD1B5B4E,0x1836046F,0x87E94F9,0x1D34C537,0xF7183B0,0x46D07},{0x17813331,0x19E28A90,0x1473A4D6,0x1CACD01F,0x1EEA8838,0xAF2AE29,0x1F85292A,0x1632585E,0xD945E5},{0x919F5EF,0x1567B39F,0x19F6AD11,0x16CE47CF,0x9B36EB1,0x35B7D3,0x483B28C,0xCBEFA27,0xB5FC21}}; - -int main() -{ - int i; - BIG p[4],e[4],x[4],r[4]; - csprng rng; - char raw[100]; - for (i=0;i<100;i++) raw[i]=i; - RAND_seed(&rng,100,raw); - - - FF_init(x,3,4); - - FF_copy(p,P,4); - FF_copy(e,p,4); - FF_dec(e,1,4); - FF_norm(e,4); - - - - printf("p= ");FF_output(p,4); printf("\n"); - if (FF_prime(p,&rng,4)) printf("p is a prime\n"); - printf("e= ");FF_output(e,4); printf("\n"); - - FF_skpow(r,x,e,p,4); - printf("r= ");FF_output(r,4); printf("\n"); -} - -*/
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/fp.c ---------------------------------------------------------------------- diff --git a/c/fp.c b/c/fp.c deleted file mode 100755 index aa858cc..0000000 --- a/c/fp.c +++ /dev/null @@ -1,559 +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 mod p functions */ -/* Small Finite Field arithmetic */ -/* SU=m, SU is Stack Usage (NOT_SPECIAL Modulus) */ - -#include "amcl.h" - -/* Fast Modular Reduction Methods */ - -/* r=d mod m */ -/* d MUST be normalised */ -/* Products must be less than pR in all cases !!! */ -/* So when multiplying two numbers, their product *must* be less than MODBITS+BASEBITS*NLEN */ -/* Results *may* be one bit bigger than MODBITS */ - -#if MODTYPE == PSEUDO_MERSENNE -/* r=d mod m */ - -void FP_nres(BIG a) {} - -void FP_redc(BIG a) {} - -/* reduce a DBIG to a BIG exploiting the special form of the modulus */ -void FP_mod(BIG r,DBIG d) -{ - BIG t,b,m; - chunk v,tw; - BIG_split(t,b,d,MODBITS); - -/* Note that all of the excess gets pushed into t. So if squaring a value with a 4-bit excess, this results in - t getting all 8 bits of the excess product! So products must be less than pR which is Montgomery compatible */ - - if (MConst < NEXCESS) - { - BIG_imul(t,t,MConst); - - BIG_norm(t); - tw=t[NLEN-1]; - t[NLEN-1]&=TMASK; - t[0]+=MConst*((tw>>TBITS)); - } - else - { - v=BIG_pmul(t,t,MConst); - tw=t[NLEN-1]; - t[NLEN-1]&=TMASK; -#if CHUNK == 16 - t[1]+=muladd(MConst,((tw>>TBITS)+(v<<(BASEBITS-TBITS))),0,&t[0]); -#else - t[0]+=MConst*((tw>>TBITS)+(v<<(BASEBITS-TBITS))); -#endif - } - BIG_add(r,t,b); - BIG_norm(r); -} -#endif - -#if MODTYPE == MONTGOMERY_FRIENDLY - -/* convert to Montgomery n-residue form */ -void FP_nres(BIG a) -{ - DBIG d; - BIG m; - BIG_rcopy(m,Modulus); - BIG_dscopy(d,a); - BIG_dshl(d,NLEN*BASEBITS); - BIG_dmod(a,d,m); -} - -/* convert back to regular form */ -void FP_redc(BIG a) -{ - DBIG d; - BIG_dzero(d); - BIG_dscopy(d,a); - FP_mod(a,d); -} - -/* fast modular reduction from DBIG to BIG exploiting special form of the modulus */ -void FP_mod(BIG a,DBIG d) -{ - int i; - chunk k; - - for (i=0;i<NLEN;i++) - d[NLEN+i]+=muladd(d[i],MConst-1,d[i],&d[NLEN+i-1]); - - BIG_sducopy(a,d); - BIG_norm(a); -} - -#endif - -#if MODTYPE == NOT_SPECIAL - -/* convert BIG a to Montgomery n-residue form */ -/* SU= 120 */ -void FP_nres(BIG a) -{ - DBIG d; - BIG m; - BIG_rcopy(m,Modulus); - BIG_dscopy(d,a); - BIG_dshl(d,NLEN*BASEBITS); - BIG_dmod(a,d,m); -} - -/* SU= 80 */ -/* convert back to regular form */ -void FP_redc(BIG a) -{ - DBIG d; - BIG_dzero(d); - BIG_dscopy(d,a); - FP_mod(a,d); -} - -/* reduce a DBIG to a BIG using Montgomery's no trial division method */ -/* d is expected to be dnormed before entry */ -/* SU= 112 */ -void FP_mod(BIG a,DBIG d) -{ - int i,j; - chunk m,carry; - BIG md; - -#ifdef dchunk - dchunk sum; - chunk sp; -#endif - - BIG_rcopy(md,Modulus); - -#ifdef COMBA - -/* Faster to Combafy it.. Let the compiler unroll the loops! */ - - sum=d[0]; - for (j=0;j<NLEN;j++) - { - for (i=0;i<j;i++) sum+=(dchunk)d[i]*md[j-i]; - if (MConst==-1) sp=(-(chunk)sum)&MASK; - else - { - if (MConst==1) sp=((chunk)sum)&MASK; - else sp=((chunk)sum*MConst)&MASK; - } - d[j]=sp; sum+=(dchunk)sp*md[0]; /* no need for &MASK here! */ - sum=d[j+1]+(sum>>BASEBITS); - } - - for (j=NLEN;j<DNLEN-2;j++) - { - for (i=j-NLEN+1;i<NLEN;i++) sum+=(dchunk)d[i]*md[j-i]; - d[j]=(chunk)sum&MASK; - sum=d[j+1]+(sum>>BASEBITS); - } - - sum+=(dchunk)d[NLEN-1]*md[NLEN-1]; - d[DNLEN-2]=(chunk)sum&MASK; - sum=d[DNLEN-1]+(sum>>BASEBITS); - d[DNLEN-1]=(chunk)sum&MASK; - - BIG_sducopy(a,d); - BIG_norm(a); - -#else - for (i=0;i<NLEN;i++) - { - if (MConst==-1) m=(-d[i])&MASK; - else - { - if (MConst==1) m=d[i]; - else m=(MConst*d[i])&MASK; - } - carry=0; - for (j=0;j<NLEN;j++) - carry=muladd(m,md[j],carry,&d[i+j]); - d[NLEN+i]+=carry; - } - BIG_sducopy(a,d); - BIG_norm(a); - -#endif -} - -#endif - -/* test x==0 ? */ -/* SU= 48 */ -int FP_iszilch(BIG x) -{ - BIG m; - BIG_rcopy(m,Modulus); - BIG_mod(x,m); - return BIG_iszilch(x); -} - -/* output FP */ -/* SU= 48 */ -void FP_output(BIG r) -{ - BIG c; - BIG_copy(c,r); - FP_redc(c); - BIG_output(c); -} - -void FP_rawoutput(BIG r) -{ - BIG_rawoutput(r); -} - -#ifdef GET_STATS -int tsqr=0,rsqr=0,tmul=0,rmul=0; -int tadd=0,radd=0,tneg=0,rneg=0; -int tdadd=0,rdadd=0,tdneg=0,rdneg=0; -#endif - -/* r=a*b mod Modulus */ -/* product must be less that p.R - and we need to know this in advance! */ -/* SU= 88 */ -void FP_mul(BIG r,BIG a,BIG b) -{ - DBIG d; - chunk ea=EXCESS(a); - chunk eb=EXCESS(b); - if ((ea+1)*(eb+1)+1>=FEXCESS) - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it %d %d\n",ea,eb); -#endif - FP_reduce(a); /* it is sufficient to fully reduce just one of them < p */ -#ifdef GET_STATS - rmul++; - } - tmul++; -#else - } -#endif - - BIG_mul(d,a,b); - FP_mod(r,d); -} - -/* multiplication by an integer, r=a*c */ -/* SU= 136 */ -void FP_imul(BIG r,BIG a,int c) -{ - DBIG d; - BIG m; - int s=0; - chunk afx; - BIG_norm(a); - if (c<0) - { - c=-c; - s=1; - } - afx=(EXCESS(a)+1)*(c+1)+1; - if (c<NEXCESS && afx<FEXCESS) - BIG_imul(r,a,c); - else - { - if (afx<FEXCESS) - { - BIG_pmul(r,a,c); - } - else - { - BIG_rcopy(m,Modulus); - BIG_pxmul(d,a,c); - BIG_dmod(r,d,m); - } - } - if (s) FP_neg(r,r); - BIG_norm(r); -} - -/* Set r=a^2 mod m */ -/* SU= 88 */ -void FP_sqr(BIG r,BIG a) -{ - DBIG d; - chunk ea=EXCESS(a); - if ((ea+1)*(ea+1)+1>=FEXCESS) - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it %d\n",ea); -#endif - FP_reduce(a); -#ifdef GET_STATS - rsqr++; - } - tsqr++; -#else - } -#endif - BIG_sqr(d,a); - FP_mod(r,d); -} - -/* SU= 16 */ -/* Set r=a+b */ -void FP_add(BIG r,BIG a,BIG b) -{ - BIG_add(r,a,b); - if (EXCESS(r)+2>=FEXCESS) /* +2 because a and b not normalised */ - { -#ifdef DEBUG_REDUCE - printf("Sum too large - reducing it %d\n",EXCESS(r)); -#endif - FP_reduce(r); -#ifdef GET_STATS - radd++; - } - tadd++; -#else - } -#endif -} - -/* Set r=a-b mod m */ -/* SU= 56 */ -void FP_sub(BIG r,BIG a,BIG b) -{ - BIG n; - FP_neg(n,b); - FP_add(r,a,n); -} - -/* SU= 48 */ -/* Fully reduce a mod Modulus */ -void FP_reduce(BIG a) -{ - BIG m; - BIG_rcopy(m,Modulus); - BIG_mod(a,m); -} - -/* Set r=-a mod Modulus */ -/* SU= 64 */ -void FP_neg(BIG r,BIG a) -{ - int sb; - chunk ov; - BIG m,t; - - BIG_rcopy(m,Modulus); - BIG_norm(a); - - ov=EXCESS(a); - sb=1; while(ov!=0) {sb++;ov>>=1;} /* only unpredictable branch */ - - BIG_fshl(m,sb); - BIG_sub(r,m,a); - - if (EXCESS(r)>=FEXCESS) - { -#ifdef DEBUG_REDUCE - printf("Negation too large - reducing it %d\n",EXCESS(r)); -#endif - FP_reduce(r); -#ifdef GET_STATS - rneg++; - } - tneg++; -#else - } -#endif - -} - -/* Set r=a/2. */ -/* SU= 56 */ -void FP_div2(BIG r,BIG a) -{ - BIG m; - BIG_rcopy(m,Modulus); - BIG_norm(a); - if (BIG_parity(a)==0) - { - BIG_copy(r,a); - BIG_fshr(r,1); - } - else - { - BIG_add(r,a,m); - BIG_norm(r); - BIG_fshr(r,1); - } -} - -/* set w=1/x */ -void FP_inv(BIG w,BIG x) -{ - BIG m; - BIG_rcopy(m,Modulus); - BIG_copy(w,x); - FP_redc(w); - - BIG_invmodp(w,w,m); - FP_nres(w); -} - -/* SU=8 */ -/* set n=1 */ -void FP_one(BIG n) -{ - BIG_one(n); FP_nres(n); -} - -/* Set r=a^b mod Modulus */ -/* SU= 136 */ -void FP_pow(BIG r,BIG a,BIG b) -{ - BIG w,z,zilch; - int bt; - BIG_zero(zilch); - - BIG_norm(b); - BIG_copy(z,b); - BIG_copy(w,a); - FP_one(r); - while(1) - { - bt=BIG_parity(z); - BIG_fshr(z,1); - if (bt) FP_mul(r,r,w); - if (BIG_comp(z,zilch)==0) break; - FP_sqr(w,w); - } - FP_reduce(r); -} - -/* is r a QR? */ -int FP_qr(BIG r) -{ - int j; - BIG m; - BIG_rcopy(m,Modulus); - FP_redc(r); - j=BIG_jacobi(r,m); - FP_nres(r); - if (j==1) return 1; - return 0; - -} - -/* Set a=sqrt(b) mod Modulus */ -/* SU= 160 */ -void FP_sqrt(BIG r,BIG a) -{ - BIG v,i,b; - BIG m; - BIG_rcopy(m,Modulus); - BIG_mod(a,m); - BIG_copy(b,m); - if (MOD8==5) - { - BIG_dec(b,5); BIG_norm(b); BIG_fshr(b,3); /* (p-5)/8 */ - BIG_copy(i,a); BIG_fshl(i,1); - FP_pow(v,i,b); - FP_mul(i,i,v); FP_mul(i,i,v); - BIG_dec(i,1); - FP_mul(r,a,v); FP_mul(r,r,i); - BIG_mod(r,m); - } - if (MOD8==3 || MOD8==7) - { - BIG_inc(b,1); BIG_norm(b); BIG_fshr(b,2); /* (p+1)/4 */ - FP_pow(r,a,b); - } -} - -/* -int main() -{ - - BIG r; - - FP_one(r); - FP_sqr(r,r); - - BIG_output(r); - - int i,carry; - DBIG c={0,0,0,0,0,0,0,0}; - BIG a={1,2,3,4}; - BIG b={3,4,5,6}; - BIG r={11,12,13,14}; - BIG s={23,24,25,15}; - BIG w; - -// printf("NEXCESS= %d\n",NEXCESS); -// printf("MConst= %d\n",MConst); - - BIG_copy(b,Modulus); - BIG_dec(b,1); - BIG_norm(b); - - BIG_randomnum(r); BIG_norm(r); BIG_mod(r,Modulus); -// BIG_randomnum(s); norm(s); BIG_mod(s,Modulus); - -// BIG_output(r); -// BIG_output(s); - - BIG_output(r); - FP_nres(r); - BIG_output(r); - BIG_copy(a,r); - FP_redc(r); - BIG_output(r); - BIG_dscopy(c,a); - FP_mod(r,c); - BIG_output(r); - - -// exit(0); - -// copy(r,a); - printf("r= "); BIG_output(r); - BIG_modsqr(r,r,Modulus); - printf("r^2= "); BIG_output(r); - - FP_nres(r); - FP_sqrt(r,r); - FP_redc(r); - printf("r= "); BIG_output(r); - BIG_modsqr(r,r,Modulus); - printf("r^2= "); BIG_output(r); - - -// for (i=0;i<100000;i++) FP_sqr(r,r); -// for (i=0;i<100000;i++) - FP_sqrt(r,r); - - BIG_output(r); -} -*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/fp12.c ---------------------------------------------------------------------- diff --git a/c/fp12.c b/c/fp12.c deleted file mode 100755 index 51f41cc..0000000 --- a/c/fp12.c +++ /dev/null @@ -1,688 +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 Fp^12 functions */ -/* SU=m, m is Stack Usage (no lazy )*/ -/* FP12 elements are of the form a+i.b+i^2.c */ - -#include "amcl.h" - -/* test x==0 ? */ -/* SU= 8 */ -int FP12_iszilch(FP12 *x) -{ - if (FP4_iszilch(&(x->a)) && FP4_iszilch(&(x->b)) && FP4_iszilch(&(x->c))) return 1; - return 0; -} - -/* test x==1 ? */ -/* SU= 8 */ -int FP12_isunity(FP12 *x) -{ - if (FP4_isunity(&(x->a)) && FP4_iszilch(&(x->b)) && FP4_iszilch(&(x->c))) return 1; - return 0; -} - -/* FP12 copy w=x */ -/* SU= 16 */ -void FP12_copy(FP12 *w,FP12 *x) -{ - if (x==w) return; - FP4_copy(&(w->a),&(x->a)); - FP4_copy(&(w->b),&(x->b)); - FP4_copy(&(w->c),&(x->c)); -} - -/* FP12 w=1 */ -/* SU= 8 */ -void FP12_one(FP12 *w) -{ - FP4_one(&(w->a)); - FP4_zero(&(w->b)); - FP4_zero(&(w->c)); -} - -/* return 1 if x==y, else 0 */ -/* SU= 16 */ -int FP12_equals(FP12 *x,FP12 *y) -{ - if (FP4_equals(&(x->a),&(y->a)) && FP4_equals(&(x->b),&(y->b)) && FP4_equals(&(x->b),&(y->b))) - return 1; - return 0; -} - -/* Set w=conj(x) */ -/* SU= 8 */ -void FP12_conj(FP12 *w,FP12 *x) -{ - FP12_copy(w,x); - FP4_conj(&(w->a),&(w->a)); - FP4_nconj(&(w->b),&(w->b)); - FP4_conj(&(w->c),&(w->c)); -} - -/* Create FP12 from FP4 */ -/* SU= 8 */ -void FP12_from_FP4(FP12 *w,FP4 *a) -{ - FP4_copy(&(w->a),a); - FP4_zero(&(w->b)); - FP4_zero(&(w->c)); -} - -/* Create FP12 from 3 FP4's */ -/* SU= 16 */ -void FP12_from_FP4s(FP12 *w,FP4 *a,FP4 *b,FP4 *c) -{ - FP4_copy(&(w->a),a); - FP4_copy(&(w->b),b); - FP4_copy(&(w->c),c); -} - -/* Granger-Scott Unitary Squaring. This does not benefit from lazy reduction */ -/* SU= 600 */ -void FP12_usqr(FP12 *w,FP12 *x) -{ - FP4 A,B,C,D; - - FP4_copy(&A,&(x->a)); - - FP4_sqr(&(w->a),&(x->a)); - FP4_add(&D,&(w->a),&(w->a)); - FP4_add(&(w->a),&D,&(w->a)); - -#if CHUNK<64 - FP4_norm(&(w->a)); -#endif - - FP4_nconj(&A,&A); - - FP4_add(&A,&A,&A); - FP4_add(&(w->a),&(w->a),&A); - FP4_sqr(&B,&(x->c)); - FP4_times_i(&B); - - FP4_add(&D,&B,&B); - FP4_add(&B,&B,&D); -#if CHUNK<64 - FP4_norm(&B); -#endif - FP4_sqr(&C,&(x->b)); - - FP4_add(&D,&C,&C); - FP4_add(&C,&C,&D); - -#if CHUNK<64 - FP4_norm(&C); -#endif - FP4_conj(&(w->b),&(x->b)); - FP4_add(&(w->b),&(w->b),&(w->b)); - FP4_nconj(&(w->c),&(x->c)); - - FP4_add(&(w->c),&(w->c),&(w->c)); - FP4_add(&(w->b),&B,&(w->b)); - FP4_add(&(w->c),&C,&(w->c)); - FP12_reduce(w); /* reduce here as in pow function repeated squarings would trigger multiple reductions */ - -} - -/* FP12 squaring w=x^2 */ -/* SU= 600 */ -void FP12_sqr(FP12 *w,FP12 *x) -{ -/* Use Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */ - - FP4 A,B,C,D; - - FP4_sqr(&A,&(x->a)); - FP4_mul(&B,&(x->b),&(x->c)); - FP4_add(&B,&B,&B); - FP4_sqr(&C,&(x->c)); - FP4_mul(&D,&(x->a),&(x->b)); - FP4_add(&D,&D,&D); - FP4_add(&(w->c),&(x->a),&(x->c)); - FP4_add(&(w->c),&(x->b),&(w->c)); - - FP4_sqr(&(w->c),&(w->c)); - - FP4_copy(&(w->a),&A); - - FP4_add(&A,&A,&B); -#if CHUNK<64 - FP4_norm(&A); -#endif - FP4_add(&A,&A,&C); - FP4_add(&A,&A,&D); -#if CHUNK<64 - FP4_norm(&A); -#endif - FP4_neg(&A,&A); - FP4_times_i(&B); - FP4_times_i(&C); - - FP4_add(&(w->a),&(w->a),&B); - FP4_add(&(w->b),&C,&D); - FP4_add(&(w->c),&(w->c),&A); - - FP12_norm(w); -} - -/* FP12 full multiplication w=w*y */ - - -/* SU= 896 */ -/* FP12 full multiplication w=w*y */ -void FP12_mul(FP12 *w,FP12 *y) -{ - FP4 z0,z1,z2,z3,t0,t1; - - FP4_mul(&z0,&(w->a),&(y->a)); - FP4_mul(&z2,&(w->b),&(y->b)); // - - FP4_add(&t0,&(w->a),&(w->b)); - FP4_add(&t1,&(y->a),&(y->b)); // - FP4_mul(&z1,&t0,&t1); - FP4_add(&t0,&(w->b),&(w->c)); - - FP4_add(&t1,&(y->b),&(y->c)); // - FP4_mul(&z3,&t0,&t1); - - FP4_neg(&t0,&z0); - FP4_neg(&t1,&z2); - - FP4_add(&z1,&z1,&t0); // z1=z1-z0 -#if CHUNK<64 - FP4_norm(&z1); -#endif - FP4_add(&(w->b),&z1,&t1); -// z1=z1-z2 - FP4_add(&z3,&z3,&t1); // z3=z3-z2 - FP4_add(&z2,&z2,&t0); // z2=z2-z0 - - FP4_add(&t0,&(w->a),&(w->c)); - - FP4_add(&t1,&(y->a),&(y->c)); - FP4_mul(&t0,&t1,&t0); - FP4_add(&z2,&z2,&t0); - - FP4_mul(&t0,&(w->c),&(y->c)); - FP4_neg(&t1,&t0); -#if CHUNK<64 - FP4_norm(&z2); - FP4_norm(&z3); - FP4_norm(&(w->b)); -#endif - FP4_add(&(w->c),&z2,&t1); - FP4_add(&z3,&z3,&t1); - FP4_times_i(&t0); - FP4_add(&(w->b),&(w->b),&t0); - - FP4_times_i(&z3); - FP4_add(&(w->a),&z0,&z3); - - FP12_norm(w); -} - -/* FP12 multiplication w=w*y */ -/* SU= 744 */ -/* catering for special case that arises from special form of ATE pairing line function */ -void FP12_smul(FP12 *w,FP12 *y) -{ - FP4 z0,z2,z3,t0,t1; - - FP4_copy(&z3,&(w->b)); - FP4_mul(&z0,&(w->a),&(y->a)); - FP4_pmul(&z2,&(w->b),&(y->b).a); - FP4_add(&(w->b),&(w->a),&(w->b)); - FP4_copy(&t1,&(y->a)); - FP2_add(&t1.a,&t1.a,&(y->b).a); - - FP4_mul(&(w->b),&(w->b),&t1); - FP4_add(&z3,&z3,&(w->c)); - FP4_pmul(&z3,&z3,&(y->b).a); - FP4_neg(&t0,&z0); - FP4_neg(&t1,&z2); - - FP4_add(&(w->b),&(w->b),&t0); // z1=z1-z0 -#if CHUNK<64 - FP4_norm(&(w->b)); -#endif - FP4_add(&(w->b),&(w->b),&t1); // z1=z1-z2 - - FP4_add(&z3,&z3,&t1); // z3=z3-z2 - FP4_add(&z2,&z2,&t0); // z2=z2-z0 - - FP4_add(&t0,&(w->a),&(w->c)); - - FP4_mul(&t0,&(y->a),&t0); - FP4_add(&(w->c),&z2,&t0); - - FP4_times_i(&z3); - FP4_add(&(w->a),&z0,&z3); - - FP12_norm(w); -} - -/* Set w=1/x */ -/* SU= 600 */ -void FP12_inv(FP12 *w,FP12 *x) -{ - FP4 f0,f1,f2,f3; - FP12_norm(x); - - FP4_sqr(&f0,&(x->a)); - FP4_mul(&f1,&(x->b),&(x->c)); - FP4_times_i(&f1); - FP4_sub(&f0,&f0,&f1); /* y.a */ - - FP4_sqr(&f1,&(x->c)); - FP4_times_i(&f1); - FP4_mul(&f2,&(x->a),&(x->b)); - FP4_sub(&f1,&f1,&f2); /* y.b */ - - FP4_sqr(&f2,&(x->b)); - FP4_mul(&f3,&(x->a),&(x->c)); - FP4_sub(&f2,&f2,&f3); /* y.c */ - - FP4_mul(&f3,&(x->b),&f2); - FP4_times_i(&f3); - FP4_mul(&(w->a),&f0,&(x->a)); - FP4_add(&f3,&(w->a),&f3); - FP4_mul(&(w->c),&f1,&(x->c)); - FP4_times_i(&(w->c)); - - FP4_add(&f3,&(w->c),&f3); - FP4_inv(&f3,&f3); - - FP4_mul(&(w->a),&f0,&f3); - FP4_mul(&(w->b),&f1,&f3); - FP4_mul(&(w->c),&f2,&f3); - -} - -/* constant time powering by small integer of max length bts */ - -void FP12_pinpow(FP12 *r,int e,int bts) -{ - int i,b; - FP12 R[2]; - - FP12_one(&R[0]); - FP12_copy(&R[1],r); - - for (i=bts-1;i>=0;i--) - { - b=(e>>i)&1; - FP12_mul(&R[1-b],&R[b]); - FP12_usqr(&R[b],&R[b]); - } - FP12_copy(r,&R[0]); -} - -/* SU= 528 */ -/* set r=a^b */ -/* Note this is simple square and multiply, so not side-channel safe */ - -void FP12_pow(FP12 *r,FP12 *a,BIG b) -{ - FP12 w; - BIG z,zilch; - int bt; - BIG_zero(zilch); - BIG_norm(b); - BIG_copy(z,b); - FP12_copy(&w,a); - FP12_one(r); - - while(1) - { - bt=BIG_parity(z); - BIG_shr(z,1); - if (bt) - FP12_mul(r,&w); - if (BIG_comp(z,zilch)==0) break; - FP12_usqr(&w,&w); - } - - FP12_reduce(r); -} - -/* p=q0^u0.q1^u1.q2^u2.q3^u3 */ -/* Timing attack secure, but not cache attack secure */ - -void FP12_pow4(FP12 *p,FP12 *q,BIG u[4]) -{ - int i,j,a[4],nb,m; - FP12 g[8],c,s[2]; - BIG t[4],mt; - sign8 w[NLEN*BASEBITS+1]; - - for (i=0;i<4;i++) - BIG_copy(t[i],u[i]); - - FP12_copy(&g[0],&q[0]); FP12_conj(&s[0],&q[1]); FP12_mul(&g[0],&s[0]); /* P/Q */ - FP12_copy(&g[1],&g[0]); - FP12_copy(&g[2],&g[0]); - FP12_copy(&g[3],&g[0]); - FP12_copy(&g[4],&q[0]); FP12_mul(&g[4],&q[1]); /* P*Q */ - FP12_copy(&g[5],&g[4]); - FP12_copy(&g[6],&g[4]); - FP12_copy(&g[7],&g[4]); - - FP12_copy(&s[1],&q[2]); FP12_conj(&s[0],&q[3]); FP12_mul(&s[1],&s[0]); /* R/S */ - FP12_conj(&s[0],&s[1]); FP12_mul(&g[1],&s[0]); - FP12_mul(&g[2],&s[1]); - FP12_mul(&g[5],&s[0]); - FP12_mul(&g[6],&s[1]); - FP12_copy(&s[1],&q[2]); FP12_mul(&s[1],&q[3]); /* R*S */ - FP12_conj(&s[0],&s[1]); FP12_mul(&g[0],&s[0]); - FP12_mul(&g[3],&s[1]); - FP12_mul(&g[4],&s[0]); - FP12_mul(&g[7],&s[1]); - -/* if power is even add 1 to power, and add q to correction */ - FP12_one(&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]); - FP12_mul(&c,&q[i]); - } - BIG_add(mt,mt,t[i]); BIG_norm(mt); - } - - FP12_conj(&c,&c); - 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); - FP12_copy(p,&g[(w[nb]-1)/2]); - - for (i=nb-1;i>=0;i--) - { - m=w[i]>>7; - j=(w[i]^m)-m; /* j=abs(w[i]) */ - j=(j-1)/2; - FP12_copy(&s[0],&g[j]); - FP12_conj(&s[1],&g[j]); - FP12_usqr(p,p); - FP12_mul(p,&s[m&1]); - } - FP12_mul(p,&c); /* apply correction */ - FP12_reduce(p); -} - -/* Set w=w^p using Frobenius */ -/* SU= 160 */ -void FP12_frob(FP12 *w,FP2 *f) -{ - FP2 f2,f3; - FP2_sqr(&f2,f); /* f2=f^2 */ - FP2_mul(&f3,&f2,f); /* f3=f^3 */ - - FP4_frob(&(w->a),&f3); - FP4_frob(&(w->b),&f3); - FP4_frob(&(w->c),&f3); - - FP4_pmul(&(w->b),&(w->b),f); - FP4_pmul(&(w->c),&(w->c),&f2); -} - -/* SU= 8 */ -/* normalise all components of w */ -void FP12_norm(FP12 *w) -{ - FP4_norm(&(w->a)); - FP4_norm(&(w->b)); - FP4_norm(&(w->c)); -} - -/* SU= 8 */ -/* reduce all components of w */ -void FP12_reduce(FP12 *w) -{ - FP4_reduce(&(w->a)); - FP4_reduce(&(w->b)); - FP4_reduce(&(w->c)); -} - -/* trace function w=trace(x) */ -/* SU= 8 */ -void FP12_trace(FP4 *w,FP12 *x) -{ - FP4_imul(w,&(x->a),3); - FP4_reduce(w); -} - -/* SU= 8 */ -/* Output w in hex */ -void FP12_output(FP12 *w) -{ - printf("["); - FP4_output(&(w->a)); - printf(","); - FP4_output(&(w->b)); - printf(","); - FP4_output(&(w->c)); - printf("]"); -} - -/* SU= 64 */ -/* Convert g to octet string w */ -void FP12_toOctet(octet *W,FP12 *g) -{ - BIG a; - W->len=12*MODBYTES; - - BIG_copy(a,(*g).a.a.a); FP_redc(a); BIG_toBytes(&(W->val[0]),a); - BIG_copy(a,(*g).a.a.b); FP_redc(a); BIG_toBytes(&(W->val[MODBYTES]),a); - BIG_copy(a,(*g).a.b.a); FP_redc(a); BIG_toBytes(&(W->val[2*MODBYTES]),a); - BIG_copy(a,(*g).a.b.b); FP_redc(a); BIG_toBytes(&(W->val[3*MODBYTES]),a); - - BIG_copy(a,(*g).b.a.a); FP_redc(a); BIG_toBytes(&(W->val[4*MODBYTES]),a); - BIG_copy(a,(*g).b.a.b); FP_redc(a); BIG_toBytes(&(W->val[5*MODBYTES]),a); - BIG_copy(a,(*g).b.b.a); FP_redc(a); BIG_toBytes(&(W->val[6*MODBYTES]),a); - BIG_copy(a,(*g).b.b.b); FP_redc(a); BIG_toBytes(&(W->val[7*MODBYTES]),a); - - BIG_copy(a,(*g).c.a.a); FP_redc(a); BIG_toBytes(&(W->val[8*MODBYTES]),a); - BIG_copy(a,(*g).c.a.b); FP_redc(a); BIG_toBytes(&(W->val[9*MODBYTES]),a); - BIG_copy(a,(*g).c.b.a); FP_redc(a); BIG_toBytes(&(W->val[10*MODBYTES]),a); - BIG_copy(a,(*g).c.b.b); FP_redc(a); BIG_toBytes(&(W->val[11*MODBYTES]),a); -} - -/* SU= 24 */ -/* Restore g from octet string w */ -void FP12_fromOctet(FP12 *g,octet *W) -{ - BIG_fromBytes((*g).a.a.a,&W->val[0]); FP_nres((*g).a.a.a); - BIG_fromBytes((*g).a.a.b,&W->val[MODBYTES]); FP_nres((*g).a.a.b); - BIG_fromBytes((*g).a.b.a,&W->val[2*MODBYTES]); FP_nres((*g).a.b.a); - BIG_fromBytes((*g).a.b.b,&W->val[3*MODBYTES]); FP_nres((*g).a.b.b); - BIG_fromBytes((*g).b.a.a,&W->val[4*MODBYTES]); FP_nres((*g).b.a.a); - BIG_fromBytes((*g).b.a.b,&W->val[5*MODBYTES]); FP_nres((*g).b.a.b); - BIG_fromBytes((*g).b.b.a,&W->val[6*MODBYTES]); FP_nres((*g).b.b.a); - BIG_fromBytes((*g).b.b.b,&W->val[7*MODBYTES]); FP_nres((*g).b.b.b); - BIG_fromBytes((*g).c.a.a,&W->val[8*MODBYTES]); FP_nres((*g).c.a.a); - BIG_fromBytes((*g).c.a.b,&W->val[9*MODBYTES]); FP_nres((*g).c.a.b); - BIG_fromBytes((*g).c.b.a,&W->val[10*MODBYTES]); FP_nres((*g).c.b.a); - BIG_fromBytes((*g).c.b.b,&W->val[11*MODBYTES]); FP_nres((*g).c.b.b); -} - -/* -int main(){ - FP2 f,w0,w1; - FP4 t0,t1,t2; - FP12 w,t,lv; - BIG a,b; - BIG p; - - //Test w^(P^4) = w mod p^2 -// BIG_randomnum(a); -// BIG_randomnum(b); -// BIG_mod(a,Modulus); BIG_mod(b,Modulus); - BIG_zero(a); BIG_zero(b); BIG_inc(a,1); BIG_inc(b,2); FP_nres(a); FP_nres(b); - FP2_from_zps(&w0,a,b); - -// BIG_randomnum(a); BIG_randomnum(b); -// BIG_mod(a,Modulus); BIG_mod(b,Modulus); - BIG_zero(a); BIG_zero(b); BIG_inc(a,3); BIG_inc(b,4); FP_nres(a); FP_nres(b); - FP2_from_zps(&w1,a,b); - - FP4_from_FP2s(&t0,&w0,&w1); - FP4_reduce(&t0); - -// BIG_randomnum(a); -// BIG_randomnum(b); -// BIG_mod(a,Modulus); BIG_mod(b,Modulus); - BIG_zero(a); BIG_zero(b); BIG_inc(a,5); BIG_inc(b,6); FP_nres(a); FP_nres(b); - FP2_from_zps(&w0,a,b); - -// BIG_randomnum(a); BIG_randomnum(b); -// BIG_mod(a,Modulus); BIG_mod(b,Modulus); - - BIG_zero(a); BIG_zero(b); BIG_inc(a,7); BIG_inc(b,8); FP_nres(a); FP_nres(b); - FP2_from_zps(&w1,a,b); - - FP4_from_FP2s(&t1,&w0,&w1); - FP4_reduce(&t1); - -// BIG_randomnum(a); -// BIG_randomnum(b); -// BIG_mod(a,Modulus); BIG_mod(b,Modulus); - BIG_zero(a); BIG_zero(b); BIG_inc(a,9); BIG_inc(b,10); FP_nres(a); FP_nres(b); - FP2_from_zps(&w0,a,b); - -// BIG_randomnum(a); BIG_randomnum(b); -// BIG_mod(a,Modulus); BIG_mod(b,Modulus); - BIG_zero(a); BIG_zero(b); BIG_inc(a,11); BIG_inc(b,12); FP_nres(a); FP_nres(b); - FP2_from_zps(&w1,a,b); - - FP4_from_FP2s(&t2,&w0,&w1); - FP4_reduce(&t2); - - FP12_from_FP4s(&w,&t0,&t1,&t2); - - FP12_copy(&t,&w); - - printf("w= "); - FP12_output(&w); - printf("\n"); - - BIG_rcopy(p,Modulus); - //BIG_zero(p); BIG_inc(p,7); - - FP12_pow(&w,&w,p); - - printf("w^p= "); - FP12_output(&w); - printf("\n"); - - FP2_gfc(&f,12); - FP12_frob(&t,&f); - printf("w^p= "); - FP12_output(&t); - printf("\n"); - -//exit(0); - - FP12_pow(&w,&w,p); - //printf("w^p^2= "); - //FP12_output(&w); - //printf("\n"); - FP12_pow(&w,&w,p); - //printf("w^p^3= "); - //FP12_output(&w); - //printf("\n"); - FP12_pow(&w,&w,p); - FP12_pow(&w,&w,p); - FP12_pow(&w,&w,p); - printf("w^p^6= "); - FP12_output(&w); - printf("\n"); - FP12_pow(&w,&w,p); - FP12_pow(&w,&w,p); - printf("w^p^8= "); - FP12_output(&w); - printf("\n"); - FP12_pow(&w,&w,p); - FP12_pow(&w,&w,p); - FP12_pow(&w,&w,p); - printf("w^p^11= "); - FP12_output(&w); - printf("\n"); - - // BIG_zero(p); BIG_inc(p,7); BIG_norm(p); - FP12_pow(&w,&w,p); - - printf("w^p12= "); - FP12_output(&w); - printf("\n"); -//exit(0); - - FP12_inv(&t,&w); - printf("1/w mod p^4 = "); - FP12_output(&t); - printf("\n"); - - FP12_inv(&w,&t); - printf("1/(1/w) mod p^4 = "); - FP12_output(&w); - printf("\n"); - - - - FP12_inv(&lv,&w); -//printf("w= "); FP12_output(&w); printf("\n"); - FP12_conj(&w,&w); -//printf("w= "); FP12_output(&w); printf("\n"); -//exit(0); - FP12_mul(&w,&w,&lv); -//printf("w= "); FP12_output(&w); printf("\n"); - FP12_copy(&lv,&w); - FP12_frob(&w,&f); - FP12_frob(&w,&f); - FP12_mul(&w,&w,&lv); - -//printf("w= "); FP12_output(&w); printf("\n"); -//exit(0); - -w.unitary=0; -FP12_conj(&lv,&w); - printf("rx= "); FP12_output(&lv); printf("\n"); -FP12_inv(&lv,&w); - printf("ry= "); FP12_output(&lv); printf("\n"); - - - return 0; -} - -*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/fp2.c ---------------------------------------------------------------------- diff --git a/c/fp2.c b/c/fp2.c deleted file mode 100755 index 618815b..0000000 --- a/c/fp2.c +++ /dev/null @@ -1,421 +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 Fp^2 functions */ -/* SU=m, m is Stack Usage (no lazy )*/ - -/* FP2 elements are of the form a+ib, where i is sqrt(-1) */ -#include "amcl.h" - -/* test x==0 ? */ -/* SU= 8 */ -int FP2_iszilch(FP2 *x) -{ - BIG m; - FP2_reduce(x); - if (BIG_iszilch(x->a) && BIG_iszilch(x->b)) return 1; - return 0; -} - -/* Move b to a if d=1 */ -void FP2_cmove(FP2 *f,FP2 *g,int d) -{ - BIG_cmove(f->a,g->a,d); - BIG_cmove(f->b,g->b,d); -} - -/* test x==1 ? */ -/* SU= 48 */ -int FP2_isunity(FP2 *x) -{ - BIG one; - FP_one(one); - FP2_reduce(x); - if (BIG_comp(x->a,one)==0 && BIG_iszilch(x->b)) return 1; - return 0; -} - -/* SU= 8 */ -/* Fully reduce a and b mod Modulus */ -void FP2_reduce(FP2 *w) -{ - FP_reduce(w->a); - FP_reduce(w->b); -} - -/* return 1 if x==y, else 0 */ -/* SU= 16 */ -int FP2_equals(FP2 *x,FP2 *y) -{ - FP2_reduce(x); FP2_reduce(y); - if (BIG_comp(x->a,y->a)==0 && BIG_comp(x->b,y->b)==0) - return 1; - return 0; -} - -/* Create FP2 from two FPs */ -/* SU= 16 */ -void FP2_from_FPs(FP2 *w,BIG x,BIG y) -{ - BIG_copy(w->a,x); - BIG_copy(w->b,y); -} - -/* Create FP2 from two BIGS */ -/* SU= 16 */ -void FP2_from_BIGs(FP2 *w,BIG x,BIG y) -{ - BIG_copy(w->a,x); - BIG_copy(w->b,y); - FP_nres(w->a); FP_nres(w->b); -} - -/* Create FP2 from FP */ -/* SU= 8 */ -void FP2_from_FP(FP2 *w,BIG x) -{ - BIG_copy(w->a,x); - BIG_zero(w->b); -} - -/* Create FP2 from BIG */ -/* SU= 8 */ -void FP2_from_BIG(FP2 *w,BIG x) -{ - BIG_copy(w->a,x); FP_nres(w->a); - BIG_zero(w->b); -} - -/* FP2 copy w=x */ -/* SU= 16 */ -void FP2_copy(FP2 *w,FP2 *x) -{ - if (w==x) return; - BIG_copy(w->a,x->a); - BIG_copy(w->b,x->b); -} - -/* FP2 set w=0 */ -/* SU= 8 */ -void FP2_zero(FP2 *w) -{ - BIG_zero(w->a); - BIG_zero(w->b); -} - -/* FP2 set w=1 */ -/* SU= 48 */ -void FP2_one(FP2 *w) -{ - BIG one; - FP_one(one); - FP2_from_FP(w,one); -} - -/* Set w=-x */ -/* SU= 88 */ -void FP2_neg(FP2 *w,FP2 *x) -{ /* Just one neg! */ - BIG m,t; - FP2_norm(x); - FP_add(m,x->a,x->b); - FP_neg(m,m); - BIG_norm(m); - FP_add(t,m,x->b); - FP_add(w->b,m,x->a); - BIG_copy(w->a,t); -} - -/* Set w=conj(x) */ -/* SU= 16 */ -void FP2_conj(FP2 *w,FP2 *x) -{ - BIG_copy(w->a,x->a); - FP_neg(w->b,x->b); -} - -/* Set w=x+y */ -/* SU= 16 */ -void FP2_add(FP2 *w,FP2 *x,FP2 *y) -{ - FP_add(w->a,x->a,y->a); - FP_add(w->b,x->b,y->b); -} - -/* Set w=x-y */ -/* SU= 16 */ -void FP2_sub(FP2 *w,FP2 *x,FP2 *y) -{ - FP2 m; - FP2_neg(&m,y); - FP2_add(w,x,&m); -} - -/* Set w=s*x, where s is FP */ -/* SU= 16 */ -void FP2_pmul(FP2 *w,FP2 *x,BIG s) -{ - FP_mul(w->a,x->a,s); - FP_mul(w->b,x->b,s); -} - -/* SU= 16 */ -/* Set w=s*x, where s is int */ -void FP2_imul(FP2 *w,FP2 *x,int s) -{ - FP_imul(w->a,x->a,s); - FP_imul(w->b,x->b,s); -} - -/* Set w=x^2 */ -/* SU= 128 */ -void FP2_sqr(FP2 *w,FP2 *x) -{ - BIG w1,w3,mb; - - FP_mul(w3,x->a,x->b); /* norms x */ - FP_add(w1,x->a,x->b); /* w1#2 w1=2 */ - FP_neg(mb,x->b); /* mb#2 mb=1 */ - FP_add(w->a,x->a,mb); /* w2#3 w2=3 */ - FP_mul(w->a,w1,w->a); /* w->a#2 w->a=1 w1&w2=6 w1*w2=2 */ - - FP_add(w->b,w3,w3); /* w->b#4 w->b=2 */ - - FP2_norm(w); - -} - - -/* Set w=x*y */ -/* SU= 168 */ -void FP2_mul(FP2 *w,FP2 *x,FP2 *y) -{ - BIG w1,w2,w5,mw; - - FP_mul(w1,x->a,y->a); /* norms x */ - FP_mul(w2,x->b,y->b); /* and y */ - - FP_add(w5,x->a,x->b); - - FP_add(w->b,y->a,y->b); - - FP_mul(w->b,w->b,w5); - FP_add(mw,w1,w2); - FP_neg(mw,mw); - - FP_add(w->b,w->b,mw); - FP_add(mw,w1,mw); - FP_add(w->a,w1,mw); - - FP2_norm(w); - -} - -/* output FP2 in hex format [a,b] */ -/* SU= 16 */ -void FP2_output(FP2 *w) -{ - FP2_reduce(w); - FP_redc(w->a); FP_redc(w->b); - printf("[");BIG_output(w->a);printf(",");BIG_output(w->b);printf("]"); - FP_nres(w->a); FP_nres(w->b); -} - -/* SU= 8 */ -void FP2_rawoutput(FP2 *w) -{ - printf("[");BIG_rawoutput(w->a);printf(",");BIG_rawoutput(w->b);printf("]"); -} - - -/* Set w=1/x */ -/* SU= 128 */ -void FP2_inv(FP2 *w,FP2 *x) -{ - BIG m,w1,w2; - BIG_rcopy(m,Modulus); - FP2_norm(x); - FP_sqr(w1,x->a); - FP_sqr(w2,x->b); - FP_add(w1,w1,w2); - - FP_redc(w1); - BIG_invmodp(w1,w1,m); - FP_nres(w1); - FP_mul(w->a,x->a,w1); - FP_neg(w1,w1); - FP_mul(w->b,x->b,w1); -// FP2_norm(w); -} - - -/* Set w=x/2 */ -/* SU= 16 */ -void FP2_div2(FP2 *w,FP2 *x) -{ - FP_div2(w->a,x->a); - FP_div2(w->b,x->b); -} - -/* Set w*=(1+sqrt(-1)) */ -/* where X^2-(1+sqrt(-1)) is irreducible for FP4, assumes p=3 mod 8 */ - -/* SU= 128 */ -void FP2_mul_ip(FP2 *w) -{ - FP2 t; - BIG z; - - FP2_norm(w); - FP2_copy(&t,w); - - BIG_copy(z,w->a); - FP_neg(w->a,w->b); - BIG_copy(w->b,z); - - FP2_add(w,&t,w); - FP2_norm(w); -} - -/* Set w/=(1+sqrt(-1)) */ -/* SU= 88 */ -void FP2_div_ip(FP2 *w) -{ - FP2 t; - FP2_norm(w); - FP_add(t.a,w->a,w->b); - FP_sub(t.b,w->b,w->a); - FP2_div2(w,&t); -} - -/* SU= 8 */ -/* normalise a and b components of w */ -void FP2_norm(FP2 *w) -{ - BIG_norm(w->a); - BIG_norm(w->b); -} - -/* Set w=a^b mod m */ -/* SU= 208 */ -void FP2_pow(FP2 *r,FP2* a,BIG b) -{ - FP2 w; - BIG z,one,zilch; - int bt; - - BIG_norm(b); - BIG_copy(z,b); - FP2_copy(&w,a); - FP_one(one); - BIG_zero(zilch); - FP2_from_FP(r,one); - while(1) - { - bt=BIG_parity(z); - BIG_shr(z,1); - if (bt) FP2_mul(r,r,&w); - if (BIG_comp(z,zilch)==0) break; - FP2_sqr(&w,&w); - } - FP2_reduce(r); -} - -/* sqrt(a+ib) = sqrt(a+sqrt(a*a-n*b*b)/2)+ib/(2*sqrt(a+sqrt(a*a-n*b*b)/2)) */ -/* returns true if u is QR */ - -int FP2_sqrt(FP2 *w,FP2 *u) -{ - BIG w1,w2,q; - FP2_copy(w,u); - if (FP2_iszilch(w)) return 1; - - BIG_rcopy(q,Modulus); - FP_sqr(w1,w->b); - FP_sqr(w2,w->a); - FP_add(w1,w1,w2); - if (!FP_qr(w1)) - { - FP2_zero(w); - return 0; - } - FP_sqrt(w1,w1); - FP_add(w2,w->a,w1); - FP_div2(w2,w2); - if (!FP_qr(w2)) - { - FP_sub(w2,w->a,w1); - FP_div2(w2,w2); - if (!FP_qr(w2)) - { - FP2_zero(w); - return 0; - } - } - FP_sqrt(w2,w2); - BIG_copy(w->a,w2); - FP_add(w2,w2,w2); - FP_redc(w2); - BIG_invmodp(w2,w2,q); - FP_nres(w2); - FP_mul(w->b,w->b,w2); - return 1; -} - -/* -int main() -{ - int i; - FP2 w,z; - BIG a,b,e; - BIG pp1,pm1; - BIG_unity(a); BIG_unity(b); - FP2_from_BIGs(&w,a,b); -// for (i=0;i<100;i++) -// { -// BIG_randomnum(a); BIG_randomnum(b); -// BIG_mod(a,Modulus); BIG_mod(b,Modulus); -// FP2_from_FPs(&w,a,b); -// FP2_output(&w); -// FP2_inv(&z,&w); -// FP2_output(&z); -// FP2_inv(&z,&z); -// FP2_output(&z); -// FP2_output(&w); -// if (FP2_comp(&w,&z)!=1) printf("error \n"); -// else printf("OK \n"); -// } -//exit(0); - printf("w= "); FP2_output(&w); printf("\n"); - BIG_zero(e); BIG_inc(e,27); - FP2_pow(&w,&w,e); - FP2_output(&w); -exit(0); - BIG_rcopy(pp1,Modulus); - BIG_rcopy(pm1,Modulus); - BIG_inc(pp1,1); - BIG_dec(pm1,1); - BIG_norm(pp1); - BIG_norm(pm1); - FP2_pow(&w,&w,pp1); - FP2_pow(&w,&w,pm1); - FP2_output(&w); -} - -*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/fp4.c ---------------------------------------------------------------------- diff --git a/c/fp4.c b/c/fp4.c deleted file mode 100755 index 0dafe0d..0000000 --- a/c/fp4.c +++ /dev/null @@ -1,636 +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 Fp^4 functions */ -/* SU=m, m is Stack Usage (no lazy )*/ - -/* FP4 elements are of the form a+ib, where i is sqrt(-1+sqrt(-1)) */ - -#include "amcl.h" - -/* test x==0 ? */ -/* SU= 8 */ -int FP4_iszilch(FP4 *x) -{ - if (FP2_iszilch(&(x->a)) && FP2_iszilch(&(x->b))) return 1; - return 0; -} - -/* test x==1 ? */ -/* SU= 8 */ -int FP4_isunity(FP4 *x) -{ - if (FP2_isunity(&(x->a)) && FP2_iszilch(&(x->b))) return 1; - return 0; -} - -/* test is w real? That is in a+ib test b is zero */ -int FP4_isreal(FP4 *w) -{ - return FP2_iszilch(&(w->b)); -} - -/* return 1 if x==y, else 0 */ -/* SU= 16 */ -int FP4_equals(FP4 *x,FP4 *y) -{ - if (FP2_equals(&(x->a),&(y->a)) && FP2_equals(&(x->b),&(y->b))) - return 1; - return 0; -} - -/* set FP4 from two FP2s */ -/* SU= 16 */ -void FP4_from_FP2s(FP4 *w,FP2 * x,FP2* y) -{ - FP2_copy(&(w->a), x); - FP2_copy(&(w->b), y); -} - -/* set FP4 from FP2 */ -/* SU= 8 */ -void FP4_from_FP2(FP4 *w,FP2 *x) -{ - FP2_copy(&(w->a), x); - FP2_zero(&(w->b)); -} - -/* FP4 copy w=x */ -/* SU= 16 */ -void FP4_copy(FP4 *w,FP4 *x) -{ - if (w==x) return; - FP2_copy(&(w->a), &(x->a)); - FP2_copy(&(w->b), &(x->b)); -} - -/* FP4 w=0 */ -/* SU= 8 */ -void FP4_zero(FP4 *w) -{ - FP2_zero(&(w->a)); - FP2_zero(&(w->b)); -} - -/* FP4 w=1 */ -/* SU= 8 */ -void FP4_one(FP4 *w) -{ - FP2_one(&(w->a)); - FP2_zero(&(w->b)); -} - -/* Set w=-x */ -/* SU= 160 */ -void FP4_neg(FP4 *w,FP4 *x) -{ /* Just one field neg */ - FP2 m,t; - FP2_add(&m,&(x->a),&(x->b)); - FP2_neg(&m,&m); - FP2_norm(&m); - FP2_add(&t,&m,&(x->b)); - FP2_add(&(w->b),&m,&(x->a)); - FP2_copy(&(w->a),&t); -} - -/* Set w=conj(x) */ -/* SU= 16 */ -void FP4_conj(FP4 *w,FP4 *x) -{ - FP2_copy(&(w->a), &(x->a)); - FP2_neg(&(w->b), &(x->b)); - FP2_norm(&(w->b)); -} - -/* Set w=-conj(x) */ -/* SU= 16 */ -void FP4_nconj(FP4 *w,FP4 *x) -{ - FP2_copy(&(w->b),&(x->b)); - FP2_neg(&(w->a), &(x->a)); - FP2_norm(&(w->a)); -} - -/* Set w=x+y */ -/* SU= 16 */ -void FP4_add(FP4 *w,FP4 *x,FP4 *y) -{ - FP2_add(&(w->a), &(x->a), &(y->a)); - FP2_add(&(w->b), &(x->b), &(y->b)); -} - -/* Set w=x-y */ -/* SU= 160 */ -void FP4_sub(FP4 *w,FP4 *x,FP4 *y) -{ - FP4 my; - FP4_neg(&my, y); - FP4_add(w, x, &my); - -} -/* SU= 8 */ -/* reduce all components of w mod Modulus */ -void FP4_reduce(FP4 *w) -{ - FP2_reduce(&(w->a)); - FP2_reduce(&(w->b)); -} - -/* SU= 8 */ -/* normalise all elements of w */ -void FP4_norm(FP4 *w) -{ - FP2_norm(&(w->a)); - FP2_norm(&(w->b)); -} - -/* Set w=s*x, where s is FP2 */ -/* SU= 16 */ -void FP4_pmul(FP4 *w,FP4 *x,FP2 *s) -{ - FP2_mul(&(w->a),&(x->a),s); - FP2_mul(&(w->b),&(x->b),s); -} - -/* SU= 16 */ -/* Set w=s*x, where s is int */ -void FP4_imul(FP4 *w,FP4 *x,int s) -{ - FP2_imul(&(w->a),&(x->a),s); - FP2_imul(&(w->b),&(x->b),s); -} - -/* Set w=x^2 */ -/* SU= 232 */ -void FP4_sqr(FP4 *w,FP4 *x) -{ - FP2 t1,t2,t3; - - FP2_mul(&t3,&(x->a),&(x->b)); /* norms x */ - FP2_copy(&t2,&(x->b)); - FP2_add(&t1,&(x->a),&(x->b)); - FP2_mul_ip(&t2); - - FP2_add(&t2,&(x->a),&t2); - - FP2_mul(&(w->a),&t1,&t2); - - FP2_copy(&t2,&t3); - FP2_mul_ip(&t2); - - FP2_add(&t2,&t2,&t3); - - FP2_neg(&t2,&t2); - FP2_add(&(w->a),&(w->a),&t2); /* a=(a+b)(a+i^2.b)-i^2.ab-ab = a*a+ib*ib */ - FP2_add(&(w->b),&t3,&t3); /* b=2ab */ - - FP4_norm(w); -} - -/* Set w=x*y */ -/* SU= 312 */ -void FP4_mul(FP4 *w,FP4 *x,FP4 *y) -{ - - FP2 t1,t2,t3,t4; - FP2_mul(&t1,&(x->a),&(y->a)); /* norms x */ - FP2_mul(&t2,&(x->b),&(y->b)); /* and y */ - FP2_add(&t3,&(y->b),&(y->a)); - FP2_add(&t4,&(x->b),&(x->a)); - - - FP2_mul(&t4,&t4,&t3); /* (xa+xb)(ya+yb) */ - FP2_sub(&t4,&t4,&t1); -#if CHUNK<64 - FP2_norm(&t4); -#endif - FP2_sub(&(w->b),&t4,&t2); - FP2_mul_ip(&t2); - FP2_add(&(w->a),&t2,&t1); - - FP4_norm(w); -} - -/* output FP4 in format [a,b] */ -/* SU= 8 */ -void FP4_output(FP4 *w) -{ - printf("["); - FP2_output(&(w->a)); - printf(","); - FP2_output(&(w->b)); - printf("]"); -} - -/* SU= 8 */ -void FP4_rawoutput(FP4 *w) -{ - printf("["); - FP2_rawoutput(&(w->a)); - printf(","); - FP2_rawoutput(&(w->b)); - printf("]"); -} - -/* Set w=1/x */ -/* SU= 160 */ -void FP4_inv(FP4 *w,FP4 *x) -{ - FP2 t1,t2; - FP2_sqr(&t1,&(x->a)); - FP2_sqr(&t2,&(x->b)); - FP2_mul_ip(&t2); - FP2_sub(&t1,&t1,&t2); - FP2_inv(&t1,&t1); - FP2_mul(&(w->a),&t1,&(x->a)); - FP2_neg(&t1,&t1); - FP2_mul(&(w->b),&t1,&(x->b)); -} - -/* w*=i where i = sqrt(-1+sqrt(-1)) */ -/* SU= 200 */ -void FP4_times_i(FP4 *w) -{ - BIG z; - FP2 s,t; -#if CHUNK<64 - FP4_norm(w); -#endif - FP2_copy(&t,&(w->b)); - - FP2_copy(&s,&t); - - BIG_copy(z,s.a); - FP_neg(s.a,s.b); - BIG_copy(s.b,z); - - FP2_add(&t,&t,&s); -#if CHUNK<64 - FP2_norm(&t); -#endif - FP2_copy(&(w->b),&(w->a)); - FP2_copy(&(w->a),&t); -} - -/* Set w=w^p using Frobenius */ -/* SU= 16 */ -void FP4_frob(FP4 *w,FP2 *f) -{ - FP2_conj(&(w->a),&(w->a)); - FP2_conj(&(w->b),&(w->b)); - FP2_mul( &(w->b),f,&(w->b)); -} - -/* Set r=a^b mod m */ -/* SU= 240 */ -void FP4_pow(FP4 *r,FP4* a,BIG b) -{ - FP4 w; - BIG z,zilch; - int bt; - - BIG_zero(zilch); - BIG_norm(b); - BIG_copy(z,b); - FP4_copy(&w,a); - FP4_one(r); - - while(1) - { - bt=BIG_parity(z); - BIG_shr(z,1); - if (bt) FP4_mul(r,r,&w); - if (BIG_comp(z,zilch)==0) break; - FP4_sqr(&w,&w); - } - FP4_reduce(r); -} - -/* SU= 304 */ -/* XTR xtr_a function */ -void FP4_xtr_A(FP4 *r,FP4 *w,FP4 *x,FP4 *y,FP4 *z) -{ - FP4 t1,t2; - - FP4_copy(r,x); - - FP4_sub(&t1,w,y); - - FP4_pmul(&t1,&t1,&(r->a)); - FP4_add(&t2,w,y); - FP4_pmul(&t2,&t2,&(r->b)); - FP4_times_i(&t2); - - FP4_add(r,&t1,&t2); - FP4_add(r,r,z); - - FP4_norm(r); -} - -/* SU= 152 */ -/* XTR xtr_d function */ -void FP4_xtr_D(FP4 *r,FP4 *x) -{ - FP4 w; - FP4_copy(r,x); - FP4_conj(&w,r); - FP4_add(&w,&w,&w); - FP4_sqr(r,r); - FP4_sub(r,r,&w); - FP4_reduce(r); /* reduce here as multiple calls trigger automatic reductions */ -} - -/* SU= 728 */ -/* r=x^n using XTR method on traces of FP12s */ -void FP4_xtr_pow(FP4 *r,FP4 *x,BIG n) -{ - int i,par,nb; - BIG v; - FP2 w; - FP4 t,a,b,c; - - BIG_zero(v); BIG_inc(v,3); - FP2_from_BIG(&w,v); - FP4_from_FP2(&a,&w); - FP4_copy(&b,x); - FP4_xtr_D(&c,x); - - BIG_norm(n); par=BIG_parity(n); BIG_copy(v,n); BIG_shr(v,1); - if (par==0) {BIG_dec(v,1); BIG_norm(v);} - - nb=BIG_nbits(v); - - for (i=nb-1;i>=0;i--) - { - if (!BIG_bit(v,i)) - { - FP4_copy(&t,&b); - FP4_conj(x,x); - FP4_conj(&c,&c); - FP4_xtr_A(&b,&a,&b,x,&c); - FP4_conj(x,x); - FP4_xtr_D(&c,&t); - FP4_xtr_D(&a,&a); - } - else - { - FP4_conj(&t,&a); - FP4_xtr_D(&a,&b); - FP4_xtr_A(&b,&c,&b,x,&t); - FP4_xtr_D(&c,&c); - } - } - if (par==0) FP4_copy(r,&c); - else FP4_copy(r,&b); - FP4_reduce(r); -} - -/* SU= 872 */ -/* r=ck^a.cl^n using XTR double exponentiation method on traces of FP12s. See Stam thesis. */ -void FP4_xtr_pow2(FP4 *r,FP4 *ck,FP4 *cl,FP4 *ckml,FP4 *ckm2l,BIG a,BIG b) -{ - int i,f2,nb; - BIG d,e,w; - FP4 t,cu,cv,cumv,cum2v; - - BIG_norm(a); - BIG_norm(b); - BIG_copy(e,a); - BIG_copy(d,b); - FP4_copy(&cu,ck); - FP4_copy(&cv,cl); - FP4_copy(&cumv,ckml); - FP4_copy(&cum2v,ckm2l); - - f2=0; - while (BIG_parity(d)==0 && BIG_parity(e)==0) - { - BIG_shr(d,1); - BIG_shr(e,1); - f2++; - } - while (BIG_comp(d,e)!=0) - { - if (BIG_comp(d,e)>0) - { - BIG_imul(w,e,4); BIG_norm(w); - if (BIG_comp(d,w)<=0) - { - BIG_copy(w,d); - BIG_copy(d,e); - BIG_sub(e,w,e); BIG_norm(e); - FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); - FP4_conj(&cum2v,&cumv); - FP4_copy(&cumv,&cv); - FP4_copy(&cv,&cu); - FP4_copy(&cu,&t); - } - else if (BIG_parity(d)==0) - { - BIG_shr(d,1); - FP4_conj(r,&cum2v); - FP4_xtr_A(&t,&cu,&cumv,&cv,r); - FP4_xtr_D(&cum2v,&cumv); - FP4_copy(&cumv,&t); - FP4_xtr_D(&cu,&cu); - } - else if (BIG_parity(e)==1) - { - BIG_sub(d,d,e); BIG_norm(d); - BIG_shr(d,1); - FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); - FP4_xtr_D(&cu,&cu); - FP4_xtr_D(&cum2v,&cv); - FP4_conj(&cum2v,&cum2v); - FP4_copy(&cv,&t); - } - else - { - BIG_copy(w,d); - BIG_copy(d,e); BIG_shr(d,1); - BIG_copy(e,w); - FP4_xtr_D(&t,&cumv); - FP4_conj(&cumv,&cum2v); - FP4_conj(&cum2v,&t); - FP4_xtr_D(&t,&cv); - FP4_copy(&cv,&cu); - FP4_copy(&cu,&t); - } - } - if (BIG_comp(d,e)<0) - { - BIG_imul(w,d,4); BIG_norm(w); - if (BIG_comp(e,w)<=0) - { - BIG_sub(e,e,d); BIG_norm(e); - FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); - FP4_copy(&cum2v,&cumv); - FP4_copy(&cumv,&cu); - FP4_copy(&cu,&t); - } - else if (BIG_parity(e)==0) - { - BIG_copy(w,d); - BIG_copy(d,e); BIG_shr(d,1); - BIG_copy(e,w); - FP4_xtr_D(&t,&cumv); - FP4_conj(&cumv,&cum2v); - FP4_conj(&cum2v,&t); - FP4_xtr_D(&t,&cv); - FP4_copy(&cv,&cu); - FP4_copy(&cu,&t); - } - else if (BIG_parity(d)==1) - { - BIG_copy(w,e); - BIG_copy(e,d); - BIG_sub(w,w,d); BIG_norm(w); - BIG_copy(d,w); BIG_shr(d,1); - FP4_xtr_A(&t,&cu,&cv,&cumv,&cum2v); - FP4_conj(&cumv,&cumv); - FP4_xtr_D(&cum2v,&cu); - FP4_conj(&cum2v,&cum2v); - FP4_xtr_D(&cu,&cv); - FP4_copy(&cv,&t); - } - else - { - BIG_shr(d,1); - FP4_conj(r,&cum2v); - FP4_xtr_A(&t,&cu,&cumv,&cv,r); - FP4_xtr_D(&cum2v,&cumv); - FP4_copy(&cumv,&t); - FP4_xtr_D(&cu,&cu); - } - } - } - FP4_xtr_A(r,&cu,&cv,&cumv,&cum2v); - for (i=0;i<f2;i++) FP4_xtr_D(r,r); - FP4_xtr_pow(r,r,d); -} -/* -int main(){ - FP2 w0,w1,f; - FP4 w,t; - FP4 c1,c2,c3,c4,cr; - BIG a,b; - BIG e,e1,e2; - BIG p,md; - - - BIG_rcopy(md,Modulus); - //Test w^(P^4) = w mod p^2 - BIG_zero(a); BIG_inc(a,27); - BIG_zero(b); BIG_inc(b,45); - FP2_from_BIGs(&w0,a,b); - - BIG_zero(a); BIG_inc(a,33); - BIG_zero(b); BIG_inc(b,54); - FP2_from_BIGs(&w1,a,b); - - FP4_from_FP2s(&w,&w0,&w1); - FP4_reduce(&w); - - printf("w= "); - FP4_output(&w); - printf("\n"); - - - FP4_copy(&t,&w); - - - BIG_copy(p,md); - FP4_pow(&w,&w,p); - - printf("w^p= "); - FP4_output(&w); - printf("\n"); -//exit(0); - - BIG_rcopy(a,CURVE_Fra); - BIG_rcopy(b,CURVE_Frb); - FP2_from_BIGs(&f,a,b); - - FP4_frob(&t,&f); - printf("w^p= "); - FP4_output(&t); - printf("\n"); - - FP4_pow(&w,&w,p); - FP4_pow(&w,&w,p); - FP4_pow(&w,&w,p); - printf("w^p4= "); - FP4_output(&w); - printf("\n"); - -// Test 1/(1/x) = x mod p^4 - FP4_from_FP2s(&w,&w0,&w1); - printf("Test Inversion \nw= "); - FP4_output(&w); - printf("\n"); - - FP4_inv(&w,&w); - printf("1/w mod p^4 = "); - FP4_output(&w); - printf("\n"); - - FP4_inv(&w,&w); - printf("1/(1/w) mod p^4 = "); - FP4_output(&w); - printf("\n"); - - BIG_zero(e); BIG_inc(e,12); - - - - // FP4_xtr_A(&w,&t,&w,&t,&t); - FP4_xtr_pow(&w,&w,e); - - printf("w^e= "); - FP4_output(&w); - printf("\n"); - - - BIG_zero(a); BIG_inc(a,37); - BIG_zero(b); BIG_inc(b,17); - FP2_from_BIGs(&w0,a,b); - - BIG_zero(a); BIG_inc(a,49); - BIG_zero(b); BIG_inc(b,31); - FP2_from_BIGs(&w1,a,b); - - FP4_from_FP2s(&c1,&w0,&w1); - FP4_from_FP2s(&c2,&w0,&w1); - FP4_from_FP2s(&c3,&w0,&w1); - FP4_from_FP2s(&c4,&w0,&w1); - - BIG_zero(e1); BIG_inc(e1,3331); - BIG_zero(e2); BIG_inc(e2,3372); - - FP4_xtr_pow2(&w,&c1,&w,&c2,&c3,e1,e2); - - printf("c^e= "); - FP4_output(&w); - printf("\n"); - - - return 0; -} -*/ - http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/gcm.c ---------------------------------------------------------------------- diff --git a/c/gcm.c b/c/gcm.c deleted file mode 100755 index c36b3fb..0000000 --- a/c/gcm.c +++ /dev/null @@ -1,368 +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. -*/ - - - -/* - * Implementation of the AES-GCM Encryption/Authentication - * - * Some restrictions.. - * 1. Only for use with AES - * 2. Returned tag is always 128-bits. Truncate at your own risk. - * 3. The order of function calls must follow some rules - * - * Typical sequence of calls.. - * 1. call GCM_init - * 2. call GCM_add_header any number of times, as long as length of header is multiple of 16 bytes (block size) - * 3. call GCM_add_header one last time with any length of header - * 4. call GCM_add_cipher any number of times, as long as length of cipher/plaintext is multiple of 16 bytes - * 5. call GCM_add_cipher one last time with any length of cipher/plaintext - * 6. call GCM_finish to extract the tag. - * - * See http://www.mindspring.com/~dmcgrew/gcm-nist-6.pdf - */ -/* SU=m, m is Stack Usage */ - -#include <stdlib.h> -#include <string.h> -#include "amcl.h" - -#define NB 4 -#define MR_TOBYTE(x) ((uchar)((x))) - -static unsign32 pack(const uchar *b) -{ /* pack bytes into a 32-bit Word */ - return ((unsign32)b[0]<<24)|((unsign32)b[1]<<16)|((unsign32)b[2]<<8)|(unsign32)b[3]; -} - -static void unpack(unsign32 a,uchar *b) -{ /* unpack bytes from a word */ - b[3]=MR_TOBYTE(a); - b[2]=MR_TOBYTE(a>>8); - b[1]=MR_TOBYTE(a>>16); - b[0]=MR_TOBYTE(a>>24); -} - -static void precompute(gcm *g,uchar *H) -{ /* precompute small 2k bytes gf2m table of x^n.H */ - int i,j; - unsign32 *last,*next,b; - - for (i=j=0;i<NB;i++,j+=4) g->table[0][i]=pack((uchar *)&H[j]); - - for (i=1;i<128;i++) - { - next=g->table[i]; last=g->table[i-1]; b=0; - for (j=0;j<NB;j++) {next[j]=b|(last[j])>>1; b=last[j]<<31;} - if (b) next[0]^=0xE1000000; /* irreducible polynomial */ - } -} - -/* SU= 32 */ -static void gf2mul(gcm *g) -{ /* gf2m mul - Z=H*X mod 2^128 */ - int i,j,m,k; - unsign32 P[4]; - uchar b; - - P[0]=P[1]=P[2]=P[3]=0; - j=8; m=0; - for (i=0;i<128;i++) - { - b=(g->stateX[m]>>(--j))&1; - if (b) for (k=0;k<NB;k++) P[k]^=g->table[i][k]; - if (j==0) - { - j=8; m++; - if (m==16) break; - } - } - for (i=j=0;i<NB;i++,j+=4) unpack(P[i],(uchar *)&g->stateX[j]); -} - -/* SU= 32 */ -static void GCM_wrap(gcm *g) -{ /* Finish off GHASH */ - int i,j; - unsign32 F[4]; - uchar L[16]; - -/* convert lengths from bytes to bits */ - F[0]=(g->lenA[0]<<3)|(g->lenA[1]&0xE0000000)>>29; - F[1]=g->lenA[1]<<3; - F[2]=(g->lenC[0]<<3)|(g->lenC[1]&0xE0000000)>>29; - F[3]=g->lenC[1]<<3; - for (i=j=0;i<NB;i++,j+=4) unpack(F[i],(uchar *)&L[j]); - - for (i=0;i<16;i++) g->stateX[i]^=L[i]; - gf2mul(g); -} - -static int GCM_ghash(gcm *g,char *plain,int len) -{ - int i,j=0; - unsign32 counter; - uchar B[16]; - if (g->status==GCM_ACCEPTING_HEADER) g->status=GCM_ACCEPTING_CIPHER; - if (g->status!=GCM_ACCEPTING_CIPHER) return 0; - - while (j<len) - { - for (i=0;i<16 && j<len;i++) - { - g->stateX[i]^=plain[j++]; - g->lenC[1]++; if (g->lenC[1]==0) g->lenC[0]++; - } - gf2mul(g); - } - if (len%16!=0) g->status=GCM_NOT_ACCEPTING_MORE; - return 1; -} - -/* SU= 48 */ -/* Initialize GCM mode */ -void GCM_init(gcm* g,char *key,int niv,char *iv) -{ /* iv size niv is usually 12 bytes (96 bits). AES key is 16 bytes */ - int i; - uchar H[16]; - for (i=0;i<16;i++) {H[i]=0; g->stateX[i]=0;} - - AES_init(&(g->a),ECB,key,iv); - AES_ecb_encrypt(&(g->a),H); /* E(K,0) */ - precompute(g,H); - - g->lenA[0]=g->lenC[0]=g->lenA[1]=g->lenC[1]=0; - if (niv==12) - { - for (i=0;i<12;i++) g->a.f[i]=iv[i]; - unpack((unsign32)1,(uchar *)&(g->a.f[12])); /* initialise IV */ - for (i=0;i<16;i++) g->Y_0[i]=g->a.f[i]; - } - else - { - g->status=GCM_ACCEPTING_CIPHER; - GCM_ghash(g,iv,niv); /* GHASH(H,0,IV) */ - GCM_wrap(g); - for (i=0;i<16;i++) {g->a.f[i]=g->stateX[i];g->Y_0[i]=g->a.f[i];g->stateX[i]=0;} - g->lenA[0]=g->lenC[0]=g->lenA[1]=g->lenC[1]=0; - } - g->status=GCM_ACCEPTING_HEADER; -} - -/* SU= 24 */ -/* Add Header data - included but not encrypted */ -int GCM_add_header(gcm* g,char *header,int len) -{ /* Add some header. Won't be encrypted, but will be authenticated. len is length of header */ - int i,j=0; - if (g->status!=GCM_ACCEPTING_HEADER) return 0; - - while (j<len) - { - for (i=0;i<16 && j<len;i++) - { - g->stateX[i]^=header[j++]; - g->lenA[1]++; if (g->lenA[1]==0) g->lenA[0]++; - } - gf2mul(g); - } - if (len%16!=0) g->status=GCM_ACCEPTING_CIPHER; - return 1; -} - -/* SU= 48 */ -/* Add Plaintext - included and encrypted */ -int GCM_add_plain(gcm *g,char *cipher,char *plain,int len) -{ /* Add plaintext to extract ciphertext, len is length of plaintext. */ - int i,j=0; - unsign32 counter; - uchar B[16]; - if (g->status==GCM_ACCEPTING_HEADER) g->status=GCM_ACCEPTING_CIPHER; - if (g->status!=GCM_ACCEPTING_CIPHER) return 0; - - while (j<len) - { - counter=pack((uchar *)&(g->a.f[12])); - counter++; - unpack(counter,(uchar *)&(g->a.f[12])); /* increment counter */ - for (i=0;i<16;i++) B[i]=g->a.f[i]; - AES_ecb_encrypt(&(g->a),B); /* encrypt it */ - - for (i=0;i<16 && j<len;i++) - { - cipher[j]=plain[j]^B[i]; - g->stateX[i]^=cipher[j++]; - g->lenC[1]++; if (g->lenC[1]==0) g->lenC[0]++; - } - gf2mul(g); - } - if (len%16!=0) g->status=GCM_NOT_ACCEPTING_MORE; - return 1; -} - -/* SU= 48 */ -/* Add Ciphertext - decrypts to plaintext */ -int GCM_add_cipher(gcm *g,char *plain,char *cipher,int len) -{ /* Add ciphertext to extract plaintext, len is length of ciphertext. */ - int i,j=0; - unsign32 counter; - uchar B[16]; - if (g->status==GCM_ACCEPTING_HEADER) g->status=GCM_ACCEPTING_CIPHER; - if (g->status!=GCM_ACCEPTING_CIPHER) return 0; - - while (j<len) - { - counter=pack((uchar *)&(g->a.f[12])); - counter++; - unpack(counter,(uchar *)&(g->a.f[12])); /* increment counter */ - for (i=0;i<16;i++) B[i]=g->a.f[i]; - AES_ecb_encrypt(&(g->a),B); /* encrypt it */ - for (i=0;i<16 && j<len;i++) - { - plain[j]=cipher[j]^B[i]; - g->stateX[i]^=cipher[j++]; - g->lenC[1]++; if (g->lenC[1]==0) g->lenC[0]++; - } - gf2mul(g); - } - if (len%16!=0) g->status=GCM_NOT_ACCEPTING_MORE; - return 1; -} - -/* SU= 16 */ -/* Finish and extract Tag */ -void GCM_finish(gcm *g,char *tag) -{ /* Finish off GHASH and extract tag (MAC) */ - int i; - - GCM_wrap(g); - -/* extract tag */ - if (tag!=NULL) - { - AES_ecb_encrypt(&(g->a),g->Y_0); /* E(K,Y0) */ - for (i=0;i<16;i++) g->Y_0[i]^=g->stateX[i]; - for (i=0;i<16;i++) {tag[i]=g->Y_0[i];g->Y_0[i]=g->stateX[i]=0;} - } - g->status=GCM_FINISHED; - AES_end(&(g->a)); -} - - -// Compile with -// gcc -O2 amcl_gcm.c amcl_aes.c -o amcl_gcm.exe -/* SU= 16 -*/ -/* -static void hex2bytes(char *hex,char *bin) -{ - int i; - char v; - int len=strlen(hex); - for (i = 0; i < len/2; i++) { - char c = hex[2*i]; - if (c >= '0' && c <= '9') { - v = c - '0'; - } else if (c >= 'A' && c <= 'F') { - v = c - 'A' + 10; - } else if (c >= 'a' && c <= 'f') { - v = c - 'a' + 10; - } else { - v = 0; - } - v <<= 4; - c = hex[2*i + 1]; - if (c >= '0' && c <= '9') { - v += c - '0'; - } else if (c >= 'A' && c <= 'F') { - v += c - 'A' + 10; - } else if (c >= 'a' && c <= 'f') { - v += c - 'a' + 10; - } else { - v = 0; - } - bin[i] = v; - } -} -*/ -/* -int main() -{ - int i; - - char* KT="feffe9928665731c6d6a8f9467308308"; - char* MT="d9313225f88406e5a55909c5aff5269a86a7a9531534f7da2e4c303d8a318a721c3c0c95956809532fcf0e2449a6b525b16aedf5aa0de657ba637b39"; - char* HT="feedfacedeadbeeffeedfacedeadbeefabaddad2"; -// char* NT="cafebabefacedbaddecaf888"; -// Tag should be 5bc94fbc3221a5db94fae95ae7121a47 - char* NT="9313225df88406e555909c5aff5269aa6a7a9538534f7da1e4c303d2a318a728c3c0c95156809539fcf0e2429a6b525416aedbf5a0de6a57a637b39b"; -// Tag should be 619cc5aefffe0bfa462af43c1699d050 - - - int len=strlen(MT)/2; - int lenH=strlen(HT)/2; - int lenK=strlen(KT)/2; - int lenIV=strlen(NT)/2; - - char T[16]; // Tag - char K[16]; // AES Key - char H[64]; // Header - to be included in Authentication, but not encrypted - char N[100]; // IV - Initialisation vector - char M[100]; // Plaintext to be encrypted/authenticated - char C[100]; // Ciphertext - char P[100]; // Recovered Plaintext - - gcm g; - - hex2bytes(MT, M); - hex2bytes(HT, H); - hex2bytes(NT, N); - hex2bytes(KT, K); - - printf("Plaintext=\n"); - for (i=0;i<len;i++) printf("%02x",(unsigned char)M[i]); - printf("\n"); - - GCM_init(&g,K,lenIV,N); - GCM_add_header(&g,H,lenH); - GCM_add_plain(&g,C,M,len); - GCM_finish(&g,T); - - printf("Ciphertext=\n"); - for (i=0;i<len;i++) printf("%02x",(unsigned char)C[i]); - printf("\n"); - - printf("Tag=\n"); - for (i=0;i<16;i++) printf("%02x",(unsigned char)T[i]); - printf("\n"); - - GCM_init(&g,K,lenIV,N); - GCM_add_header(&g,H,lenH); - GCM_add_cipher(&g,P,C,len); - GCM_finish(&g,T); - - printf("Plaintext=\n"); - for (i=0;i<len;i++) printf("%02x",(unsigned char)P[i]); - printf("\n"); - - printf("Tag=\n"); - for (i=0;i<16;i++) printf("%02x",(unsigned char)T[i]); - printf("\n"); -} - -*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/hash.c ---------------------------------------------------------------------- diff --git a/c/hash.c b/c/hash.c deleted file mode 100755 index 2d11437..0000000 --- a/c/hash.c +++ /dev/null @@ -1,171 +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. -*/ - -/* - * Implementation of the Secure Hashing Algorithm (SHA-256) - * - * Generates a 256 bit message digest. It should be impossible to come - * come up with two messages that hash to the same value ("collision free"). - * - * For use with byte-oriented messages only. Could/Should be speeded - * up by unwinding loops in HASH_transform(), and assembly patches. - */ -/* SU=m, m is Stack Usage */ - -#include "amcl.h" - -#define H0 0x6A09E667L -#define H1 0xBB67AE85L -#define H2 0x3C6EF372L -#define H3 0xA54FF53AL -#define H4 0x510E527FL -#define H5 0x9B05688CL -#define H6 0x1F83D9ABL -#define H7 0x5BE0CD19L - -static const unsign32 K[64]={ -0x428a2f98L,0x71374491L,0xb5c0fbcfL,0xe9b5dba5L,0x3956c25bL,0x59f111f1L,0x923f82a4L,0xab1c5ed5L, -0xd807aa98L,0x12835b01L,0x243185beL,0x550c7dc3L,0x72be5d74L,0x80deb1feL,0x9bdc06a7L,0xc19bf174L, -0xe49b69c1L,0xefbe4786L,0x0fc19dc6L,0x240ca1ccL,0x2de92c6fL,0x4a7484aaL,0x5cb0a9dcL,0x76f988daL, -0x983e5152L,0xa831c66dL,0xb00327c8L,0xbf597fc7L,0xc6e00bf3L,0xd5a79147L,0x06ca6351L,0x14292967L, -0x27b70a85L,0x2e1b2138L,0x4d2c6dfcL,0x53380d13L,0x650a7354L,0x766a0abbL,0x81c2c92eL,0x92722c85L, -0xa2bfe8a1L,0xa81a664bL,0xc24b8b70L,0xc76c51a3L,0xd192e819L,0xd6990624L,0xf40e3585L,0x106aa070L, -0x19a4c116L,0x1e376c08L,0x2748774cL,0x34b0bcb5L,0x391c0cb3L,0x4ed8aa4aL,0x5b9cca4fL,0x682e6ff3L, -0x748f82eeL,0x78a5636fL,0x84c87814L,0x8cc70208L,0x90befffaL,0xa4506cebL,0xbef9a3f7L,0xc67178f2L}; - -#define PAD 0x80 -#define ZERO 0 - -/* functions */ - -#define S(n,x) (((x)>>n) | ((x)<<(32-n))) -#define R(n,x) ((x)>>n) - -#define Ch(x,y,z) ((x&y)^(~(x)&z)) -#define Maj(x,y,z) ((x&y)^(x&z)^(y&z)) -#define Sig0(x) (S(2,x)^S(13,x)^S(22,x)) -#define Sig1(x) (S(6,x)^S(11,x)^S(25,x)) -#define theta0(x) (S(7,x)^S(18,x)^R(3,x)) -#define theta1(x) (S(17,x)^S(19,x)^R(10,x)) - -/* SU= 72 */ -static void HASH_transform(hash *sh) -{ /* basic transformation step */ - unsign32 a,b,c,d,e,f,g,h,t1,t2; - int j; - for (j=16;j<64;j++) - sh->w[j]=theta1(sh->w[j-2])+sh->w[j-7]+theta0(sh->w[j-15])+sh->w[j-16]; - - a=sh->h[0]; b=sh->h[1]; c=sh->h[2]; d=sh->h[3]; - e=sh->h[4]; f=sh->h[5]; g=sh->h[6]; h=sh->h[7]; - - for (j=0;j<64;j++) - { /* 64 times - mush it up */ - t1=h+Sig1(e)+Ch(e,f,g)+K[j]+sh->w[j]; - t2=Sig0(a)+Maj(a,b,c); - h=g; g=f; f=e; - e=d+t1; - d=c; - c=b; - b=a; - a=t1+t2; - } - - sh->h[0]+=a; sh->h[1]+=b; sh->h[2]+=c; sh->h[3]+=d; - sh->h[4]+=e; sh->h[5]+=f; sh->h[6]+=g; sh->h[7]+=h; -} - -/* Initialise Hash function */ -void HASH_init(hash *sh) -{ /* re-initialise */ - int i; - for (i=0;i<64;i++) sh->w[i]=0L; - sh->length[0]=sh->length[1]=0L; - sh->h[0]=H0; - sh->h[1]=H1; - sh->h[2]=H2; - sh->h[3]=H3; - sh->h[4]=H4; - sh->h[5]=H5; - sh->h[6]=H6; - sh->h[7]=H7; -} - -/* process a single byte */ -void HASH_process(hash *sh,int byte) -{ /* process the next message byte */ - int cnt; -//printf("byt= %x\n",byte); - cnt=(int)((sh->length[0]/32)%16); - - sh->w[cnt]<<=8; - sh->w[cnt]|=(unsign32)(byte&0xFF); - - sh->length[0]+=8; - if (sh->length[0]==0L) { sh->length[1]++; sh->length[0]=0L; } - if ((sh->length[0]%512)==0) HASH_transform(sh); -} - -/* SU= 24 */ -/* Generate 32-byte Hash */ -void HASH_hash(hash *sh,char digest[32]) -{ /* pad message and finish - supply digest */ - int i; - unsign32 len0,len1; - len0=sh->length[0]; - len1=sh->length[1]; - HASH_process(sh,PAD); - while ((sh->length[0]%512)!=448) HASH_process(sh,ZERO); - sh->w[14]=len1; - sh->w[15]=len0; - HASH_transform(sh); - for (i=0;i<32;i++) - { /* convert to bytes */ - digest[i]=(char)((sh->h[i/4]>>(8*(3-i%4))) & 0xffL); - } - HASH_init(sh); -} - -/* test program: should produce digest */ - -//248d6a61 d20638b8 e5c02693 0c3e6039 a33ce459 64ff2167 f6ecedd4 19db06c1 - -/* -#include <stdio.h> -#include "amcl.h" - -char test[]="abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq"; - -int main() -{ - char digest[32]; - int i; - hash sh; - HASH_init(&sh); - for (i=0;test[i]!=0;i++) - HASH_process(&sh,test[i]); - - HASH_hash(&sh,digest); - for (i=0;i<32;i++) printf("%02x",(unsigned char)digest[i]); - printf("\n"); - return 0; -} - -*/ - http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/70e3a3a3/c/maxstack.c ---------------------------------------------------------------------- diff --git a/c/maxstack.c b/c/maxstack.c deleted file mode 100755 index 3eb436f..0000000 --- a/c/maxstack.c +++ /dev/null @@ -1,62 +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. -*/ - -/* - How to determine maximum stack usage - 1. Compile this file *with no optimization*, for example gcc -c maxstack.c - 2. Rename your main() function to mymain() - 3. Compile with normal level of optimization, linking to maxstack.o for example gcc maxstack.o -O3 myprogram.c -o myprogam - 4. Execute myprogram - 5. Program runs, at end prints out maximum stack usage - - Caveat Code! - Mike Scott October 2014 -*/ - -#include <stdio.h> - -#define MAXSTACK 65536 /* greater than likely stack requirement */ - -extern void mymain(); - -void start() -{ - char stack[MAXSTACK]; - int i; - for (i=0;i<MAXSTACK;i++) stack[i]=0x55; -} - -void finish() -{ - char stack[MAXSTACK]; - int i; - for (i=0;i<MAXSTACK;i++) - if (stack[i]!=0x55) break; - printf("Max Stack usage = %d\n",MAXSTACK-i); -} - -int main() -{ - start(); - - mymain(); - - finish(); - return 0; -}
