http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/java/DBIG64.java ---------------------------------------------------------------------- diff --git a/version22/java/DBIG64.java b/version22/java/DBIG64.java deleted file mode 100644 index 4596077..0000000 --- a/version22/java/DBIG64.java +++ /dev/null @@ -1,306 +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 double length DBIG number class */ - -public class DBIG { - protected long[] w=new long[ROM.DNLEN]; - -/* normalise this */ - public void norm() { - long d,carry=0; - for (int i=0;i<ROM.DNLEN-1;i++) - { - d=w[i]+carry; - carry=d>>ROM.BASEBITS; - w[i]=d&ROM.BMASK; - } - w[ROM.DNLEN-1]=(w[ROM.DNLEN-1]+carry); - } - - -/* - public String toRawString() - { - DBIG b=new DBIG(this); - String s="("; - for (int i=0;i<ROM.DNLEN-1;i++) - { - s+=Long.toHexString(b.w[i]); s+=","; - } - s+=Long.toHexString(b.w[ROM.DNLEN-1]); s+=")"; - return s; - } -*/ - -/****************************************************************************/ - -/* return number of bits in this */ - public int nbits() { - int bts,k=ROM.DNLEN-1; - long c; - norm(); - while (w[k]==0 && k>=0) k--; - if (k<0) return 0; - bts=ROM.BASEBITS*k; - c=w[k]; - while (c!=0) {c/=2; bts++;} - return bts; - } - -/* convert this to string */ - public String toString() { - DBIG b; - String s=""; - int len=nbits(); - if (len%4==0) len>>=2; //len/=4; - else {len>>=2; len++;} - - for (int i=len-1;i>=0;i--) - { - b=new DBIG(this); - b.shr(i*4); - s+=Integer.toHexString((int)(b.w[0]&15)); - } - return s; - } - - public void cmove(DBIG g,int d) - { - int i; - //long b=-d; - - for (i=0;i<ROM.DNLEN;i++) - { - w[i]^=(w[i]^g.w[i])&BIG.cast_to_chunk(-d); - } - } - -/* Constructors */ - public DBIG(int x) - { - w[0]=x; - for (int i=1;i<ROM.DNLEN;i++) - w[i]=0; - } - - public DBIG(DBIG x) - { - for (int i=0;i<ROM.DNLEN;i++) - w[i]=x.w[i]; - } - - public DBIG(BIG x) - { - for (int i=0;i<ROM.NLEN-1;i++) - w[i]=x.w[i]; //get(i); - - w[ROM.NLEN-1]=x.w[(ROM.NLEN-1)]&ROM.BMASK; /* top word normalized */ - w[ROM.NLEN]=(x.w[(ROM.NLEN-1)]>>ROM.BASEBITS); - - for (int i=ROM.NLEN+1;i<ROM.DNLEN;i++) w[i]=0; - } - -/* split DBIG at position n, return higher half, keep lower half */ - public BIG split(int n) - { - BIG t=new BIG(0); - int m=n%ROM.BASEBITS; - long nw,carry=w[ROM.DNLEN-1]<<(ROM.BASEBITS-m); - - for (int i=ROM.DNLEN-2;i>=ROM.NLEN-1;i--) - { - nw=(w[i]>>m)|carry; - carry=(w[i]<<(ROM.BASEBITS-m))&ROM.BMASK; - t.w[i-ROM.NLEN+1]=nw; - //t.set(i-ROM.NLEN+1,nw); - } - w[ROM.NLEN-1]&=(((long)1<<m)-1); - return t; - } - -/* Copy from another DBIG */ - public void copy(DBIG x) - { - for (int i=0;i<ROM.DNLEN;i++) - w[i]=x.w[i]; - } - -/* test this=0? */ - public boolean iszilch() { - for (int i=0;i<ROM.DNLEN;i++) - if (w[i]!=0) return false; - return true; - } - -/* shift this right by k bits */ - public void shr(int k) { - int n=k%ROM.BASEBITS; - int m=k/ROM.BASEBITS; - for (int i=0;i<ROM.DNLEN-m-1;i++) - w[i]=(w[m+i]>>n)|((w[m+i+1]<<(ROM.BASEBITS-n))&ROM.BMASK); - w[ROM.DNLEN-m-1]=w[ROM.DNLEN-1]>>n; - for (int i=ROM.DNLEN-m;i<ROM.DNLEN;i++) w[i]=0; - } - -/* shift this left by k bits */ - public void shl(int k) { - int n=k%ROM.BASEBITS; - int m=k/ROM.BASEBITS; - - w[ROM.DNLEN-1]=((w[ROM.DNLEN-1-m]<<n))|(w[ROM.DNLEN-m-2]>>(ROM.BASEBITS-n)); - for (int i=ROM.DNLEN-2;i>m;i--) - w[i]=((w[i-m]<<n)&ROM.BMASK)|(w[i-m-1]>>(ROM.BASEBITS-n)); - w[m]=(w[0]<<n)&ROM.BMASK; - for (int i=0;i<m;i++) w[i]=0; - } - -/* this+=x */ - public void add(DBIG x) { - for (int i=0;i<ROM.DNLEN;i++) - w[i]+=x.w[i]; - } - -/* this-=x */ - public void sub(DBIG x) { - for (int i=0;i<ROM.DNLEN;i++) - w[i]-=x.w[i]; - } - -/* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */ - public static int comp(DBIG a,DBIG b) - { - for (int i=ROM.DNLEN-1;i>=0;i--) - { - if (a.w[i]==b.w[i]) continue; - if (a.w[i]>b.w[i]) return 1; - else return -1; - } - return 0; - } - -/* reduces this DBIG mod a BIG, and returns the BIG */ - public BIG mod(BIG c) - { - int k=0; - norm(); - DBIG m=new DBIG(c); - DBIG r=new DBIG(0); - - if (comp(this,m)<0) return new BIG(this); - - do - { - m.shl(1); - k++; - } - while (comp(this,m)>=0); - - while (k>0) - { - m.shr(1); - - r.copy(this); - r.sub(m); - r.norm(); - cmove(r,(int)(1-((r.w[ROM.DNLEN-1]>>(ROM.CHUNK-1))&1))); -/* - if (comp(this,m)>=0) - { - sub(m); - norm(); - } -*/ - k--; - } - return new BIG(this); - } - -/* reduces this DBIG mod a DBIG in place */ -/* public void mod(DBIG m) - { - int k=0; - if (comp(this,m)<0) return; - - do - { - m.shl(1); - k++; - } - while (comp(this,m)>=0); - - while (k>0) - { - m.shr(1); - if (comp(this,m)>=0) - { - sub(m); - norm(); - } - k--; - } - return; - - }*/ - -/* return this/c */ - public BIG div(BIG c) - { - int d,k=0; - DBIG m=new DBIG(c); - DBIG dr=new DBIG(0); - BIG r=new BIG(0); - BIG a=new BIG(0); - BIG e=new BIG(1); - norm(); - - while (comp(this,m)>=0) - { - e.fshl(1); - m.shl(1); - k++; - } - - while (k>0) - { - m.shr(1); - e.shr(1); - - dr.copy(this); - dr.sub(m); - dr.norm(); - d=(int)(1-((dr.w[ROM.DNLEN-1]>>(ROM.CHUNK-1))&1)); - cmove(dr,d); - r.copy(a); - r.add(e); - r.norm(); - a.cmove(r,d); -/* - if (comp(this,m)>0) - { - a.add(e); - a.norm(); - sub(m); - norm(); - } */ - k--; - } - return a; - } -}
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/java/ECDH.java ---------------------------------------------------------------------- diff --git a/version22/java/ECDH.java b/version22/java/ECDH.java deleted file mode 100644 index 12b7589..0000000 --- a/version22/java/ECDH.java +++ /dev/null @@ -1,581 +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. -*/ - -/* Elliptic Curve API high-level functions */ - -public final class ECDH { - public static final int INVALID_PUBLIC_KEY=-2; - public static final int ERROR=-3; - public static final int INVALID=-4; - public static final int EFS=ROM.MODBYTES; - public static final int EGS=ROM.MODBYTES; - public static final int EAS=16; - public static final int EBS=16; - public static final int SHA256=32; - public static final int SHA384=48; - public static final int SHA512=64; - - public static final int HASH_TYPE=SHA512; - -/* Convert Integer to n-byte array */ - private static byte[] inttoBytes(int n,int len) - { - int i; - byte[] b=new byte[len]; - - for (i=0;i<len;i++) b[i]=0; - i=len; - while (n>0 && i>0) - { - i--; - b[i]=(byte)(n&0xff); - n/=256; - } - return b; - } - - private static byte[] hashit(int sha,byte[] A,int n,byte[] B,int pad) - { - byte[] R=null; - - if (sha==SHA256) - { - HASH256 H=new HASH256(); - H.process_array(A); if (n>0) H.process_num(n); - if (B!=null) H.process_array(B); - R=H.hash(); - } - if (sha==SHA384) - { - HASH384 H=new HASH384(); - H.process_array(A); if (n>0) H.process_num(n); - if (B!=null) H.process_array(B); - R=H.hash(); - } - if (sha==SHA512) - { - HASH512 H=new HASH512(); - H.process_array(A); if (n>0) H.process_num(n); - if (B!=null) H.process_array(B); - R=H.hash(); - } - if (R==null) return null; - - if (pad==0) return R; -/* If pad>0 output is truncated or padded to pad bytes */ - byte[] W=new byte[pad]; - if (pad<=sha) - { - for (int i=0;i<pad;i++) W[i]=R[i]; - } - else - { - for (int i=0;i<sha;i++) W[i]=R[i]; - for (int i=sha;i<pad;i++) W[i]=0; - } - return W; - } - -/* Key Derivation Functions */ -/* Input octet Z */ -/* Output key of length olen */ - public static byte[] KDF1(int sha,byte[] Z,int olen) - { -/* NOTE: the parameter olen is the length of the output K in bytes */ - int hlen=sha; - byte[] K=new byte[olen]; - byte[] B; - int counter,cthreshold,k=0; - - for (int i=0;i<K.length;i++) K[i]=0; - - cthreshold=olen/hlen; if (olen%hlen!=0) cthreshold++; - - for (counter=0;counter<cthreshold;counter++) - { - B=hashit(sha,Z,counter,null,0); - if (k+hlen>olen) for (int i=0;i<olen%hlen;i++) K[k++]=B[i]; - else for (int i=0;i<hlen;i++) K[k++]=B[i]; - } - return K; - } - - public static byte[] KDF2(int sha,byte[] Z,byte[] P,int olen) - { -/* NOTE: the parameter olen is the length of the output k in bytes */ - int hlen=sha; - byte[] K=new byte[olen]; - byte[] B; - int counter,cthreshold,k=0; - - for (int i=0;i<K.length;i++) K[i]=0; - - cthreshold=olen/hlen; if (olen%hlen!=0) cthreshold++; - - for (counter=1;counter<=cthreshold;counter++) - { - B=hashit(sha,Z,counter,P,0); - if (k+hlen>olen) for (int i=0;i<olen%hlen;i++) K[k++]=B[i]; - else for (int i=0;i<hlen;i++) K[k++]=B[i]; - } - - return K; - } - -/* Password based Key Derivation Function */ -/* Input password p, salt s, and repeat count */ -/* Output key of length olen */ - public static byte[] PBKDF2(int sha,byte[] Pass,byte[] Salt,int rep,int olen) - { - int i,j,k,len,d,opt; - d=olen/sha; if (olen%sha!=0) d++; - byte[] F=new byte[sha]; - byte[] U=new byte[sha]; - byte[] S=new byte[Salt.length+4]; - - byte[] K=new byte[d*sha]; - opt=0; - - for (i=1;i<=d;i++) - { - for (j=0;j<Salt.length;j++) S[j]=Salt[j]; - byte[] N=inttoBytes(i,4); - for (j=0;j<4;j++) S[Salt.length+j]=N[j]; - - HMAC(sha,S,Pass,F); - - for (j=0;j<sha;j++) U[j]=F[j]; - for (j=2;j<=rep;j++) - { - HMAC(sha,U,Pass,U); - for (k=0;k<sha;k++) F[k]^=U[k]; - } - for (j=0;j<sha;j++) K[opt++]=F[j]; - } - byte[] key=new byte[olen]; - for (i=0;i<olen;i++) key[i]=K[i]; - return key; - } - -/* Calculate HMAC of m using key k. HMAC is tag of length olen */ - public static int HMAC(int sha,byte[] M,byte[] K,byte[] tag) - { - /* Input is from an octet m * - * olen is requested output length in bytes. k is the key * - * The output is the calculated tag */ - int b=64; - if (sha>32) b=128; - byte[] B; - byte[] K0=new byte[b]; - int olen=tag.length; - - //b=K0.length; - if (olen<4 /*|| olen>sha*/) return 0; - - for (int i=0;i<b;i++) K0[i]=0; - - if (K.length > b) - { - B=hashit(sha,K,0,null,0); - for (int i=0;i<sha;i++) K0[i]=B[i]; - } - else - for (int i=0;i<K.length;i++ ) K0[i]=K[i]; - - for (int i=0;i<b;i++) K0[i]^=0x36; - B=hashit(sha,K0,0,M,0); - - for (int i=0;i<b;i++) K0[i]^=0x6a; - B=hashit(sha,K0,0,B,olen); - - for (int i=0;i<olen;i++) tag[i]=B[i]; - - return 1; - } - -/* AES encryption/decryption. Encrypt byte array M using key K and returns ciphertext */ - public static byte[] AES_CBC_IV0_ENCRYPT(byte[] K,byte[] M) - { /* AES CBC encryption, with Null IV and key K */ - /* Input is from an octet string M, output is to an octet string C */ - /* Input is padded as necessary to make up a full final block */ - AES a=new AES(); - boolean fin; - int i,j,ipt,opt; - byte[] buff=new byte[16]; - int clen=16+(M.length/16)*16; - - byte[] C=new byte[clen]; - int padlen; - - a.init(AES.CBC,K.length,K,null); - - ipt=opt=0; - fin=false; - for(;;) - { - for (i=0;i<16;i++) - { - if (ipt<M.length) buff[i]=M[ipt++]; - else {fin=true; break;} - } - if (fin) break; - a.encrypt(buff); - for (i=0;i<16;i++) - C[opt++]=buff[i]; - } - -/* last block, filled up to i-th index */ - - padlen=16-i; - for (j=i;j<16;j++) buff[j]=(byte)padlen; - - a.encrypt(buff); - - for (i=0;i<16;i++) - C[opt++]=buff[i]; - a.end(); - return C; - } - -/* returns plaintext if all consistent, else returns null string */ - public static byte[] AES_CBC_IV0_DECRYPT(byte[] K,byte[] C) - { /* padding is removed */ - AES a=new AES(); - int i,ipt,opt,ch; - byte[] buff=new byte[16]; - byte[] MM=new byte[C.length]; - boolean fin,bad; - int padlen; - ipt=opt=0; - - a.init(AES.CBC,K.length,K,null); - - if (C.length==0) return new byte[0]; - ch=C[ipt++]; - - fin=false; - - for(;;) - { - for (i=0;i<16;i++) - { - buff[i]=(byte)ch; - if (ipt>=C.length) {fin=true; break;} - else ch=C[ipt++]; - } - a.decrypt(buff); - if (fin) break; - for (i=0;i<16;i++) - MM[opt++]=buff[i]; - } - - a.end(); - bad=false; - padlen=buff[15]; - if (i!=15 || padlen<1 || padlen>16) bad=true; - if (padlen>=2 && padlen<=16) - for (i=16-padlen;i<16;i++) if (buff[i]!=padlen) bad=true; - - if (!bad) for (i=0;i<16-padlen;i++) - MM[opt++]=buff[i]; - - if (bad) return new byte[0]; - - byte[] M=new byte[opt]; - for (i=0;i<opt;i++) M[i]=MM[i]; - - return M; - } - -/* Calculate a public/private EC GF(p) key pair W,S where W=S.G mod EC(p), - * where S is the secret key and W is the public key - * and G is fixed generator. - * If RNG is NULL then the private key is provided externally in S - * otherwise it is generated randomly internally */ - public static int KEY_PAIR_GENERATE(RAND RNG,byte[] S,byte[] W) - { - BIG r,gx,gy,s,wx,wy; - ECP G,WP; - int res=0; - // byte[] T=new byte[EFS]; - - gx=new BIG(ROM.CURVE_Gx); - - if (ROM.CURVETYPE!=ROM.MONTGOMERY) - { - gy=new BIG(ROM.CURVE_Gy); - G=new ECP(gx,gy); - } - else - G=new ECP(gx); - - r=new BIG(ROM.CURVE_Order); - - if (RNG==null) - { - s=BIG.fromBytes(S); - s.mod(r); - } - else - { - s=BIG.randomnum(r,RNG); - } - - if (ROM.AES_S>0) - { - s.mod2m(2*ROM.AES_S); - } - s.toBytes(S); - - WP=G.mul(s); - WP.toBytes(W); - - return res; - } - -/* validate public key. Set full=true for fuller check */ - public static int PUBLIC_KEY_VALIDATE(boolean full,byte[] W) - { - BIG r; - ECP WP=ECP.fromBytes(W); - int res=0; - - r=new BIG(ROM.CURVE_Order); - - if (WP.is_infinity()) res=INVALID_PUBLIC_KEY; - - if (res==0 && full) - { - WP=WP.mul(r); - if (!WP.is_infinity()) res=INVALID_PUBLIC_KEY; - } - return res; - } - -/* IEEE-1363 Diffie-Hellman online calculation Z=S.WD */ - public static int ECPSVDP_DH(byte[] S,byte[] WD,byte[] Z) - { - BIG r,s,wx,wy,z; - int valid; - ECP W; - int res=0; - byte[] T=new byte[EFS]; - - s=BIG.fromBytes(S); - - W=ECP.fromBytes(WD); - if (W.is_infinity()) res=ERROR; - - if (res==0) - { - r=new BIG(ROM.CURVE_Order); - s.mod(r); - - W=W.mul(s); - if (W.is_infinity()) res=ERROR; - else - { - W.getX().toBytes(T); - for (int i=0;i<EFS;i++) Z[i]=T[i]; - } - } - return res; - } - -/* IEEE ECDSA Signature, C and D are signature on F using private key S */ - public static int ECPSP_DSA(int sha,RAND RNG,byte[] S,byte[] F,byte[] C,byte[] D) - { - byte[] T=new byte[EFS]; - BIG gx,gy,r,s,f,c,d,u,vx,w; - ECP G,V; - byte[] B=hashit(sha,F,0,null,ROM.MODBYTES); - - gx=new BIG(ROM.CURVE_Gx); - gy=new BIG(ROM.CURVE_Gy); - - G=new ECP(gx,gy); - r=new BIG(ROM.CURVE_Order); - - s=BIG.fromBytes(S); - f=BIG.fromBytes(B); - - c=new BIG(0); - d=new BIG(0); - V=new ECP(); - - do { - u=BIG.randomnum(r,RNG); - w=BIG.randomnum(r,RNG); - if (ROM.AES_S>0) - { - u.mod2m(2*ROM.AES_S); - } - V.copy(G); - V=V.mul(u); - vx=V.getX(); - c.copy(vx); - c.mod(r); - if (c.iszilch()) continue; - - u.copy(BIG.modmul(u,w,r)); - - u.invmodp(r); - d.copy(BIG.modmul(s,c,r)); - d.add(f); - - d.copy(BIG.modmul(d,w,r)); - - d.copy(BIG.modmul(u,d,r)); - } while (d.iszilch()); - - c.toBytes(T); - for (int i=0;i<EFS;i++) C[i]=T[i]; - d.toBytes(T); - for (int i=0;i<EFS;i++) D[i]=T[i]; - return 0; - } - -/* IEEE1363 ECDSA Signature Verification. Signature C and D on F is verified using public key W */ - public static int ECPVP_DSA(int sha,byte[] W,byte[] F, byte[] C,byte[] D) - { - BIG r,gx,gy,f,c,d,h2; - int res=0; - ECP G,WP,P; - int valid; - - byte[] B=hashit(sha,F,0,null,ROM.MODBYTES); - - gx=new BIG(ROM.CURVE_Gx); - gy=new BIG(ROM.CURVE_Gy); - - G=new ECP(gx,gy); - r=new BIG(ROM.CURVE_Order); - - c=BIG.fromBytes(C); - d=BIG.fromBytes(D); - f=BIG.fromBytes(B); - - if (c.iszilch() || BIG.comp(c,r)>=0 || d.iszilch() || BIG.comp(d,r)>=0) - res=INVALID; - - if (res==0) - { - d.invmodp(r); - f.copy(BIG.modmul(f,d,r)); - h2=BIG.modmul(c,d,r); - - WP=ECP.fromBytes(W); - if (WP.is_infinity()) res=ERROR; - else - { - P=new ECP(); - P.copy(WP); - P=P.mul2(h2,G,f); - if (P.is_infinity()) res=INVALID; - else - { - d=P.getX(); - d.mod(r); - if (BIG.comp(d,c)!=0) res=INVALID; - } - } - } - - return res; - } - -/* IEEE1363 ECIES encryption. Encryption of plaintext M uses public key W and produces ciphertext V,C,T */ - public static byte[] ECIES_ENCRYPT(int sha,byte[] P1,byte[] P2,RAND RNG,byte[] W,byte[] M,byte[] V,byte[] T) - { - int i,len; - - byte[] Z=new byte[EFS]; - byte[] VZ=new byte[3*EFS+1]; - byte[] K1=new byte[EAS]; - byte[] K2=new byte[EAS]; - byte[] U=new byte[EGS]; - - if (KEY_PAIR_GENERATE(RNG,U,V)!=0) return new byte[0]; - if (ECPSVDP_DH(U,W,Z)!=0) return new byte[0]; - - for (i=0;i<2*EFS+1;i++) VZ[i]=V[i]; - for (i=0;i<EFS;i++) VZ[2*EFS+1+i]=Z[i]; - - - byte[] K=KDF2(sha,VZ,P1,EFS); - - for (i=0;i<EAS;i++) {K1[i]=K[i]; K2[i]=K[EAS+i];} - - byte[] C=AES_CBC_IV0_ENCRYPT(K1,M); - - byte[] L2=inttoBytes(P2.length,8); - - byte[] AC=new byte[C.length+P2.length+8]; - for (i=0;i<C.length;i++) AC[i]=C[i]; - for (i=0;i<P2.length;i++) AC[C.length+i]=P2[i]; - for (i=0;i<8;i++) AC[C.length+P2.length+i]=L2[i]; - - HMAC(sha,AC,K2,T); - - return C; - } - -/* IEEE1363 ECIES decryption. Decryption of ciphertext V,C,T using private key U outputs plaintext M */ - public static byte[] ECIES_DECRYPT(int sha,byte[] P1,byte[] P2,byte[] V,byte[] C,byte[] T,byte[] U) - { - - int i,len; - - byte[] Z=new byte[EFS]; - byte[] VZ=new byte[3*EFS+1]; - byte[] K1=new byte[EAS]; - byte[] K2=new byte[EAS]; - byte[] TAG=new byte[T.length]; - - if (ECPSVDP_DH(U,V,Z)!=0) return new byte[0]; - - for (i=0;i<2*EFS+1;i++) VZ[i]=V[i]; - for (i=0;i<EFS;i++) VZ[2*EFS+1+i]=Z[i]; - - byte[] K=KDF2(sha,VZ,P1,EFS); - - for (i=0;i<EAS;i++) {K1[i]=K[i]; K2[i]=K[EAS+i];} - - byte[] M=AES_CBC_IV0_DECRYPT(K1,C); - - if (M.length==0) return M; - - byte[] L2=inttoBytes(P2.length,8); - - byte[] AC=new byte[C.length+P2.length+8]; - - for (i=0;i<C.length;i++) AC[i]=C[i]; - for (i=0;i<P2.length;i++) AC[C.length+i]=P2[i]; - for (i=0;i<8;i++) AC[C.length+P2.length+i]=L2[i]; - - HMAC(sha,AC,K2,TAG); - - boolean same=true; - for (i=0;i<T.length;i++) if (T[i]!=TAG[i]) same=false; - if (!same) return new byte[0]; - - return M; - - } -} http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/java/ECP.java ---------------------------------------------------------------------- diff --git a/version22/java/ECP.java b/version22/java/ECP.java deleted file mode 100644 index d315e45..0000000 --- a/version22/java/ECP.java +++ /dev/null @@ -1,917 +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. -*/ - -/* Elliptic Curve Point class */ - -public final class ECP { - private FP x; - private FP y; - private FP z; - private boolean INF; - -/* Constructor - set to O */ - public ECP() { - INF=true; - x=new FP(0); - y=new FP(1); - z=new FP(1); - } -/* test for O point-at-infinity */ - public boolean is_infinity() { - if (ROM.CURVETYPE==ROM.EDWARDS) - { - x.reduce(); y.reduce(); z.reduce(); - return (x.iszilch() && y.equals(z)); - } - else return INF; - } -/* Conditional swap of P and Q dependant on d */ - private void cswap(ECP Q,int d) - { - x.cswap(Q.x,d); - if (ROM.CURVETYPE!=ROM.MONTGOMERY) y.cswap(Q.y,d); - z.cswap(Q.z,d); - if (ROM.CURVETYPE!=ROM.EDWARDS) - { - boolean bd; - if (d==0) bd=false; - else bd=true; - bd=bd&(INF^Q.INF); - INF^=bd; - Q.INF^=bd; - } - } - -/* Conditional move of Q to P dependant on d */ - private void cmove(ECP Q,int d) - { - x.cmove(Q.x,d); - if (ROM.CURVETYPE!=ROM.MONTGOMERY) y.cmove(Q.y,d); - z.cmove(Q.z,d); - if (ROM.CURVETYPE!=ROM.EDWARDS) - { - boolean bd; - if (d==0) bd=false; - else bd=true; - INF^=(INF^Q.INF)&bd; - } - } - -/* return 1 if b==c, no branching */ - private static int teq(int b,int c) - { - int x=b^c; - x-=1; // if x=0, x now -1 - return ((x>>31)&1); - } - -/* Constant time select from pre-computed table */ - private void select(ECP W[],int b) - { - ECP MP=new ECP(); - int m=b>>31; - int babs=(b^m)-m; - - babs=(babs-1)/2; - - cmove(W[0],teq(babs,0)); // conditional move - cmove(W[1],teq(babs,1)); - cmove(W[2],teq(babs,2)); - cmove(W[3],teq(babs,3)); - cmove(W[4],teq(babs,4)); - cmove(W[5],teq(babs,5)); - cmove(W[6],teq(babs,6)); - cmove(W[7],teq(babs,7)); - - MP.copy(this); - MP.neg(); - cmove(MP,(int)(m&1)); - } - -/* Test P == Q */ - public boolean equals(ECP Q) { - if (is_infinity() && Q.is_infinity()) return true; - if (is_infinity() || Q.is_infinity()) return false; - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - { - FP zs2=new FP(z); zs2.sqr(); - FP zo2=new FP(Q.z); zo2.sqr(); - FP zs3=new FP(zs2); zs3.mul(z); - FP zo3=new FP(zo2); zo3.mul(Q.z); - zs2.mul(Q.x); - zo2.mul(x); - if (!zs2.equals(zo2)) return false; - zs3.mul(Q.y); - zo3.mul(y); - if (!zs3.equals(zo3)) return false; - } - else - { - FP a=new FP(0); - FP b=new FP(0); - a.copy(x); a.mul(Q.z); a.reduce(); - b.copy(Q.x); b.mul(z); b.reduce(); - if (!a.equals(b)) return false; - if (ROM.CURVETYPE==ROM.EDWARDS) - { - a.copy(y); a.mul(Q.z); a.reduce(); - b.copy(Q.y); b.mul(z); b.reduce(); - if (!a.equals(b)) return false; - } - } - return true; - } - -/* this=P */ - public void copy(ECP P) - { - x.copy(P.x); - if (ROM.CURVETYPE!=ROM.MONTGOMERY) y.copy(P.y); - z.copy(P.z); - INF=P.INF; - } -/* this=-this */ - public void neg() { - if (is_infinity()) return; - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - { - y.neg(); y.norm(); - } - if (ROM.CURVETYPE==ROM.EDWARDS) - { - x.neg(); x.norm(); - } - return; - } -/* set this=O */ - public void inf() { - INF=true; - x.zero(); - y.one(); - z.one(); - // y=new FP(1); - // z=new FP(1); - } - -/* Calculate RHS of curve equation */ - public static FP RHS(FP x) { - x.norm(); - FP r=new FP(x); - r.sqr(); - - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - { // x^3+Ax+B - FP b=new FP(new BIG(ROM.CURVE_B)); - r.mul(x); - if (ROM.CURVE_A==-3) - { - FP cx=new FP(x); - cx.imul(3); - cx.neg(); cx.norm(); - r.add(cx); - } - r.add(b); - } - if (ROM.CURVETYPE==ROM.EDWARDS) - { // (Ax^2-1)/(Bx^2-1) - FP b=new FP(new BIG(ROM.CURVE_B)); - - FP one=new FP(1); - b.mul(r); - b.sub(one); - if (ROM.CURVE_A==-1) r.neg(); - r.sub(one); - - b.inverse(); - - r.mul(b); - } - if (ROM.CURVETYPE==ROM.MONTGOMERY) - { // x^3+Ax^2+x - FP x3=new FP(0); - x3.copy(r); - x3.mul(x); - r.imul(ROM.CURVE_A); - r.add(x3); - r.add(x); - } - r.reduce(); - return r; - } - -/* set (x,y) from two BIGs */ - public ECP(BIG ix,BIG iy) { - x=new FP(ix); - y=new FP(iy); - z=new FP(1); - FP rhs=RHS(x); - - if (ROM.CURVETYPE==ROM.MONTGOMERY) - { - if (rhs.jacobi()==1) INF=false; - else inf(); - } - else - { - FP y2=new FP(y); - y2.sqr(); - if (y2.equals(rhs)) INF=false; - else inf(); - } - } -/* set (x,y) from BIG and a bit */ - public ECP(BIG ix,int s) { - x=new FP(ix); - FP rhs=RHS(x); - y=new FP(0); - z=new FP(1); - if (rhs.jacobi()==1) - { - FP ny=rhs.sqrt(); - if (ny.redc().parity()!=s) ny.neg(); - y.copy(ny); - INF=false; - } - else inf(); - } - -/* set from x - calculate y from curve equation */ - public ECP(BIG ix) { - x=new FP(ix); - FP rhs=RHS(x); - y=new FP(0); - z=new FP(1); - if (rhs.jacobi()==1) - { - if (ROM.CURVETYPE!=ROM.MONTGOMERY) y.copy(rhs.sqrt()); - INF=false; - } - else INF=true; - } - -/* set to affine - from (x,y,z) to (x,y) */ - public void affine() { - if (is_infinity()) return; - FP one=new FP(1); - if (z.equals(one)) return; - z.inverse(); - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - { - FP z2=new FP(z); - z2.sqr(); - x.mul(z2); x.reduce(); - y.mul(z2); - y.mul(z); y.reduce(); - } - if (ROM.CURVETYPE==ROM.EDWARDS) - { - x.mul(z); x.reduce(); - y.mul(z); y.reduce(); - } - if (ROM.CURVETYPE==ROM.MONTGOMERY) - { - x.mul(z); x.reduce(); - } - z.copy(one); - } -/* extract x as a BIG */ - public BIG getX() - { - affine(); - return x.redc(); - } -/* extract y as a BIG */ - public BIG getY() - { - affine(); - return y.redc(); - } - -/* get sign of Y */ - public int getS() - { - affine(); - BIG y=getY(); - return y.parity(); - } -/* extract x as an FP */ - public FP getx() - { - return x; - } -/* extract y as an FP */ - public FP gety() - { - return y; - } -/* extract z as an FP */ - public FP getz() - { - return z; - } -/* convert to byte array */ - public void toBytes(byte[] b) - { - byte[] t=new byte[ROM.MODBYTES]; - if (ROM.CURVETYPE!=ROM.MONTGOMERY) b[0]=0x04; - else b[0]=0x02; - - affine(); - x.redc().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) b[i+1]=t[i]; - if (ROM.CURVETYPE!=ROM.MONTGOMERY) - { - y.redc().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) b[i+ROM.MODBYTES+1]=t[i]; - } - } -/* convert from byte array to point */ - public static ECP fromBytes(byte[] b) - { - byte[] t=new byte[ROM.MODBYTES]; - BIG p=new BIG(ROM.Modulus); - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=b[i+1]; - BIG px=BIG.fromBytes(t); - if (BIG.comp(px,p)>=0) return new ECP(); - - if (b[0]==0x04) - { - for (int i=0;i<ROM.MODBYTES;i++) t[i]=b[i+ROM.MODBYTES+1]; - BIG py=BIG.fromBytes(t); - if (BIG.comp(py,p)>=0) return new ECP(); - return new ECP(px,py); - } - else return new ECP(px); - } -/* convert to hex string */ - public String toString() { - if (is_infinity()) return "infinity"; - affine(); - if (ROM.CURVETYPE==ROM.MONTGOMERY) return "("+x.redc().toString()+")"; - else return "("+x.redc().toString()+","+y.redc().toString()+")"; - } -/* this*=2 */ - public void dbl() { - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - { - if (INF) return; - if (y.iszilch()) - { - inf(); - return; - } - - FP w1=new FP(x); - FP w6=new FP(z); - FP w2=new FP(0); - FP w3=new FP(x); - FP w8=new FP(x); - - if (ROM.CURVE_A==-3) - { - w6.sqr(); - w1.copy(w6); - w1.neg(); - w3.add(w1); - w8.add(w6); - w3.mul(w8); - w8.copy(w3); - w8.imul(3); - } - else - { - w1.sqr(); - w8.copy(w1); - w8.imul(3); - } - - w2.copy(y); w2.sqr(); - w3.copy(x); w3.mul(w2); - w3.imul(4); - w1.copy(w3); w1.neg(); - w1.norm(); - - x.copy(w8); x.sqr(); - x.add(w1); - x.add(w1); - x.norm(); - - z.mul(y); - z.add(z); - - w2.add(w2); - w2.sqr(); - w2.add(w2); - w3.sub(x); - y.copy(w8); y.mul(w3); - y.sub(w2); - y.norm(); - z.norm(); - } - if (ROM.CURVETYPE==ROM.EDWARDS) - { - FP C=new FP(x); - FP D=new FP(y); - FP H=new FP(z); - FP J=new FP(0); - - x.mul(y); x.add(x); - C.sqr(); - D.sqr(); - if (ROM.CURVE_A==-1) C.neg(); - y.copy(C); y.add(D); - y.norm(); - H.sqr(); H.add(H); - z.copy(y); - J.copy(y); J.sub(H); - x.mul(J); - C.sub(D); - y.mul(C); - z.mul(J); - - x.norm(); - y.norm(); - z.norm(); - } - if (ROM.CURVETYPE==ROM.MONTGOMERY) - { - FP A=new FP(x); - FP B=new FP(x); - FP AA=new FP(0); - FP BB=new FP(0); - FP C=new FP(0); - - if (INF) return; - - A.add(z); - AA.copy(A); AA.sqr(); - B.sub(z); - BB.copy(B); BB.sqr(); - C.copy(AA); C.sub(BB); - - x.copy(AA); x.mul(BB); - - A.copy(C); A.imul((ROM.CURVE_A+2)/4); - - BB.add(A); - z.copy(BB); z.mul(C); - x.norm(); - z.norm(); - } - return; - } - -/* this+=Q */ - public void add(ECP Q) { - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - { - if (INF) - { - copy(Q); - return; - } - if (Q.INF) return; - - boolean aff=false; - - FP one=new FP(1); - if (Q.z.equals(one)) aff=true; - - FP A,C; - FP B=new FP(z); - FP D=new FP(z); - if (!aff) - { - A=new FP(Q.z); - C=new FP(Q.z); - - A.sqr(); B.sqr(); - C.mul(A); D.mul(B); - - A.mul(x); - C.mul(y); - } - else - { - A=new FP(x); - C=new FP(y); - - B.sqr(); - D.mul(B); - } - - B.mul(Q.x); B.sub(A); - D.mul(Q.y); D.sub(C); - - if (B.iszilch()) - { - if (D.iszilch()) - { - dbl(); - return; - } - else - { - INF=true; - return; - } - } - - if (!aff) z.mul(Q.z); - z.mul(B); - - FP e=new FP(B); e.sqr(); - B.mul(e); - A.mul(e); - - e.copy(A); - e.add(A); e.add(B); - x.copy(D); x.sqr(); x.sub(e); - - A.sub(x); - y.copy(A); y.mul(D); - C.mul(B); y.sub(C); - - x.norm(); - y.norm(); - z.norm(); - } - if (ROM.CURVETYPE==ROM.EDWARDS) - { - FP b=new FP(new BIG(ROM.CURVE_B)); - FP A=new FP(z); - FP B=new FP(0); - FP C=new FP(x); - FP D=new FP(y); - FP E=new FP(0); - FP F=new FP(0); - FP G=new FP(0); - // FP H=new FP(0); - // FP I=new FP(0); - - A.mul(Q.z); - B.copy(A); B.sqr(); - C.mul(Q.x); - D.mul(Q.y); - - E.copy(C); E.mul(D); E.mul(b); - F.copy(B); F.sub(E); - G.copy(B); G.add(E); - - if (ROM.CURVE_A==1) - { - E.copy(D); E.sub(C); - } - C.add(D); - - B.copy(x); B.add(y); - D.copy(Q.x); D.add(Q.y); - B.mul(D); - B.sub(C); - B.mul(F); - x.copy(A); x.mul(B); - - if (ROM.CURVE_A==1) - { - C.copy(E); C.mul(G); - } - if (ROM.CURVE_A==-1) - { - C.mul(G); - } - y.copy(A); y.mul(C); - z.copy(F); z.mul(G); - x.norm(); y.norm(); z.norm(); - } - return; - } - -/* Differential Add for Montgomery curves. this+=Q where W is this-Q and is affine. */ - public void dadd(ECP Q,ECP W) { - FP A=new FP(x); - FP B=new FP(x); - FP C=new FP(Q.x); - FP D=new FP(Q.x); - FP DA=new FP(0); - FP CB=new FP(0); - - A.add(z); - B.sub(z); - - C.add(Q.z); - D.sub(Q.z); - - DA.copy(D); DA.mul(A); - CB.copy(C); CB.mul(B); - - A.copy(DA); A.add(CB); A.sqr(); - B.copy(DA); B.sub(CB); B.sqr(); - - x.copy(A); - z.copy(W.x); z.mul(B); - - if (z.iszilch()) inf(); - else INF=false; - - x.norm(); - } -/* this-=Q */ - public void sub(ECP Q) { - Q.neg(); - add(Q); - Q.neg(); - } - - public static void multiaffine(int m,ECP[] P) - { - int i; - FP t1=new FP(0); - FP t2=new FP(0); - - FP[] work=new FP[m]; - - for (i=0;i<m;i++) - work[i]=new FP(0); - - work[0].one(); - work[1].copy(P[0].z); - - for (i=2;i<m;i++) - { - work[i].copy(work[i-1]); - work[i].mul(P[i-1].z); - } - - t1.copy(work[m-1]); - t1.mul(P[m-1].z); - t1.inverse(); - t2.copy(P[m-1].z); - work[m-1].mul(t1); - - for (i=m-2;;i--) - { - if (i==0) - { - work[0].copy(t1); - work[0].mul(t2); - break; - } - work[i].mul(t2); - work[i].mul(t1); - t2.mul(P[i].z); - } -/* now work[] contains inverses of all Z coordinates */ - - for (i=0;i<m;i++) - { - P[i].z.one(); - t1.copy(work[i]); - t1.sqr(); - P[i].x.mul(t1); - t1.mul(work[i]); - P[i].y.mul(t1); - } - } - -/* constant time multiply by small integer of length bts - use ladder */ - public ECP pinmul(int e,int bts) { - if (ROM.CURVETYPE==ROM.MONTGOMERY) - return this.mul(new BIG(e)); - else - { - int nb,i,b; - ECP P=new ECP(); - ECP R0=new ECP(); - ECP R1=new ECP(); R1.copy(this); - - for (i=bts-1;i>=0;i--) - { - b=(e>>i)&1; - P.copy(R1); - P.add(R0); - R0.cswap(R1,b); - R1.copy(P); - R0.dbl(); - R0.cswap(R1,b); - } - P.copy(R0); - P.affine(); - return P; - } - } - -/* return e.this */ - - public ECP mul(BIG e) { - if (e.iszilch() || is_infinity()) return new ECP(); - ECP P=new ECP(); - if (ROM.CURVETYPE==ROM.MONTGOMERY) - { -/* use Ladder */ - int nb,i,b; - ECP D=new ECP(); - ECP R0=new ECP(); R0.copy(this); - ECP R1=new ECP(); R1.copy(this); - R1.dbl(); - D.copy(this); D.affine(); - nb=e.nbits(); - for (i=nb-2;i>=0;i--) - { - b=e.bit(i); - P.copy(R1); - P.dadd(R0,D); - R0.cswap(R1,b); - R1.copy(P); - R0.dbl(); - R0.cswap(R1,b); - } - P.copy(R0); - } - else - { -// fixed size windows - int i,b,nb,m,s,ns; - BIG mt=new BIG(); - BIG t=new BIG(); - ECP Q=new ECP(); - ECP C=new ECP(); - ECP[] W=new ECP[8]; - byte[] w=new byte[1+(ROM.NLEN*ROM.BASEBITS+3)/4]; - - affine(); - -// precompute table - Q.copy(this); - Q.dbl(); - W[0]=new ECP(); - W[0].copy(this); - - for (i=1;i<8;i++) - { - W[i]=new ECP(); - W[i].copy(W[i-1]); - W[i].add(Q); - } - -// convert the table to affine - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - multiaffine(8,W); - -// make exponent odd - add 2P if even, P if odd - t.copy(e); - s=t.parity(); - t.inc(1); t.norm(); ns=t.parity(); mt.copy(t); mt.inc(1); mt.norm(); - t.cmove(mt,s); - Q.cmove(this,ns); - C.copy(Q); - - nb=1+(t.nbits()+3)/4; - -// convert exponent to signed 4-bit window - for (i=0;i<nb;i++) - { - w[i]=(byte)(t.lastbits(5)-16); - t.dec(w[i]); t.norm(); - t.fshr(4); - } - w[nb]=(byte)t.lastbits(5); - - P.copy(W[(w[nb]-1)/2]); - for (i=nb-1;i>=0;i--) - { - Q.select(W,w[i]); - P.dbl(); - P.dbl(); - P.dbl(); - P.dbl(); - P.add(Q); - } - P.sub(C); /* apply correction */ - } - P.affine(); - return P; - } - -/* Return e.this+f.Q */ - - public ECP mul2(BIG e,ECP Q,BIG f) { - BIG te=new BIG(); - BIG tf=new BIG(); - BIG mt=new BIG(); - ECP S=new ECP(); - ECP T=new ECP(); - ECP C=new ECP(); - ECP[] W=new ECP[8]; - byte[] w=new byte[1+(ROM.NLEN*ROM.BASEBITS+1)/2]; - int i,s,ns,nb; - byte a,b; - - affine(); - Q.affine(); - - te.copy(e); - tf.copy(f); - -// precompute table - W[1]=new ECP(); W[1].copy(this); W[1].sub(Q); - W[2]=new ECP(); W[2].copy(this); W[2].add(Q); - S.copy(Q); S.dbl(); - W[0]=new ECP(); W[0].copy(W[1]); W[0].sub(S); - W[3]=new ECP(); W[3].copy(W[2]); W[3].add(S); - T.copy(this); T.dbl(); - W[5]=new ECP(); W[5].copy(W[1]); W[5].add(T); - W[6]=new ECP(); W[6].copy(W[2]); W[6].add(T); - W[4]=new ECP(); W[4].copy(W[5]); W[4].sub(S); - W[7]=new ECP(); W[7].copy(W[6]); W[7].add(S); - -// convert the table to affine - if (ROM.CURVETYPE==ROM.WEIERSTRASS) - multiaffine(8,W); - -// if multiplier is odd, add 2, else add 1 to multiplier, and add 2P or P to correction - - s=te.parity(); - te.inc(1); te.norm(); ns=te.parity(); mt.copy(te); mt.inc(1); mt.norm(); - te.cmove(mt,s); - T.cmove(this,ns); - C.copy(T); - - s=tf.parity(); - tf.inc(1); tf.norm(); ns=tf.parity(); mt.copy(tf); mt.inc(1); mt.norm(); - tf.cmove(mt,s); - S.cmove(Q,ns); - C.add(S); - - mt.copy(te); mt.add(tf); mt.norm(); - nb=1+(mt.nbits()+1)/2; - -// convert exponent to signed 2-bit window - for (i=0;i<nb;i++) - { - a=(byte)(te.lastbits(3)-4); - te.dec(a); te.norm(); - te.fshr(2); - b=(byte)(tf.lastbits(3)-4); - tf.dec(b); tf.norm(); - tf.fshr(2); - w[i]=(byte)(4*a+b); - } - w[nb]=(byte)(4*te.lastbits(3)+tf.lastbits(3)); - S.copy(W[(w[nb]-1)/2]); - - for (i=nb-1;i>=0;i--) - { - T.select(W,w[i]); - S.dbl(); - S.dbl(); - S.add(T); - } - S.sub(C); /* apply correction */ - S.affine(); - return S; - } - -/* - public static void main(String[] args) { - - BIG Gx=new BIG(ROM.CURVE_Gx); - BIG Gy; - ECP P; - if (ROM.CURVETYPE!=ROM.MONTGOMERY) Gy=new BIG(ROM.CURVE_Gy); - BIG r=new BIG(ROM.CURVE_Order); - - //r.dec(7); - - System.out.println("Gx= "+Gx.toString()); - if (ROM.CURVETYPE!=ROM.MONTGOMERY) System.out.println("Gy= "+Gy.toString()); - - if (ROM.CURVETYPE!=ROM.MONTGOMERY) P=new ECP(Gx,Gy); - else P=new ECP(Gx); - - System.out.println("P= "+P.toString()); - - ECP R=P.mul(r); - //for (int i=0;i<10000;i++) - // R=P.mul(r); - - System.out.println("R= "+R.toString()); - } */ -} - http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/java/ECP2.java ---------------------------------------------------------------------- diff --git a/version22/java/ECP2.java b/version22/java/ECP2.java deleted file mode 100644 index ec9f674..0000000 --- a/version22/java/ECP2.java +++ /dev/null @@ -1,624 +0,0 @@ -/* -Licensed to the Apache Software Foundation (ASF) under one -or more contributor license agreements. See the NOTICE file -distributed with this work for additional information -regarding copyright ownership. The ASF licenses this file -to you under the Apache License, Version 2.0 (the -"License"); you may not use this file except in compliance -with the License. You may obtain a copy of the License at - - http://www.apache.org/licenses/LICENSE-2.0 - -Unless required by applicable law or agreed to in writing, -software distributed under the License is distributed on an -"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY -KIND, either express or implied. See the License for the -specific language governing permissions and limitations -under the License. -*/ - -/* AMCL Weierstrass elliptic curve functions over FP2 */ - -public final class ECP2 { - private FP2 x; - private FP2 y; - private FP2 z; - private boolean INF; - -/* Constructor - set this=O */ - public ECP2() { - INF=true; - x=new FP2(0); - y=new FP2(1); - z=new FP2(1); - } - -/* Test this=O? */ - public boolean is_infinity() { - return INF; - } -/* copy this=P */ - public void copy(ECP2 P) - { - x.copy(P.x); - y.copy(P.y); - z.copy(P.z); - INF=P.INF; - } -/* set this=O */ - public void inf() { - INF=true; - x.zero(); - y.zero(); - z.zero(); - } - -/* Conditional move of Q to P dependant on d */ - public void cmove(ECP2 Q,int d) - { - x.cmove(Q.x,d); - y.cmove(Q.y,d); - z.cmove(Q.z,d); - - boolean bd; - if (d==0) bd=false; - else bd=true; - INF^=(INF^Q.INF)&bd; - } - -/* return 1 if b==c, no branching */ - public static int teq(int b,int c) - { - int x=b^c; - x-=1; // if x=0, x now -1 - return ((x>>31)&1); - } - -/* Constant time select from pre-computed table */ - public void select(ECP2 W[],int b) - { - ECP2 MP=new ECP2(); - int m=b>>31; - int babs=(b^m)-m; - - babs=(babs-1)/2; - - cmove(W[0],teq(babs,0)); // conditional move - cmove(W[1],teq(babs,1)); - cmove(W[2],teq(babs,2)); - cmove(W[3],teq(babs,3)); - cmove(W[4],teq(babs,4)); - cmove(W[5],teq(babs,5)); - cmove(W[6],teq(babs,6)); - cmove(W[7],teq(babs,7)); - - MP.copy(this); - MP.neg(); - cmove(MP,(int)(m&1)); - } - -/* Test if P == Q */ - public boolean equals(ECP2 Q) { - if (is_infinity() && Q.is_infinity()) return true; - if (is_infinity() || Q.is_infinity()) return false; - - FP2 zs2=new FP2(z); zs2.sqr(); - FP2 zo2=new FP2(Q.z); zo2.sqr(); - FP2 zs3=new FP2(zs2); zs3.mul(z); - FP2 zo3=new FP2(zo2); zo3.mul(Q.z); - zs2.mul(Q.x); - zo2.mul(x); - if (!zs2.equals(zo2)) return false; - zs3.mul(Q.y); - zo3.mul(y); - if (!zs3.equals(zo3)) return false; - - return true; - } -/* set this=-this */ - public void neg() { - if (is_infinity()) return; - y.neg(); y.norm(); - return; - } -/* set to Affine - (x,y,z) to (x,y) */ - public void affine() { - if (is_infinity()) return; - FP2 one=new FP2(1); - if (z.equals(one)) return; - z.inverse(); - - FP2 z2=new FP2(z); - z2.sqr(); - x.mul(z2); x.reduce(); - y.mul(z2); - y.mul(z); y.reduce(); - z.copy(one); - } -/* extract affine x as FP2 */ - public FP2 getX() - { - affine(); - return x; - } -/* extract affine y as FP2 */ - public FP2 getY() - { - affine(); - return y; - } -/* extract projective x */ - public FP2 getx() - { - return x; - } -/* extract projective y */ - public FP2 gety() - { - return y; - } -/* extract projective z */ - public FP2 getz() - { - return z; - } -/* convert to byte array */ - public void toBytes(byte[] b) - { - byte[] t=new byte[ROM.MODBYTES]; - affine(); - x.getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) - b[i]=t[i]; - x.getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) - b[i+ROM.MODBYTES]=t[i]; - - y.getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) - b[i+2*ROM.MODBYTES]=t[i]; - y.getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) - b[i+3*ROM.MODBYTES]=t[i]; - } -/* convert from byte array to point */ - public static ECP2 fromBytes(byte[] b) - { - byte[] t=new byte[ROM.MODBYTES]; - BIG ra; - BIG rb; - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=b[i]; - ra=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=b[i+ROM.MODBYTES]; - rb=BIG.fromBytes(t); - FP2 rx=new FP2(ra,rb); - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=b[i+2*ROM.MODBYTES]; - ra=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=b[i+3*ROM.MODBYTES]; - rb=BIG.fromBytes(t); - FP2 ry=new FP2(ra,rb); - - return new ECP2(rx,ry); - } -/* convert this to hex string */ - public String toString() { - if (is_infinity()) return "infinity"; - affine(); - return "("+x.toString()+","+y.toString()+")"; - } - -/* Calculate RHS of twisted curve equation x^3+B/i */ - public static FP2 RHS(FP2 x) { - x.norm(); - FP2 r=new FP2(x); - r.sqr(); - FP2 b=new FP2(new BIG(ROM.CURVE_B)); - b.div_ip(); - r.mul(x); - r.add(b); - - r.reduce(); - return r; - } - -/* construct this from (x,y) - but set to O if not on curve */ - public ECP2(FP2 ix,FP2 iy) { - x=new FP2(ix); - y=new FP2(iy); - z=new FP2(1); - FP2 rhs=RHS(x); - FP2 y2=new FP2(y); - y2.sqr(); - if (y2.equals(rhs)) INF=false; - else {x.zero();INF=true;} - } - -/* construct this from x - but set to O if not on curve */ - public ECP2(FP2 ix) { - x=new FP2(ix); - y=new FP2(1); - z=new FP2(1); - FP2 rhs=RHS(x); - if (rhs.sqrt()) - { - y.copy(rhs); - INF=false; - } - else {x.zero();INF=true;} - } - -/* this+=this */ - public int dbl() { - if (INF) return -1; - if (y.iszilch()) - { - inf(); - return -1; - } - - FP2 w1=new FP2(x); - FP2 w2=new FP2(0); - FP2 w3=new FP2(x); - FP2 w8=new FP2(x); - - w1.sqr(); - w8.copy(w1); - w8.imul(3); - - w2.copy(y); w2.sqr(); - w3.copy(x); w3.mul(w2); - w3.imul(4); - w1.copy(w3); w1.neg(); - w1.norm(); - - x.copy(w8); x.sqr(); - x.add(w1); - x.add(w1); - x.norm(); - - z.mul(y); - z.add(z); - - w2.add(w2); - w2.sqr(); - w2.add(w2); - w3.sub(x); - y.copy(w8); y.mul(w3); - // w2.norm(); - y.sub(w2); - - y.norm(); - z.norm(); - - return 1; - } - -/* this+=Q - return 0 for add, 1 for double, -1 for O */ - public int add(ECP2 Q) { - if (INF) - { - copy(Q); - return -1; - } - if (Q.INF) return -1; - - boolean aff=false; - - if (Q.z.isunity()) aff=true; - - FP2 A,C; - FP2 B=new FP2(z); - FP2 D=new FP2(z); - if (!aff) - { - A=new FP2(Q.z); - C=new FP2(Q.z); - - A.sqr(); B.sqr(); - C.mul(A); D.mul(B); - - A.mul(x); - C.mul(y); - } - else - { - A=new FP2(x); - C=new FP2(y); - - B.sqr(); - D.mul(B); - } - - B.mul(Q.x); B.sub(A); - D.mul(Q.y); D.sub(C); - - if (B.iszilch()) - { - if (D.iszilch()) - { - dbl(); - return 1; - } - else - { - INF=true; - return -1; - } - } - - if (!aff) z.mul(Q.z); - z.mul(B); - - FP2 e=new FP2(B); e.sqr(); - B.mul(e); - A.mul(e); - - e.copy(A); - e.add(A); e.add(B); - x.copy(D); x.sqr(); x.sub(e); - - A.sub(x); - y.copy(A); y.mul(D); - C.mul(B); y.sub(C); - - x.norm(); - y.norm(); - z.norm(); - - return 0; - } - -/* set this-=Q */ - public int sub(ECP2 Q) { - Q.neg(); - int D=add(Q); - Q.neg(); - return D; - } -/* set this*=q, where q is Modulus, using Frobenius */ - public void frob(FP2 X) - { - if (INF) return; - FP2 X2=new FP2(X); - X2.sqr(); - x.conj(); - y.conj(); - z.conj(); - z.reduce(); - x.mul(X2); - y.mul(X2); - y.mul(X); - } - -/* normalises m-array of ECP2 points. Requires work vector of m FP2s */ - - public static void multiaffine(int m,ECP2[] P) - { - int i; - FP2 t1=new FP2(0); - FP2 t2=new FP2(0); - - FP2[] work=new FP2[m]; - work[0]=new FP2(1); - work[1]=new FP2(P[0].z); - for (i=2;i<m;i++) - { - work[i]=new FP2(work[i-1]); - work[i].mul(P[i-1].z); - } - - t1.copy(work[m-1]); t1.mul(P[m-1].z); - - t1.inverse(); - - t2.copy(P[m-1].z); - work[m-1].mul(t1); - - for (i=m-2;;i--) - { - if (i==0) - { - work[0].copy(t1); - work[0].mul(t2); - break; - } - work[i].mul(t2); - work[i].mul(t1); - t2.mul(P[i].z); - } -/* now work[] contains inverses of all Z coordinates */ - - for (i=0;i<m;i++) - { - P[i].z.one(); - t1.copy(work[i]); t1.sqr(); - P[i].x.mul(t1); - t1.mul(work[i]); - P[i].y.mul(t1); - } - } - -/* P*=e */ - public ECP2 mul(BIG e) - { -/* fixed size windows */ - int i,b,nb,m,s,ns; - BIG mt=new BIG(); - BIG t=new BIG(); - ECP2 P=new ECP2(); - ECP2 Q=new ECP2(); - ECP2 C=new ECP2(); - ECP2[] W=new ECP2[8]; - byte[] w=new byte[1+(ROM.NLEN*ROM.BASEBITS+3)/4]; - - if (is_infinity()) return new ECP2(); - - affine(); - -/* precompute table */ - Q.copy(this); - Q.dbl(); - W[0]=new ECP2(); - W[0].copy(this); - - for (i=1;i<8;i++) - { - W[i]=new ECP2(); - W[i].copy(W[i-1]); - W[i].add(Q); - } - -/* convert the table to affine */ - - multiaffine(8,W); - -/* make exponent odd - add 2P if even, P if odd */ - t.copy(e); - s=t.parity(); - t.inc(1); t.norm(); ns=t.parity(); mt.copy(t); mt.inc(1); mt.norm(); - t.cmove(mt,s); - Q.cmove(this,ns); - C.copy(Q); - - nb=1+(t.nbits()+3)/4; -/* convert exponent to signed 4-bit window */ - for (i=0;i<nb;i++) - { - w[i]=(byte)(t.lastbits(5)-16); - t.dec(w[i]); t.norm(); - t.fshr(4); - } - w[nb]=(byte)t.lastbits(5); - - P.copy(W[(w[nb]-1)/2]); - for (i=nb-1;i>=0;i--) - { - Q.select(W,w[i]); - P.dbl(); - P.dbl(); - P.dbl(); - P.dbl(); - P.add(Q); - } - P.sub(C); - P.affine(); - return P; - } - -/* P=u0.Q0+u1*Q1+u2*Q2+u3*Q3 */ - public static ECP2 mul4(ECP2[] Q,BIG[] u) - { - int i,j,nb; - int[] a=new int[4]; - ECP2 T=new ECP2(); - ECP2 C=new ECP2(); - ECP2 P=new ECP2(); - ECP2[] W=new ECP2[8]; - - BIG mt=new BIG(); - BIG[] t=new BIG[4]; - - byte[] w=new byte[ROM.NLEN*ROM.BASEBITS+1]; - - for (i=0;i<4;i++) - { - t[i]=new BIG(u[i]); - Q[i].affine(); - } - -/* precompute table */ - - W[0]=new ECP2(); W[0].copy(Q[0]); W[0].sub(Q[1]); - W[1]=new ECP2(); W[1].copy(W[0]); - W[2]=new ECP2(); W[2].copy(W[0]); - W[3]=new ECP2(); W[3].copy(W[0]); - W[4]=new ECP2(); W[4].copy(Q[0]); W[4].add(Q[1]); - W[5]=new ECP2(); W[5].copy(W[4]); - W[6]=new ECP2(); W[6].copy(W[4]); - W[7]=new ECP2(); W[7].copy(W[4]); - T.copy(Q[2]); T.sub(Q[3]); - W[1].sub(T); - W[2].add(T); - W[5].sub(T); - W[6].add(T); - T.copy(Q[2]); T.add(Q[3]); - W[0].sub(T); - W[3].add(T); - W[4].sub(T); - W[7].add(T); - - multiaffine(8,W); - -/* if multiplier is even add 1 to multiplier, and add P to correction */ - mt.zero(); C.inf(); - for (i=0;i<4;i++) - { - if (t[i].parity()==0) - { - t[i].inc(1); t[i].norm(); - C.add(Q[i]); - } - mt.add(t[i]); mt.norm(); - } - - nb=1+mt.nbits(); - -/* convert exponent to signed 1-bit window */ - for (j=0;j<nb;j++) - { - for (i=0;i<4;i++) - { - a[i]=(byte)(t[i].lastbits(2)-2); - t[i].dec(a[i]); t[i].norm(); - t[i].fshr(1); - } - w[j]=(byte)(8*a[0]+4*a[1]+2*a[2]+a[3]); - } - w[nb]=(byte)(8*t[0].lastbits(2)+4*t[1].lastbits(2)+2*t[2].lastbits(2)+t[3].lastbits(2)); - - P.copy(W[(w[nb]-1)/2]); - for (i=nb-1;i>=0;i--) - { - T.select(W,w[i]); - P.dbl(); - P.add(T); - } - P.sub(C); /* apply correction */ - - P.affine(); - return P; - } - -/* - public static void main(String[] args) { - BIG r=new BIG(ROM.Modulus); - - BIG Pxa=new BIG(ROM.CURVE_Pxa); - BIG Pxb=new BIG(ROM.CURVE_Pxb); - BIG Pya=new BIG(ROM.CURVE_Pya); - BIG Pyb=new BIG(ROM.CURVE_Pyb); - - BIG Fra=new BIG(ROM.CURVE_Fra); - BIG Frb=new BIG(ROM.CURVE_Frb); - - FP2 f=new FP2(Fra,Frb); - - FP2 Px=new FP2(Pxa,Pxb); - FP2 Py=new FP2(Pya,Pyb); - - ECP2 P=new ECP2(Px,Py); - - System.out.println("P= "+P.toString()); - - P=P.mul(r); - System.out.println("P= "+P.toString()); - - ECP2 Q=new ECP2(Px,Py); - Q.frob(f); - System.out.println("Q= "+Q.toString()); - } */ - - -} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/java/FF.java ---------------------------------------------------------------------- diff --git a/version22/java/FF.java b/version22/java/FF.java deleted file mode 100644 index a6ee1fe..0000000 --- a/version22/java/FF.java +++ /dev/null @@ -1,941 +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. -*/ - -/* Large Finite Field arithmetic */ -/* AMCL mod p functions */ - -public final class FF { - private final BIG[] v; - private final int length; - -/* Constructors */ - public FF(int n) - { - v=new BIG[n]; - for (int i=0;i<n;i++) - v[i]=new BIG(0); - length=n; - } - - public int getlen() - { - return length; - } - -/* set to integer */ - public void set(int m) - { - zero(); - v[0].set(0,(m&ROM.BMASK)); - v[0].set(1,(m>>ROM.BASEBITS)); - } - -/* copy from FF b */ - public void copy(FF b) - { - for (int i=0;i<length;i++) - { - v[i].copy(b.v[i]); - } - } - -/* x=y<<n */ - public void dsucopy(FF b) - { - for (int i=0;i<b.length;i++) - { - v[b.length+i].copy(b.v[i]); - v[i].zero(); - } - } - -/* x=y */ - public void dscopy(FF b) - { - for (int i=0;i<b.length;i++) - { - v[i].copy(b.v[i]); - v[b.length+i].zero(); - } - } - -/* x=y>>n */ - public void sducopy(FF b) - { - for (int i=0;i<length;i++) - { - v[i].copy(b.v[length+i]); - } - } - -/* set to zero */ - public void zero() - { - for (int i=0;i<length;i++) - { - v[i].zero(); - } - } - - public void one() - { - v[0].one(); - for (int i=1;i<length;i++) - { - v[i].zero(); - } - } - -/* test equals 0 */ - public boolean iszilch() - { - for (int i=0;i<length;i++) - { - if (!v[i].iszilch()) return false; - } - return true; - } - -/* shift right by BIGBITS-bit words */ - public void shrw(int n) - { - for (int i=0;i<n;i++) - { - v[i].copy(v[i+n]); - v[i+n].zero(); - } - } - -/* shift left by BIGBITS-bit words */ - public void shlw(int n) - { - for (int i=0;i<n;i++) - { - v[n+i].copy(v[i]); - v[i].zero(); - } - } - -/* extract last bit */ - public int parity() - { - return v[0].parity(); - } - - public int lastbits(int m) - { - return v[0].lastbits(m); - } - -/* compare x and y - must be normalised, and of same length */ - public static int comp(FF a,FF b) - { - int i,j; - for (i=a.length-1;i>=0;i--) - { - j=BIG.comp(a.v[i],b.v[i]); - if (j!=0) return j; - } - return 0; - } - -/* recursive add */ - public void radd(int vp,FF x,int xp,FF y,int yp,int n) - { - for (int i=0;i<n;i++) - { - v[vp+i].copy(x.v[xp+i]); - v[vp+i].add(y.v[yp+i]); - } - } - -/* recursive inc */ - public void rinc(int vp,FF y,int yp,int n) - { - for (int i=0;i<n;i++) - { - v[vp+i].add(y.v[yp+i]); - } - } - -/* recursive sub */ - public void rsub(int vp,FF x,int xp,FF y,int yp,int n) - { - for (int i=0;i<n;i++) - { - v[vp+i].copy(x.v[xp+i]); - v[vp+i].sub(y.v[yp+i]); - } - } - -/* recursive dec */ - public void rdec(int vp,FF y,int yp,int n) - { - for (int i=0;i<n;i++) - { - v[vp+i].sub(y.v[yp+i]); - } - } - -/* simple add */ - public void add(FF b) - { - for (int i=0;i<length;i++) - v[i].add(b.v[i]); - } - -/* simple sub */ - public void sub(FF b) - { - for (int i=0;i<length;i++) - v[i].sub(b.v[i]); - } - -/* reverse sub */ - public void revsub(FF b) - { - for (int i=0;i<length;i++) - v[i].rsub(b.v[i]); - } - -/* increment/decrement by a small integer */ - public void inc(int m) - { - v[0].inc(m); - norm(); - } - - public void dec(int m) - { - v[0].dec(m); - norm(); - } - - /* normalise - but hold any overflow in top part unless n<0 */ - private void rnorm(int vp,int n) - { - boolean trunc=false; - int i; - long carry; - if (n<0) - { /* -v n signals to do truncation */ - n=-n; - trunc=true; - } - for (i=0;i<n-1;i++) - { - carry=v[vp+i].norm(); - v[vp+i].xortop(carry<<ROM.P_TBITS); - v[vp+i+1].incl(carry); - } - carry=v[vp+n-1].norm(); - if (trunc) - v[vp+n-1].xortop(carry<<ROM.P_TBITS); - } - - public void norm() - { - rnorm(0,length); - } - -/* shift left by one bit */ - public void shl() - { - int i,carry,delay_carry=0; - for (i=0;i<length-1;i++) - { - carry=v[i].fshl(1); - v[i].inc(delay_carry); - v[i].xortop((long)carry<<ROM.P_TBITS); - delay_carry=carry; - } - v[length-1].fshl(1); - v[length-1].inc(delay_carry); - } - -/* shift right by one bit */ - - public void shr() - { - int carry; - for (int i=length-1;i>0;i--) - { - carry=v[i].fshr(1); - v[i-1].xortop((long)carry<<ROM.P_TBITS); - } - v[0].fshr(1); - } - -/* Convert to Hex String */ - public String toString() - { - norm(); - String s=""; - for (int i=length-1;i>=0;i--) - { - s+=v[i].toString(); //s+=" "; - } - return s; - } - -/* - public String toRawString(int len) - { - // norm(len); - String s=""; - for (int i=len-1;i>=0;i--) - { - s+=v[i].toRawString(); s+=" "; - } - return s; - } -*/ -/* Convert FFs to/from byte arrays */ - public void toBytes(byte[] b) - { - for (int i=0;i<length;i++) - { - v[i].tobytearray(b,(length-i-1)*ROM.MODBYTES); - } - } - - public static void fromBytes(FF x,byte[] b) - { - for (int i=0;i<x.length;i++) - { - x.v[i]=BIG.frombytearray(b,(x.length-i-1)*ROM.MODBYTES); - } - } - -/* in-place swapping using xor - side channel resistant - lengths must be the same */ - private static void cswap(FF a,FF b,int d) - { - for (int i=0;i<a.length;i++) - { - // BIG.cswap(a.v[i],b.v[i],d); - a.v[i].cswap(b.v[i],d); - } - } - -/* z=x*y, t is workspace */ - private void karmul(int vp,FF x,int xp,FF y,int yp,FF t,int tp,int n) - { - int nd2; - if (n==1) - { - DBIG d=BIG.mul(x.v[xp],y.v[yp]); - v[vp+1]=d.split(8*ROM.MODBYTES); - v[vp].copy(d); - return; - } - nd2=n/2; - radd(vp,x,xp,x,xp+nd2,nd2); - rnorm(vp,nd2); /* Important - required for 32-bit build */ - radd(vp+nd2,y,yp,y,yp+nd2,nd2); - rnorm(vp+nd2,nd2); /* Important - required for 32-bit build */ - - t.karmul(tp,this,vp,this,vp+nd2,t,tp+n,nd2); - karmul(vp,x,xp,y,yp,t,tp+n,nd2); - karmul(vp+n,x,xp+nd2,y,yp+nd2,t,tp+n,nd2); - t.rdec(tp,this,vp,n); - t.rdec(tp,this,vp+n,n); - rinc(vp+nd2,t,tp,n); - rnorm(vp,2*n); - } - - private void karsqr(int vp,FF x,int xp,FF t,int tp,int n) - { - int nd2; - if (n==1) - { - DBIG d=BIG.sqr(x.v[xp]); - v[vp+1].copy(d.split(8*ROM.MODBYTES)); - v[vp].copy(d); - return; - } - - nd2=n/2; - karsqr(vp,x,xp,t,tp+n,nd2); - karsqr(vp+n,x,xp+nd2,t,tp+n,nd2); - t.karmul(tp,x,xp,x,xp+nd2,t,tp+n,nd2); - rinc(vp+nd2,t,tp,n); - rinc(vp+nd2,t,tp,n); - rnorm(vp+nd2,n); - } - - - private void karmul_lower(int vp,FF x,int xp,FF y,int yp,FF t,int tp,int n) - { /* Calculates Least Significant bottom half of x*y */ - int nd2; - if (n==1) - { /* only calculate bottom half of product */ - v[vp].copy(BIG.smul(x.v[xp],y.v[yp])); - return; - } - nd2=n/2; - karmul(vp,x,xp,y,yp,t,tp+n,nd2); - t.karmul_lower(tp,x,xp+nd2,y,yp,t,tp+n,nd2); - rinc(vp+nd2,t,tp,nd2); - t.karmul_lower(tp,x,xp,y,yp+nd2,t,tp+n,nd2); - - rinc(vp+nd2,t,tp,nd2); - rnorm(vp+nd2,-nd2); /* truncate it */ - } - - private void karmul_upper(FF x,FF y,FF t,int n) - { /* Calculates Most Significant upper half of x*y, given lower part */ - int nd2; - - nd2=n/2; - radd(n,x,0,x,nd2,nd2); - radd(n+nd2,y,0,y,nd2,nd2); - rnorm(n,nd2); - rnorm(n+nd2,nd2); - - t.karmul(0,this,n+nd2,this,n,t,n,nd2); /* t = (a0+a1)(b0+b1) */ - karmul(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) */ - t.rdec(0,this,n,n); /* t=t-a1b1 */ - rinc(nd2,this,0,nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */ - rdec(nd2,t,0,nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */ - rnorm(0,-n); /* a0b0 now in z - truncate it */ - t.rdec(0,this,0,n); /* (a0+a1)(b0+b1) - a0b0 */ - rinc(nd2,t,0,n); - - rnorm(nd2,n); - } - - /* z=x*y. Assumes x and y are of same length. */ - public static FF mul(FF x,FF y) - { - int n=x.length; - FF z=new FF(2*n); - FF t=new FF(2*n); -// x.norm(); y.norm(); - z.karmul(0,x,0,y,0,t,0,n); - return z; - } - - /* z=x^2 */ - public static FF sqr(FF x) - { - int n=x.length; - FF z=new FF(2*n); - FF t=new FF(2*n); -// x.norm(); - z.karsqr(0,x,0,t,0,n); - return z; - } - -/* return low part of product this*y */ - public void lmul(FF y) - { - int n=length; - FF t=new FF(2*n); - FF x=new FF(n); x.copy(this); -// x.norm(); y.norm(); - karmul_lower(0,x,0,y,0,t,0,n); - } - -/* Set b=b mod c */ - public void mod(FF c) - { - int k=0; - - norm(); - if (comp(this,c)<0) - return; - do - { - c.shl(); - k++; - } while (comp(this,c)>=0); - - while (k>0) - { - c.shr(); - if (comp(this,c)>=0) - { - sub(c); - norm(); - } - k--; - } - } - -/* return This mod modulus, N is modulus, ND is Montgomery Constant */ - public FF reduce(FF N,FF ND) - { /* fast karatsuba Montgomery reduction */ - int n=N.length; - FF t=new FF(2*n); - FF r=new FF(n); - FF m=new FF(n); - - r.sducopy(this); - m.karmul_lower(0,this,0,ND,0,t,0,n); - karmul_upper(N,m,t,n); - m.sducopy(this); - - r.add(N); - r.sub(m); - r.norm(); - - return r; - } - -/* Set r=this mod b */ -/* this is of length - 2*n */ -/* r,b is of length - n */ - public FF dmod(FF b) - { - int k,n=b.length; - FF m=new FF(2*n); - FF x=new FF(2*n); - FF r=new FF(n); - - x.copy(this); - x.norm(); - m.dsucopy(b); k=ROM.BIGBITS*n; - - while (comp(x,m)>=0) - { - x.sub(m); - x.norm(); - } - - while (k>0) - { - m.shr(); - - if (comp(x,m)>=0) - { - x.sub(m); - x.norm(); - } - k--; - } - - r.copy(x); - r.mod(b); - return r; - } - -/* Set return=1/this mod p. Binary method - a<p on entry */ - - public void invmodp(FF p) - { - int n=p.length; - - FF u=new FF(n); - FF v=new FF(n); - FF x1=new FF(n); - FF x2=new FF(n); - FF t=new FF(n); - FF one=new FF(n); - - one.one(); - u.copy(this); - v.copy(p); - x1.copy(one); - x2.zero(); - - // reduce n in here as well! - while (comp(u,one)!=0 && comp(v,one)!=0) - { - while (u.parity()==0) - { - u.shr(); - if (x1.parity()!=0) - { - x1.add(p); - x1.norm(); - } - x1.shr(); - } - while (v.parity()==0) - { - v.shr(); - if (x2.parity()!=0) - { - x2.add(p); - x2.norm(); - } - x2.shr(); - } - if (comp(u,v)>=0) - { - - u.sub(v); - u.norm(); - if (comp(x1,x2)>=0) x1.sub(x2); - else - { - t.copy(p); - t.sub(x2); - x1.add(t); - } - x1.norm(); - } - else - { - v.sub(u); - v.norm(); - if (comp(x2,x1)>=0) x2.sub(x1); - else - { - t.copy(p); - t.sub(x1); - x2.add(t); - } - x2.norm(); - } - } - if (comp(u,one)==0) - copy(x1); - else - copy(x2); - } - -/* nresidue mod m */ - public void nres(FF m) - { - int n=m.length; - FF d=new FF(2*n); - d.dsucopy(this); - copy(d.dmod(m)); - } - - public void redc(FF m,FF ND) - { - int n=m.length; - FF d=new FF(2*n); - mod(m); - d.dscopy(this); - copy(d.reduce(m,ND)); - mod(m); - } - - private void mod2m(int m) - { - for (int i=m;i<length;i++) - v[i].zero(); - } - - /* U=1/a mod 2^m - Arazi & Qi */ - private FF invmod2m() - { - int i,n=length; - - FF b=new FF(n); - FF c=new FF(n); - FF U=new FF(n); - FF t; - - U.zero(); - U.v[0].copy(v[0]); - U.v[0].invmod2m(); - - for (i=1;i<n;i<<=1) - { - b.copy(this); b.mod2m(i); - t=mul(U,b); - - t.shrw(i); b.copy(t); - c.copy(this); c.shrw(i); c.mod2m(i); - c.lmul(U); c.mod2m(i); - - b.add(c); b.norm(); - b.lmul(U); b.mod2m(i); - - c.one(); c.shlw(i); b.revsub(c); b.norm(); - b.shlw(i); - U.add(b); - } - U.norm(); - return U; - } - - public void random(RAND rng) - { - int n=length; - for (int i=0;i<n;i++) - { - v[i].copy(BIG.random(rng)); - } - /* make sure top bit is 1 */ - while (v[n-1].nbits()<ROM.MODBYTES*8) v[n-1].copy(BIG.random(rng)); - } - - /* generate random x */ - public void randomnum(FF p,RAND rng) - { - int n=length; - FF d=new FF(2*n); - - for (int i=0;i<2*n;i++) - { - d.v[i].copy(BIG.random(rng)); - } - copy(d.dmod(p)); - } - - /* this*=y mod p */ - public void modmul(FF y,FF p,FF nd) - { - if (BIG.ff_pexceed(v[length-1],y.v[y.length-1])) mod(p); - FF d=mul(this,y); - copy(d.reduce(p,nd)); - } - - /* this*=y mod p */ - public void modsqr(FF p,FF nd) - { - if (BIG.ff_sexceed(v[length-1])) mod(p); - FF d=sqr(this); - copy(d.reduce(p,nd)); - } - - /* this=this^e mod p using side-channel resistant Montgomery Ladder, for large e */ - public void skpow(FF e,FF p) - { - int i,b,n=p.length; - FF R0=new FF(n); - FF R1=new FF(n); - FF ND=p.invmod2m(); - - mod(p); - R0.one(); - R1.copy(this); - R0.nres(p); - R1.nres(p); - - for (i=8*ROM.MODBYTES*n-1;i>=0;i--) - { - b=e.v[i/ROM.BIGBITS].bit(i%ROM.BIGBITS); - copy(R0); - modmul(R1,p,ND); - - cswap(R0,R1,b); - R0.modsqr(p,ND); - - R1.copy(this); - cswap(R0,R1,b); - } - copy(R0); - redc(p,ND); - } - - /* this =this^e mod p using side-channel resistant Montgomery Ladder, for short e */ - public void skpow(BIG e,FF p) - { - int i,b,n=p.length; - FF R0=new FF(n); - FF R1=new FF(n); - FF ND=p.invmod2m(); - - mod(p); - R0.one(); - R1.copy(this); - R0.nres(p); - R1.nres(p); - - for (i=8*ROM.MODBYTES-1;i>=0;i--) - { - b=e.bit(i); - copy(R0); - modmul(R1,p,ND); - - cswap(R0,R1,b); - R0.modsqr(p,ND); - - R1.copy(this); - cswap(R0,R1,b); - } - copy(R0); - redc(p,ND); - } - - /* raise to an integer power - right-to-left method */ - public void power(int e,FF p) - { - int n=p.length; - FF w=new FF(n); - FF ND=p.invmod2m(); - boolean f=true; - - w.copy(this); - w.nres(p); - - if (e==2) - { - copy(w); - modsqr(p,ND); - } - else for (; ; ) - { - if (e%2==1) - { - if (f) copy(w); - else modmul(w,p,ND); - f=false; - } - e>>=1; - if (e==0) break; - w.modsqr(p,ND); - } - redc(p,ND); - } - - /* this=this^e mod p, faster but not side channel resistant */ - public void pow(FF e,FF p) - { - int i,b,n=p.length; - FF w=new FF(n); - FF ND=p.invmod2m(); - - w.copy(this); - one(); - nres(p); - w.nres(p); - for (i=8*ROM.MODBYTES*n-1;i>=0;i--) - { - modsqr(p,ND); - b=e.v[i/ROM.BIGBITS].bit(i%ROM.BIGBITS); - if (b==1) modmul(w,p,ND); - } - redc(p,ND); - } - - /* double exponentiation r=x^e.y^f mod p */ - public void pow2(BIG e,FF y,BIG f,FF p) - { - int i,eb,fb,n=p.length; - FF xn=new FF(n); - FF yn=new FF(n); - FF xy=new FF(n); - FF ND=p.invmod2m(); - - xn.copy(this); - yn.copy(y); - xn.nres(p); - yn.nres(p); - xy.copy(xn); xy.modmul(yn,p,ND); - one(); - nres(p); - - for (i=8*ROM.MODBYTES-1;i>=0;i--) - { - eb=e.bit(i); - fb=f.bit(i); - modsqr(p,ND); - if (eb==1) - { - if (fb==1) modmul(xy,p,ND); - else modmul(xn,p,ND); - } - else - { - if (fb==1) modmul(yn,p,ND); - } - } - redc(p,ND); - } - - private static int igcd(int x,int y) - { /* integer GCD, returns GCD of x and y */ - int 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 n */ - public boolean cfactor(int s) - { - int r,n=length; - int g; - - FF x=new FF(n); - FF y=new FF(n); - - y.set(s); - x.copy(this); - x.norm(); - - do - { - x.sub(y); - x.norm(); - while (!x.iszilch() && x.parity()==0) x.shr(); - } - while (comp(x,y)>0); - - g=(int)x.v[0].get(0); - r=igcd(s,g); - if (r>1) return true; - return false; - } - - /* Miller-Rabin test for primality. Slow. */ - public static boolean prime(FF p,RAND rng) - { - int i,j,s=0,n=p.length; - boolean loop; - FF d=new FF(n); - FF x=new FF(n); - FF unity=new FF(n); - FF nm1=new FF(n); - - int sf=4849845; /* 3*5*.. *19 */ - p.norm(); - - if (p.cfactor(sf)) return false; - unity.one(); - nm1.copy(p); - nm1.sub(unity); - nm1.norm(); - d.copy(nm1); - - while (d.parity()==0) - { - d.shr(); - s++; - } - if (s==0) return false; - for (i=0;i<10;i++) - { - x.randomnum(p,rng); - x.pow(d,p); - - if (comp(x,unity)==0 || comp(x,nm1)==0) continue; - loop=false; - for (j=1;j<s;j++) - { - x.power(2,p); - if (comp(x,unity)==0) return false; - if (comp(x,nm1)==0) {loop=true; break;} - } - if (loop) continue; - return false; - } - return true; - } - -} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/java/FP.java ---------------------------------------------------------------------- diff --git a/version22/java/FP.java b/version22/java/FP.java deleted file mode 100644 index bafa46b..0000000 --- a/version22/java/FP.java +++ /dev/null @@ -1,345 +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. -*/ - -/* Finite Field arithmetic */ -/* AMCL mod p functions */ - -public final class FP { - private final BIG x; - private static BIG p=new BIG(ROM.Modulus); - -/* Constructors */ - public FP(int a) - { - x=new BIG(a); - nres(); - } - - public FP() - { - x=new BIG(0); - } - - public FP(BIG a) - { - x=new BIG(a); - nres(); - } - - public FP(FP a) - { - x=new BIG(a.x); - } - -/* convert to string */ - public String toString() - { - String s=redc().toString(); - return s; - } - - public String toRawString() - { - String s=x.toRawString(); - return s; - } - -/* convert to Montgomery n-residue form */ - public void nres() - { - if (ROM.MODTYPE!=ROM.PSEUDO_MERSENNE && ROM.MODTYPE!=ROM.GENERALISED_MERSENNE) - { - DBIG d=new DBIG(x); - d.shl(ROM.NLEN*ROM.BASEBITS); - x.copy(d.mod(p)); - } - } - -/* convert back to regular form */ - public BIG redc() - { - if (ROM.MODTYPE!=ROM.PSEUDO_MERSENNE && ROM.MODTYPE!=ROM.GENERALISED_MERSENNE) - { - DBIG d=new DBIG(x); - return BIG.mod(d); - } - else - { - BIG r=new BIG(x); - return r; - } - } - -/* test this=0? */ - public boolean iszilch() { - reduce(); - return x.iszilch(); - } - -/* copy from FP b */ - public void copy(FP b) - { - x.copy(b.x); - } - -/* set this=0 */ - public void zero() - { - x.zero(); - } - -/* set this=1 */ - public void one() - { - x.one(); nres(); - } - -/* normalise this */ - public void norm() - { - x.norm(); - } - -/* swap FPs depending on d */ - public void cswap(FP b,int d) - { - x.cswap(b.x,d); - } - -/* copy FPs depending on d */ - public void cmove(FP b,int d) - { - x.cmove(b.x,d); - } - -/* this*=b mod Modulus */ - public void mul(FP b) - { - norm(); - b.norm(); - - if (BIG.pexceed(x,b.x)) reduce(); - - DBIG d=BIG.mul(x,b.x); - x.copy(BIG.mod(d)); - } - -/* this*=c mod Modulus, where c is a small int */ - public void imul(int c) - { - norm(); - boolean s=false; - if (c<0) - { - c=-c; - s=true; - } - if (c<ROM.NEXCESS && ((BIG.EXCESS(x)+1)*(c+1)+1)<ROM.FEXCESS) - { - x.imul(c); - } - else - { - if (((BIG.EXCESS(x)+1)*(c+1)+1)<ROM.FEXCESS) x.pmul(c); - else - { - DBIG d=x.pxmul(c); - x.copy(d.mod(p)); - } - } - if (s) neg(); - norm(); - } - -/* this*=this mod Modulus */ - public void sqr() - { - DBIG d; - norm(); - - if (BIG.sexceed(x)) reduce(); - - d=BIG.sqr(x); - x.copy(BIG.mod(d)); - } - -/* this+=b */ - public void add(FP b) { - x.add(b.x); - if (BIG.EXCESS(x)+2>=ROM.FEXCESS) reduce(); - } - -// https://graphics.stanford.edu/~seander/bithacks.html -// constant time log to base 2 (or number of bits in) - - private static int logb2(int 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+1; - } - -/* this = -this mod Modulus */ - public void neg() - { - int sb; - BIG m=new BIG(p); - - norm(); - sb=logb2((int)BIG.EXCESS(x)); -/* - ov=BIG.EXCESS(x); - sb=1; while(ov!=0) {sb++;ov>>=1;} -*/ - m.fshl(sb); - x.rsub(m); - - if (BIG.EXCESS(x)>=ROM.FEXCESS) reduce(); - } - -/* this-=b */ - public void sub(FP b) - { - FP n=new FP(b); - n.neg(); - this.add(n); - } - -/* this/=2 mod Modulus */ - public void div2() - { - x.norm(); - if (x.parity()==0) - x.fshr(1); - else - { - x.add(p); - x.norm(); - x.fshr(1); - } - } - -/* this=1/this mod Modulus */ - public void inverse() - { - BIG r=redc(); - r.invmodp(p); - x.copy(r); - nres(); - } - -/* return TRUE if this==a */ - public boolean equals(FP a) - { - a.reduce(); - reduce(); - if (BIG.comp(a.x,x)==0) return true; - return false; - } - -/* reduce this mod Modulus */ - public void reduce() - { - x.mod(p); - } - -/* return this^e mod Modulus */ - public FP pow(BIG e) - { - int bt; - FP r=new FP(1); - e.norm(); - x.norm(); - FP m=new FP(this); - while (true) - { - bt=e.parity(); - e.fshr(1); - if (bt==1) r.mul(m); - if (e.iszilch()) break; - m.sqr(); - } - r.x.mod(p); - return r; - } - -/* return sqrt(this) mod Modulus */ - public FP sqrt() - { - reduce(); - BIG b=new BIG(p); - if (ROM.MOD8==5) - { - b.dec(5); b.norm(); b.shr(3); - FP i=new FP(this); i.x.shl(1); - FP v=i.pow(b); - i.mul(v); i.mul(v); - i.x.dec(1); - FP r=new FP(this); - r.mul(v); r.mul(i); - r.reduce(); - return r; - } - else - { - b.inc(1); b.norm(); b.shr(2); - return pow(b); - } - } - -/* return jacobi symbol (this/Modulus) */ - public int jacobi() - { - BIG w=redc(); - return w.jacobi(p); - } -/* - public static void main(String[] args) { - BIG m=new BIG(ROM.Modulus); - BIG x=new BIG(3); - BIG e=new BIG(m); - e.dec(1); - - System.out.println("m= "+m.nbits()); - - - BIG r=x.powmod(e,m); - - System.out.println("m= "+m.toString()); - System.out.println("r= "+r.toString()); - - BIG.cswap(m,r,0); - - System.out.println("m= "+m.toString()); - System.out.println("r= "+r.toString()); - -// FP y=new FP(3); -// FP s=y.pow(e); -// System.out.println("s= "+s.toString()); - - } */ -} http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/1add7560/version22/java/FP12.java ---------------------------------------------------------------------- diff --git a/version22/java/FP12.java b/version22/java/FP12.java deleted file mode 100644 index 7ef0607..0000000 --- a/version22/java/FP12.java +++ /dev/null @@ -1,641 +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 */ -/* FP12 elements are of the form a+i.b+i^2.c */ - -public final class FP12 { - private final FP4 a; - private final FP4 b; - private final FP4 c; -/* reduce all components of this mod Modulus */ - public void reduce() - { - a.reduce(); - b.reduce(); - c.reduce(); - } -/* normalise all components of this */ - public void norm() - { - a.norm(); - b.norm(); - c.norm(); - } -/* test x==0 ? */ - public boolean iszilch() { - reduce(); - return (a.iszilch() && b.iszilch() && c.iszilch()); - } -/* test x==1 ? */ - public boolean isunity() { - FP4 one=new FP4(1); - return (a.equals(one) && b.iszilch() && c.iszilch()); - } -/* return 1 if x==y, else 0 */ - public boolean equals(FP12 x) - { - return (a.equals(x.a) && b.equals(x.b) && c.equals(x.c)); - } -/* extract a from this */ - public FP4 geta() - { - return a; - } -/* extract b */ - public FP4 getb() - { - return b; - } -/* extract c */ - public FP4 getc() - { - return c; - } -/* copy this=x */ - public void copy(FP12 x) - { - a.copy(x.a); - b.copy(x.b); - c.copy(x.c); - } -/* set this=1 */ - public void one() - { - a.one(); - b.zero(); - c.zero(); - } -/* this=conj(this) */ - public void conj() - { - a.conj(); - b.nconj(); - c.conj(); - } -/* Constructors */ - public FP12(FP4 d) - { - a=new FP4(d); - b=new FP4(0); - c=new FP4(0); - } - - public FP12(int d) - { - a=new FP4(d); - b=new FP4(0); - c=new FP4(0); - } - - public FP12(FP4 d,FP4 e,FP4 f) - { - a=new FP4(d); - b=new FP4(e); - c=new FP4(f); - } - - public FP12(FP12 x) - { - a=new FP4(x.a); - b=new FP4(x.b); - c=new FP4(x.c); - } - -/* Granger-Scott Unitary Squaring */ - public void usqr() - { - FP4 A=new FP4(a); - FP4 B=new FP4(c); - FP4 C=new FP4(b); - FP4 D=new FP4(0); - - a.sqr(); - D.copy(a); D.add(a); - a.add(D); - - a.norm(); - A.nconj(); - - A.add(A); - a.add(A); - B.sqr(); - B.times_i(); - - D.copy(B); D.add(B); - B.add(D); - B.norm(); - - C.sqr(); - D.copy(C); D.add(C); - C.add(D); - C.norm(); - - b.conj(); - b.add(b); - c.nconj(); - - c.add(c); - b.add(B); - c.add(C); - reduce(); - - } - -/* Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */ - public void sqr() - { - FP4 A=new FP4(a); - FP4 B=new FP4(b); - FP4 C=new FP4(c); - FP4 D=new FP4(a); - - A.sqr(); - B.mul(c); - B.add(B); - C.sqr(); - D.mul(b); - D.add(D); - - c.add(a); - c.add(b); - c.sqr(); - - a.copy(A); - - A.add(B); - A.norm(); - A.add(C); - A.add(D); - A.norm(); - - A.neg(); - B.times_i(); - C.times_i(); - - a.add(B); - - b.copy(C); b.add(D); - c.add(A); - norm(); - } - -/* FP12 full multiplication this=this*y */ - public void mul(FP12 y) - { - FP4 z0=new FP4(a); - FP4 z1=new FP4(0); - FP4 z2=new FP4(b); - FP4 z3=new FP4(0); - FP4 t0=new FP4(a); - FP4 t1=new FP4(y.a); - - z0.mul(y.a); - z2.mul(y.b); - - t0.add(b); - t1.add(y.b); - - z1.copy(t0); z1.mul(t1); - t0.copy(b); t0.add(c); - - t1.copy(y.b); t1.add(y.c); - z3.copy(t0); z3.mul(t1); - - t0.copy(z0); t0.neg(); - t1.copy(z2); t1.neg(); - - z1.add(t0); - z1.norm(); - b.copy(z1); b.add(t1); - - z3.add(t1); - z2.add(t0); - - t0.copy(a); t0.add(c); - t1.copy(y.a); t1.add(y.c); - t0.mul(t1); - z2.add(t0); - - t0.copy(c); t0.mul(y.c); - t1.copy(t0); t1.neg(); - - z2.norm(); - z3.norm(); - b.norm(); - - c.copy(z2); c.add(t1); - z3.add(t1); - t0.times_i(); - b.add(t0); - - z3.times_i(); - a.copy(z0); a.add(z3); - norm(); - } - -/* Special case of multiplication arises from special form of ATE pairing line function */ - public void smul(FP12 y) - { - FP4 z0=new FP4(a); - FP4 z2=new FP4(b); - FP4 z3=new FP4(b); - FP4 t0=new FP4(0); - FP4 t1=new FP4(y.a); - - z0.mul(y.a); - z2.pmul(y.b.real()); - b.add(a); - t1.real().add(y.b.real()); - - b.mul(t1); - z3.add(c); - z3.pmul(y.b.real()); - - t0.copy(z0); t0.neg(); - t1.copy(z2); t1.neg(); - - b.add(t0); - b.norm(); - - b.add(t1); - z3.add(t1); - z2.add(t0); - - t0.copy(a); t0.add(c); - t0.mul(y.a); - c.copy(z2); c.add(t0); - - z3.times_i(); - a.copy(z0); a.add(z3); - - norm(); - } - -/* this=1/this */ - public void inverse() - { - FP4 f0=new FP4(a); - FP4 f1=new FP4(b); - FP4 f2=new FP4(a); - FP4 f3=new FP4(0); - - norm(); - f0.sqr(); - f1.mul(c); - f1.times_i(); - f0.sub(f1); - - f1.copy(c); f1.sqr(); - f1.times_i(); - f2.mul(b); - f1.sub(f2); - - f2.copy(b); f2.sqr(); - f3.copy(a); f3.mul(c); - f2.sub(f3); - - f3.copy(b); f3.mul(f2); - f3.times_i(); - a.mul(f0); - f3.add(a); - c.mul(f1); - c.times_i(); - - f3.add(c); - f3.inverse(); - a.copy(f0); a.mul(f3); - b.copy(f1); b.mul(f3); - c.copy(f2); c.mul(f3); - } - -/* this=this^p using Frobenius */ - public void frob(FP2 f) - { - FP2 f2=new FP2(f); - FP2 f3=new FP2(f); - - f2.sqr(); - f3.mul(f2); - - a.frob(f3); - b.frob(f3); - c.frob(f3); - - b.pmul(f); - c.pmul(f2); - } - -/* trace function */ - public FP4 trace() - { - FP4 t=new FP4(0); - t.copy(a); - t.imul(3); - t.reduce(); - return t; - } - -/* convert from byte array to FP12 */ - public static FP12 fromBytes(byte[] w) - { - BIG a,b; - FP2 c,d; - FP4 e,f,g; - byte[] t=new byte[ROM.MODBYTES]; - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i]; - a=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+ROM.MODBYTES]; - b=BIG.fromBytes(t); - c=new FP2(a,b); - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+2*ROM.MODBYTES]; - a=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+3*ROM.MODBYTES]; - b=BIG.fromBytes(t); - d=new FP2(a,b); - - e=new FP4(c,d); - - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+4*ROM.MODBYTES]; - a=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+5*ROM.MODBYTES]; - b=BIG.fromBytes(t); - c=new FP2(a,b); - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+6*ROM.MODBYTES]; - a=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+7*ROM.MODBYTES]; - b=BIG.fromBytes(t); - d=new FP2(a,b); - - f=new FP4(c,d); - - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+8*ROM.MODBYTES]; - a=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+9*ROM.MODBYTES]; - b=BIG.fromBytes(t); - c=new FP2(a,b); - - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+10*ROM.MODBYTES]; - a=BIG.fromBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) t[i]=w[i+11*ROM.MODBYTES]; - b=BIG.fromBytes(t); - d=new FP2(a,b); - - g=new FP4(c,d); - - return new FP12(e,f,g); - } - -/* convert this to byte array */ - public void toBytes(byte[] w) - { - byte[] t=new byte[ROM.MODBYTES]; - a.geta().getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i]=t[i]; - a.geta().getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+ROM.MODBYTES]=t[i]; - a.getb().getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+2*ROM.MODBYTES]=t[i]; - a.getb().getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+3*ROM.MODBYTES]=t[i]; - - b.geta().getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+4*ROM.MODBYTES]=t[i]; - b.geta().getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+5*ROM.MODBYTES]=t[i]; - b.getb().getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+6*ROM.MODBYTES]=t[i]; - b.getb().getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+7*ROM.MODBYTES]=t[i]; - - c.geta().getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+8*ROM.MODBYTES]=t[i]; - c.geta().getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+9*ROM.MODBYTES]=t[i]; - c.getb().getA().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+10*ROM.MODBYTES]=t[i]; - c.getb().getB().toBytes(t); - for (int i=0;i<ROM.MODBYTES;i++) w[i+11*ROM.MODBYTES]=t[i]; - } - -/* convert to hex string */ - public String toString() - { - return ("["+a.toString()+","+b.toString()+","+c.toString()+"]"); - } - -/* this=this^e */ -/* Note this is simple square and multiply, so not side-channel safe */ - public FP12 pow(BIG e) - { - norm(); - e.norm(); - FP12 w=new FP12(this); - BIG z=new BIG(e); - FP12 r=new FP12(1); - - while (true) - { - int bt=z.parity(); - z.fshr(1); - if (bt==1) r.mul(w); - if (z.iszilch()) break; - w.usqr(); - } - r.reduce(); - return r; - } - -/* constant time powering by small integer of max length bts */ - public void pinpow(int e,int bts) - { - int i,b; - FP12 [] R=new FP12[2]; - R[0]=new FP12(1); - R[1]=new FP12(this); - for (i=bts-1;i>=0;i--) - { - b=(e>>i)&1; - R[1-b].mul(R[b]); - R[b].usqr(); - } - this.copy(R[0]); - } - -/* p=q0^u0.q1^u1.q2^u2.q3^u3 */ -/* Timing attack secure, but not cache attack secure */ - - public static FP12 pow4(FP12[] q,BIG[] u) - { - int i,j,nb,m; - int[] a=new int[4]; - FP12 [] g=new FP12[8]; - FP12 [] s=new FP12[2]; - FP12 c=new FP12(1); - FP12 p=new FP12(0); - BIG [] t=new BIG[4]; - BIG mt=new BIG(0); - byte[] w=new byte[ROM.NLEN*ROM.BASEBITS+1]; - - for (i=0;i<4;i++) - t[i]=new BIG(u[i]); - - s[0]=new FP12(0); - s[1]=new FP12(0); - - g[0]=new FP12(q[0]); s[0].copy(q[1]); s[0].conj(); g[0].mul(s[0]); - g[1]=new FP12(g[0]); - g[2]=new FP12(g[0]); - g[3]=new FP12(g[0]); - g[4]=new FP12(q[0]); g[4].mul(q[1]); - g[5]=new FP12(g[4]); - g[6]=new FP12(g[4]); - g[7]=new FP12(g[4]); - - s[1].copy(q[2]); s[0].copy(q[3]); s[0].conj(); s[1].mul(s[0]); - s[0].copy(s[1]); s[0].conj(); g[1].mul(s[0]); - g[2].mul(s[1]); - g[5].mul(s[0]); - g[6].mul(s[1]); - s[1].copy(q[2]); s[1].mul(q[3]); - s[0].copy(s[1]); s[0].conj(); g[0].mul(s[0]); - g[3].mul(s[1]); - g[4].mul(s[0]); - g[7].mul(s[1]); - -/* if power is even add 1 to power, and add q to correction */ - - for (i=0;i<4;i++) - { - if (t[i].parity()==0) - { - t[i].inc(1); t[i].norm(); - c.mul(q[i]); - } - mt.add(t[i]); mt.norm(); - } - c.conj(); - nb=1+mt.nbits(); - -/* convert exponent to signed 1-bit window */ - for (j=0;j<nb;j++) - { - for (i=0;i<4;i++) - { - a[i]=(t[i].lastbits(2)-2); - t[i].dec(a[i]); t[i].norm(); - t[i].fshr(1); - } - w[j]=(byte)(8*a[0]+4*a[1]+2*a[2]+a[3]); - } - w[nb]=(byte)(8*t[0].lastbits(2)+4*t[1].lastbits(2)+2*t[2].lastbits(2)+t[3].lastbits(2)); - p.copy(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; - s[0].copy(g[j]); s[1].copy(g[j]); s[1].conj(); - p.usqr(); - p.mul(s[m&1]); - } - p.mul(c); /* apply correction */ - p.reduce(); - return p; - } - -/* - public static void main(String[] args) { - BIG p=new BIG(ROM.Modulus); - FP2 w0,w1; - BIG a=new BIG(0); - BIG b=new BIG(0); - - a.zero(); b.zero(); a.inc(1); b.inc(2); - w0=new FP2(a,b); - a.zero(); b.zero(); a.inc(3); b.inc(4); - w1=new FP2(a,b); - FP4 t0=new FP4(w0,w1); - - a.zero(); b.zero(); a.inc(5); b.inc(6); - w0=new FP2(a,b); - a.zero(); b.zero(); a.inc(7); b.inc(8); - w1=new FP2(a,b); - FP4 t1=new FP4(w0,w1); - - a.zero(); b.zero(); a.inc(9); b.inc(10); - w0=new FP2(a,b); - a.zero(); b.zero(); a.inc(11); b.inc(12); - w1=new FP2(a,b); - FP4 t2=new FP4(w0,w1); - - FP12 w=new FP12(t0,t1,t2); - FP12 t=new FP12(w); - - System.out.println("w= "+w.toString()); - - a=new BIG(ROM.CURVE_Fra); - b=new BIG(ROM.CURVE_Frb); - - FP2 f=new FP2(a,b); - - w.frob(f); - System.out.println("w= "+w.toString()); - - w=t.pow(p); - - System.out.println("w= "+w.toString()); - - w.inverse(); - - System.out.println("1/w= "+w.toString()); - - w.inverse(); - - System.out.println("w= "+w.toString()); - - t.copy(w); - w.conj(); - t.inverse(); - w.mul(t); - - System.out.println("w^(p^6-1)= "+w.toString()); - - t.copy(w); - w.frob(f); - w.frob(f); - w.mul(t); - - System.out.println("w^(p^6-1)(p^2+1)= "+w.toString()); - - t.copy(w); - - t.inverse(); - w.conj(); - - System.out.println("w= "+w.toString()); - System.out.println("t= "+t.toString()); - } */ -}
