http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version3/c/ff.c ---------------------------------------------------------------------- diff --git a/version3/c/ff.c b/version3/c/ff.c deleted file mode 100644 index fd64dd9..0000000 --- a/version3/c/ff.c +++ /dev/null @@ -1,1155 +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 "ff_WWW.h" - -/* Arazi and Qi inversion mod 256 */ -static int invmod256(int a) -{ - int 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^BIGBITS. This is very fast! */ -void BIG_XXX_invmod2m(BIG_XXX a) -{ - int i; - BIG_XXX U,t1,b,c; - BIG_XXX_zero(U); - BIG_XXX_inc(U,invmod256(BIG_XXX_lastbits(a,8))); - for (i=8; i<BIGBITS_XXX; i<<=1) - { - BIG_XXX_norm(U); - BIG_XXX_copy(b,a); - BIG_XXX_mod2m(b,i); // bottom i bits of a - - BIG_XXX_smul(t1,U,b); - BIG_XXX_shr(t1,i); // top i bits of U*b - - BIG_XXX_copy(c,a); - BIG_XXX_shr(c,i); - BIG_XXX_mod2m(c,i); // top i bits of a - - BIG_XXX_smul(b,U,c); - BIG_XXX_mod2m(b,i); // bottom i bits of U*c - - BIG_XXX_add(t1,t1,b); - BIG_XXX_norm(t1); - BIG_XXX_smul(b,t1,U); - BIG_XXX_copy(t1,b); // (t1+b)*U - BIG_XXX_mod2m(t1,i); // bottom i bits of (t1+b)*U - - BIG_XXX_one(b); - BIG_XXX_shl(b,i); - BIG_XXX_sub(t1,b,t1); - BIG_XXX_norm(t1); - - BIG_XXX_shl(t1,i); - - BIG_XXX_add(U,U,t1); - } - BIG_XXX_copy(a,U); - BIG_XXX_norm(a); - BIG_XXX_mod2m(a,BIGBITS_XXX); -} - -/* -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_WWW_copy(BIG_XXX x[],BIG_XXX y[],int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_copy(x[i],y[i]); -} - -/* x=y<<n */ -static void FF_WWW_dsucopy(BIG_XXX x[],BIG_XXX y[],int n) -{ - int i; - for (i=0; i<n; i++) - { - BIG_XXX_copy(x[n+i],y[i]); - BIG_XXX_zero(x[i]); - } -} - -/* x=y */ -static void FF_WWW_dscopy(BIG_XXX x[],BIG_XXX y[],int n) -{ - int i; - for (i=0; i<n; i++) - { - BIG_XXX_copy(x[i],y[i]); - BIG_XXX_zero(x[n+i]); - } -} - -/* x=y>>n */ -static void FF_WWW_sducopy(BIG_XXX x[],BIG_XXX y[],int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_copy(x[i],y[n+i]); -} - -/* set to zero */ -void FF_WWW_zero(BIG_XXX x[],int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_zero(x[i]); -} - -/* test equals 0 */ -int FF_WWW_iszilch(BIG_XXX x[],int n) -{ - int i; - for (i=0; i<n; i++) - if (!BIG_XXX_iszilch(x[i])) return 0; - return 1; -} - -/* shift right by BIGBITS-bit words */ -static void FF_WWW_shrw(BIG_XXX a[],int n) -{ - int i; - for (i=0; i<n; i++) - { - BIG_XXX_copy(a[i],a[i+n]); - BIG_XXX_zero(a[i+n]); - } -} - -/* shift left by BIGBITS-bit words */ -static void FF_WWW_shlw(BIG_XXX a[],int n) -{ - int i; - for (i=0; i<n; i++) - { - BIG_XXX_copy(a[i+n],a[i]); - BIG_XXX_zero(a[i]); - } -} - -/* extract last bit */ -int FF_WWW_parity(BIG_XXX x[]) -{ - return BIG_XXX_parity(x[0]); -} - -/* extract last m bits */ -int FF_WWW_lastbits(BIG_XXX x[],int m) -{ - return BIG_XXX_lastbits(x[0],m); -} - -/* x=1 */ -void FF_WWW_one(BIG_XXX x[],int n) -{ - int i; - BIG_XXX_one(x[0]); - for (i=1; i<n; i++) - BIG_XXX_zero(x[i]); -} - -/* x=m, where m is 32-bit int */ -void FF_WWW_init(BIG_XXX x[],sign32 m,int n) -{ - int i; - BIG_XXX_zero(x[0]); -#if CHUNK<64 - x[0][0]=(chunk)(m&BMASK_XXX); - x[0][1]=(chunk)(m>>BASEBITS_XXX); -#else - x[0][0]=(chunk)m; -#endif - for (i=1; i<n; i++) - BIG_XXX_zero(x[i]); -} - -/* compare x and y - must be normalised */ -int FF_WWW_comp(BIG_XXX x[],BIG_XXX y[],int n) -{ - int i,j; - for (i=n-1; i>=0; i--) - { - j=BIG_XXX_comp(x[i],y[i]); - if (j!=0) return j; - } - return 0; -} - -/* recursive add */ -static void FF_WWW_radd(BIG_XXX z[],int zp,BIG_XXX x[],int xp,BIG_XXX y[],int yp,int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_add(z[zp+i],x[xp+i],y[yp+i]); -} - -/* recursive inc */ -static void FF_WWW_rinc(BIG_XXX z[],int zp,BIG_XXX y[],int yp,int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_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_WWW_rdec(BIG_XXX z[],int zp,BIG_XXX y[],int yp,int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_sub(z[zp+i],z[zp+i],y[yp+i]); -} - -/* simple add */ -void FF_WWW_add(BIG_XXX z[],BIG_XXX x[],BIG_XXX y[],int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_add(z[i],x[i],y[i]); -} - -/* simple sub */ -void FF_WWW_sub(BIG_XXX z[],BIG_XXX x[],BIG_XXX y[],int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_sub(z[i],x[i],y[i]); -} - -/* increment/decrement by a small integer */ -void FF_WWW_inc(BIG_XXX x[],int m,int n) -{ - BIG_XXX_inc(x[0],m); - FF_WWW_norm(x,n); -} - -void FF_WWW_dec(BIG_XXX x[],int m,int n) -{ - BIG_XXX_dec(x[0],m); - FF_WWW_norm(x,n); -} - -/* normalise - but hold any overflow in top part unless n<0 */ -static void FF_WWW_rnorm(BIG_XXX 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_XXX_norm(z[zp+i]); - - z[zp+i][NLEN_XXX-1]^=carry<<P_TBITS_WWW; /* remove it */ - z[zp+i+1][0]+=carry; - } - carry=BIG_XXX_norm(z[zp+n-1]); - if (trunc) z[zp+n-1][NLEN_XXX-1]^=carry<<P_TBITS_WWW; -} - -void FF_WWW_norm(BIG_XXX z[],int n) -{ - FF_WWW_rnorm(z,0,n); -} - -/* shift left by one bit */ -void FF_WWW_shl(BIG_XXX x[],int n) -{ - int i; - int carry,delay_carry=0; - for (i=0; i<n-1; i++) - { - carry=BIG_XXX_fshl(x[i],1); - x[i][0]|=delay_carry; - x[i][NLEN_XXX-1]^=(chunk)carry<<P_TBITS_WWW; - delay_carry=carry; - } - BIG_XXX_fshl(x[n-1],1); - x[n-1][0]|=delay_carry; -} - -/* shift right by one bit */ -void FF_WWW_shr(BIG_XXX x[],int n) -{ - int i; - int carry; - for (i=n-1; i>0; i--) - { - carry=BIG_XXX_fshr(x[i],1); - x[i-1][NLEN_XXX-1]|=(chunk)carry<<P_TBITS_WWW; - } - BIG_XXX_fshr(x[0],1); -} - -void FF_WWW_output(BIG_XXX x[],int n) -{ - int i; - FF_WWW_norm(x,n); - for (i=n-1; i>=0; i--) - { - BIG_XXX_output(x[i]); - printf(" "); - } -} - -void FF_WWW_rawoutput(BIG_XXX x[],int n) -{ - int i; - for (i=n-1; i>=0; i--) - { - BIG_XXX_rawoutput(x[i]); - printf(" "); - } -} - -/* Convert FFs to/from octet strings */ -void FF_WWW_toOctet(octet *w,BIG_XXX x[],int n) -{ - int i; - w->len=n*MODBYTES_XXX; - for (i=0; i<n; i++) - { - BIG_XXX_toBytes(&(w->val[(n-i-1)*MODBYTES_XXX]),x[i]); - } -} - -void FF_WWW_fromOctet(BIG_XXX x[],octet *w,int n) -{ - int i; - for (i=0; i<n; i++) - { - BIG_XXX_fromBytes(x[i],&(w->val[(n-i-1)*MODBYTES_XXX])); - } -} - -/* in-place swapping using xor - side channel resistant */ -static void FF_WWW_cswap(BIG_XXX a[],BIG_XXX b[],int d,int n) -{ - int i; - for (i=0; i<n; i++) - BIG_XXX_cswap(a[i],b[i],d); - return; -} - -/* z=x*y, t is workspace */ -static void FF_WWW_karmul(BIG_XXX z[],int zp,BIG_XXX x[],int xp,BIG_XXX y[],int yp,BIG_XXX t[],int tp,int n) -{ - int nd2; - if (n==1) - { - BIG_XXX_norm(x[xp]); - BIG_XXX_norm(y[yp]); - BIG_XXX_mul(t[tp],x[xp],y[yp]); - BIG_XXX_split(z[zp+1],z[zp],t[tp],BIGBITS_XXX); - return; - } - - nd2=n/2; - FF_WWW_radd(z,zp,x,xp,x,xp+nd2,nd2); - FF_WWW_rnorm(z,zp,nd2); /* needs this if recursion level too deep */ - - FF_WWW_radd(z,zp+nd2,y,yp,y,yp+nd2,nd2); - FF_WWW_rnorm(z,zp+nd2,nd2); - FF_WWW_karmul(t,tp,z,zp,z,zp+nd2,t,tp+n,nd2); - FF_WWW_karmul(z,zp,x,xp,y,yp,t,tp+n,nd2); - FF_WWW_karmul(z,zp+n,x,xp+nd2,y,yp+nd2,t,tp+n,nd2); - FF_WWW_rdec(t,tp,z,zp,n); - FF_WWW_rdec(t,tp,z,zp+n,n); - FF_WWW_rinc(z,zp+nd2,t,tp,n); - FF_WWW_rnorm(z,zp,2*n); -} - -static void FF_WWW_karsqr(BIG_XXX z[],int zp,BIG_XXX x[],int xp,BIG_XXX t[],int tp,int n) -{ - int nd2; - if (n==1) - { - BIG_XXX_norm(x[xp]); - BIG_XXX_sqr(t[tp],x[xp]); - BIG_XXX_split(z[zp+1],z[zp],t[tp],BIGBITS_XXX); - return; - } - nd2=n/2; - FF_WWW_karsqr(z,zp,x,xp,t,tp+n,nd2); - FF_WWW_karsqr(z,zp+n,x,xp+nd2,t,tp+n,nd2); - FF_WWW_karmul(t,tp,x,xp,x,xp+nd2,t,tp+n,nd2); - FF_WWW_rinc(z,zp+nd2,t,tp,n); - FF_WWW_rinc(z,zp+nd2,t,tp,n); - - FF_WWW_rnorm(z,zp+nd2,n); /* was FF_rnorm(z,zp,2*n) */ -} - -static void FF_WWW_karmul_lower(BIG_XXX z[],int zp,BIG_XXX x[],int xp,BIG_XXX y[],int yp,BIG_XXX 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_XXX_norm(x[xp]); - BIG_XXX_norm(y[yp]); - BIG_XXX_smul(z[zp],x[xp],y[yp]); - return; - } - nd2=n/2; - FF_WWW_karmul(z,zp,x,xp,y,yp,t,tp+n,nd2); - FF_WWW_karmul_lower(t,tp,x,xp+nd2,y,yp,t,tp+n,nd2); - FF_WWW_rinc(z,zp+nd2,t,tp,nd2); - FF_WWW_karmul_lower(t,tp,x,xp,y,yp+nd2,t,tp+n,nd2); - FF_WWW_rinc(z,zp+nd2,t,tp,nd2); - FF_WWW_rnorm(z,zp+nd2,-nd2); /* truncate it */ -} - -static void FF_WWW_karmul_upper(BIG_XXX z[],BIG_XXX x[],BIG_XXX y[],BIG_XXX t[],int n) -{ - /* Calculates Most Significant upper half of x*y, given lower part */ - int nd2; - - nd2=n/2; - FF_WWW_radd(z,n,x,0,x,nd2,nd2); - FF_WWW_radd(z,n+nd2,y,0,y,nd2,nd2); - FF_WWW_rnorm(z,n,nd2); - FF_WWW_rnorm(z,n+nd2,nd2); - - FF_WWW_karmul(t,0,z,n+nd2,z,n,t,n,nd2); /* t = (a0+a1)(b0+b1) */ - FF_WWW_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_WWW_rdec(t,0,z,n,n); /* t=t-a1b1 */ - FF_WWW_rinc(z,nd2,z,0,nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */ - FF_WWW_rdec(z,nd2,t,0,nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */ - FF_WWW_rnorm(z,0,-n); /* a0b0 now in z - truncate it */ - FF_WWW_rdec(t,0,z,0,n); /* (a0+a1)(b0+b1) - a0b0 */ - FF_WWW_rinc(z,nd2,t,0,n); - - FF_WWW_rnorm(z,nd2,n); -} - -/* z=x*y */ -void FF_WWW_mul(BIG_XXX z[],BIG_XXX x[],BIG_XXX y[],int n) -{ -#ifndef C99 - BIG_XXX t[2*FFLEN_WWW]; -#else - BIG_XXX t[2*n]; -#endif -// FF_norm(x,n); /* change here */ -// FF_norm(y,n); /* change here */ - FF_WWW_karmul(z,0,x,0,y,0,t,0,n); -} - -/* return low part of product */ -static void FF_WWW_lmul(BIG_XXX z[],BIG_XXX x[],BIG_XXX y[],int n) -{ -#ifndef C99 - BIG_XXX t[2*FFLEN_WWW]; -#else - BIG_XXX t[2*n]; -#endif -// FF_norm(x,n); /* change here */ -// FF_norm(y,n); /* change here */ - FF_WWW_karmul_lower(z,0,x,0,y,0,t,0,n); -} - -/* Set b=b mod c */ -void FF_WWW_mod(BIG_XXX b[],BIG_XXX c[],int n) -{ - int k=0; - - FF_WWW_norm(b,n); - if (FF_WWW_comp(b,c,n)<0) - return; - do - { - FF_WWW_shl(c,n); - k++; - } - while (FF_WWW_comp(b,c,n)>=0); - - while (k>0) - { - FF_WWW_shr(c,n); - if (FF_WWW_comp(b,c,n)>=0) - { - FF_WWW_sub(b,b,c,n); - FF_WWW_norm(b,n); - } - k--; - } -} - -/* z=x^2 */ -void FF_WWW_sqr(BIG_XXX z[],BIG_XXX x[],int n) -{ -#ifndef C99 - BIG_XXX t[2*FFLEN_WWW]; -#else - BIG_XXX t[2*n]; -#endif -// FF_norm(x,n); /* change here */ - FF_WWW_karsqr(z,0,x,0,t,0,n); -} - -/* r=t mod modulus, N is modulus, ND is Montgomery Constant */ -static void FF_WWW_reduce(BIG_XXX r[],BIG_XXX T[],BIG_XXX N[],BIG_XXX ND[],int n) -{ - /* fast karatsuba Montgomery reduction */ -#ifndef C99 - BIG_XXX t[2*FFLEN_WWW]; - BIG_XXX m[FFLEN_WWW]; -#else - BIG_XXX t[2*n]; - BIG_XXX m[n]; -#endif - FF_WWW_sducopy(r,T,n); /* keep top half of T */ - //FF_norm(T,n); /* change here */ - FF_WWW_karmul_lower(m,0,T,0,ND,0,t,0,n); /* m=T.(1/N) mod R */ - - //FF_norm(N,n); /* change here */ - FF_WWW_karmul_upper(T,N,m,t,n); /* T=mN */ - FF_WWW_sducopy(m,T,n); - - FF_WWW_add(r,r,N,n); - FF_WWW_sub(r,r,m,n); - FF_WWW_norm(r,n); -} - - -/* Set r=a mod b */ -/* a is of length - 2*n */ -/* r,b is of length - n */ -void FF_WWW_dmod(BIG_XXX r[],BIG_XXX a[],BIG_XXX b[],int n) -{ - int k; -#ifndef C99 - BIG_XXX m[2*FFLEN_WWW]; - BIG_XXX x[2*FFLEN_WWW]; -#else - BIG_XXX m[2*n]; - BIG_XXX x[2*n]; -#endif - FF_WWW_copy(x,a,2*n); - FF_WWW_norm(x,2*n); - FF_WWW_dsucopy(m,b,n); - k=BIGBITS_XXX*n; - - while (FF_WWW_comp(x,m,2*n)>=0) - { - FF_WWW_sub(x,x,m,2*n); - FF_WWW_norm(x,2*n); - } - - while (k>0) - { - FF_WWW_shr(m,2*n); - - if (FF_WWW_comp(x,m,2*n)>=0) - { - FF_WWW_sub(x,x,m,2*n); - FF_WWW_norm(x,2*n); - } - - k--; - } - FF_WWW_copy(r,x,n); - FF_WWW_mod(r,b,n); -} - -/* Set r=1/a mod p. Binary method - a<p on entry */ - -void FF_WWW_invmodp(BIG_XXX r[],BIG_XXX a[],BIG_XXX p[],int n) -{ -#ifndef C99 - BIG_XXX u[FFLEN_WWW],v[FFLEN_WWW],x1[FFLEN_WWW],x2[FFLEN_WWW],t[FFLEN_WWW],one[FFLEN_WWW]; -#else - BIG_XXX u[n],v[n],x1[n],x2[n],t[n],one[n]; -#endif - FF_WWW_copy(u,a,n); - FF_WWW_copy(v,p,n); - FF_WWW_one(one,n); - FF_WWW_copy(x1,one,n); - FF_WWW_zero(x2,n); - -// reduce n in here as well! - while (FF_WWW_comp(u,one,n)!=0 && FF_WWW_comp(v,one,n)!=0) - { - while (FF_WWW_parity(u)==0) - { - FF_WWW_shr(u,n); - if (FF_WWW_parity(x1)!=0) - { - FF_WWW_add(x1,p,x1,n); - FF_WWW_norm(x1,n); - } - FF_WWW_shr(x1,n); - } - while (FF_WWW_parity(v)==0) - { - FF_WWW_shr(v,n); - if (FF_WWW_parity(x2)!=0) - { - FF_WWW_add(x2,p,x2,n); - FF_WWW_norm(x2,n); - } - FF_WWW_shr(x2,n); - } - if (FF_WWW_comp(u,v,n)>=0) - { - - FF_WWW_sub(u,u,v,n); - FF_WWW_norm(u,n); - if (FF_WWW_comp(x1,x2,n)>=0) FF_WWW_sub(x1,x1,x2,n); - else - { - FF_WWW_sub(t,p,x2,n); - FF_WWW_add(x1,x1,t,n); - } - FF_WWW_norm(x1,n); - } - else - { - FF_WWW_sub(v,v,u,n); - FF_WWW_norm(v,n); - if (FF_WWW_comp(x2,x1,n)>=0) FF_WWW_sub(x2,x2,x1,n); - else - { - FF_WWW_sub(t,p,x1,n); - FF_WWW_add(x2,x2,t,n); - } - FF_WWW_norm(x2,n); - } - } - if (FF_WWW_comp(u,one,n)==0) - FF_WWW_copy(r,x1,n); - else - FF_WWW_copy(r,x2,n); -} - -/* nesidue mod m */ -static void FF_WWW_nres(BIG_XXX a[],BIG_XXX m[],int n) -{ -#ifndef C99 - BIG_XXX d[2*FFLEN_WWW]; -#else - BIG_XXX d[2*n]; -#endif - if (n==1) - { - BIG_XXX_dscopy(d[0],a[0]); - BIG_XXX_dshl(d[0],NLEN_XXX*BASEBITS_XXX); - BIG_XXX_dmod(a[0],d[0],m[0]); - } - else - { - FF_WWW_dsucopy(d,a,n); - FF_WWW_dmod(a,d,m,n); - } -} - -static void FF_WWW_redc(BIG_XXX a[],BIG_XXX m[],BIG_XXX ND[],int n) -{ -#ifndef C99 - BIG_XXX d[2*FFLEN_WWW]; -#else - BIG_XXX d[2*n]; -#endif - if (n==1) - { - BIG_XXX_dzero(d[0]); - BIG_XXX_dscopy(d[0],a[0]); - BIG_XXX_monty(a[0],m[0],((chunk)1<<BASEBITS_XXX)-ND[0][0],d[0]); - } - else - { - FF_WWW_mod(a,m,n); - FF_WWW_dscopy(d,a,n); - FF_WWW_reduce(a,d,m,ND,n); - FF_WWW_mod(a,m,n); - } -} - -/* U=1/a mod 2^m - Arazi & Qi */ -static void FF_WWW_invmod2m(BIG_XXX U[],BIG_XXX a[],int n) -{ - int i; -#ifndef C99 - BIG_XXX t1[FFLEN_WWW],b[FFLEN_WWW],c[FFLEN_WWW]; -#else - BIG_XXX t1[2*n],b[n],c[n]; -#endif - - FF_WWW_zero(U,n); - FF_WWW_zero(b,n); - FF_WWW_zero(c,n); - FF_WWW_zero(t1,2*n); - - BIG_XXX_copy(U[0],a[0]); - BIG_XXX_invmod2m(U[0]); - for (i=1; i<n; i<<=1) - { - FF_WWW_copy(b,a,i); - FF_WWW_mul(t1,U,b,i); - FF_WWW_shrw(t1,i); // top half to bottom half, top half=0 - - FF_WWW_copy(c,a,2*i); - FF_WWW_shrw(c,i); // top half of c - FF_WWW_lmul(b,U,c,i); // should set top half of b=0 - FF_WWW_add(t1,t1,b,i); - FF_WWW_norm(t1,2*i); - FF_WWW_lmul(b,t1,U,i); - FF_WWW_copy(t1,b,i); - FF_WWW_one(b,i); - FF_WWW_shlw(b,i); - FF_WWW_sub(t1,b,t1,2*i); - FF_WWW_norm(t1,2*i); - FF_WWW_shlw(t1,i); - FF_WWW_add(U,U,t1,2*i); - } - - FF_WWW_norm(U,n); -} - -void FF_WWW_random(BIG_XXX x[],csprng *rng,int n) -{ - int i; - for (i=0; i<n; i++) - { - BIG_XXX_random(x[i],rng); - } - /* make sure top bit is 1 */ - while (BIG_XXX_nbits(x[n-1])<MODBYTES_XXX*8) BIG_XXX_random(x[n-1],rng); -} - -/* generate random x mod p */ -void FF_WWW_randomnum(BIG_XXX x[],BIG_XXX p[],csprng *rng,int n) -{ - int i; -#ifndef C99 - BIG_XXX d[2*FFLEN_WWW]; -#else - BIG_XXX d[2*n]; -#endif - for (i=0; i<2*n; i++) - { - BIG_XXX_random(d[i],rng); - } - FF_WWW_dmod(x,d,p,n); -} - -static void FF_WWW_modmul(BIG_XXX z[],BIG_XXX x[],BIG_XXX y[],BIG_XXX p[],BIG_XXX ND[],int n) -{ -#ifndef C99 - BIG_XXX d[2*FFLEN_WWW]; -#else - BIG_XXX d[2*n]; -#endif - chunk ex=P_EXCESS_WWW(x[n-1]); - chunk ey=P_EXCESS_WWW(y[n-1]); -#ifdef dchunk - if ((dchunk)(ex+1)*(ey+1)>(dchunk)P_FEXCESS_WWW) -#else - if ((ex+1)>P_FEXCESS_WWW/(ey+1)) -#endif - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it %d %d\n",ex,ey); -#endif - FF_WWW_mod(x,p,n); - } - - if (n==1) - { - BIG_XXX_mul(d[0],x[0],y[0]); - BIG_XXX_monty(z[0],p[0],((chunk)1<<BASEBITS_XXX)-ND[0][0],d[0]); - } - else - { - FF_WWW_mul(d,x,y,n); - FF_WWW_reduce(z,d,p,ND,n); - } -} - -static void FF_WWW_modsqr(BIG_XXX z[],BIG_XXX x[],BIG_XXX p[],BIG_XXX ND[],int n) -{ -#ifndef C99 - BIG_XXX d[2*FFLEN_WWW]; -#else - BIG_XXX d[2*n]; -#endif - chunk ex=P_EXCESS_WWW(x[n-1]); -#ifdef dchunk - if ((dchunk)(ex+1)*(ex+1)>(dchunk)P_FEXCESS_WWW) -#else - if ((ex+1)>P_FEXCESS_WWW/(ex+1)) -#endif - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it %d\n",ex); -#endif - FF_WWW_mod(x,p,n); - } - if (n==1) - { - BIG_XXX_sqr(d[0],x[0]); - BIG_XXX_monty(z[0],p[0],((chunk)1<<BASEBITS_XXX)-ND[0][0],d[0]); - } - else - { - FF_WWW_sqr(d,x,n); - FF_WWW_reduce(z,d,p,ND,n); - } -} - -/* r=x^e mod p using side-channel resistant Montgomery Ladder, for large e */ -void FF_WWW_skpow(BIG_XXX r[],BIG_XXX x[],BIG_XXX e[],BIG_XXX p[],int n) -{ - int i,b; -#ifndef C99 - BIG_XXX R0[FFLEN_WWW],R1[FFLEN_WWW],ND[FFLEN_WWW]; -#else - BIG_XXX R0[n],R1[n],ND[n]; -#endif - FF_WWW_invmod2m(ND,p,n); - - FF_WWW_one(R0,n); - FF_WWW_copy(R1,x,n); - FF_WWW_nres(R0,p,n); - FF_WWW_nres(R1,p,n); - - for (i=8*MODBYTES_XXX*n-1; i>=0; i--) - { - b=BIG_XXX_bit(e[i/BIGBITS_XXX],i%BIGBITS_XXX); - FF_WWW_modmul(r,R0,R1,p,ND,n); - - FF_WWW_cswap(R0,R1,b,n); - FF_WWW_modsqr(R0,R0,p,ND,n); - - FF_WWW_copy(R1,r,n); - FF_WWW_cswap(R0,R1,b,n); - } - FF_WWW_copy(r,R0,n); - FF_WWW_redc(r,p,ND,n); -} - -/* r=x^e mod p using side-channel resistant Montgomery Ladder, for short e */ -void FF_WWW_skspow(BIG_XXX r[],BIG_XXX x[],BIG_XXX e,BIG_XXX p[],int n) -{ - int i,b; -#ifndef C99 - BIG_XXX R0[FFLEN_WWW],R1[FFLEN_WWW],ND[FFLEN_WWW]; -#else - BIG_XXX R0[n],R1[n],ND[n]; -#endif - FF_WWW_invmod2m(ND,p,n); - FF_WWW_one(R0,n); - FF_WWW_copy(R1,x,n); - FF_WWW_nres(R0,p,n); - FF_WWW_nres(R1,p,n); - for (i=8*MODBYTES_XXX-1; i>=0; i--) - { - b=BIG_XXX_bit(e,i); - FF_WWW_modmul(r,R0,R1,p,ND,n); - FF_WWW_cswap(R0,R1,b,n); - FF_WWW_modsqr(R0,R0,p,ND,n); - FF_WWW_copy(R1,r,n); - FF_WWW_cswap(R0,R1,b,n); - } - FF_WWW_copy(r,R0,n); - FF_WWW_redc(r,p,ND,n); -} - -/* raise to an integer power - right-to-left method */ -void FF_WWW_power(BIG_XXX r[],BIG_XXX x[],int e,BIG_XXX p[],int n) -{ - int f=1; -#ifndef C99 - BIG_XXX w[FFLEN_WWW],ND[FFLEN_WWW]; -#else - BIG_XXX w[n],ND[n]; -#endif - FF_WWW_invmod2m(ND,p,n); - - FF_WWW_copy(w,x,n); - FF_WWW_nres(w,p,n); - - if (e==2) - { - FF_WWW_modsqr(r,w,p,ND,n); - } - else for (;;) - { - if (e%2==1) - { - if (f) FF_WWW_copy(r,w,n); - else FF_WWW_modmul(r,r,w,p,ND,n); - f=0; - } - e>>=1; - if (e==0) break; - FF_WWW_modsqr(w,w,p,ND,n); - } - - FF_WWW_redc(r,p,ND,n); -} - -/* r=x^e mod p, faster but not side channel resistant */ -void FF_WWW_pow(BIG_XXX r[],BIG_XXX x[],BIG_XXX e[],BIG_XXX p[],int n) -{ - int i,b; -#ifndef C99 - BIG_XXX w[FFLEN_WWW],ND[FFLEN_WWW]; -#else - BIG_XXX w[n],ND[n]; -#endif - FF_WWW_invmod2m(ND,p,n); - - FF_WWW_copy(w,x,n); - FF_WWW_one(r,n); - FF_WWW_nres(r,p,n); - FF_WWW_nres(w,p,n); - - for (i=8*MODBYTES_XXX*n-1; i>=0; i--) - { - FF_WWW_modsqr(r,r,p,ND,n); - b=BIG_XXX_bit(e[i/BIGBITS_XXX],i%BIGBITS_XXX); - if (b==1) FF_WWW_modmul(r,r,w,p,ND,n); - } - FF_WWW_redc(r,p,ND,n); -} - -/* double exponentiation r=x^e.y^f mod p */ -void FF_WWW_pow2(BIG_XXX r[],BIG_XXX x[],BIG_XXX e,BIG_XXX y[],BIG_XXX f,BIG_XXX p[],int n) -{ - int i,eb,fb; -#ifndef C99 - BIG_XXX xn[FFLEN_WWW],yn[FFLEN_WWW],xy[FFLEN_WWW],ND[FFLEN_WWW]; -#else - BIG_XXX xn[n],yn[n],xy[n],ND[n]; -#endif - - FF_WWW_invmod2m(ND,p,n); - - FF_WWW_copy(xn,x,n); - FF_WWW_copy(yn,y,n); - FF_WWW_nres(xn,p,n); - FF_WWW_nres(yn,p,n); - FF_WWW_modmul(xy,xn,yn,p,ND,n); - FF_WWW_one(r,n); - FF_WWW_nres(r,p,n); - - for (i=8*MODBYTES_XXX-1; i>=0; i--) - { - eb=BIG_XXX_bit(e,i); - fb=BIG_XXX_bit(f,i); - FF_WWW_modsqr(r,r,p,ND,n); - if (eb==1) - { - if (fb==1) FF_WWW_modmul(r,r,xy,p,ND,n); - else FF_WWW_modmul(r,r,xn,p,ND,n); - } - else - { - if (fb==1) FF_WWW_modmul(r,r,yn,p,ND,n); - } - } - FF_WWW_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_WWW_cfactor(BIG_XXX w[],sign32 s,int n) -{ - int r; - sign32 g; -#ifndef C99 - BIG_XXX x[FFLEN_WWW],y[FFLEN_WWW]; -#else - BIG_XXX x[n],y[n]; -#endif - FF_WWW_init(y,s,n); - FF_WWW_copy(x,w,n); - FF_WWW_norm(x,n); - -// if (FF_parity(x)==0) return 1; - do - { - FF_WWW_sub(x,x,y,n); - FF_WWW_norm(x,n); - while (!FF_WWW_iszilch(x,n) && FF_WWW_parity(x)==0) FF_WWW_shr(x,n); - } - while (FF_WWW_comp(x,y,n)>0); -#if CHUNK<32 - g=x[0][0]+((sign32)(x[0][1])<<BASEBITS_XXX); -#else - g=(sign32)x[0][0]; -#endif - r=igcd(s,g); - if (r>1) return 1; - return 0; -} - -/* Miller-Rabin test for primality. Slow. */ -int FF_WWW_prime(BIG_XXX p[],csprng *rng,int n) -{ - int i,j,loop,s=0; -#ifndef C99 - BIG_XXX d[FFLEN_WWW],x[FFLEN_WWW],unity[FFLEN_WWW],nm1[FFLEN_WWW]; -#else - BIG_XXX d[n],x[n],unity[n],nm1[n]; -#endif - sign32 sf=4849845;/* 3*5*.. *19 */ - - FF_WWW_norm(p,n); - - if (FF_WWW_cfactor(p,sf,n)) return 0; - - FF_WWW_one(unity,n); - FF_WWW_sub(nm1,p,unity,n); - FF_WWW_norm(nm1,n); - FF_WWW_copy(d,nm1,n); - while (FF_WWW_parity(d)==0) - { - FF_WWW_shr(d,n); - s++; - } - if (s==0) return 0; - - for (i=0; i<10; i++) - { - FF_WWW_randomnum(x,p,rng,n); - FF_WWW_pow(x,x,d,p,n); - if (FF_WWW_comp(x,unity,n)==0 || FF_WWW_comp(x,nm1,n)==0) continue; - loop=0; - for (j=1; j<s; j++) - { - FF_WWW_power(x,x,2,p,n); - if (FF_WWW_comp(x,unity,n)==0) return 0; - if (FF_WWW_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/1add7560/version3/c/ff.h ---------------------------------------------------------------------- diff --git a/version3/c/ff.h b/version3/c/ff.h deleted file mode 100644 index a50e653..0000000 --- a/version3/c/ff.h +++ /dev/null @@ -1,296 +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 ff.h - * @author Mike Scott - * @brief FF Header File - * - */ - -#ifndef FF_WWW_H -#define FF_WWW_H - -#include "big_XXX.h" -#include "config_ff_WWW.h" - -#define HFLEN_WWW (FFLEN_WWW/2) /**< Useful for half-size RSA private key operations */ -#define P_MBITS_WWW (MODBYTES_XXX*8) /**< Number of bits in modulus */ -#define P_TBITS_WWW (P_MBITS_WWW%BASEBITS_XXX) /**< TODO */ -#define P_EXCESS_WWW(a) (((a[NLEN_XXX-1])>>(P_TBITS_WWW))+1) /**< TODO */ -#define P_FEXCESS_WWW ((chunk)1<<(BASEBITS_XXX*NLEN_XXX-P_MBITS_WWW-1)) /**< TODO */ - - -/* Finite Field Prototypes */ -/** @brief Copy one FF element of given length to another - * - @param x FF instance to be copied to, on exit = y - @param y FF instance to be copied from - @param n size of FF in BIGs - - */ -extern void FF_WWW_copy(BIG_XXX *x,BIG_XXX *y,int n); -/** @brief Initialize an FF element of given length from a 32-bit integer m - * - @param x FF instance to be copied to, on exit = m - @param m integer - @param n size of FF in BIGs - */ -extern void FF_WWW_init(BIG_XXX *x,sign32 m,int n); -/** @brief Set FF element of given size to zero - * - @param x FF instance to be set to zero - @param n size of FF in BIGs - */ -extern void FF_WWW_zero(BIG_XXX *x,int n); -/** @brief Tests for FF element equal to zero - * - @param x FF number to be tested - @param n size of FF in BIGs - @return 1 if zero, else returns 0 - */ -extern int FF_WWW_iszilch(BIG_XXX *x,int n); -/** @brief return parity of an FF, that is the least significant bit - * - @param x FF number - @return 0 or 1 - */ -extern int FF_WWW_parity(BIG_XXX *x); -/** @brief return least significant m bits of an FF - * - @param x FF number - @param m number of bits to return. Assumed to be less than BASEBITS. - @return least significant n bits as an integer - */ -extern int FF_WWW_lastbits(BIG_XXX *x,int m); -/** @brief Set FF element of given size to unity - * - @param x FF instance to be set to unity - @param n size of FF in BIGs - */ -extern void FF_WWW_one(BIG_XXX *x,int n); -/** @brief Compares two FF numbers. Inputs must be normalised externally - * - @param x first FF number to be compared - @param y second FF number to be compared - @param n size of FF in BIGs - @return -1 is x<y, 0 if x=y, 1 if x>y - */ -extern int FF_WWW_comp(BIG_XXX *x,BIG_XXX *y,int n); -/** @brief addition of two FFs - * - @param x FF instance, on exit = y+z - @param y FF instance - @param z FF instance - @param n size of FF in BIGs - */ -extern void FF_WWW_add(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n); -/** @brief subtraction of two FFs - * - @param x FF instance, on exit = y-z - @param y FF instance - @param z FF instance - @param n size of FF in BIGs - */ -extern void FF_WWW_sub(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n); -/** @brief increment an FF by an integer,and normalise - * - @param x FF instance, on exit = x+m - @param m an integer to be added to x - @param n size of FF in BIGs - */ -extern void FF_WWW_inc(BIG_XXX *x,int m,int n); -/** @brief Decrement an FF by an integer,and normalise - * - @param x FF instance, on exit = x-m - @param m an integer to be subtracted from x - @param n size of FF in BIGs - */ -extern void FF_WWW_dec(BIG_XXX *x,int m,int n); -/** @brief Normalises the components of an FF - * - @param x FF instance to be normalised - @param n size of FF in BIGs - */ -extern void FF_WWW_norm(BIG_XXX *x,int n); -/** @brief Shift left an FF by 1 bit - * - @param x FF instance to be shifted left - @param n size of FF in BIGs - */ -extern void FF_WWW_shl(BIG_XXX *x,int n); -/** @brief Shift right an FF by 1 bit - * - @param x FF instance to be shifted right - @param n size of FF in BIGs - */ -extern void FF_WWW_shr(BIG_XXX *x,int n); -/** @brief Formats and outputs an FF to the console - * - @param x FF instance to be printed - @param n size of FF in BIGs - */ -extern void FF_WWW_output(BIG_XXX *x,int n); -/** @brief Formats and outputs an FF to the console, in raw form - * - @param x FF instance to be printed - @param n size of FF in BIGs - */ -extern void FF_WWW_rawoutput(BIG_XXX *x,int n); -/** @brief Formats and outputs an FF instance to an octet string - * - Converts an FF to big-endian base 256 form. - @param S output octet string - @param x FF instance to be converted to an octet string - @param n size of FF in BIGs - */ -extern void FF_WWW_toOctet(octet *S,BIG_XXX *x,int n); -/** @brief Populates an FF instance from an octet string - * - Creates FF from big-endian base 256 form. - @param x FF instance to be created from an octet string - @param S input octet string - @param n size of FF in BIGs - */ -extern void FF_WWW_fromOctet(BIG_XXX *x,octet *S,int n); -/** @brief Multiplication of two FFs - * - Uses Karatsuba method internally - @param x FF instance, on exit = y*z - @param y FF instance - @param z FF instance - @param n size of FF in BIGs - */ -extern void FF_WWW_mul(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n); -/** @brief Reduce FF mod a modulus - * - This is slow - @param x FF instance to be reduced mod m - on exit = x mod m - @param m FF modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_mod(BIG_XXX *x,BIG_XXX *m,int n); -/** @brief Square an FF - * - Uses Karatsuba method internally - @param x FF instance, on exit = y^2 - @param y FF instance to be squared - @param n size of FF in BIGs - */ -extern void FF_WWW_sqr(BIG_XXX *x,BIG_XXX *y,int n); -/** @brief Reduces a double-length FF with respect to a given modulus - * - This is slow - @param x FF instance, on exit = y mod z - @param y FF instance, of double length 2*n - @param z FF modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_dmod(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n); -/** @brief Invert an FF mod a prime modulus - * - @param x FF instance, on exit = 1/y mod z - @param y FF instance - @param z FF prime modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_invmodp(BIG_XXX *x,BIG_XXX *y,BIG_XXX *z,int n); -/** @brief Create an FF from a random number generator - * - @param x FF instance, on exit x is a random number of length n BIGs with most significant bit a 1 - @param R an instance of a Cryptographically Secure Random Number Generator - @param n size of FF in BIGs - */ -extern void FF_WWW_random(BIG_XXX *x,csprng *R,int n); -/** @brief Create a random FF less than a given modulus from a random number generator - * - @param x FF instance, on exit x is a random number < y - @param y FF instance, the modulus - @param R an instance of a Cryptographically Secure Random Number Generator - @param n size of FF in BIGs - */ -extern void FF_WWW_randomnum(BIG_XXX *x,BIG_XXX *y,csprng *R,int n); -/** @brief Calculate r=x^e mod m, side channel resistant - * - @param r FF instance, on exit = x^e mod p - @param x FF instance - @param e FF exponent - @param m FF modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_skpow(BIG_XXX *r,BIG_XXX *x,BIG_XXX * e,BIG_XXX *m,int n); -/** @brief Calculate r=x^e mod m, side channel resistant - * - For short BIG exponent - @param r FF instance, on exit = x^e mod p - @param x FF instance - @param e BIG exponent - @param m FF modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_skspow(BIG_XXX *r,BIG_XXX *x,BIG_XXX e,BIG_XXX *m,int n); -/** @brief Calculate r=x^e mod m - * - For very short integer exponent - @param r FF instance, on exit = x^e mod p - @param x FF instance - @param e integer exponent - @param m FF modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_power(BIG_XXX *r,BIG_XXX *x,int e,BIG_XXX *m,int n); -/** @brief Calculate r=x^e mod m - * - @param r FF instance, on exit = x^e mod p - @param x FF instance - @param e FF exponent - @param m FF modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_pow(BIG_XXX *r,BIG_XXX *x,BIG_XXX *e,BIG_XXX *m,int n); -/** @brief Test if an FF has factor in common with integer s - * - @param x FF instance to be tested - @param s the supplied integer - @param n size of FF in BIGs - @return 1 if gcd(x,s)!=1, else return 0 - */ -extern int FF_WWW_cfactor(BIG_XXX *x,sign32 s,int n); -/** @brief Test if an FF is prime - * - Uses Miller-Rabin Method - @param x FF instance to be tested - @param R an instance of a Cryptographically Secure Random Number Generator - @param n size of FF in BIGs - @return 1 if x is (almost certainly) prime, else return 0 - */ -extern int FF_WWW_prime(BIG_XXX *x,csprng *R,int n); -/** @brief Calculate r=x^e.y^f mod m - * - @param r FF instance, on exit = x^e.y^f mod p - @param x FF instance - @param e BIG exponent - @param y FF instance - @param f BIG exponent - @param m FF modulus - @param n size of FF in BIGs - */ -extern void FF_WWW_pow2(BIG_XXX *r,BIG_XXX *x,BIG_XXX e,BIG_XXX *y,BIG_XXX f,BIG_XXX *m,int n); - -#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version3/c/fp.c ---------------------------------------------------------------------- diff --git a/version3/c/fp.c b/version3/c/fp.c deleted file mode 100644 index 0b60382..0000000 --- a/version3/c/fp.c +++ /dev/null @@ -1,878 +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 "fp_YYY.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_YYY == PSEUDO_MERSENNE -/* r=d mod m */ - -/* Converts from BIG integer to residue form mod Modulus */ -void FP_YYY_nres(FP_YYY *y,BIG_XXX x) -{ - BIG_XXX_copy(y->g,x); - y->XES=1; -} - -/* Converts from residue form back to BIG integer form */ -void FP_YYY_redc(BIG_XXX x,FP_YYY *y) -{ - BIG_XXX_copy(x,y->g); -} - -/* reduce a DBIG to a BIG exploiting the special form of the modulus */ -void FP_YYY_mod(BIG_XXX r,DBIG_XXX d) -{ - BIG_XXX t,b; - chunk v,tw; - BIG_XXX_split(t,b,d,MODBITS_YYY); - - /* 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_YYY < NEXCESS_XXX) - { - BIG_XXX_imul(t,t,MConst_YYY); - BIG_XXX_norm(t); - BIG_XXX_add(r,t,b); - BIG_XXX_norm(r); - tw=r[NLEN_XXX-1]; - r[NLEN_XXX-1]&=TMASK_YYY; - r[0]+=MConst_YYY*((tw>>TBITS_YYY)); - } - else - { - v=BIG_XXX_pmul(t,t,MConst_YYY); - BIG_XXX_add(r,t,b); - BIG_XXX_norm(r); - tw=r[NLEN_XXX-1]; - r[NLEN_XXX-1]&=TMASK_YYY; -#if CHUNK == 16 - r[1]+=muladd_XXX(MConst_YYY,((tw>>TBITS_YYY)+(v<<(BASEBITS_XXX-TBITS_YYY))),0,&r[0]); -#else - r[0]+=MConst_YYY*((tw>>TBITS_YYY)+(v<<(BASEBITS_XXX-TBITS_YYY))); -#endif - } - BIG_XXX_norm(r); -} -#endif - -/* This only applies to Curve C448, so specialised (for now) */ -#if MODTYPE_YYY == GENERALISED_MERSENNE - -void FP_YYY_nres(FP_YYY *y,BIG_XXX x) -{ - BIG_XXX_copy(y->g,x); - y->XES=1; -} - -/* Converts from residue form back to BIG integer form */ -void FP_YYY_redc(BIG_XXX x,FP_YYY *y) -{ - BIG_XXX_copy(x,y->g); -} - -/* reduce a DBIG to a BIG exploiting the special form of the modulus */ -void FP_YYY_mod(BIG_XXX r,DBIG_XXX d) -{ - BIG_XXX t,b; - chunk carry; - BIG_XXX_split(t,b,d,MBITS_YYY); - - BIG_XXX_add(r,t,b); - - BIG_XXX_dscopy(d,t); - BIG_XXX_dshl(d,MBITS_YYY/2); - - BIG_XXX_split(t,b,d,MBITS_YYY); - - BIG_XXX_add(r,r,t); - BIG_XXX_add(r,r,b); - BIG_XXX_norm(r); - BIG_XXX_shl(t,MBITS_YYY/2); - - BIG_XXX_add(r,r,t); - - carry=r[NLEN_XXX-1]>>TBITS_YYY; - - r[NLEN_XXX-1]&=TMASK_YYY; - r[0]+=carry; - - r[224/BASEBITS_XXX]+=carry<<(224%BASEBITS_XXX); /* need to check that this falls mid-word */ - BIG_XXX_norm(r); -} - -#endif - -#if MODTYPE_YYY == MONTGOMERY_FRIENDLY - -/* convert to Montgomery n-residue form */ -void FP_YYY_nres(FP_YYY *y,BIG_XXX x) -{ - DBIG_XXX d; - BIG_XXX r; - BIG_XXX_rcopy(r,R2modp_YYY); - BIG_XXX_mul(d,x,r); - FP_YYY_mod(y->g,d); - y->XES=2; -} - -/* convert back to regular form */ -void FP_YYY_redc(BIG_XXX x,FP_YYY *y) -{ - DBIG_XXX d; - BIG_XXX_dzero(d); - BIG_XXX_dscopy(d,y->g); - FP_YYY_mod(x,d); -} - -/* fast modular reduction from DBIG to BIG exploiting special form of the modulus */ -void FP_YYY_mod(BIG_XXX a,DBIG_XXX d) -{ - int i; - - for (i=0; i<NLEN_XXX; i++) - d[NLEN_XXX+i]+=muladd_XXX(d[i],MConst_YYY-1,d[i],&d[NLEN_XXX+i-1]); - - BIG_XXX_sducopy(a,d); - BIG_XXX_norm(a); -} - -#endif - -#if MODTYPE_YYY == NOT_SPECIAL - -/* convert to Montgomery n-residue form */ -void FP_YYY_nres(FP_YYY *y,BIG_XXX x) -{ - DBIG_XXX d; - BIG_XXX r; - BIG_XXX_rcopy(r,R2modp_YYY); - BIG_XXX_mul(d,x,r); - FP_YYY_mod(y->g,d); - y->XES=2; -} - -/* convert back to regular form */ -void FP_YYY_redc(BIG_XXX x,FP_YYY *y) -{ - DBIG_XXX d; - BIG_XXX_dzero(d); - BIG_XXX_dscopy(d,y->g); - FP_YYY_mod(x,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_YYY_mod(BIG_XXX a,DBIG_XXX d) -{ - BIG_XXX mdls; - BIG_XXX_rcopy(mdls,Modulus_YYY); - BIG_XXX_monty(a,mdls,MConst_YYY,d); -} - -#endif - -/* test x==0 ? */ -/* SU= 48 */ -int FP_YYY_iszilch(FP_YYY *x) -{ - BIG_XXX m,t; - BIG_XXX_rcopy(m,Modulus_YYY); - BIG_XXX_copy(t,x->g); - BIG_XXX_mod(t,m); - return BIG_XXX_iszilch(t); -} - -void FP_YYY_copy(FP_YYY *y,FP_YYY *x) -{ - BIG_XXX_copy(y->g,x->g); - y->XES=x->XES; -} - -void FP_YYY_rcopy(FP_YYY *y, const BIG_XXX c) -{ - BIG_XXX b; - BIG_XXX_rcopy(b,c); - FP_YYY_nres(y,b); -} - -/* Swap a and b if d=1 */ -void FP_YYY_cswap(FP_YYY *a,FP_YYY *b,int d) -{ - sign32 t,c=d; - BIG_XXX_cswap(a->g,b->g,d); - - c=~(c-1); - t=c&((a->XES)^(b->XES)); - a->XES^=t; - b->XES^=t; - -} - -/* Move b to a if d=1 */ -void FP_YYY_cmove(FP_YYY *a,FP_YYY *b,int d) -{ - sign32 c=-d; - - BIG_XXX_cmove(a->g,b->g,d); - a->XES^=(a->XES^b->XES)&c; -} - -void FP_YYY_zero(FP_YYY *x) -{ - BIG_XXX_zero(x->g); - x->XES=1; -} - -int FP_YYY_equals(FP_YYY *x,FP_YYY *y) -{ - FP_YYY xg,yg; - FP_YYY_copy(&xg,x); - FP_YYY_copy(&yg,y); - FP_YYY_reduce(&xg); - FP_YYY_reduce(&yg); - if (BIG_XXX_comp(xg.g,yg.g)==0) return 1; - return 0; -} - -/* output FP */ -/* SU= 48 */ -void FP_YYY_output(FP_YYY *r) -{ - BIG_XXX c; - FP_YYY_redc(c,r); - BIG_XXX_output(c); -} - -void FP_YYY_rawoutput(FP_YYY *r) -{ - BIG_XXX_rawoutput(r->g); -} - -#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 - -#ifdef FUSED_MODMUL - -/* Insert fastest code here */ - -#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_YYY_mul(FP_YYY *r,FP_YYY *a,FP_YYY *b) -{ - DBIG_XXX d; -// chunk ea,eb; -// BIG_XXX_norm(a); -// BIG_XXX_norm(b); -// ea=EXCESS_YYY(a->g); -// eb=EXCESS_YYY(b->g); - - - if ((sign64)a->XES*b->XES>(sign64)FEXCESS_YYY) - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it\n"); -#endif - FP_YYY_reduce(a); /* it is sufficient to fully reduce just one of them < p */ - } - -#ifdef FUSED_MODMUL - FP_YYY_modmul(r->g,a->g,b->g); -#else - BIG_XXX_mul(d,a->g,b->g); - FP_YYY_mod(r->g,d); -#endif - r->XES=2; -} - - -/* multiplication by an integer, r=a*c */ -/* SU= 136 */ -void FP_YYY_imul(FP_YYY *r,FP_YYY *a,int c) -{ - int s=0; - - if (c<0) - { - c=-c; - s=1; - } - -#if MODTYPE_YYY==PSEUDO_MERSENNE || MODTYPE_YYY==GENERALISED_MERSENNE - DBIG_XXX d; - BIG_XXX_pxmul(d,a->g,c); - FP_YYY_mod(r->g,d); - r->XES=2; - -#else - //Montgomery - BIG_XXX k; - FP_YYY f; - if (a->XES*c<=FEXCESS_YYY) - { - BIG_XXX_pmul(r->g,a->g,c); - r->XES=a->XES*c; // careful here - XES jumps! - } - else - { - // don't want to do this - only a problem for Montgomery modulus and larger constants - BIG_XXX_zero(k); - BIG_XXX_inc(k,c); - BIG_XXX_norm(k); - FP_YYY_nres(&f,k); - FP_YYY_mul(r,a,&f); - } -#endif - /* - if (c<=NEXCESS_XXX && a->XES*c <= FEXCESS_YYY) - { - BIG_XXX_imul(r->g,a->g,c); - r->XES=a->XES*c; - FP_YYY_norm(r); - } - else - { - BIG_XXX_pxmul(d,a->g,c); - - BIG_XXX_rcopy(m,Modulus_YYY); - BIG_XXX_dmod(r->g,d,m); - //FP_YYY_mod(r->g,d); /// BIG problem here! Too slow for PM, How to do fast for Monty? - r->XES=2; - } - */ - if (s) - { - FP_YYY_neg(r,r); - FP_YYY_norm(r); - } -} - -/* Set r=a^2 mod m */ -/* SU= 88 */ -void FP_YYY_sqr(FP_YYY *r,FP_YYY *a) -{ - DBIG_XXX d; -// chunk ea; -// BIG_XXX_norm(a); -// ea=EXCESS_YYY(a->g); - - - if ((sign64)a->XES*a->XES>(sign64)FEXCESS_YYY) - { -#ifdef DEBUG_REDUCE - printf("Product too large - reducing it\n"); -#endif - FP_YYY_reduce(a); - } - - BIG_XXX_sqr(d,a->g); - FP_YYY_mod(r->g,d); - r->XES=2; -} - -/* SU= 16 */ -/* Set r=a+b */ -void FP_YYY_add(FP_YYY *r,FP_YYY *a,FP_YYY *b) -{ - BIG_XXX_add(r->g,a->g,b->g); - r->XES=a->XES+b->XES; - if (r->XES>FEXCESS_YYY) - { -#ifdef DEBUG_REDUCE - printf("Sum too large - reducing it \n"); -#endif - FP_YYY_reduce(r); - } -} - -/* Set r=a-b mod m */ -/* SU= 56 */ -void FP_YYY_sub(FP_YYY *r,FP_YYY *a,FP_YYY *b) -{ - FP_YYY n; -// BIG_XXX_norm(b); - FP_YYY_neg(&n,b); -// BIG_XXX_norm(n); - FP_YYY_add(r,a,&n); -} - -// https://graphics.stanford.edu/~seander/bithacks.html -// constant time log to base 2 (or number of bits in) - -static int logb2(unsign32 v) -{ - int r; - v |= v >> 1; - v |= v >> 2; - v |= v >> 4; - v |= v >> 8; - v |= v >> 16; - - v = v - ((v >> 1) & 0x55555555); - v = (v & 0x33333333) + ((v >> 2) & 0x33333333); - r = (((v + (v >> 4)) & 0xF0F0F0F) * 0x1010101) >> 24; - return r; -} - -// find appoximation to quotient of a/m -// Out by at most 2. -// Note that MAXXES is bounded to be 2-bits less than half a word -static int quo(BIG_XXX n,BIG_XXX m) -{ - int sh; - chunk num,den; - int hb=CHUNK/2; - if (TBITS_YYY<hb) - { - sh=hb-TBITS_YYY; - num=(n[NLEN_XXX-1]<<sh)|(n[NLEN_XXX-2]>>(BASEBITS_XXX-sh)); - den=(m[NLEN_XXX-1]<<sh)|(m[NLEN_XXX-2]>>(BASEBITS_XXX-sh)); - } - else - { - num=n[NLEN_XXX-1]; - den=m[NLEN_XXX-1]; - } - return (int)(num/(den+1)); -} - -/* SU= 48 */ -/* Fully reduce a mod Modulus */ -void FP_YYY_reduce(FP_YYY *a) -{ - BIG_XXX m,r; - int sr,sb,q; - chunk carry; - - BIG_XXX_rcopy(m,Modulus_YYY); - - BIG_XXX_norm(a->g); - - if (a->XES>16) - { - q=quo(a->g,m); - carry=BIG_XXX_pmul(r,m,q); - r[NLEN_XXX-1]+=(carry<<BASEBITS_XXX); // correction - put any carry out back in again - BIG_XXX_sub(a->g,a->g,r); - BIG_XXX_norm(a->g); - sb=2; - } - else sb=logb2(a->XES-1); // sb does not depend on the actual data - - BIG_XXX_fshl(m,sb); - - while (sb>0) - { -// constant time... - sr=BIG_XXX_ssn(r,a->g,m); // optimized combined shift, subtract and norm - BIG_XXX_cmove(a->g,r,1-sr); - sb--; - } - - //BIG_XXX_mod(a->g,m); - a->XES=1; -} - -void FP_YYY_norm(FP_YYY *x) -{ - BIG_XXX_norm(x->g); -} - -/* Set r=-a mod Modulus */ -/* SU= 64 */ -void FP_YYY_neg(FP_YYY *r,FP_YYY *a) -{ - int sb; - BIG_XXX m; - - BIG_XXX_rcopy(m,Modulus_YYY); - - sb=logb2(a->XES-1); - BIG_XXX_fshl(m,sb); - BIG_XXX_sub(r->g,m,a->g); - r->XES=((sign32)1<<sb)+1; - - if (r->XES>FEXCESS_YYY) - { -#ifdef DEBUG_REDUCE - printf("Negation too large - reducing it \n"); -#endif - FP_YYY_reduce(r); - } - -} - -/* Set r=a/2. */ -/* SU= 56 */ -void FP_YYY_div2(FP_YYY *r,FP_YYY *a) -{ - BIG_XXX m; - BIG_XXX_rcopy(m,Modulus_YYY); - FP_YYY_copy(r,a); -// BIG_XXX_norm(a); - if (BIG_XXX_parity(a->g)==0) - { - - BIG_XXX_fshr(r->g,1); - } - else - { - BIG_XXX_add(r->g,r->g,m); - BIG_XXX_norm(r->g); - BIG_XXX_fshr(r->g,1); - } -} - -#if MODTYPE_YYY == PSEUDO_MERSENNE - -// See eprint paper "On inversion modulo pseudo-Mersenne primes" -// If p=3 mod 4 r= x^{(p-3)/4}, if p=5 mod 8 r=x^{(p-5)/8} - -static void FP_YYY_fpow(FP_YYY *r,FP_YYY *x) -{ - int i,j,k,bw,w,c,nw,lo,m,n; - FP_YYY xp[11],t,key; - const int ac[]={1,2,3,6,12,15,30,60,120,240,255}; -// phase 1 - FP_YYY_copy(&xp[0],x); // 1 - FP_YYY_sqr(&xp[1],x); // 2 - FP_YYY_mul(&xp[2],&xp[1],x); //3 - FP_YYY_sqr(&xp[3],&xp[2]); // 6 - FP_YYY_sqr(&xp[4],&xp[3]); // 12 - FP_YYY_mul(&xp[5],&xp[4],&xp[2]); // 15 - FP_YYY_sqr(&xp[6],&xp[5]); // 30 - FP_YYY_sqr(&xp[7],&xp[6]); // 60 - FP_YYY_sqr(&xp[8],&xp[7]); // 120 - FP_YYY_sqr(&xp[9],&xp[8]); // 240 - FP_YYY_mul(&xp[10],&xp[9],&xp[5]); // 255 - - if (MOD8_YYY==5) - { - n=MODBITS_YYY-3; - c=(MConst_YYY+5)/8; - } else { - n=MODBITS_YYY-2; - c=(MConst_YYY+3)/4; - } - - bw=0; w=1; while (w<c) {w*=2; bw+=1;} - k=w-c; - - if (k!=0) - { - i=10; while (ac[i]>k) i--; - FP_YYY_copy(&key,&xp[i]); - k-=ac[i]; - } - while (k!=0) - { - i--; - if (ac[i]>k) continue; - FP_YYY_mul(&key,&key,&xp[i]); - k-=ac[i]; - } - -// phase 2 - FP_YYY_copy(&xp[1],&xp[2]); - FP_YYY_copy(&xp[2],&xp[5]); - FP_YYY_copy(&xp[3],&xp[10]); - - j=3; m=8; - nw=n-bw; - while (2*m<nw) - { - FP_YYY_copy(&t,&xp[j++]); - for (i=0;i<m;i++) - FP_YYY_sqr(&t,&t); - FP_YYY_mul(&xp[j],&xp[j-1],&t); - m*=2; - } - - lo=nw-m; - FP_YYY_copy(r,&xp[j]); - - while (lo!=0) - { - m/=2; j--; - if (lo<m) continue; - lo-=m; - FP_YYY_copy(&t,r); - for (i=0;i<m;i++) - FP_YYY_sqr(&t,&t); - FP_YYY_mul(r,&t,&xp[j]); - } -// phase 3 - - for (i=0;i<bw;i++ ) - FP_YYY_sqr(r,r); - - if (w-c!=0) - FP_YYY_mul(r,r,&key); -} - -void FP_YYY_inv(FP_YYY *r,FP_YYY *x) -{ - FP_YYY y,t; - FP_YYY_fpow(&y,x); - if (MOD8_YYY==5) - { // r=x^3.y^8 - FP_YYY_sqr(&t,x); - FP_YYY_mul(&t,&t,x); - FP_YYY_sqr(&y,&y); - FP_YYY_sqr(&y,&y); - FP_YYY_sqr(&y,&y); - FP_YYY_mul(r,&t,&y); - } else { - FP_YYY_sqr(&y,&y); - FP_YYY_sqr(&y,&y); - FP_YYY_mul(r,&y,x); - } -} - -#else - -void FP_YYY_pow(FP_YYY *r,FP_YYY *a,BIG_XXX b) -{ - sign8 w[1+(NLEN_XXX*BASEBITS_XXX+3)/4]; - FP_YYY tb[16]; - BIG_XXX t; - int i,nb; - - FP_YYY_norm(a); - BIG_XXX_norm(b); - BIG_XXX_copy(t,b); - nb=1+(BIG_XXX_nbits(t)+3)/4; - /* convert exponent to 4-bit window */ - for (i=0; i<nb; i++) - { - w[i]=BIG_XXX_lastbits(t,4); - BIG_XXX_dec(t,w[i]); - BIG_XXX_norm(t); - BIG_XXX_fshr(t,4); - } - - FP_YYY_one(&tb[0]); - FP_YYY_copy(&tb[1],a); - for (i=2;i<16;i++) - FP_YYY_mul(&tb[i],&tb[i-1],a); - - FP_YYY_copy(r,&tb[w[nb-1]]); - for (i=nb-2; i>=0; i--) - { - FP_YYY_sqr(r,r); - FP_YYY_sqr(r,r); - FP_YYY_sqr(r,r); - FP_YYY_sqr(r,r); - FP_YYY_mul(r,r,&tb[w[i]]); - } - FP_YYY_reduce(r); -} - -/* set w=1/x */ -void FP_YYY_inv(FP_YYY *w,FP_YYY *x) -{ - - BIG_XXX m2; - BIG_XXX_rcopy(m2,Modulus_YYY); - BIG_XXX_dec(m2,2); - BIG_XXX_norm(m2); - FP_YYY_pow(w,x,m2); -} -#endif - -/* SU=8 */ -/* set n=1 */ -void FP_YYY_one(FP_YYY *n) -{ - BIG_XXX b; - BIG_XXX_one(b); - FP_YYY_nres(n,b); -} - -/* Set r=a^b mod Modulus */ -/* SU= 136 */ -/* -void FP_YYY_pow(FP_YYY *r,FP_YYY *a,BIG_XXX b) -{ - BIG_XXX z,zilch; - FP_YYY w; - int bt; - BIG_XXX_zero(zilch); - - BIG_XXX_norm(b); - BIG_XXX_copy(z,b); - FP_YYY_copy(&w,a); - FP_YYY_one(r); - while(1) - { - bt=BIG_XXX_parity(z); - BIG_XXX_fshr(z,1); - if (bt) FP_YYY_mul(r,r,&w); - if (BIG_XXX_comp(z,zilch)==0) break; - FP_YYY_sqr(&w,&w); - } - FP_YYY_reduce(r); -} -*/ - - - -/* is r a QR? */ -int FP_YYY_qr(FP_YYY *r) -{ - int j; - BIG_XXX m; - BIG_XXX b; - BIG_XXX_rcopy(m,Modulus_YYY); - FP_YYY_redc(b,r); - j=BIG_XXX_jacobi(b,m); - FP_YYY_nres(r,b); - if (j==1) return 1; - return 0; - -} - -/* Set a=sqrt(b) mod Modulus */ -/* SU= 160 */ -void FP_YYY_sqrt(FP_YYY *r,FP_YYY *a) -{ - FP_YYY v,i; - BIG_XXX b; - BIG_XXX m; - BIG_XXX_rcopy(m,Modulus_YYY); - BIG_XXX_mod(a->g,m); - BIG_XXX_copy(b,m); - if (MOD8_YYY==5) - { - FP_YYY_copy(&i,a); // i=x - BIG_XXX_fshl(i.g,1); // i=2x -#if MODTYPE_YYY == PSEUDO_MERSENNE - FP_YYY_fpow(&v,&i); -#else - BIG_XXX_dec(b,5); - BIG_XXX_norm(b); - BIG_XXX_fshr(b,3); // (p-5)/8 - FP_YYY_pow(&v,&i,b); // v=(2x)^(p-5)/8 -#endif - FP_YYY_mul(&i,&i,&v); // i=(2x)^(p+3)/8 - FP_YYY_mul(&i,&i,&v); // i=(2x)^(p-1)/4 - BIG_XXX_dec(i.g,1); // i=(2x)^(p-1)/4 - 1 - FP_YYY_mul(r,a,&v); - FP_YYY_mul(r,r,&i); - FP_YYY_reduce(r); - } - if (MOD8_YYY==3 || MOD8_YYY==7) - { -#if MODTYPE_YYY == PSEUDO_MERSENNE - FP_YYY_fpow(r,a); - FP_YYY_mul(r,r,a); -#else - BIG_XXX_inc(b,1); - BIG_XXX_norm(b); - BIG_XXX_fshr(b,2); /* (p+1)/4 */ - FP_YYY_pow(r,a,b); -#endif - } -} - -/* -int main() -{ - - BIG_XXX r; - - FP_YYY_one(r); - FP_YYY_sqr(r,r); - - BIG_XXX_output(r); - - int i,carry; - DBIG_XXX c={0,0,0,0,0,0,0,0}; - BIG_XXX a={1,2,3,4}; - BIG_XXX b={3,4,5,6}; - BIG_XXX r={11,12,13,14}; - BIG_XXX s={23,24,25,15}; - BIG_XXX w; - -// printf("NEXCESS_XXX= %d\n",NEXCESS_XXX); -// printf("MConst_YYY= %d\n",MConst_YYY); - - BIG_XXX_copy(b,Modulus_YYY); - BIG_XXX_dec(b,1); - BIG_XXX_norm(b); - - BIG_XXX_randomnum(r); BIG_XXX_norm(r); BIG_XXX_mod(r,Modulus_YYY); -// BIG_XXX_randomnum(s); norm(s); BIG_XXX_mod(s,Modulus_YYY); - -// BIG_XXX_output(r); -// BIG_XXX_output(s); - - BIG_XXX_output(r); - FP_YYY_nres(r); - BIG_XXX_output(r); - BIG_XXX_copy(a,r); - FP_YYY_redc(r); - BIG_XXX_output(r); - BIG_XXX_dscopy(c,a); - FP_YYY_mod(r,c); - BIG_XXX_output(r); - - -// exit(0); - -// copy(r,a); - printf("r= "); BIG_XXX_output(r); - BIG_XXX_modsqr(r,r,Modulus_YYY); - printf("r^2= "); BIG_XXX_output(r); - - FP_YYY_nres(r); - FP_YYY_sqrt(r,r); - FP_YYY_redc(r); - printf("r= "); BIG_XXX_output(r); - BIG_XXX_modsqr(r,r,Modulus_YYY); - printf("r^2= "); BIG_XXX_output(r); - - -// for (i=0;i<100000;i++) FP_YYY_sqr(r,r); -// for (i=0;i<100000;i++) - FP_YYY_sqrt(r,r); - - BIG_XXX_output(r); -} -*/ http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version3/c/fp.h ---------------------------------------------------------------------- diff --git a/version3/c/fp.h b/version3/c/fp.h deleted file mode 100644 index a7883f2..0000000 --- a/version3/c/fp.h +++ /dev/null @@ -1,245 +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 fp.h - * @author Mike Scott - * @brief FP Header File - * - */ - -#ifndef FP_YYY_H -#define FP_YYY_H - -#include "big_XXX.h" -#include "config_field_YYY.h" - - -/** - @brief FP Structure - quadratic extension field -*/ - -typedef struct -{ - BIG_XXX g; /**< Big representation of field element */ - sign32 XES; /**< Excess */ -} FP_YYY; - - -/* Field Params - see rom.c */ -extern const BIG_XXX Modulus_YYY; /**< Actual Modulus set in romf_yyy.c */ -extern const BIG_XXX R2modp_YYY; /**< Montgomery constant */ -extern const chunk MConst_YYY; /**< Constant associated with Modulus - for Montgomery = 1/p mod 2^BASEBITS */ - - -#define MODBITS_YYY MBITS_YYY /**< Number of bits in Modulus for selected curve */ -#define TBITS_YYY (MBITS_YYY%BASEBITS_XXX) /**< Number of active bits in top word */ -#define TMASK_YYY (((chunk)1<<TBITS_YYY)-1) /**< Mask for active bits in top word */ -#define FEXCESS_YYY (((sign32)1<<MAXXES_YYY)-1) /**< 2^(BASEBITS*NLEN-MODBITS)-1 - normalised BIG can be multiplied by less than this before reduction */ -#define OMASK_YYY (-((chunk)(1)<<TBITS_YYY)) /**< for masking out overflow bits */ - -//#define FUSED_MODMUL -//#define DEBUG_REDUCE - -/* FP prototypes */ - -/** @brief Tests for FP equal to zero mod Modulus - * - @param x BIG number to be tested - @return 1 if zero, else returns 0 - */ -extern int FP_YYY_iszilch(FP_YYY *x); - - -/** @brief Set FP to zero - * - @param x FP number to be set to 0 - */ -extern void FP_YYY_zero(FP_YYY *x); - -/** @brief Copy an FP - * - @param y FP number to be copied to - @param x FP to be copied from - */ -extern void FP_YYY_copy(FP_YYY *y,FP_YYY *x); - -/** @brief Copy from ROM to an FP - * - @param y FP number to be copied to - @param x BIG to be copied from ROM - */ -extern void FP_YYY_rcopy(FP_YYY *y,const BIG_XXX x); - - -/** @brief Compares two FPs - * - @param x FP number - @param y FP number - @return 1 if equal, else returns 0 - */ -extern int FP_YYY_equals(FP_YYY *x,FP_YYY *y); - - -/** @brief Conditional constant time swap of two FP numbers - * - Conditionally swaps parameters in constant time (without branching) - @param x an FP number - @param y another FP number - @param s swap takes place if not equal to 0 - */ -extern void FP_YYY_cswap(FP_YYY *x,FP_YYY *y,int s); -/** @brief Conditional copy of FP number - * - Conditionally copies second parameter to the first (without branching) - @param x an FP number - @param y another FP number - @param s copy takes place if not equal to 0 - */ -extern void FP_YYY_cmove(FP_YYY *x,FP_YYY *y,int s); -/** @brief Converts from BIG integer to residue form mod Modulus - * - @param x BIG number to be converted - @param y FP result - */ -extern void FP_YYY_nres(FP_YYY *y,BIG_XXX x); -/** @brief Converts from residue form back to BIG integer form - * - @param y FP number to be converted to BIG - @param x BIG result - */ -extern void FP_YYY_redc(BIG_XXX x,FP_YYY *y); -/** @brief Sets FP to representation of unity in residue form - * - @param x FP number to be set equal to unity. - */ -extern void FP_YYY_one(FP_YYY *x); -/** @brief Reduces DBIG to BIG exploiting special form of the modulus - * - This function comes in different flavours depending on the form of Modulus that is currently in use. - @param r BIG number, on exit = d mod Modulus - @param d DBIG number to be reduced - */ -extern void FP_YYY_mod(BIG_XXX r,DBIG_XXX d); - -#ifdef FUSED_MODMUL -extern void FP_YYY_modmul(BIG_XXX,BIG_XXX,BIG_XXX); -#endif - -/** @brief Fast Modular multiplication of two FPs, mod Modulus - * - Uses appropriate fast modular reduction method - @param x FP number, on exit the modular product = y*z mod Modulus - @param y FP number, the multiplicand - @param z FP number, the multiplier - */ -extern void FP_YYY_mul(FP_YYY *x,FP_YYY *y,FP_YYY *z); -/** @brief Fast Modular multiplication of an FP, by a small integer, mod Modulus - * - @param x FP number, on exit the modular product = y*i mod Modulus - @param y FP number, the multiplicand - @param i a small number, the multiplier - */ -extern void FP_YYY_imul(FP_YYY *x,FP_YYY *y,int i); -/** @brief Fast Modular squaring of an FP, mod Modulus - * - Uses appropriate fast modular reduction method - @param x FP number, on exit the modular product = y^2 mod Modulus - @param y FP number, the number to be squared - - */ -extern void FP_YYY_sqr(FP_YYY *x,FP_YYY *y); -/** @brief Modular addition of two FPs, mod Modulus - * - @param x FP number, on exit the modular sum = y+z mod Modulus - @param y FP number - @param z FP number - */ -extern void FP_YYY_add(FP_YYY *x,FP_YYY *y,FP_YYY *z); -/** @brief Modular subtraction of two FPs, mod Modulus - * - @param x FP number, on exit the modular difference = y-z mod Modulus - @param y FP number - @param z FP number - */ -extern void FP_YYY_sub(FP_YYY *x,FP_YYY *y,FP_YYY *z); -/** @brief Modular division by 2 of an FP, mod Modulus - * - @param x FP number, on exit =y/2 mod Modulus - @param y FP number - */ -extern void FP_YYY_div2(FP_YYY *x,FP_YYY *y); -/** @brief Fast Modular exponentiation of an FP, to the power of a BIG, mod Modulus - * - @param x FP number, on exit = y^z mod Modulus - @param y FP number - @param z BIG number exponent - */ -extern void FP_YYY_pow(FP_YYY *x,FP_YYY *y,BIG_XXX z); -/** @brief Fast Modular square root of a an FP, mod Modulus - * - @param x FP number, on exit = sqrt(y) mod Modulus - @param y FP number, the number whose square root is calculated - - */ -extern void FP_YYY_sqrt(FP_YYY *x,FP_YYY *y); -/** @brief Modular negation of a an FP, mod Modulus - * - @param x FP number, on exit = -y mod Modulus - @param y FP number - */ -extern void FP_YYY_neg(FP_YYY *x,FP_YYY *y); -/** @brief Outputs an FP number to the console - * - Converts from residue form before output - @param x an FP number - */ -extern void FP_YYY_output(FP_YYY *x); -/** @brief Outputs an FP number to the console, in raw form - * - @param x a BIG number - */ -extern void FP_YYY_rawoutput(FP_YYY *x); -/** @brief Reduces possibly unreduced FP mod Modulus - * - @param x FP number, on exit reduced mod Modulus - */ -extern void FP_YYY_reduce(FP_YYY *x); -/** @brief normalizes FP - * - @param x FP number, on exit normalized - */ -extern void FP_YYY_norm(FP_YYY *x); -/** @brief Tests for FP a quadratic residue mod Modulus - * - @param x FP number to be tested - @return 1 if quadratic residue, else returns 0 if quadratic non-residue - */ -extern int FP_YYY_qr(FP_YYY *x); -/** @brief Modular inverse of a an FP, mod Modulus - * - @param x FP number, on exit = 1/y mod Modulus - @param y FP number - */ -extern void FP_YYY_inv(FP_YYY *x,FP_YYY *y); - - - - -#endif http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version3/c/fp12.c ---------------------------------------------------------------------- diff --git a/version3/c/fp12.c b/version3/c/fp12.c deleted file mode 100644 index 860fc12..0000000 --- a/version3/c/fp12.c +++ /dev/null @@ -1,984 +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 "fp12_YYY.h" - -/* 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 FP12_YYY_select(FP12_YYY *f,FP12_YYY g[],sign32 b) -{ - FP12_YYY invf; - sign32 m=b>>31; - sign32 babs=(b^m)-m; - - babs=(babs-1)/2; - - FP12_YYY_cmove(f,&g[0],teq(babs,0)); // conditional move - FP12_YYY_cmove(f,&g[1],teq(babs,1)); - FP12_YYY_cmove(f,&g[2],teq(babs,2)); - FP12_YYY_cmove(f,&g[3],teq(babs,3)); - FP12_YYY_cmove(f,&g[4],teq(babs,4)); - FP12_YYY_cmove(f,&g[5],teq(babs,5)); - FP12_YYY_cmove(f,&g[6],teq(babs,6)); - FP12_YYY_cmove(f,&g[7],teq(babs,7)); - - FP12_YYY_copy(&invf,f); - FP12_YYY_conj(&invf,&invf); // 1/f - FP12_YYY_cmove(f,&invf,(int)(m&1)); -} - - - -/* test x==0 ? */ -/* SU= 8 */ -int FP12_YYY_iszilch(FP12_YYY *x) -{ - if (FP4_YYY_iszilch(&(x->a)) && FP4_YYY_iszilch(&(x->b)) && FP4_YYY_iszilch(&(x->c))) return 1; - return 0; -} - -/* test x==1 ? */ -/* SU= 8 */ -int FP12_YYY_isunity(FP12_YYY *x) -{ - if (FP4_YYY_isunity(&(x->a)) && FP4_YYY_iszilch(&(x->b)) && FP4_YYY_iszilch(&(x->c))) return 1; - return 0; -} - -/* FP12 copy w=x */ -/* SU= 16 */ -void FP12_YYY_copy(FP12_YYY *w,FP12_YYY *x) -{ - if (x==w) return; - FP4_YYY_copy(&(w->a),&(x->a)); - FP4_YYY_copy(&(w->b),&(x->b)); - FP4_YYY_copy(&(w->c),&(x->c)); -} - -/* FP12 w=1 */ -/* SU= 8 */ -void FP12_YYY_one(FP12_YYY *w) -{ - FP4_YYY_one(&(w->a)); - FP4_YYY_zero(&(w->b)); - FP4_YYY_zero(&(w->c)); -} - -/* return 1 if x==y, else 0 */ -/* SU= 16 */ -int FP12_YYY_equals(FP12_YYY *x,FP12_YYY *y) -{ - if (FP4_YYY_equals(&(x->a),&(y->a)) && FP4_YYY_equals(&(x->b),&(y->b)) && FP4_YYY_equals(&(x->b),&(y->b))) - return 1; - return 0; -} - -/* Set w=conj(x) */ -/* SU= 8 */ -void FP12_YYY_conj(FP12_YYY *w,FP12_YYY *x) -{ - FP12_YYY_copy(w,x); - FP4_YYY_conj(&(w->a),&(w->a)); - FP4_YYY_nconj(&(w->b),&(w->b)); - FP4_YYY_conj(&(w->c),&(w->c)); -} - -/* Create FP12 from FP4 */ -/* SU= 8 */ -void FP12_YYY_from_FP4(FP12_YYY *w,FP4_YYY *a) -{ - FP4_YYY_copy(&(w->a),a); - FP4_YYY_zero(&(w->b)); - FP4_YYY_zero(&(w->c)); -} - -/* Create FP12 from 3 FP4's */ -/* SU= 16 */ -void FP12_YYY_from_FP4s(FP12_YYY *w,FP4_YYY *a,FP4_YYY *b,FP4_YYY *c) -{ - FP4_YYY_copy(&(w->a),a); - FP4_YYY_copy(&(w->b),b); - FP4_YYY_copy(&(w->c),c); -} - -/* Granger-Scott Unitary Squaring. This does not benefit from lazy reduction */ -/* SU= 600 */ -void FP12_YYY_usqr(FP12_YYY *w,FP12_YYY *x) -{ - FP4_YYY A,B,C,D; - - FP4_YYY_copy(&A,&(x->a)); - - FP4_YYY_sqr(&(w->a),&(x->a)); - FP4_YYY_add(&D,&(w->a),&(w->a)); - FP4_YYY_add(&(w->a),&D,&(w->a)); - - FP4_YYY_norm(&(w->a)); - FP4_YYY_nconj(&A,&A); - - FP4_YYY_add(&A,&A,&A); - FP4_YYY_add(&(w->a),&(w->a),&A); - FP4_YYY_sqr(&B,&(x->c)); - FP4_YYY_times_i(&B); - - FP4_YYY_add(&D,&B,&B); - FP4_YYY_add(&B,&B,&D); - FP4_YYY_norm(&B); - - FP4_YYY_sqr(&C,&(x->b)); - - FP4_YYY_add(&D,&C,&C); - FP4_YYY_add(&C,&C,&D); - - FP4_YYY_norm(&C); - FP4_YYY_conj(&(w->b),&(x->b)); - FP4_YYY_add(&(w->b),&(w->b),&(w->b)); - FP4_YYY_nconj(&(w->c),&(x->c)); - - FP4_YYY_add(&(w->c),&(w->c),&(w->c)); - FP4_YYY_add(&(w->b),&B,&(w->b)); - FP4_YYY_add(&(w->c),&C,&(w->c)); - - FP12_YYY_reduce(w); /* reduce here as in pow function repeated squarings would trigger multiple reductions */ -} - -/* FP12 squaring w=x^2 */ -/* SU= 600 */ -void FP12_YYY_sqr(FP12_YYY *w,FP12_YYY *x) -{ - /* Use Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */ - - FP4_YYY A,B,C,D; - - FP4_YYY_sqr(&A,&(x->a)); - FP4_YYY_mul(&B,&(x->b),&(x->c)); - FP4_YYY_add(&B,&B,&B); - FP4_YYY_norm(&B); - FP4_YYY_sqr(&C,&(x->c)); - - FP4_YYY_mul(&D,&(x->a),&(x->b)); - FP4_YYY_add(&D,&D,&D); - FP4_YYY_add(&(w->c),&(x->a),&(x->c)); - FP4_YYY_add(&(w->c),&(x->b),&(w->c)); - FP4_YYY_norm(&(w->c)); - - FP4_YYY_sqr(&(w->c),&(w->c)); - - FP4_YYY_copy(&(w->a),&A); - FP4_YYY_add(&A,&A,&B); - - FP4_YYY_norm(&A); - - FP4_YYY_add(&A,&A,&C); - FP4_YYY_add(&A,&A,&D); - - FP4_YYY_norm(&A); - FP4_YYY_neg(&A,&A); - FP4_YYY_times_i(&B); - FP4_YYY_times_i(&C); - - FP4_YYY_add(&(w->a),&(w->a),&B); - FP4_YYY_add(&(w->b),&C,&D); - FP4_YYY_add(&(w->c),&(w->c),&A); - - FP12_YYY_norm(w); -} - -/* FP12 full multiplication w=w*y */ - - -/* SU= 896 */ -/* FP12 full multiplication w=w*y */ -void FP12_YYY_mul(FP12_YYY *w,FP12_YYY *y) -{ - FP4_YYY z0,z1,z2,z3,t0,t1; - - FP4_YYY_mul(&z0,&(w->a),&(y->a)); - FP4_YYY_mul(&z2,&(w->b),&(y->b)); // - - FP4_YYY_add(&t0,&(w->a),&(w->b)); - FP4_YYY_add(&t1,&(y->a),&(y->b)); // - - FP4_YYY_norm(&t0); - FP4_YYY_norm(&t1); - - FP4_YYY_mul(&z1,&t0,&t1); - FP4_YYY_add(&t0,&(w->b),&(w->c)); - FP4_YYY_add(&t1,&(y->b),&(y->c)); // - - FP4_YYY_norm(&t0); - FP4_YYY_norm(&t1); - - FP4_YYY_mul(&z3,&t0,&t1); - - FP4_YYY_neg(&t0,&z0); - FP4_YYY_neg(&t1,&z2); - - FP4_YYY_add(&z1,&z1,&t0); // z1=z1-z0 -// FP4_YYY_norm(&z1); - FP4_YYY_add(&(w->b),&z1,&t1); -// z1=z1-z2 - FP4_YYY_add(&z3,&z3,&t1); // z3=z3-z2 - FP4_YYY_add(&z2,&z2,&t0); // z2=z2-z0 - - FP4_YYY_add(&t0,&(w->a),&(w->c)); - FP4_YYY_add(&t1,&(y->a),&(y->c)); - - FP4_YYY_norm(&t0); - FP4_YYY_norm(&t1); - - FP4_YYY_mul(&t0,&t1,&t0); - FP4_YYY_add(&z2,&z2,&t0); - - FP4_YYY_mul(&t0,&(w->c),&(y->c)); - FP4_YYY_neg(&t1,&t0); - - FP4_YYY_add(&(w->c),&z2,&t1); - FP4_YYY_add(&z3,&z3,&t1); - FP4_YYY_times_i(&t0); - FP4_YYY_add(&(w->b),&(w->b),&t0); - FP4_YYY_norm(&z3); - FP4_YYY_times_i(&z3); - FP4_YYY_add(&(w->a),&z0,&z3); - - FP12_YYY_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_YYY_smul(FP12_YYY *w,FP12_YYY *y,int type) -{ - FP4_YYY z0,z1,z2,z3,t0,t1; - - if (type==D_TYPE) - { - // y->c is 0 - - FP4_YYY_copy(&z3,&(w->b)); - FP4_YYY_mul(&z0,&(w->a),&(y->a)); - - FP4_YYY_pmul(&z2,&(w->b),&(y->b).a); - FP4_YYY_add(&(w->b),&(w->a),&(w->b)); - FP4_YYY_copy(&t1,&(y->a)); - FP2_YYY_add(&t1.a,&t1.a,&(y->b).a); - - FP4_YYY_norm(&t1); - FP4_YYY_norm(&(w->b)); - - FP4_YYY_mul(&(w->b),&(w->b),&t1); - FP4_YYY_add(&z3,&z3,&(w->c)); - FP4_YYY_norm(&z3); - FP4_YYY_pmul(&z3,&z3,&(y->b).a); - FP4_YYY_neg(&t0,&z0); - FP4_YYY_neg(&t1,&z2); - - FP4_YYY_add(&(w->b),&(w->b),&t0); // z1=z1-z0 -// FP4_YYY_norm(&(w->b)); - FP4_YYY_add(&(w->b),&(w->b),&t1); // z1=z1-z2 - - FP4_YYY_add(&z3,&z3,&t1); // z3=z3-z2 - FP4_YYY_add(&z2,&z2,&t0); // z2=z2-z0 - - FP4_YYY_add(&t0,&(w->a),&(w->c)); - - FP4_YYY_norm(&t0); - FP4_YYY_norm(&z3); - - FP4_YYY_mul(&t0,&(y->a),&t0); - FP4_YYY_add(&(w->c),&z2,&t0); - - FP4_YYY_times_i(&z3); - FP4_YYY_add(&(w->a),&z0,&z3); - } - - if (type==M_TYPE) - { - // y->b is zero - FP4_YYY_mul(&z0,&(w->a),&(y->a)); - FP4_YYY_add(&t0,&(w->a),&(w->b)); - FP4_YYY_norm(&t0); - - FP4_YYY_mul(&z1,&t0,&(y->a)); - FP4_YYY_add(&t0,&(w->b),&(w->c)); - FP4_YYY_norm(&t0); - - FP4_YYY_pmul(&z3,&t0,&(y->c).b); - FP4_YYY_times_i(&z3); - - FP4_YYY_neg(&t0,&z0); - FP4_YYY_add(&z1,&z1,&t0); // z1=z1-z0 - - FP4_YYY_copy(&(w->b),&z1); - - FP4_YYY_copy(&z2,&t0); - - FP4_YYY_add(&t0,&(w->a),&(w->c)); - FP4_YYY_add(&t1,&(y->a),&(y->c)); - - FP4_YYY_norm(&t0); - FP4_YYY_norm(&t1); - - FP4_YYY_mul(&t0,&t1,&t0); - FP4_YYY_add(&z2,&z2,&t0); - - FP4_YYY_pmul(&t0,&(w->c),&(y->c).b); - FP4_YYY_times_i(&t0); - FP4_YYY_neg(&t1,&t0); - FP4_YYY_times_i(&t0); - - FP4_YYY_add(&(w->c),&z2,&t1); - FP4_YYY_add(&z3,&z3,&t1); - - FP4_YYY_add(&(w->b),&(w->b),&t0); - FP4_YYY_norm(&z3); - FP4_YYY_times_i(&z3); - FP4_YYY_add(&(w->a),&z0,&z3); - } - FP12_YYY_norm(w); -} - -/* Set w=1/x */ -/* SU= 600 */ -void FP12_YYY_inv(FP12_YYY *w,FP12_YYY *x) -{ - FP4_YYY f0,f1,f2,f3; -// FP12_YYY_norm(x); - - FP4_YYY_sqr(&f0,&(x->a)); - FP4_YYY_mul(&f1,&(x->b),&(x->c)); - FP4_YYY_times_i(&f1); - FP4_YYY_sub(&f0,&f0,&f1); /* y.a */ - FP4_YYY_norm(&f0); - - FP4_YYY_sqr(&f1,&(x->c)); - FP4_YYY_times_i(&f1); - FP4_YYY_mul(&f2,&(x->a),&(x->b)); - FP4_YYY_sub(&f1,&f1,&f2); /* y.b */ - FP4_YYY_norm(&f1); - - FP4_YYY_sqr(&f2,&(x->b)); - FP4_YYY_mul(&f3,&(x->a),&(x->c)); - FP4_YYY_sub(&f2,&f2,&f3); /* y.c */ - FP4_YYY_norm(&f2); - - FP4_YYY_mul(&f3,&(x->b),&f2); - FP4_YYY_times_i(&f3); - FP4_YYY_mul(&(w->a),&f0,&(x->a)); - FP4_YYY_add(&f3,&(w->a),&f3); - FP4_YYY_mul(&(w->c),&f1,&(x->c)); - FP4_YYY_times_i(&(w->c)); - - FP4_YYY_add(&f3,&(w->c),&f3); - FP4_YYY_norm(&f3); - - FP4_YYY_inv(&f3,&f3); - - FP4_YYY_mul(&(w->a),&f0,&f3); - FP4_YYY_mul(&(w->b),&f1,&f3); - FP4_YYY_mul(&(w->c),&f2,&f3); - -} - -/* constant time powering by small integer of max length bts */ - -void FP12_YYY_pinpow(FP12_YYY *r,int e,int bts) -{ - int i,b; - FP12_YYY R[2]; - - FP12_YYY_one(&R[0]); - FP12_YYY_copy(&R[1],r); - - for (i=bts-1; i>=0; i--) - { - b=(e>>i)&1; - FP12_YYY_mul(&R[1-b],&R[b]); - FP12_YYY_usqr(&R[b],&R[b]); - } - FP12_YYY_copy(r,&R[0]); -} - -/* Compressed powering of unitary elements y=x^(e mod r) */ - -void FP12_YYY_compow(FP4_YYY *c,FP12_YYY *x,BIG_XXX e,BIG_XXX r) -{ - FP12_YYY g1,g2; - FP4_YYY cp,cpm1,cpm2; - FP2_YYY f; - BIG_XXX q,a,b,m; - - BIG_XXX_rcopy(a,Fra_YYY); - BIG_XXX_rcopy(b,Frb_YYY); - FP2_YYY_from_BIGs(&f,a,b); - - BIG_XXX_rcopy(q,Modulus_YYY); - - FP12_YYY_copy(&g1,x); - FP12_YYY_copy(&g2,x); - - BIG_XXX_copy(m,q); - BIG_XXX_mod(m,r); - - BIG_XXX_copy(a,e); - BIG_XXX_mod(a,m); - - BIG_XXX_copy(b,e); - BIG_XXX_sdiv(b,m); - - FP12_YYY_trace(c,&g1); - - if (BIG_XXX_iszilch(b)) - { - FP4_YYY_xtr_pow(c,c,e); - return; - } - - - FP12_YYY_frob(&g2,&f); - FP12_YYY_trace(&cp,&g2); - - FP12_YYY_conj(&g1,&g1); - FP12_YYY_mul(&g2,&g1); - FP12_YYY_trace(&cpm1,&g2); - FP12_YYY_mul(&g2,&g1); - FP12_YYY_trace(&cpm2,&g2); - - FP4_YYY_xtr_pow2(c,&cp,c,&cpm1,&cpm2,a,b); - -} - - -/* SU= 528 */ -/* set r=a^b */ -/* Note this is simple square and multiply, so not side-channel safe */ - -void FP12_YYY_pow(FP12_YYY *r,FP12_YYY *a,BIG_XXX b) -{ - FP12_YYY w,sf; - BIG_XXX b1,b3; - int i,nb,bt; - BIG_XXX_copy(b1,b); - BIG_XXX_norm(b1); - BIG_XXX_pmul(b3,b1,3); - BIG_XXX_norm(b3); - - FP12_YYY_copy(&sf,a); - FP12_YYY_norm(&sf); - FP12_YYY_copy(&w,&sf); - - - nb=BIG_XXX_nbits(b3); - for (i=nb-2; i>=1; i--) - { - FP12_YYY_usqr(&w,&w); - bt=BIG_XXX_bit(b3,i)-BIG_XXX_bit(b1,i); - if (bt==1) - FP12_YYY_mul(&w,&sf); - if (bt==-1) - { - FP12_YYY_conj(&sf,&sf); - FP12_YYY_mul(&w,&sf); - FP12_YYY_conj(&sf,&sf); - } - } - - FP12_YYY_copy(r,&w); - FP12_YYY_reduce(r); - - /* - while(1) - { - bt=BIG_XXX_parity(z); - BIG_XXX_shr(z,1); - if (bt) - FP12_YYY_mul(r,&w); - if (BIG_XXX_comp(z,zilch)==0) break; - FP12_YYY_usqr(&w,&w); - } - - FP12_YYY_reduce(r); */ -} - -/* p=q0^u0.q1^u1.q2^u2.q3^u3 */ -/* Side channel attack secure */ -// Bos & Costello https://eprint.iacr.org/2013/458.pdf -// Faz-Hernandez & Longa & Sanchez https://eprint.iacr.org/2013/158.pdf - -void FP12_YYY_pow4(FP12_YYY *p,FP12_YYY *q,BIG_XXX u[4]) -{ - int i,j,k,nb,pb,bt; - FP12_YYY g[8],r; - BIG_XXX t[4],mt; - sign8 w[NLEN_XXX*BASEBITS_XXX+1]; - sign8 s[NLEN_XXX*BASEBITS_XXX+1]; - - for (i=0; i<4; i++) - BIG_XXX_copy(t[i],u[i]); - - -// Precomputed table - FP12_YYY_copy(&g[0],&q[0]); // q[0] - FP12_YYY_copy(&g[1],&g[0]); - FP12_YYY_mul(&g[1],&q[1]); // q[0].q[1] - FP12_YYY_copy(&g[2],&g[0]); - FP12_YYY_mul(&g[2],&q[2]); // q[0].q[2] - FP12_YYY_copy(&g[3],&g[1]); - FP12_YYY_mul(&g[3],&q[2]); // q[0].q[1].q[2] - FP12_YYY_copy(&g[4],&g[0]); - FP12_YYY_mul(&g[4],&q[3]); // q[0].q[3] - FP12_YYY_copy(&g[5],&g[1]); - FP12_YYY_mul(&g[5],&q[3]); // q[0].q[1].q[3] - FP12_YYY_copy(&g[6],&g[2]); - FP12_YYY_mul(&g[6],&q[3]); // q[0].q[2].q[3] - FP12_YYY_copy(&g[7],&g[3]); - FP12_YYY_mul(&g[7],&q[3]); // q[0].q[1].q[2].q[3] - -// Make it odd - pb=1-BIG_XXX_parity(t[0]); - BIG_XXX_inc(t[0],pb); - BIG_XXX_norm(t[0]); - -// Number of bits - BIG_XXX_zero(mt); - for (i=0; i<4; i++) - { - BIG_XXX_or(mt,mt,t[i]); - } - nb=1+BIG_XXX_nbits(mt); - -// Sign pivot - s[nb-1]=1; - for (i=0;i<nb-1;i++) - { - BIG_XXX_fshr(t[0],1); - s[i]=2*BIG_XXX_parity(t[0])-1; - } - -// Recoded exponent - for (i=0; i<nb; i++) - { - w[i]=0; - k=1; - for (j=1; j<4; j++) - { - bt=s[i]*BIG_XXX_parity(t[j]); - BIG_XXX_fshr(t[j],1); - - BIG_XXX_dec(t[j],(bt>>1)); - BIG_XXX_norm(t[j]); - w[i]+=bt*k; - k*=2; - } - } - -// Main loop - FP12_YYY_select(p,g,2*w[nb-1]+1); - for (i=nb-2; i>=0; i--) - { - FP12_YYY_select(&r,g,2*w[i]+s[i]); - FP12_YYY_usqr(p,p); - FP12_YYY_mul(p,&r); - } -// apply correction - FP12_YYY_conj(&r,&q[0]); - FP12_YYY_mul(&r,p); - FP12_YYY_cmove(p,&r,pb); - - FP12_YYY_reduce(p); -} - -/* p=q0^u0.q1^u1.q2^u2.q3^u3 */ -/* Timing attack secure, but not cache attack secure */ -/* -void FP12_YYY_pow4(FP12_YYY *p,FP12_YYY *q,BIG_XXX u[4]) -{ - int i,j,a[4],nb,m; - FP12_YYY g[8],c,s[2]; - BIG_XXX t[4],mt; - sign8 w[NLEN_XXX*BASEBITS_XXX+1]; - - for (i=0; i<4; i++) - BIG_XXX_copy(t[i],u[i]); - - FP12_YYY_copy(&g[0],&q[0]); - FP12_YYY_conj(&s[0],&q[1]); - FP12_YYY_mul(&g[0],&s[0]); // P/Q - FP12_YYY_copy(&g[1],&g[0]); - FP12_YYY_copy(&g[2],&g[0]); - FP12_YYY_copy(&g[3],&g[0]); - FP12_YYY_copy(&g[4],&q[0]); - FP12_YYY_mul(&g[4],&q[1]); // P*Q - FP12_YYY_copy(&g[5],&g[4]); - FP12_YYY_copy(&g[6],&g[4]); - FP12_YYY_copy(&g[7],&g[4]); - - FP12_YYY_copy(&s[1],&q[2]); - FP12_YYY_conj(&s[0],&q[3]); - FP12_YYY_mul(&s[1],&s[0]); // R/S - FP12_YYY_conj(&s[0],&s[1]); - FP12_YYY_mul(&g[1],&s[0]); - FP12_YYY_mul(&g[2],&s[1]); - FP12_YYY_mul(&g[5],&s[0]); - FP12_YYY_mul(&g[6],&s[1]); - FP12_YYY_copy(&s[1],&q[2]); - FP12_YYY_mul(&s[1],&q[3]); // R*S - FP12_YYY_conj(&s[0],&s[1]); - FP12_YYY_mul(&g[0],&s[0]); - FP12_YYY_mul(&g[3],&s[1]); - FP12_YYY_mul(&g[4],&s[0]); - FP12_YYY_mul(&g[7],&s[1]); - - // if power is even add 1 to power, and add q to correction - FP12_YYY_one(&c); - - BIG_XXX_zero(mt); - for (i=0; i<4; i++) - { - if (BIG_XXX_parity(t[i])==0) - { - BIG_XXX_inc(t[i],1); - BIG_XXX_norm(t[i]); - FP12_YYY_mul(&c,&q[i]); - } - BIG_XXX_add(mt,mt,t[i]); - BIG_XXX_norm(mt); - } - - FP12_YYY_conj(&c,&c); - nb=1+BIG_XXX_nbits(mt); - - // convert exponent to signed 1-bit window - for (j=0; j<nb; j++) - { - for (i=0; i<4; i++) - { - a[i]=BIG_XXX_lastbits(t[i],2)-2; - BIG_XXX_dec(t[i],a[i]); - BIG_XXX_norm(t[i]); - BIG_XXX_fshr(t[i],1); - } - w[j]=8*a[0]+4*a[1]+2*a[2]+a[3]; - } - w[nb]=8*BIG_XXX_lastbits(t[0],2)+4*BIG_XXX_lastbits(t[1],2)+2*BIG_XXX_lastbits(t[2],2)+BIG_XXX_lastbits(t[3],2); - FP12_YYY_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_YYY_copy(&s[0],&g[j]); - FP12_YYY_conj(&s[1],&g[j]); - FP12_YYY_usqr(p,p); - FP12_YYY_mul(p,&s[m&1]); - } - FP12_YYY_mul(p,&c); // apply correction - FP12_YYY_reduce(p); -} -*/ -/* Set w=w^p using Frobenius */ -/* SU= 160 */ -void FP12_YYY_frob(FP12_YYY *w,FP2_YYY *f) -{ - FP2_YYY f2,f3; - FP2_YYY_sqr(&f2,f); /* f2=f^2 */ - FP2_YYY_mul(&f3,&f2,f); /* f3=f^3 */ - - FP4_YYY_frob(&(w->a),&f3); - FP4_YYY_frob(&(w->b),&f3); - FP4_YYY_frob(&(w->c),&f3); - - FP4_YYY_pmul(&(w->b),&(w->b),f); - FP4_YYY_pmul(&(w->c),&(w->c),&f2); -} - -/* SU= 8 */ -/* normalise all components of w */ -void FP12_YYY_norm(FP12_YYY *w) -{ - FP4_YYY_norm(&(w->a)); - FP4_YYY_norm(&(w->b)); - FP4_YYY_norm(&(w->c)); -} - -/* SU= 8 */ -/* reduce all components of w */ -void FP12_YYY_reduce(FP12_YYY *w) -{ - FP4_YYY_reduce(&(w->a)); - FP4_YYY_reduce(&(w->b)); - FP4_YYY_reduce(&(w->c)); -} - -/* trace function w=trace(x) */ -/* SU= 8 */ -void FP12_YYY_trace(FP4_YYY *w,FP12_YYY *x) -{ - FP4_YYY_imul(w,&(x->a),3); - FP4_YYY_reduce(w); -} - -/* SU= 8 */ -/* Output w in hex */ -void FP12_YYY_output(FP12_YYY *w) -{ - printf("["); - FP4_YYY_output(&(w->a)); - printf(","); - FP4_YYY_output(&(w->b)); - printf(","); - FP4_YYY_output(&(w->c)); - printf("]"); -} - -/* SU= 64 */ -/* Convert g to octet string w */ -void FP12_YYY_toOctet(octet *W,FP12_YYY *g) -{ - BIG_XXX a; - W->len=12*MODBYTES_XXX; - - FP_YYY_redc(a,&(g->a.a.a)); - BIG_XXX_toBytes(&(W->val[0]),a); - FP_YYY_redc(a,&(g->a.a.b)); - BIG_XXX_toBytes(&(W->val[MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->a.b.a)); - BIG_XXX_toBytes(&(W->val[2*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->a.b.b)); - BIG_XXX_toBytes(&(W->val[3*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->b.a.a)); - BIG_XXX_toBytes(&(W->val[4*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->b.a.b)); - BIG_XXX_toBytes(&(W->val[5*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->b.b.a)); - BIG_XXX_toBytes(&(W->val[6*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->b.b.b)); - BIG_XXX_toBytes(&(W->val[7*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->c.a.a)); - BIG_XXX_toBytes(&(W->val[8*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->c.a.b)); - BIG_XXX_toBytes(&(W->val[9*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->c.b.a)); - BIG_XXX_toBytes(&(W->val[10*MODBYTES_XXX]),a); - FP_YYY_redc(a,&(g->c.b.b)); - BIG_XXX_toBytes(&(W->val[11*MODBYTES_XXX]),a); -} - -/* SU= 24 */ -/* Restore g from octet string w */ -void FP12_YYY_fromOctet(FP12_YYY *g,octet *W) -{ - BIG_XXX b; - BIG_XXX_fromBytes(b,&W->val[0]); - FP_YYY_nres(&(g->a.a.a),b); - BIG_XXX_fromBytes(b,&W->val[MODBYTES_XXX]); - FP_YYY_nres(&(g->a.a.b),b); - BIG_XXX_fromBytes(b,&W->val[2*MODBYTES_XXX]); - FP_YYY_nres(&(g->a.b.a),b); - BIG_XXX_fromBytes(b,&W->val[3*MODBYTES_XXX]); - FP_YYY_nres(&(g->a.b.b),b); - BIG_XXX_fromBytes(b,&W->val[4*MODBYTES_XXX]); - FP_YYY_nres(&(g->b.a.a),b); - BIG_XXX_fromBytes(b,&W->val[5*MODBYTES_XXX]); - FP_YYY_nres(&(g->b.a.b),b); - BIG_XXX_fromBytes(b,&W->val[6*MODBYTES_XXX]); - FP_YYY_nres(&(g->b.b.a),b); - BIG_XXX_fromBytes(b,&W->val[7*MODBYTES_XXX]); - FP_YYY_nres(&(g->b.b.b),b); - BIG_XXX_fromBytes(b,&W->val[8*MODBYTES_XXX]); - FP_YYY_nres(&(g->c.a.a),b); - BIG_XXX_fromBytes(b,&W->val[9*MODBYTES_XXX]); - FP_YYY_nres(&(g->c.a.b),b); - BIG_XXX_fromBytes(b,&W->val[10*MODBYTES_XXX]); - FP_YYY_nres(&(g->c.b.a),b); - BIG_XXX_fromBytes(b,&W->val[11*MODBYTES_XXX]); - FP_YYY_nres(&(g->c.b.b),b); -} - -/* Move b to a if d=1 */ -void FP12_YYY_cmove(FP12_YYY *f,FP12_YYY *g,int d) -{ - FP4_YYY_cmove(&(f->a),&(g->a),d); - FP4_YYY_cmove(&(f->b),&(g->b),d); - FP4_YYY_cmove(&(f->c),&(g->c),d); -} - - -/* -int main(){ - FP2_YYY f,w0,w1; - FP4_YYY t0,t1,t2; - FP12_YYY w,t,lv; - BIG_XXX a,b; - BIG_XXX p; - - //Test w^(P^4) = w mod p^2 -// BIG_XXX_randomnum(a); -// BIG_XXX_randomnum(b); -// BIG_XXX_mod(a,Modulus); BIG_XXX_mod(b,Modulus); - BIG_XXX_zero(a); BIG_XXX_zero(b); BIG_XXX_inc(a,1); BIG_XXX_inc(b,2); FP_YYY_nres(a); FP_YYY_nres(b); - FP2_YYY_from_zps(&w0,a,b); - -// BIG_XXX_randomnum(a); BIG_XXX_randomnum(b); -// BIG_XXX_mod(a,Modulus); BIG_XXX_mod(b,Modulus); - BIG_XXX_zero(a); BIG_XXX_zero(b); BIG_XXX_inc(a,3); BIG_XXX_inc(b,4); FP_YYY_nres(a); FP_YYY_nres(b); - FP2_YYY_from_zps(&w1,a,b); - - FP4_YYY_from_FP2s(&t0,&w0,&w1); - FP4_YYY_reduce(&t0); - -// BIG_XXX_randomnum(a); -// BIG_XXX_randomnum(b); -// BIG_XXX_mod(a,Modulus); BIG_XXX_mod(b,Modulus); - BIG_XXX_zero(a); BIG_XXX_zero(b); BIG_XXX_inc(a,5); BIG_XXX_inc(b,6); FP_YYY_nres(a); FP_YYY_nres(b); - FP2_YYY_from_zps(&w0,a,b); - -// BIG_XXX_randomnum(a); BIG_XXX_randomnum(b); -// BIG_XXX_mod(a,Modulus); BIG_XXX_mod(b,Modulus); - - BIG_XXX_zero(a); BIG_XXX_zero(b); BIG_XXX_inc(a,7); BIG_XXX_inc(b,8); FP_YYY_nres(a); FP_YYY_nres(b); - FP2_YYY_from_zps(&w1,a,b); - - FP4_YYY_from_FP2s(&t1,&w0,&w1); - FP4_YYY_reduce(&t1); - -// BIG_XXX_randomnum(a); -// BIG_XXX_randomnum(b); -// BIG_XXX_mod(a,Modulus); BIG_XXX_mod(b,Modulus); - BIG_XXX_zero(a); BIG_XXX_zero(b); BIG_XXX_inc(a,9); BIG_XXX_inc(b,10); FP_YYY_nres(a); FP_YYY_nres(b); - FP2_YYY_from_zps(&w0,a,b); - -// BIG_XXX_randomnum(a); BIG_XXX_randomnum(b); -// BIG_XXX_mod(a,Modulus); BIG_XXX_mod(b,Modulus); - BIG_XXX_zero(a); BIG_XXX_zero(b); BIG_XXX_inc(a,11); BIG_XXX_inc(b,12); FP_YYY_nres(a); FP_YYY_nres(b); - FP2_YYY_from_zps(&w1,a,b); - - FP4_YYY_from_FP2s(&t2,&w0,&w1); - FP4_YYY_reduce(&t2); - - FP12_YYY_from_FP4s(&w,&t0,&t1,&t2); - - FP12_YYY_copy(&t,&w); - - printf("w= "); - FP12_YYY_output(&w); - printf("\n"); - - BIG_XXX_rcopy(p,Modulus); - //BIG_XXX_zero(p); BIG_XXX_inc(p,7); - - FP12_YYY_pow(&w,&w,p); - - printf("w^p= "); - FP12_YYY_output(&w); - printf("\n"); - - FP2_YYY_gfc(&f,12); - FP12_YYY_frob(&t,&f); - printf("w^p= "); - FP12_YYY_output(&t); - printf("\n"); - -//exit(0); - - FP12_YYY_pow(&w,&w,p); - //printf("w^p^2= "); - //FP12_YYY_output(&w); - //printf("\n"); - FP12_YYY_pow(&w,&w,p); - //printf("w^p^3= "); - //FP12_YYY_output(&w); - //printf("\n"); - FP12_YYY_pow(&w,&w,p); - FP12_YYY_pow(&w,&w,p); - FP12_YYY_pow(&w,&w,p); - printf("w^p^6= "); - FP12_YYY_output(&w); - printf("\n"); - FP12_YYY_pow(&w,&w,p); - FP12_YYY_pow(&w,&w,p); - printf("w^p^8= "); - FP12_YYY_output(&w); - printf("\n"); - FP12_YYY_pow(&w,&w,p); - FP12_YYY_pow(&w,&w,p); - FP12_YYY_pow(&w,&w,p); - printf("w^p^11= "); - FP12_YYY_output(&w); - printf("\n"); - - // BIG_XXX_zero(p); BIG_XXX_inc(p,7); BIG_XXX_norm(p); - FP12_YYY_pow(&w,&w,p); - - printf("w^p12= "); - FP12_YYY_output(&w); - printf("\n"); -//exit(0); - - FP12_YYY_inv(&t,&w); - printf("1/w mod p^4 = "); - FP12_YYY_output(&t); - printf("\n"); - - FP12_YYY_inv(&w,&t); - printf("1/(1/w) mod p^4 = "); - FP12_YYY_output(&w); - printf("\n"); - - - - FP12_YYY_inv(&lv,&w); -//printf("w= "); FP12_YYY_output(&w); printf("\n"); - FP12_YYY_conj(&w,&w); -//printf("w= "); FP12_YYY_output(&w); printf("\n"); -//exit(0); - FP12_YYY_mul(&w,&w,&lv); -//printf("w= "); FP12_YYY_output(&w); printf("\n"); - FP12_YYY_copy(&lv,&w); - FP12_YYY_frob(&w,&f); - FP12_YYY_frob(&w,&f); - FP12_YYY_mul(&w,&w,&lv); - -//printf("w= "); FP12_YYY_output(&w); printf("\n"); -//exit(0); - -w.unitary=0; -FP12_YYY_conj(&lv,&w); - printf("rx= "); FP12_YYY_output(&lv); printf("\n"); -FP12_YYY_inv(&lv,&w); - printf("ry= "); FP12_YYY_output(&lv); printf("\n"); - - - return 0; -} - -*/
