http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/java/DBIG64.java ---------------------------------------------------------------------- diff --git a/version22/java/DBIG64.java b/version22/java/DBIG64.java new file mode 100644 index 0000000..4596077 --- /dev/null +++ b/version22/java/DBIG64.java @@ -0,0 +1,306 @@ +/* +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/c25f9e5c/version22/java/ECDH.java ---------------------------------------------------------------------- diff --git a/version22/java/ECDH.java b/version22/java/ECDH.java new file mode 100644 index 0000000..12b7589 --- /dev/null +++ b/version22/java/ECDH.java @@ -0,0 +1,581 @@ +/* +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/c25f9e5c/version22/java/ECP.java ---------------------------------------------------------------------- diff --git a/version22/java/ECP.java b/version22/java/ECP.java new file mode 100644 index 0000000..d315e45 --- /dev/null +++ b/version22/java/ECP.java @@ -0,0 +1,917 @@ +/* +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/c25f9e5c/version22/java/ECP2.java ---------------------------------------------------------------------- diff --git a/version22/java/ECP2.java b/version22/java/ECP2.java new file mode 100644 index 0000000..ec9f674 --- /dev/null +++ b/version22/java/ECP2.java @@ -0,0 +1,624 @@ +/* +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/c25f9e5c/version22/java/FF.java ---------------------------------------------------------------------- diff --git a/version22/java/FF.java b/version22/java/FF.java new file mode 100644 index 0000000..a6ee1fe --- /dev/null +++ b/version22/java/FF.java @@ -0,0 +1,941 @@ +/* +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/c25f9e5c/version22/java/FP.java ---------------------------------------------------------------------- diff --git a/version22/java/FP.java b/version22/java/FP.java new file mode 100644 index 0000000..bafa46b --- /dev/null +++ b/version22/java/FP.java @@ -0,0 +1,345 @@ +/* +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/c25f9e5c/version22/java/FP12.java ---------------------------------------------------------------------- diff --git a/version22/java/FP12.java b/version22/java/FP12.java new file mode 100644 index 0000000..7ef0607 --- /dev/null +++ b/version22/java/FP12.java @@ -0,0 +1,641 @@ +/* +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()); + } */ +}
