http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/ECP2.js ---------------------------------------------------------------------- diff --git a/version22/js/ECP2.js b/version22/js/ECP2.js new file mode 100644 index 0000000..6c75271 --- /dev/null +++ b/version22/js/ECP2.js @@ -0,0 +1,604 @@ +/* + 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 */ + +/* Constructor, set this=O */ +var ECP2=function() +{ + this.x=new FP2(0); + this.y=new FP2(1); + this.z=new FP2(1); + this.INF=true; +}; + +ECP2.prototype={ +/* Test this=O? */ + is_infinity: function() + { + return this.INF; + }, +/* copy this=P */ + copy: function(P) + { + this.x.copy(P.x); + this.y.copy(P.y); + this.z.copy(P.z); + this.INF=P.INF; + }, +/* set this=O */ + inf: function() + { + this.INF=true; + this.x.zero(); + this.y.zero(); + this.z.zero(); + }, + +/* conditional move of Q to P dependant on d */ + cmove: function(Q,d) + { + this.x.cmove(Q.x,d); + this.y.cmove(Q.y,d); + this.z.cmove(Q.z,d); + + var bd=(d!==0)?true:false; + this.INF^=(this.INF^Q.INF)&bd; + }, + +/* Constant time select from pre-computed table */ + select: function(W,b) + { + var MP=new ECP2(); + var m=b>>31; + var babs=(b^m)-m; + + babs=(babs-1)/2; + + this.cmove(W[0],ECP2.teq(babs,0)); // conditional move + this.cmove(W[1],ECP2.teq(babs,1)); + this.cmove(W[2],ECP2.teq(babs,2)); + this.cmove(W[3],ECP2.teq(babs,3)); + this.cmove(W[4],ECP2.teq(babs,4)); + this.cmove(W[5],ECP2.teq(babs,5)); + this.cmove(W[6],ECP2.teq(babs,6)); + this.cmove(W[7],ECP2.teq(babs,7)); + + MP.copy(this); + MP.neg(); + this.cmove(MP,(m&1)); + }, + +/* Test P == Q */ + + equals: function(Q) { + if (this.is_infinity() && Q.is_infinity()) return true; + if (this.is_infinity() || Q.is_infinity()) return false; + + var zs2=new FP2(this.z); /*zs2.copy(this.z);*/ zs2.sqr(); + var zo2=new FP2(Q.z); /*zo2.copy(Q.z);*/ zo2.sqr(); + var zs3=new FP2(zs2); /*zs3.copy(zs2);*/ zs3.mul(this.z); + var zo3=new FP2(zo2); /*zo3.copy(zo2);*/ zo3.mul(Q.z); + zs2.mul(Q.x); + zo2.mul(this.x); + if (!zs2.equals(zo2)) return false; + zs3.mul(Q.y); + zo3.mul(this.y); + if (!zs3.equals(zo3)) return false; + + return true; + }, +/* set this=-this */ + neg: function() + { + if (this.is_infinity()) return; + this.y.neg(); this.y.norm(); + return; + }, +/* convert this to affine, from (x,y,z) to (x,y) */ + affine: function() + { + if (this.is_infinity()) return; + var one=new FP2(1); + if (this.z.equals(one)) return; + this.z.inverse(); + + var z2=new FP2(this.z); //z2.copy(this.z); + z2.sqr(); + this.x.mul(z2); this.x.reduce(); + this.y.mul(z2); + this.y.mul(this.z); this.y.reduce(); + this.z=one; + }, +/* extract affine x as FP2 */ + getX: function() + { + this.affine(); + return this.x; + }, +/* extract affine y as FP2 */ + getY: function() + { + this.affine(); + return this.y; + }, +/* extract projective x */ + getx: function() + { + return this.x; + }, +/* extract projective y */ + gety: function() + { + return this.y; + }, +/* extract projective z */ + getz: function() + { + return this.z; + }, +/* convert this to byte array */ + toBytes: function(b) + { + var i,t=[]; + this.affine(); + this.x.getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) + b[i]=t[i]; + this.x.getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) + b[i+ROM.MODBYTES]=t[i]; + + this.y.getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) + b[i+2*ROM.MODBYTES]=t[i]; + this.y.getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) + b[i+3*ROM.MODBYTES]=t[i]; + }, +/* convert this to hex string */ + toString: function() + { + if (this.is_infinity()) return "infinity"; + this.affine(); + return "("+this.x.toString()+","+this.y.toString()+")"; + }, +/* set this=(x,y) */ + setxy: function(ix,iy) + { + this.x.copy(ix); + this.y.copy(iy); + this.z.one(); + + var rhs=ECP2.RHS(this.x); + + var y2=new FP2(this.y); //y2.copy(this.y); + y2.sqr(); + if (y2.equals(rhs)) this.INF=false; + else this.inf(); + }, + +/* set this=(x,.) */ + setx: function(ix) + { + this.x.copy(ix); + this.z.one(); + + var rhs=ECP2.RHS(this.x); + + if (rhs.sqrt()) + { + this.y.copy(rhs); + this.INF=false; + } + else this.inf(); + }, + +/* set this*=q, where q is Modulus, using Frobenius */ + frob: function(X) + { + if (this.INF) return; + var X2=new FP2(X); //X2.copy(X); + X2.sqr(); + this.x.conj(); + this.y.conj(); + this.z.conj(); + this.z.reduce(); + this.x.mul(X2); + this.y.mul(X2); + this.y.mul(X); + }, +/* this+=this */ + dbl: function() + { + if (this.INF) return -1; + if (this.y.iszilch()) + { + this.inf(); + return -1; + } + + var w1=new FP2(this.x); //w1.copy(this.x); + var w2=new FP2(0); + var w3=new FP2(this.x); //w3.copy(this.x); + var w8=new FP2(this.x); //w8.copy(this.x); + + w1.sqr(); + w8.copy(w1); + w8.imul(3); + + w2.copy(this.y); w2.sqr(); + w3.copy(this.x); w3.mul(w2); + w3.imul(4); + w1.copy(w3); w1.neg(); + + + this.x.copy(w8); this.x.sqr(); + this.x.add(w1); + this.x.add(w1); + this.x.norm(); + + this.z.mul(this.y); + this.z.add(this.z); + + w2.add(w2); + w2.sqr(); + w2.add(w2); + w3.sub(this.x); + this.y.copy(w8); this.y.mul(w3); + this.y.sub(w2); + this.y.norm(); + this.z.norm(); + + return 1; + }, +/* this+=Q - return 0 for add, 1 for double, -1 for O */ +/* this+=Q */ + add: function(Q) + { + if (this.INF) + { + this.copy(Q); + return -1; + } + if (Q.INF) return -1; + + var aff=false; + + if (Q.z.isunity()) aff=true; + + var A,C; + var B=new FP2(this.z); + var D=new FP2(this.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(this.x); + C.mul(this.y); + } + else + { + A=new FP2(this.x); + C=new FP2(this.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()) + { + this.dbl(); + return 1; + } + else + { + this.INF=true; + return -1; + } + } + + if (!aff) this.z.mul(Q.z); + this.z.mul(B); + + var e=new FP2(B); e.sqr(); + B.mul(e); + A.mul(e); + + e.copy(A); + e.add(A); e.add(B); + this.x.copy(D); this.x.sqr(); this.x.sub(e); + + A.sub(this.x); + this.y.copy(A); this.y.mul(D); + C.mul(B); this.y.sub(C); + + this.x.norm(); + this.y.norm(); + this.z.norm(); + return 0; + }, +/* this-=Q */ + sub: function(Q) + { + Q.neg(); + var D=this.add(Q); + Q.neg(); + return D; + }, + +/* P*=e */ + mul: function(e) + { +/* fixed size windows */ + var i,b,nb,m,s,ns; + var mt=new BIG(); + var t=new BIG(); + var C=new ECP2(); + var P=new ECP2(); + var Q=new ECP2(); + var W=[]; + var w=[]; + + if (this.is_infinity()) return new ECP2(); + + this.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 + + ECP2.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+Math.floor((t.nbits()+3)/4); + +// convert exponent to signed 4-bit window + for (i=0;i<nb;i++) + { + w[i]=(t.lastbits(5)-16); + t.dec(w[i]); t.norm(); + t.fshr(4); + } + w[nb]=t.lastbits(5); + + P.copy(W[Math.floor((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; + } +}; + +/* convert from byte array to point */ +ECP2.fromBytes=function(b) +{ + var i,t=[]; + var ra,rb; + + for (i=0;i<ROM.MODBYTES;i++) t[i]=b[i]; + ra=BIG.fromBytes(t); + for (i=0;i<ROM.MODBYTES;i++) t[i]=b[i+ROM.MODBYTES]; + rb=BIG.fromBytes(t); + + var rx=new FP2(ra,rb); //rx.bset(ra,rb); + + for (i=0;i<ROM.MODBYTES;i++) t[i]=b[i+2*ROM.MODBYTES]; + ra=BIG.fromBytes(t); + for (i=0;i<ROM.MODBYTES;i++) t[i]=b[i+3*ROM.MODBYTES]; + rb=BIG.fromBytes(t); + + var ry=new FP2(ra,rb); //ry.bset(ra,rb); + + var P=new ECP2(); + P.setxy(rx,ry); + return P; +}; + +/* Calculate RHS of curve equation x^3+B */ +ECP2.RHS=function(x) +{ + x.norm(); + var r=new FP2(x); //r.copy(x); + r.sqr(); + + var c=new BIG(0); c.rcopy(ROM.CURVE_B); + var b=new FP2(c); //b.bseta(c); + b.div_ip(); + r.mul(x); + r.add(b); + + r.reduce(); + return r; +}; + +/* normalises m-array of ECP2 points. Requires work vector of m FP2s */ + +ECP2.multiaffine=function(m,P) +{ + var i; + var t1=new FP2(0); + var t2=new FP2(0); + var work=[]; + + 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=u0.Q0+u1*Q1+u2*Q2+u3*Q3 */ +ECP2.mul4=function(Q,u) +{ + var i,j,nb; + var a=[]; + var T=new ECP2(); + var C=new ECP2(); + var P=new ECP2(); + var W=[]; + var mt=new BIG(); + var t=[]; + var w=[]; + + 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); + + ECP2.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]=(t[i].lastbits(2)-2); + t[i].dec(a[i]); t[i].norm(); + t[i].fshr(1); + } + w[j]=(8*a[0]+4*a[1]+2*a[2]+a[3]); + } + w[nb]=(8*t[0].lastbits(2)+4*t[1].lastbits(2)+2*t[2].lastbits(2)+t[3].lastbits(2)); + + P.copy(W[Math.floor((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; +}; + +/* return 1 if b==c, no branching */ +ECP2.teq=function(b,c) +{ + var x=b^c; + x-=1; // if x=0, x now -1 + return ((x>>31)&1); +}; +
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/FF.js ---------------------------------------------------------------------- diff --git a/version22/js/FF.js b/version22/js/FF.js new file mode 100644 index 0000000..94dedc6 --- /dev/null +++ b/version22/js/FF.js @@ -0,0 +1,947 @@ +/* + 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 FF number class */ + +/* General purpose Constructor */ +var FF = function(n) { + this.v=new Array(n); + this.length=n; + for (var i=0;i<n;i++) + this.v[i]=new BIG(0); +}; + +FF.prototype={ +/* set to zero */ + + P_EXCESS: function() + { + return ((this.v[this.length-1].get(ROM.NLEN-1)&FF.P_OMASK)>>(FF.P_TBITS)); + }, + + zero: function() + { + for (var i=0;i<this.length;i++) this.v[i].zero(); + return this; + }, + + getlen: function() + { + return this.length; + }, + +/* set to integer */ + set: function(m) + { + this.zero(); + this.v[0].set(0,(m&ROM.BMASK)); + this.v[0].set(1,(m>>ROM.BASEBITS)); + }, +/* copy from FF b */ + copy: function(b) + { + for (var i=0;i<this.length;i++) + { + this.v[i].copy(b.v[i]); + } + }, +/* copy from FF b */ + rcopy: function(b) + { + for (var i=0;i<this.length;i++) + { + this.v[i].rcopy(b[i]); + } + }, +/* x=y<<n */ + dsucopy: function(b) + { + for (var i=0;i<b.length;i++) + { + this.v[b.length+i].copy(b.v[i]); + this.v[i].zero(); + } + }, +/* x=y */ + dscopy: function(b) + { + for (var i=0;i<b.length;i++) + { + this.v[i].copy(b.v[i]); + this.v[b.length+i].zero(); + } + }, + +/* x=y>>n */ + sducopy: function(b) + { + for (var i=0;i<this.length;i++) + { + this.v[i].copy(b.v[this.length+i]); + } + }, + one: function() + { + this.v[0].one(); + for (var i=1;i<this.length;i++) + { + this.v[i].zero(); + } + }, +/* test equals 0 */ + iszilch: function() + { + for (var i=0;i<this.length;i++) + { + if (!this.v[i].iszilch()) return false; + } + return true; + }, +/* shift right by BIGBITS-bit words */ + shrw: function(n) + { + for (var i=0;i<n;i++) + { + this.v[i].copy(this.v[i+n]); + this.v[i+n].zero(); + } + }, + +/* shift left by BIGBITS-bit words */ + shlw: function(n) + { + for (var i=0;i<n;i++) + { + this.v[n+i].copy(this.v[i]); + this.v[i].zero(); + } + }, +/* extract last bit */ + parity: function() + { + return this.v[0].parity(); + }, + + lastbits: function(m) + { + return this.v[0].lastbits(m); + }, + + +/* recursive add */ + radd: function(vp,x,xp,y,yp,n) + { + for (var i=0;i<n;i++) + { + this.v[vp+i].copy(x.v[xp+i]); + this.v[vp+i].add(y.v[yp+i]); + } + }, + +/* recursive inc */ + rinc: function(vp,y,yp,n) + { + for (var i=0;i<n;i++) + { + this.v[vp+i].add(y.v[yp+i]); + } + }, + +/* recursive sub */ + rsub: function(vp,x,xp,y,yp,n) + { + for (var i=0;i<n;i++) + { + this.v[vp+i].copy(x.v[xp+i]); + this.v[vp+i].sub(y.v[yp+i]); + } + }, + +/* recursive dec */ + rdec: function(vp,y,yp,n) + { + for (var i=0;i<n;i++) + { + this.v[vp+i].sub(y.v[yp+i]); + } + }, + +/* simple add */ + add: function(b) + { + for (var i=0;i<this.length;i++) + this.v[i].add(b.v[i]); + }, + +/* simple sub */ + sub: function(b) + { + for (var i=0;i<this.length;i++) + this.v[i].sub(b.v[i]); + }, + +/* reverse sub */ + revsub: function(b) + { + for (var i=0;i<this.length;i++) + this.v[i].rsub(b.v[i]); + }, + +/* increment/decrement by a small integer */ + inc: function(m) + { + this.v[0].inc(m); + this.norm(); + }, + + dec: function(m) + { + this.v[0].dec(m); + this.norm(); + }, + + /* normalise - but hold any overflow in top part unless n<0 */ + rnorm: function(vp,n) + { + var trunc=false; + var i,carry; + if (n<0) + { /* -v n signals to do truncation */ + n=-n; + trunc=true; + } + for (i=0;i<n-1;i++) + { + carry=this.v[vp+i].norm(); + this.v[vp+i].xortop(carry<<FF.P_TBITS); + this.v[vp+i+1].inc(carry); + } + carry=this.v[vp+n-1].norm(); + if (trunc) + this.v[vp+n-1].xortop(carry<<FF.P_TBITS); + return this; + }, + norm: function() + { + this.rnorm(0,this.length); + }, + +/* shift left by one bit */ + shl: function() + { + var i,carry,delay_carry=0; + for (i=0;i<this.length-1;i++) + { + carry=this.v[i].fshl(1); + this.v[i].inc(delay_carry); + this.v[i].xortop(carry<<FF.P_TBITS); + delay_carry=carry; + } + this.v[this.length-1].fshl(1); + this.v[this.length-1].inc(delay_carry); + }, + +/* shift right by one bit */ + shr: function() + { + var i,carry; + for (i=this.length-1;i>0;i--) + { + carry=this.v[i].fshr(1); + this.v[i-1].ortop(carry<<FF.P_TBITS); + } + this.v[0].fshr(1); + }, + +/* Convert to Hex String */ + toString: function() + { + this.norm(); + var s=""; + + for (var i=this.length-1;i>=0;i--) + { + s+=this.v[i].toString(); + } + return s; + }, +/* Convert FFs to/from byte arrays */ + toBytes: function(b) + { + for (var i=0;i<this.length;i++) + { + this.v[i].tobytearray(b,(this.length-i-1)*ROM.MODBYTES); + } + }, + +/* z=x*y, t is workspace */ + karmul: function(vp,x,xp,y,yp,t,tp,n) + { + var nd2; + if (n==1) + { + var d=BIG.mul(x.v[xp],y.v[yp]); + this.v[vp+1]=d.split(8*ROM.MODBYTES); + this.v[vp].copy(d); + return; + } + nd2=n/2; + this.radd(vp,x,xp,x,xp+nd2,nd2); + this.rnorm(vp,nd2); /* Important - required for 32-bit build */ + this.radd(vp+nd2,y,yp,y,yp+nd2,nd2); + this.rnorm(vp+nd2,nd2); /* Important - required for 32-bit build */ + t.karmul(tp,this,vp,this,vp+nd2,t,tp+n,nd2); + this.karmul(vp,x,xp,y,yp,t,tp+n,nd2); + this.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); + this.rinc(vp+nd2,t,tp,n); + this.rnorm(vp,2*n); + }, + + karsqr: function(vp,x,xp,t,tp,n) + { + var nd2; + if (n==1) + { + var d=BIG.sqr(x.v[xp]); + this.v[vp+1].copy(d.split(8*ROM.MODBYTES)); + this.v[vp].copy(d); + return; + } + + nd2=n/2; + this.karsqr(vp,x,xp,t,tp+n,nd2); + this.karsqr(vp+n,x,xp+nd2,t,tp+n,nd2); + t.karmul(tp,x,xp,x,xp+nd2,t,tp+n,nd2); + this.rinc(vp+nd2,t,tp,n); + this.rinc(vp+nd2,t,tp,n); + this.rnorm(vp+nd2,n); + }, + + karmul_lower: function(vp,x,xp,y,yp,t,tp,n) + { /* Calculates Least Significant bottom half of x*y */ + var nd2; + if (n==1) + { /* only calculate bottom half of product */ + this.v[vp].copy(BIG.smul(x.v[xp],y.v[yp])); + return; + } + nd2=n/2; + + this.karmul(vp,x,xp,y,yp,t,tp+n,nd2); + t.karmul_lower(tp,x,xp+nd2,y,yp,t,tp+n,nd2); + this.rinc(vp+nd2,t,tp,nd2); + t.karmul_lower(tp,x,xp,y,yp+nd2,t,tp+n,nd2); + + this.rinc(vp+nd2,t,tp,nd2); + this.rnorm(vp+nd2,-nd2); /* truncate it */ + }, + + karmul_upper: function(x,y,t,n) + { /* Calculates Most Significant upper half of x*y, given lower part */ + var nd2; + + nd2=n/2; + this.radd(n,x,0,x,nd2,nd2); + this.radd(n+nd2,y,0,y,nd2,nd2); + this.rnorm(n,nd2); + this.rnorm(n+nd2,nd2); + + t.karmul(0,this,n+nd2,this,n,t,n,nd2); /* t = (a0+a1)(b0+b1) */ + this.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 */ + this.rinc(nd2,this,0,nd2); /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */ + this.rdec(nd2,t,0,nd2); /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */ + this.rnorm(0,-n); /* a0b0 now in z - truncate it */ + t.rdec(0,this,0,n); /* (a0+a1)(b0+b1) - a0b0 */ + this.rinc(nd2,t,0,n); + + this.rnorm(nd2,n); + }, + +/* return low part of product this*y */ + lmul: function(y) + { + var n=this.length; + var t=new FF(2*n); + var x=new FF(n); x.copy(this); + this.karmul_lower(0,x,0,y,0,t,0,n); + }, + +/* Set b=b mod c */ + mod: function(c) + { + var k=0; + + this.norm(); + if (FF.comp(this,c)<0) + return; + do + { + c.shl(); + k++; + } while (FF.comp(this,c)>=0); + + while (k>0) + { + c.shr(); + if (FF.comp(this,c)>=0) + { + this.sub(c); + this.norm(); + } + k--; + } + }, + +/* return This mod modulus, N is modulus, ND is Montgomery Constant */ + reduce: function(N,ND) + { /* fast karatsuba Montgomery reduction */ + var n=N.length; + var t=new FF(2*n); + var r=new FF(n); + var m=new FF(n); + + r.sducopy(this); + m.karmul_lower(0,this,0,ND,0,t,0,n); + this.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 */ + dmod: function(b) + { + var k,n=b.length; + var m=new FF(2*n); + var x=new FF(2*n); + var r=new FF(n); + + x.copy(this); + x.norm(); + m.dsucopy(b); k=ROM.BIGBITS*n; + + while (FF.comp(x,m)>=0) + { + x.sub(m); + x.norm(); + } + + while (k>0) + { + m.shr(); + + if (FF.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 */ + invmodp: function(p) + { + var n=p.length; + + var u=new FF(n); + var v=new FF(n); + var x1=new FF(n); + var x2=new FF(n); + var t=new FF(n); + var one=new FF(n); + + one.one(); + u.copy(this); + v.copy(p); + x1.copy(one); + x2.zero(); + + // reduce n in here as well! + while (FF.comp(u,one)!==0 && FF.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 (FF.comp(u,v)>=0) + { + + u.sub(v); + u.norm(); + if (FF.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 (FF.comp(x2,x1)>=0) x2.sub(x1); + else + { + t.copy(p); + t.sub(x1); + x2.add(t); + } + x2.norm(); + } + } + if (FF.comp(u,one)===0) + this.copy(x1); + else + this.copy(x2); + }, + +/* nresidue mod m */ + nres: function(m) + { + var n=m.length; + var d=new FF(2*n); + d.dsucopy(this); + this.copy(d.dmod(m)); + }, + + redc: function(m,ND) + { + var n=m.length; + var d=new FF(2*n); + + this.mod(m); + d.dscopy(this); + + this.copy(d.reduce(m,ND)); + this.mod(m); + }, + + mod2m: function(m) + { + for (var i=m;i<this.length;i++) + this.v[i].zero(); + }, + + /* U=1/a mod 2^m - Arazi & Qi */ + invmod2m: function() + { + var i,n=this.length; + + var b=new FF(n); + var c=new FF(n); + var U=new FF(n); + + var t; + + U.zero(); + U.v[0].copy(this.v[0]); + U.v[0].invmod2m(); + + for (i=1;i<n;i<<=1) + { + b.copy(this); b.mod2m(i); + t=FF.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; + }, + + random: function(rng) + { + var n=this.length; + for (var i=0;i<n;i++) + { + this.v[i].copy(BIG.random(rng)); + } + /* make sure top bit is 1 */ + while (this.v[n-1].nbits()<ROM.MODBYTES*8) this.v[n-1].copy(BIG.random(rng)); + + }, + + /* generate random x */ + randomnum: function(p,rng) + { + var n=this.length; + var d=new FF(2*n); + + for (var i=0;i<2*n;i++) + { + d.v[i].copy(BIG.random(rng)); + } + this.copy(d.dmod(p)); + }, + + /* this*=y mod p */ + modmul: function(y,p,nd) + { + var ex=this.P_EXCESS(); + var ey=y.P_EXCESS(); + if ((ex+1)>=Math.floor((FF.P_FEXCESS-1)/(ey+1))) this.mod(p); + var d=FF.mul(this,y); + this.copy(d.reduce(p,nd)); + }, + + /* this*=y mod p */ + modsqr: function(p,nd) + { + var ex=this.P_EXCESS(); + if ((ex+1)>=Math.floor((FF.P_FEXCESS-1)/(ex+1))) this.mod(p); + var d=FF.sqr(this); + this.copy(d.reduce(p,nd)); + }, + + /* this=this^e mod p using side-channel resistant Montgomery Ladder, for large e */ + skpow: function(e,p) + { + var i,b,n=p.length; + var R0=new FF(n); + var R1=new FF(n); + var ND=p.invmod2m(); + + this.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[Math.floor(i/ROM.BIGBITS)].bit(i%ROM.BIGBITS); + + this.copy(R0); + this.modmul(R1,p,ND); + + FF.cswap(R0,R1,b); + R0.modsqr(p,ND); + + R1.copy(this); + FF.cswap(R0,R1,b); + + } + + this.copy(R0); + this.redc(p,ND); + }, + + /* this =this^e mod p using side-channel resistant Montgomery Ladder, for short e */ + skspow: function(e,p) + { + var i,b,n=p.length; + var R0=new FF(n); + var R1=new FF(n); + var ND=p.invmod2m(); + + this.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); + this.copy(R0); + this.modmul(R1,p,ND); + + FF.cswap(R0,R1,b); + R0.modsqr(p,ND); + + R1.copy(this); + FF.cswap(R0,R1,b); + } + this.copy(R0); + this.redc(p,ND); + }, + + /* raise to an integer power - right-to-left method */ + power: function(e,p) + { + var n=p.length; + var f=true; + var w=new FF(n); + var ND=p.invmod2m(); + + w.copy(this); + w.nres(p); + + if (e==2) + { + this.copy(w); + this.modsqr(p,ND); + } + else for (; ; ) + { + if (e%2==1) + { + if (f) this.copy(w); + else + { + ROM.debug=true; + this.modmul(w,p,ND); + ROM.debug=false; + } + f=false; + + } + e>>=1; + if (e===0) break; + w.modsqr(p,ND); + } + + this.redc(p,ND); + }, + + /* this=this^e mod p, faster but not side channel resistant */ + pow: function(e,p) + { + var i,b,n=p.length; + var w=new FF(n); + var ND=p.invmod2m(); + + w.copy(this); + this.one(); + this.nres(p); + w.nres(p); + for (i=8*ROM.MODBYTES*n-1;i>=0;i--) + { + this.modsqr(p,ND); + b=e.v[Math.floor(i/ROM.BIGBITS)].bit(i%ROM.BIGBITS); + if (b==1) this.modmul(w,p,ND); + } + this.redc(p,ND); + }, + + /* double exponentiation r=x^e.y^f mod p */ + pow2: function(e,y,f,p) + { + var i,eb,fb,n=p.length; + var xn=new FF(n); + var yn=new FF(n); + var xy=new FF(n); + var ND=p.invmod2m(); + + xn.copy(this); + yn.copy(y); + xn.nres(p); + yn.nres(p); + xy.copy(xn); xy.modmul(yn,p,ND); + this.one(); + this.nres(p); + + for (i=8*ROM.MODBYTES-1;i>=0;i--) + { + eb=e.bit(i); + fb=f.bit(i); + this.modsqr(p,ND); + if (eb==1) + { + if (fb==1) this.modmul(xy,p,ND); + else this.modmul(xn,p,ND); + } + else + { + if (fb==1) this.modmul(yn,p,ND); + } + } + this.redc(p,ND); + }, + + /* quick and dirty check for common factor with n */ + cfactor: function(s) + { + var r,n=this.length; + var g; + + var x=new FF(n); + var 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 (FF.comp(x,y)>0); + + g=x.v[0].get(0); + r=FF.igcd(s,g); + if (r>1) return true; + return false; + } + + +}; + +FF.P_MBITS=ROM.MODBYTES*8; +FF.P_OMASK=((-1)<<(FF.P_MBITS%ROM.BASEBITS)); +FF.P_FEXCESS=(1<<(ROM.BASEBITS*ROM.NLEN-FF.P_MBITS)); +FF.P_TBITS=(FF.P_MBITS%ROM.BASEBITS); + + +/* compare x and y - must be normalised, and of same length */ +FF.comp=function(a,b) +{ + var 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; +}; + +FF.fromBytes=function(x,b) +{ + for (var 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 */ +FF.cswap=function(a,b,d) +{ + for (var 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. Assumes x and y are of same length. */ +FF.mul=function(x,y) +{ + var n=x.length; + var z=new FF(2*n); + var t=new FF(2*n); + z.karmul(0,x,0,y,0,t,0,n); + return z; +}; + + /* z=x^2 */ +FF.sqr=function(x) +{ + var n=x.length; + var z=new FF(2*n); + var t=new FF(2*n); + z.karsqr(0,x,0,t,0,n); + return z; +}; + +FF.igcd=function(x,y) +{ /* integer GCD, returns GCD of x and y */ + var r; + if (y===0) return x; + while ((r=x%y)!==0) + {x=y;y=r;} + return y; +}; + +/* Miller-Rabin test for primality. Slow. */ +FF.prime=function(p,rng) +{ + var i,j,s=0,n=p.length; + var loop; + var d=new FF(n); + var x=new FF(n); + var unity=new FF(n); + var nm1=new FF(n); + + var 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 (FF.comp(x,unity)===0 || FF.comp(x,nm1)===0) continue; + loop=false; + for (j=1;j<s;j++) + { + x.power(2,p); + if (FF.comp(x,unity)===0) return false; + if (FF.comp(x,nm1)===0) {loop=true; break;} + } + if (loop) continue; + return false; + } + return true; +}; http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/FP.js ---------------------------------------------------------------------- diff --git a/version22/js/FP.js b/version22/js/FP.js new file mode 100644 index 0000000..0d23382 --- /dev/null +++ b/version22/js/FP.js @@ -0,0 +1,360 @@ +/* + 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 */ + +/* General purpose COnstructor */ +var FP = function(x) { + if (x instanceof FP) + { + this.f=new BIG(x.f); + } + else + { + this.f=new BIG(x); + this.nres(); + } +}; + +FP.prototype={ +/* set this=0 */ + zero: function() + { + return this.f.zero(); + }, + +/* copy from a BIG in ROM */ + rcopy: function(y) + { + this.f.rcopy(y); + this.nres(); + }, + +/* copy from another BIG */ + bcopy: function(y) + { + this.f.copy(y); + this.nres(); +//alert("4. f= "+this.f.toString()); + }, + +/* copy from another FP */ + copy: function(y) + { + return this.f.copy(y.f); + }, + +/* conditional swap of a and b depending on d */ + cswap: function(b,d) + { + this.f.cswap(b.f,d); + }, + +/* conditional copy of b to a depending on d */ + cmove: function(b,d) + { + this.f.cmove(b.f,d); + }, + +/* convert to Montgomery n-residue form */ + nres: function() + { + if (ROM.MODTYPE!=ROM.PSEUDO_MERSENNE && ROM.MODTYPE!=ROM.GENERALISED_MERSENNE) + { + var p=new BIG(); + p.rcopy(ROM.Modulus); + var d=new DBIG(0); +//alert("f= "+this.f.toString()); + d.hcopy(this.f); + d.norm(); +//alert("1. d= "+d.toString()); + d.shl(ROM.NLEN*ROM.BASEBITS); +//alert("2. d= "+d.toString()); + this.f.copy(d.mod(p)); +//alert("3. f= "+this.f.toString()); + + } + return this; + }, + +/* convert back to regular form */ + redc: function() + { + var r=new BIG(0); + r.copy(this.f); + if (ROM.MODTYPE!=ROM.PSEUDO_MERSENNE && ROM.MODTYPE!=ROM.GENERALISED_MERSENNE) + { + var d=new DBIG(0); + d.hcopy(this.f); +//alert("rd= "+d.toString()); + var w=BIG.mod(d); +//alert("w= "+w.toString()); + r.copy(w); + } + + return r; + }, + +/* convert this to string */ + toString: function() + { + var s=this.redc().toString(); + return s; + }, + +/* test this=0 */ + iszilch: function() + { + this.reduce(); + return this.f.iszilch(); + }, + +/* reduce this mod Modulus */ + reduce: function() + { + var p=new BIG(0); + p.rcopy(ROM.Modulus); + return this.f.mod(p); + }, + +/* set this=1 */ + one: function() + { + this.f.one(); + return this.nres(); + }, + +/* normalise this */ + norm: function() + { + return this.f.norm(); + }, + +/* this*=b mod Modulus */ + mul: function(b) + { + this.norm(); + b.norm(); + var ea=BIG.EXCESS(this.f); + var eb=BIG.EXCESS(b.f); + + if ((ea+1)*(eb+1)>ROM.FEXCESS) this.reduce(); + //if ((ea+1) >= Math.floor((ROM.FEXCESS-1)/(eb+1))) this.reduce(); + + var d=BIG.mul(this.f,b.f); + this.f.copy(BIG.mod(d)); + return this; + }, + +/* this*=c mod Modulus where c is an int */ + imul: function(c) + { + var s=false; + this.norm(); + if (c<0) + { + c=-c; + s=true; + } + + var afx=(BIG.EXCESS(this.f)+1)*(c+1)+1; + if (c<ROM.NEXCESS && afx<ROM.FEXCESS) + { + this.f.imul(c); + } + else + { + if (afx<ROM.FEXCESS) this.f.pmul(c); + else + { + var p=new BIG(0); + p.rcopy(ROM.Modulus); + var d=this.f.pxmul(c); + this.f.copy(d.mod(p)); + } + } + if (s) this.neg(); + return this.norm(); + }, + +/* this*=this mod Modulus */ + sqr: function() + { + var d; + this.norm(); + var ea=BIG.EXCESS(this.f); + + if ((ea+1)*(ea+1)>ROM.FEXCESS) this.reduce(); + //if ((ea+1)>= Math.floor((ROM.FEXCESS-1)/(ea+1))) this.reduce(); + + d=BIG.sqr(this.f); + var t=BIG.mod(d); + this.f.copy(t); + return this; + }, + +/* this+=b */ + add: function(b) + { + this.f.add(b.f); + if (BIG.EXCESS(this.f)+2>=ROM.FEXCESS) this.reduce(); + return this; + }, +/* this=-this mod Modulus */ + neg: function() + { + var sb,ov; + var m=new BIG(0); + m.rcopy(ROM.Modulus); + + this.norm(); + sb=FP.logb2(BIG.EXCESS(this.f)); + +// ov=BIG.EXCESS(this.f); +// sb=1; while(ov!==0) {sb++;ov>>=1;} + + m.fshl(sb); + this.f.rsub(m); + if (BIG.EXCESS(this.f)>=ROM.FEXCESS) this.reduce(); + return this; + }, + +/* this-=b */ + sub: function(b) + { + var n=new FP(0); + n.copy(b); + n.neg(); + this.add(n); + return this; + }, + +/* this/=2 mod Modulus */ + div2: function() + { + this.norm(); + if (this.f.parity()===0) + this.f.fshr(1); + else + { + var p=new BIG(0); + p.rcopy(ROM.Modulus); + + this.f.add(p); + this.f.norm(); + this.f.fshr(1); + } + return this; + }, + +/* this=1/this mod Modulus */ + inverse: function() + { + var p=new BIG(0); + p.rcopy(ROM.Modulus); + var r=this.redc(); + r.invmodp(p); + this.f.copy(r); + return this.nres(); + }, + +/* return TRUE if this==a */ + equals: function(a) + { + a.reduce(); + this.reduce(); + if (BIG.comp(a.f,this.f)===0) return true; + return false; + }, + +/* return this^e mod Modulus */ + pow: function(e) + { + var bt; + var r=new FP(1); + e.norm(); + this.norm(); + var m=new FP(0); + m.copy(this); + while (true) + { + bt=e.parity(); + e.fshr(1); + if (bt==1) r.mul(m); + if (e.iszilch()) break; + m.sqr(); + } + + r.reduce(); + return r; + }, + +/* return jacobi symbol (this/Modulus) */ + jacobi: function() + { + var p=new BIG(0); + p.rcopy(ROM.Modulus); + var w=this.redc(); + return w.jacobi(p); + }, + +/* return sqrt(this) mod Modulus */ + sqrt: function() + { + this.reduce(); + var b=new BIG(0); + b.rcopy(ROM.Modulus); + if (ROM.MOD8==5) + { + b.dec(5); b.norm(); b.shr(3); + var i=new FP(0); + i.copy(this); + i.f.shl(1); + var v=i.pow(b); + i.mul(v); i.mul(v); + i.f.dec(1); + var r=new FP(0); + r.copy(this); + r.mul(v); r.mul(i); + r.reduce(); + return r; + } + else + { + b.inc(1); b.norm(); b.shr(2); + return this.pow(b); + } + } + +}; + +FP.logb2=function(v) +{ + 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); + var r = ((v + (v >>> 4) & 0xF0F0F0F) * 0x1010101) >>> 24; + return r+1; +}; http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/FP12.js ---------------------------------------------------------------------- diff --git a/version22/js/FP12.js b/version22/js/FP12.js new file mode 100644 index 0000000..0d85044 --- /dev/null +++ b/version22/js/FP12.js @@ -0,0 +1,558 @@ +/* + 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 */ + +/* general purpose constructor */ +var FP12= function(d,e,f) +{ + if (d instanceof FP12) + { + this.a=new FP4(d.a); + this.b=new FP4(d.b); + this.c=new FP4(d.c); + } + else + { + this.a=new FP4(d); + this.b=new FP4(e); + this.c=new FP4(f); + } +}; + +FP12.prototype={ +/* reduce all components of this mod Modulus */ + reduce: function() + { + this.a.reduce(); + this.b.reduce(); + this.c.reduce(); + }, +/* normalize all components of this mod Modulus */ + norm: function() + { + this.a.norm(); + this.b.norm(); + this.c.norm(); + }, +/* test x==0 ? */ + iszilch: function() + { + this.reduce(); + return (this.a.iszilch() && this.b.iszilch() && this.c.iszilch()); + }, +/* test x==1 ? */ + isunity: function() + { + var one=new FP4(1); + return (this.a.equals(one) && this.b.iszilch() && this.b.iszilch()); + }, +/* extract a from this */ + geta: function() + { + return this.a; + }, +/* extract b */ + getb: function() + { + return this.b; + }, +/* extract c */ + getc: function() + { + return this.c; + }, +/* return 1 if x==y, else 0 */ + equals: function(x) + { + return (this.a.equals(x.a) && this.b.equals(x.b)&& this.c.equals(x.c)); + }, +/* copy this=x */ + copy: function(x) + { + this.a.copy(x.a); + this.b.copy(x.b); + this.c.copy(x.c); + }, +/* set this=1 */ + one: function() + { + this.a.one(); + this.b.zero(); + this.c.zero(); + }, +/* this=conj(this) */ + conj: function() + { + this.a.conj(); + this.b.nconj(); + this.c.conj(); + }, + +/* set this from 3 FP4s */ + set: function(d,e,f) + { + this.a.copy(d); + this.b.copy(e); + this.c.copy(f); + }, +/* set this from one FP4 */ + seta: function(d) + { + this.a.copy(d); + this.b.zero(); + this.c.zero(); + }, + +/* Granger-Scott Unitary Squaring */ + usqr: function() + { + var A=new FP4(this.a); //A.copy(this.a); + var B=new FP4(this.c); //B.copy(this.c); + var C=new FP4(this.b); //C.copy(this.b); + var D=new FP4(0); + + this.a.sqr(); + D.copy(this.a); D.add(this.a); + this.a.add(D); + + A.nconj(); + + A.add(A); + this.a.add(A); + B.sqr(); + B.times_i(); + + D.copy(B); D.add(B); + B.add(D); + + C.sqr(); + D.copy(C); D.add(C); + C.add(D); + + this.b.conj(); + this.b.add(this.b); + this.c.nconj(); + + this.c.add(this.c); + this.b.add(B); + this.c.add(C); + this.reduce(); + }, + +/* Chung-Hasan SQR2 method from http://cacr.uwaterloo.ca/techreports/2006/cacr2006-24.pdf */ + sqr: function() + { + var A=new FP4(this.a); //A.copy(this.a); + var B=new FP4(this.b); //B.copy(this.b); + var C=new FP4(this.c); //C.copy(this.c); + var D=new FP4(this.a); //D.copy(this.a); + + A.sqr(); + B.mul(this.c); + B.add(B); + C.sqr(); + D.mul(this.b); + D.add(D); + + this.c.add(this.a); + this.c.add(this.b); + this.c.sqr(); + + this.a.copy(A); + + A.add(B); + A.add(C); + A.add(D); + A.neg(); + B.times_i(); + C.times_i(); + + this.a.add(B); + this.b.copy(C); this.b.add(D); + this.c.add(A); + + this.norm(); + }, + +/* FP12 full multiplication this=this*y */ + mul: function(y) + { + var z0=new FP4(this.a); //z0.copy(this.a); + var z1=new FP4(0); + var z2=new FP4(this.b); //z2.copy(this.b); + var z3=new FP4(0); + var t0=new FP4(this.a); //t0.copy(this.a); + var t1=new FP4(y.a); //t1.copy(y.a); + + z0.mul(y.a); + z2.mul(y.b); + + t0.add(this.b); + t1.add(y.b); + + z1.copy(t0); z1.mul(t1); + t0.copy(this.b); t0.add(this.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); + this.b.copy(z1); this.b.add(t1); + + z3.add(t1); + z2.add(t0); + + t0.copy(this.a); t0.add(this.c); + t1.copy(y.a); t1.add(y.c); + t0.mul(t1); + z2.add(t0); + + t0.copy(this.c); t0.mul(y.c); + t1.copy(t0); t1.neg(); + + this.c.copy(z2); this.c.add(t1); + z3.add(t1); + t0.times_i(); + this.b.add(t0); + + z3.times_i(); + this.a.copy(z0); this.a.add(z3); + + this.norm(); + }, + +/* Special case this*=y that arises from special form of ATE pairing line function */ + smul: function(y) + { + var z0=new FP4(this.a); //z0.copy(this.a); + var z2=new FP4(this.b); //z2.copy(this.b); + var z3=new FP4(this.b); //z3.copy(this.b); + var t0=new FP4(0); + var t1=new FP4(y.a); //t1.copy(y.a); + + z0.mul(y.a); + z2.pmul(y.b.real()); + this.b.add(this.a); + t1.real().add(y.b.real()); + + this.b.mul(t1); + z3.add(this.c); + z3.pmul(y.b.real()); + + t0.copy(z0); t0.neg(); + t1.copy(z2); t1.neg(); + + this.b.add(t0); + + this.b.add(t1); + z3.add(t1); + z2.add(t0); + + t0.copy(this.a); t0.add(this.c); + t0.mul(y.a); + this.c.copy(z2); this.c.add(t0); + + z3.times_i(); + this.a.copy(z0); this.a.add(z3); + + this.norm(); + }, + +/* this=1/this */ + inverse: function() + { + var f0=new FP4(this.a); //f0.copy(this.a); + var f1=new FP4(this.b); //f1.copy(this.b); + var f2=new FP4(this.a); //f2.copy(this.a); + var f3=new FP4(0); + + f0.sqr(); + f1.mul(this.c); + f1.times_i(); + f0.sub(f1); + + f1.copy(this.c); f1.sqr(); + f1.times_i(); + f2.mul(this.b); + f1.sub(f2); + + f2.copy(this.b); f2.sqr(); + f3.copy(this.a); f3.mul(this.c); + f2.sub(f3); + + f3.copy(this.b); f3.mul(f2); + f3.times_i(); + this.a.mul(f0); + f3.add(this.a); + this.c.mul(f1); + this.c.times_i(); + + f3.add(this.c); + f3.inverse(); + this.a.copy(f0); this.a.mul(f3); + this.b.copy(f1); this.b.mul(f3); + this.c.copy(f2); this.c.mul(f3); + }, + +/* this=this^p, where p=Modulus, using Frobenius */ + frob: function(f) + { + var f2=new FP2(f); + var f3=new FP2(f); + + f2.sqr(); + f3.mul(f2); + + this.a.frob(f3); + this.b.frob(f3); + this.c.frob(f3); + + this.b.pmul(f); + this.c.pmul(f2); + }, + +/* trace function */ + trace: function() + { + var t=new FP4(0); + t.copy(this.a); + t.imul(3); + t.reduce(); + return t; + }, +/* convert this to hex string */ + toString: function() + { + return ("["+this.a.toString()+","+this.b.toString()+","+this.c.toString()+"]"); + }, +/* convert this to byte array */ + toBytes: function(w) + { + var i; + var t=[]; + this.a.geta().getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i]=t[i]; + this.a.geta().getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+ROM.MODBYTES]=t[i]; + this.a.getb().getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+2*ROM.MODBYTES]=t[i]; + this.a.getb().getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+3*ROM.MODBYTES]=t[i]; + + this.b.geta().getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+4*ROM.MODBYTES]=t[i]; + this.b.geta().getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+5*ROM.MODBYTES]=t[i]; + this.b.getb().getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+6*ROM.MODBYTES]=t[i]; + this.b.getb().getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+7*ROM.MODBYTES]=t[i]; + + this.c.geta().getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+8*ROM.MODBYTES]=t[i]; + this.c.geta().getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+9*ROM.MODBYTES]=t[i]; + this.c.getb().getA().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+10*ROM.MODBYTES]=t[i]; + this.c.getb().getB().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) w[i+11*ROM.MODBYTES]=t[i]; + }, + +/* set this=this^e */ + pow: function(e) + { + this.norm(); + e.norm(); + var w=new FP12(this); //w.copy(this); + var z=new BIG(e); //z.copy(e); + var r=new FP12(1); + + while (true) + { + var 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 */ + pinpow: function(e,bts) + { + var i,b; + var R=[]; + 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]); + } +}; + +/* convert from byte array to FP12 */ +FP12.fromBytes= function(w) +{ + var i,a,b,c,d,e,f,g; + var t=[]; + + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i]; + a=BIG.fromBytes(t); + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+ROM.MODBYTES]; + b=BIG.fromBytes(t); + c=new FP2(a,b); //c.bset(a,b); + + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+2*ROM.MODBYTES]; + a=BIG.fromBytes(t); + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+3*ROM.MODBYTES]; + b=BIG.fromBytes(t); + d=new FP2(a,b); //d.bset(a,b); + + e=new FP4(c,d); //e.set(c,d); + + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+4*ROM.MODBYTES]; + a=BIG.fromBytes(t); + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+5*ROM.MODBYTES]; + b=BIG.fromBytes(t); + c=new FP2(a,b); //c.bset(a,b); + + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+6*ROM.MODBYTES]; + a=BIG.fromBytes(t); + for (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); //f.set(c,d); + + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+8*ROM.MODBYTES]; + a=BIG.fromBytes(t); + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+9*ROM.MODBYTES]; + b=BIG.fromBytes(t); + c=new FP2(a,b); //c.bset(a,b); + + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+10*ROM.MODBYTES]; + a=BIG.fromBytes(t); + for (i=0;i<ROM.MODBYTES;i++) t[i]=w[i+11*ROM.MODBYTES]; + b=BIG.fromBytes(t); + d=new FP2(a,b); //d.bset(a,b); + + g=new FP4(c,d); //g.set(c,d); + + var r=new FP12(e,f,g); //r.set(e,f,g); + + return r; +}; + +/* p=q0^u0.q1^u1.q2^u2.q3^u3 */ +/* Timing attack secure, but not cache attack secure */ + +FP12.pow4= function(q,u) +{ + var i,j,nb,m; + var a=[]; + var g=[]; + var s=[]; + + var c=new FP12(1); + var p=new FP12(0); + var t=[]; + + var mt=new BIG(0); + var w=[]; + + 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]=(8*a[0]+4*a[1]+2*a[2]+a[3]); + } + w[nb]=(8*t[0].lastbits(2)+4*t[1].lastbits(2)+2*t[2].lastbits(2)+t[3].lastbits(2)); + p.copy(g[Math.floor((w[nb]-1)/2)]); + + for (i=nb-1;i>=0;i--) + { + m=w[i]>>31; + 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; +}; + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/FP2.js ---------------------------------------------------------------------- diff --git a/version22/js/FP2.js b/version22/js/FP2.js new file mode 100644 index 0000000..a7b4e95 --- /dev/null +++ b/version22/js/FP2.js @@ -0,0 +1,321 @@ +/* + 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 Fp^2 functions */ + +/* FP2 elements are of the form a+ib, where i is sqrt(-1) */ + +/* general purpose constructor */ +var FP2 =function(c,d) +{ + if (c instanceof FP2) + { + this.a=new FP(c.a); + this.b=new FP(c.b); + } + else + { + this.a=new FP(c); + this.b=new FP(d); + } +}; + +FP2.prototype={ +/* reduce components mod Modulus */ + reduce: function() + { + this.a.reduce(); + this.b.reduce(); + }, +/* normalise components of w */ + norm: function() + { + this.a.norm(); + this.b.norm(); + }, +/* test this=0 ? */ + iszilch: function() + { + this.reduce(); + return (this.a.iszilch() && this.b.iszilch()); + }, +/* test this=1 ? */ + isunity: function() + { + var one=new FP(1); + return (this.a.equals(one) && this.b.iszilch()); + }, +/* conditional copy of g to this depending on d */ + cmove:function(g,d) + { + this.a.cmove(g.a,d); + this.b.cmove(g.b,d); + }, + +/* test this=x */ + equals: function(x) { + return (this.a.equals(x.a) && this.b.equals(x.b)); + }, +/* extract a */ + getA: function() + { + return this.a.redc(); + }, +/* extract b */ + getB: function() + { + return this.b.redc(); + }, + +/* set from pair of FPs */ + set: function(c,d) + { + this.a.copy(c); + this.b.copy(d); + }, +/* set a */ + seta: function(c) + { + this.a.copy(c); + this.b.zero(); + }, + +/* set from two BIGs */ + bset: function(c,d) + { + this.a.bcopy(c); + this.b.bcopy(d); + }, + +/* set from one BIG */ + bseta: function(c) + { + this.a.bcopy(c); + this.b.zero(); + }, +/* copy this=x */ + copy: function(x) + { + this.a.copy(x.a); + this.b.copy(x.b); + }, +/* set this=0 */ + zero: function() + { + this.a.zero(); + this.b.zero(); + }, +/* set this=1 */ + one: function() + { + this.a.one(); + this.b.zero(); + }, +/* negate this */ + neg: function() + { + this.norm(); + var m=new FP(this.a); + var t=new FP(0); + + m.add(this.b); + m.neg(); + m.norm(); + t.copy(m); t.add(this.b); + this.b.copy(m); + this.b.add(this.a); + this.a.copy(t); + //this.norm(); + }, +/* conjugate this */ + conj: function() + { + this.b.neg(); + }, +/* this+=a */ + add: function(x) + { + this.a.add(x.a); + this.b.add(x.b); + }, +/* this-=x */ + sub: function(x) + { + var m=new FP2(x); //var m=new FP2(0); m.copy(x); + m.neg(); + this.add(m); + }, +/* this*=s, where s is FP */ + pmul: function(s) + { + this.a.mul(s); + this.b.mul(s); + }, +/* this*=c, where s is int */ + imul: function(c) + { + this.a.imul(c); + this.b.imul(c); + }, +/* this*=this */ + sqr: function() + { + this.norm(); + + var w1=new FP(this.a); + var w3=new FP(this.a); + var mb=new FP(this.b); + + w3.mul(this.b); + w1.add(this.b); + mb.neg(); + this.a.add(mb); + this.a.mul(w1); + this.b.copy(w3); this.b.add(w3); + this.norm(); + }, +/* this*=y */ + mul: function(y) + { + this.norm(); // This is needed here as {a,b} is not normed before additions + + var w1=new FP(this.a); + var w2=new FP(this.b); + var w5=new FP(this.a); + var mw=new FP(0); + + w1.mul(y.a); // w1=a*y.a - this norms w1 and y.a, NOT a + w2.mul(y.b); // w2=b*y.b - this norms w2 and y.b, NOT b + w5.add(this.b); // w5=a+b + this.b.copy(y.a); this.b.add(y.b); // b=y.a+y.b + + this.b.mul(w5); + mw.copy(w1); mw.add(w2); mw.neg(); + + this.b.add(mw); mw.add(w1); + this.a.copy(w1); this.a.add(mw); + + this.norm(); + }, + +/* sqrt(a+ib) = sqrt(a+sqrt(a*a-n*b*b)/2)+ib/(2*sqrt(a+sqrt(a*a-n*b*b)/2)) */ +/* returns true if this is QR */ + sqrt: function() + { + if (this.iszilch()) return true; + var w1=new FP(this.b); + var w2=new FP(this.a); + + w1.sqr(); w2.sqr(); w1.add(w2); + if (w1.jacobi()!=1) { this.zero(); return false; } + w1=w1.sqrt(); + w2.copy(this.a); w2.add(w1); w2.div2(); + if (w2.jacobi()!=1) + { + w2.copy(this.a); w2.sub(w1); w2.div2(); + if (w2.jacobi()!=1) { this.zero(); return false; } + } + w2=w2.sqrt(); + this.a.copy(w2); + w2.add(w2); + w2.inverse(); + this.b.mul(w2); + return true; + }, + +/* convert this to hex string */ + toString: function() + { + return ("["+this.a.toString()+","+this.b.toString()+"]"); + }, +/* this=1/this */ + inverse: function() + { + this.norm(); + var w1=new FP(this.a); + var w2=new FP(this.b); + w1.sqr(); + w2.sqr(); + w1.add(w2); + w1.inverse(); + this.a.mul(w1); + w1.neg(); + this.b.mul(w1); + }, +/* this/=2 */ + div2: function() + { + this.a.div2(); + this.b.div2(); + }, +/* this*=sqrt(-1) */ + times_i: function() + { + var z=new FP(this.a); //z.copy(this.a); + this.a.copy(this.b); this.a.neg(); + this.b.copy(z); + }, + +/* w*=(1+sqrt(-1)) */ +/* where X*2-(1+sqrt(-1)) is irreducible for FP4, assumes p=3 mod 8 */ + mul_ip: function() + { + this.norm(); + var t=new FP2(this);// t.copy(this); + var z=new FP(this.a); //z.copy(this.a); + this.a.copy(this.b); + this.a.neg(); + this.b.copy(z); + this.add(t); + this.norm(); + }, + +/* w/=(1+sqrt(-1)) */ + div_ip: function() + { + var t=new FP2(0); + this.norm(); + t.a.copy(this.a); t.a.add(this.b); + t.b.copy(this.b); t.b.sub(this.a); + this.copy(t); + this.div2(); + }, +/* this=this^e */ + pow: function(e) + { + var bt; + var r=new FP2(1); + this.norm(); + var x=new FP2(this); //x.copy(this); + e.norm(); + while (true) + { + bt=e.parity(); + e.fshr(1); + if (bt==1) r.mul(x); + if (e.iszilch()) break; + x.sqr(); + } + + r.reduce(); + return r; + } + +}; + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/FP4.js ---------------------------------------------------------------------- diff --git a/version22/js/FP4.js b/version22/js/FP4.js new file mode 100644 index 0000000..640ac63 --- /dev/null +++ b/version22/js/FP4.js @@ -0,0 +1,501 @@ +/* + 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 Fp^4 functions */ + +/* FP4 elements are of the form a+ib, where i is sqrt(-1+sqrt(-1)) */ + +/* general purpose constructor */ +var FP4=function(c,d) +{ + if (c instanceof FP4) + { + this.a=new FP2(c.a); + this.b=new FP2(c.b); + } + else + { + this.a=new FP2(c); + this.b=new FP2(d); + } +}; + +FP4.prototype={ +/* reduce all components of this mod Modulus */ + reduce: function() + { + this.a.reduce(); + this.b.reduce(); + }, +/* normalise all components of this mod Modulus */ + norm: function() + { + this.a.norm(); + this.b.norm(); + }, +/* test this==0 ? */ + iszilch: function() + { + this.reduce(); + return (this.a.iszilch() && this.b.iszilch()); + }, +/* test this==1 ? */ + isunity: function() + { + var one=new FP2(1); + return (this.a.equals(one) && this.b.iszilch()); + }, +/* test is w real? That is in a+ib test b is zero */ + isreal: function() + { + return this.b.iszilch(); + }, +/* extract real part a */ + real: function() + { + return this.a; + }, + + geta: function() + { + return this.a; + }, +/* extract imaginary part b */ + getb: function() + { + return this.b; + }, +/* test this=x? */ + equals: function(x) + { + return (this.a.equals(x.a) && this.b.equals(x.b)); + }, +/* copy this=x */ + copy: function(x) + { + this.a.copy(x.a); + this.b.copy(x.b); + }, +/* this=0 */ + zero: function() + { + this.a.zero(); + this.b.zero(); + }, +/* this=1 */ + one: function() + { + this.a.one(); + this.b.zero(); + }, + +/* set from two FP2s */ + set: function(c,d) + { + this.a.copy(c); + this.b.copy(d); + }, +/* set a */ + seta: function(c) + { + this.a.copy(c); + this.b.zero(); + }, +/* this=-this */ + neg: function() + { + var m=new FP2(this.a); //m.copy(this.a); + var t=new FP2(0); + m.add(this.b); + m.neg(); + m.norm(); + t.copy(m); t.add(this.b); + this.b.copy(m); + this.b.add(this.a); + this.a.copy(t); + }, +/* this=conjugate(this) */ + conj: function() + { + this.b.neg(); this.b.norm(); + }, +/* this=-conjugate(this) */ + nconj: function() + { + this.a.neg(); this.a.norm(); + }, +/* this+=x */ + add: function(x) + { + this.a.add(x.a); + this.b.add(x.b); + }, +/* this-=x */ + sub: function(x) + { + var m=new FP4(x); // m.copy(x); + m.neg(); + this.add(m); + }, +/* this*=s where s is FP2 */ + pmul: function(s) + { + this.a.mul(s); + this.b.mul(s); + }, +/* this*=c where s is int */ + imul: function(c) + { + this.a.imul(c); + this.b.imul(c); + }, +/* this*=this */ + sqr: function() + { + this.norm(); + + var t1=new FP2(this.a); //t1.copy(this.a); + var t2=new FP2(this.b); //t2.copy(this.b); + var t3=new FP2(this.a); //t3.copy(this.a); + + t3.mul(this.b); + t1.add(this.b); + t2.mul_ip(); + + t2.add(this.a); + this.a.copy(t1); + + this.a.mul(t2); + + t2.copy(t3); + t2.mul_ip(); + t2.add(t3); + + t2.neg(); + + this.a.add(t2); + + this.b.copy(t3); + this.b.add(t3); + + this.norm(); + }, +/* this*=y */ + mul: function(y) + { + this.norm(); + + var t1=new FP2(this.a); //t1.copy(this.a); + var t2=new FP2(this.b); //t2.copy(this.b); + var t3=new FP2(0); + var t4=new FP2(this.b); //t4.copy(this.b); + + t1.mul(y.a); + t2.mul(y.b); + t3.copy(y.b); + t3.add(y.a); + t4.add(this.a); + + t4.mul(t3); + t4.sub(t1); + + this.b.copy(t4); + this.b.sub(t2); + t2.mul_ip(); + this.a.copy(t2); + this.a.add(t1); + + this.norm(); + }, +/* convert to hex string */ + toString: function() + { + return ("["+this.a.toString()+","+this.b.toString()+"]"); + }, +/* this=1/this */ + inverse: function() + { + this.norm(); + + var t1=new FP2(this.a); //t1.copy(this.a); + var t2=new FP2(this.b);// t2.copy(this.b); + + t1.sqr(); + t2.sqr(); + t2.mul_ip(); + t1.sub(t2); + t1.inverse(); + this.a.mul(t1); + t1.neg(); + this.b.mul(t1); + }, + +/* this*=i where i = sqrt(-1+sqrt(-1)) */ + times_i: function() + { + var s=new FP2(this.b); //s.copy(this.b); + var t=new FP2(this.b); //t.copy(this.b); + s.times_i(); + t.add(s); + this.b.copy(this.a); + this.a.copy(t); + }, + +/* this=this^q using Frobenius, where q is Modulus */ + frob: function(f) + { + this.a.conj(); + this.b.conj(); + this.b.mul(f); + }, + +/* this=this^e */ + pow: function(e) + { + this.norm(); + e.norm(); + var w=new FP4(this); //w.copy(this); + var z=new BIG(e); //z.copy(e); + var r=new FP4(1); + while (true) + { + var bt=z.parity(); + z.fshr(1); + if (bt==1) r.mul(w); + if (z.iszilch()) break; + w.sqr(); + } + r.reduce(); + return r; + }, + +/* XTR xtr_a function */ + xtr_A: function(w,y,z) + { + var r=new FP4(w); //r.copy(w); + var t=new FP4(w); //t.copy(w); + r.sub(y); + r.pmul(this.a); + t.add(y); + t.pmul(this.b); + t.times_i(); + + this.copy(r); + this.add(t); + this.add(z); + + this.norm(); + }, +/* XTR xtr_d function */ + xtr_D: function() + { + var w=new FP4(this); //w.copy(this); + this.sqr(); w.conj(); + w.add(w); + this.sub(w); + this.reduce(); + }, +/* r=x^n using XTR method on traces of FP12s */ + xtr_pow: function(n) + { + var a=new FP4(3); + var b=new FP4(this); + var c=new FP4(b); + c.xtr_D(); + var t=new FP4(0); + var r=new FP4(0); + + n.norm(); + var par=n.parity(); + var v=new BIG(n); v.fshr(1); + if (par===0) {v.dec(1); v.norm();} + + var nb=v.nbits(); + for (var i=nb-1;i>=0;i--) + { + if (v.bit(i)!=1) + { + t.copy(b); + this.conj(); + c.conj(); + b.xtr_A(a,this,c); + this.conj(); + c.copy(t); + c.xtr_D(); + a.xtr_D(); + } + else + { + t.copy(a); t.conj(); + a.copy(b); + a.xtr_D(); + b.xtr_A(c,this,t); + c.xtr_D(); + } + } + if (par===0) r.copy(c); + else r.copy(b); + r.reduce(); + return r; + }, + +/* r=ck^a.cl^n using XTR double exponentiation method on traces of FP12s. See Stam thesis. */ + xtr_pow2: function(ck,ckml,ckm2l,a,b) + { + a.norm(); b.norm(); + var e=new BIG(a); //e.copy(a); + var d=new BIG(b); //d.copy(b); + var w=new BIG(0); + + var cu=new FP4(ck); //cu.copy(ck); // can probably be passed in w/o copying + var cv=new FP4(this); //cv.copy(this); + var cumv=new FP4(ckml); //cumv.copy(ckml); + var cum2v=new FP4(ckm2l); //cum2v.copy(ckm2l); + var r=new FP4(0); + var t=new FP4(0); + + var f2=0; + while (d.parity()===0 && e.parity()===0) + { + d.fshr(1); + e.fshr(1); + f2++; + } + + while (BIG.comp(d,e)!==0) + { + if (BIG.comp(d,e)>0) + { + w.copy(e); w.imul(4); w.norm(); + if (BIG.comp(d,w)<=0) + { + w.copy(d); d.copy(e); + e.rsub(w); e.norm(); + + t.copy(cv); + t.xtr_A(cu,cumv,cum2v); + cum2v.copy(cumv); + cum2v.conj(); + cumv.copy(cv); + cv.copy(cu); + cu.copy(t); + + } + else if (d.parity()===0) + { + d.fshr(1); + r.copy(cum2v); r.conj(); + t.copy(cumv); + t.xtr_A(cu,cv,r); + cum2v.copy(cumv); + cum2v.xtr_D(); + cumv.copy(t); + cu.xtr_D(); + } + else if (e.parity()==1) + { + d.sub(e); d.norm(); + d.fshr(1); + t.copy(cv); + t.xtr_A(cu,cumv,cum2v); + cu.xtr_D(); + cum2v.copy(cv); + cum2v.xtr_D(); + cum2v.conj(); + cv.copy(t); + } + else + { + w.copy(d); + d.copy(e); d.fshr(1); + e.copy(w); + t.copy(cumv); + t.xtr_D(); + cumv.copy(cum2v); cumv.conj(); + cum2v.copy(t); cum2v.conj(); + t.copy(cv); + t.xtr_D(); + cv.copy(cu); + cu.copy(t); + } + } + if (BIG.comp(d,e)<0) + { + w.copy(d); w.imul(4); w.norm(); + if (BIG.comp(e,w)<=0) + { + e.sub(d); e.norm(); + t.copy(cv); + t.xtr_A(cu,cumv,cum2v); + cum2v.copy(cumv); + cumv.copy(cu); + cu.copy(t); + } + else if (e.parity()===0) + { + w.copy(d); + d.copy(e); d.fshr(1); + e.copy(w); + t.copy(cumv); + t.xtr_D(); + cumv.copy(cum2v); cumv.conj(); + cum2v.copy(t); cum2v.conj(); + t.copy(cv); + t.xtr_D(); + cv.copy(cu); + cu.copy(t); + } + else if (d.parity()==1) + { + w.copy(e); + e.copy(d); + w.sub(d); w.norm(); + d.copy(w); d.fshr(1); + t.copy(cv); + t.xtr_A(cu,cumv,cum2v); + cumv.conj(); + cum2v.copy(cu); + cum2v.xtr_D(); + cum2v.conj(); + cu.copy(cv); + cu.xtr_D(); + cv.copy(t); + } + else + { + d.fshr(1); + r.copy(cum2v); r.conj(); + t.copy(cumv); + t.xtr_A(cu,cv,r); + cum2v.copy(cumv); + cum2v.xtr_D(); + cumv.copy(t); + cu.xtr_D(); + } + } + } + r.copy(cv); + r.xtr_A(cu,cumv,cum2v); + for (var i=0;i<f2;i++) + r.xtr_D(); + r=r.xtr_pow(d); + return r; + } + +}; http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/GCM.js ---------------------------------------------------------------------- diff --git a/version22/js/GCM.js b/version22/js/GCM.js new file mode 100644 index 0000000..16482d0 --- /dev/null +++ b/version22/js/GCM.js @@ -0,0 +1,305 @@ +/* + Licensed to the Apache Software Foundation (ASF) under one + or more contributor license agreements. See the NOTICE file + distributed with this work for additional information + regarding copyright ownership. The ASF licenses this file + to you under the Apache License, Version 2.0 (the + "License"); you may not use this file except in compliance + with the License. You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, + software distributed under the License is distributed on an + "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + KIND, either express or implied. See the License for the + specific language governing permissions and limitations + under the License. +*/ + +/* + * Implementation of the AES-GCM Encryption/Authentication + * + * Some restrictions.. + * 1. Only for use with AES + * 2. Returned tag is always 128-bits. Truncate at your own risk. + * 3. The order of function calls must follow some rules + * + * Typical sequence of calls.. + * 1. call GCM_init + * 2. call GCM_add_header any number of times, as long as length of header is multiple of 16 bytes (block size) + * 3. call GCM_add_header one last time with any length of header + * 4. call GCM_add_cipher any number of times, as long as length of cipher/plaintext is multiple of 16 bytes + * 5. call GCM_add_cipher one last time with any length of cipher/plaintext + * 6. call GCM_finish to extract the tag. + * + * See http://www.mindspring.com/~dmcgrew/gcm-nist-6.pdf + */ + +var GCM = function() { + this.table=new Array(128); + for (var i=0;i<128;i++) + this.table[i]=new Array(4); /* 2k bytes */ + this.stateX=[]; + this.Y_0=[]; + this.counter=0; + this.lenA=[]; + this.lenC=[]; + this.status=0; + this.a=new AES(); +}; + +GCM.prototype={ + + precompute: function(H) + { + var i,j,c; + var b=[]; + + for (i=j=0;i<4;i++,j+=4) + { + b[0]=H[j]; b[1]=H[j+1]; b[2]=H[j+2]; b[3]=H[j+3]; + this.table[0][i]=GCM.pack(b); + } + for (i=1;i<128;i++) + { + c=0; + for (j=0;j<4;j++) + { + this.table[i][j]=c|(this.table[i-1][j])>>>1; + c=this.table[i-1][j]<<31; + } + if (c!==0) this.table[i][0]^=0xE1000000; /* irreducible polynomial */ + } + }, + + gf2mul: function() + { /* gf2m mul - Z=H*X mod 2^128 */ + var i,j,m,k; + var P=[]; + var c; + var b=[]; + + P[0]=P[1]=P[2]=P[3]=0; + j=8; m=0; + for (i=0;i<128;i++) + { + c=(this.stateX[m]>>>(--j))&1; c=~c+1; + for (k=0;k<4;k++) P[k]^=(this.table[i][k]&c); + if (j===0) + { + j=8; m++; + if (m==16) break; + } + } + for (i=j=0;i<4;i++,j+=4) + { + b=GCM.unpack(P[i]); + this.stateX[j]=b[0]; this.stateX[j+1]=b[1]; this.stateX[j+2]=b[2]; this.stateX[j+3]=b[3]; + } + }, + + wrap: function() + { /* Finish off GHASH */ + var i,j; + var F=[]; + var L=[]; + var b=[]; + +/* convert lengths from bytes to bits */ + F[0]=(this.lenA[0]<<3)|(this.lenA[1]&0xE0000000)>>>29; + F[1]=this.lenA[1]<<3; + F[2]=(this.lenC[0]<<3)|(this.lenC[1]&0xE0000000)>>>29; + F[3]=this.lenC[1]<<3; + for (i=j=0;i<4;i++,j+=4) + { + b=GCM.unpack(F[i]); + L[j]=b[0]; L[j+1]=b[1]; L[j+2]=b[2]; L[j+3]=b[3]; + } + for (i=0;i<16;i++) this.stateX[i]^=L[i]; + this.gf2mul(); + }, + +/* Initialize GCM mode */ + init: function(nk,key,niv,iv) + { /* iv size niv is usually 12 bytes (96 bits). AES key size nk can be 16,24 or 32 bytes */ + var i; + var H=[]; + var b=[]; + + for (i=0;i<16;i++) {H[i]=0; this.stateX[i]=0;} + + this.a.init(ROM.ECB,nk,key,iv); + this.a.ecb_encrypt(H); /* E(K,0) */ + this.precompute(H); + + this.lenA[0]=this.lenC[0]=this.lenA[1]=this.lenC[1]=0; + if (niv==12) + { + for (i=0;i<12;i++) this.a.f[i]=iv[i]; + b=GCM.unpack(1); + this.a.f[12]=b[0]; this.a.f[13]=b[1]; this.a.f[14]=b[2]; this.a.f[15]=b[3]; /* initialise IV */ + for (i=0;i<16;i++) this.Y_0[i]=this.a.f[i]; + } + else + { + this.status=ROM.GCM_ACCEPTING_CIPHER; + this.ghash(iv,niv); /* GHASH(H,0,IV) */ + this.wrap(); + for (i=0;i<16;i++) {this.a.f[i]=this.stateX[i];this.Y_0[i]=this.a.f[i];this.stateX[i]=0;} + this.lenA[0]=this.lenC[0]=this.lenA[1]=this.lenC[1]=0; + } + this.status=ROM.GCM_ACCEPTING_HEADER; + }, + +/* Add Header data - included but not encrypted */ + add_header: function(header,len) + { /* Add some header. Won't be encrypted, but will be authenticated. len is length of header */ + var i,j=0; + if (this.status!=ROM.GCM_ACCEPTING_HEADER) return false; + + while (j<len) + { + for (i=0;i<16 && j<len;i++) + { + this.stateX[i]^=header[j++]; + this.lenA[1]++; this.lenA[1]|=0; if (this.lenA[1]===0) this.lenA[0]++; + } + this.gf2mul(); + } + if (len%16!==0) this.status=ROM.GCM_ACCEPTING_CIPHER; + return true; + }, + + ghash: function(plain,len) + { + var i,j=0; + + if (this.status==ROM.GCM_ACCEPTING_HEADER) this.status=ROM.GCM_ACCEPTING_CIPHER; + if (this.status!=ROM.GCM_ACCEPTING_CIPHER) return false; + + while (j<len) + { + for (i=0;i<16 && j<len;i++) + { + this.stateX[i]^=plain[j++]; + this.lenC[1]++; this.lenC[1]|=0; if (this.lenC[1]===0) this.lenC[0]++; + } + this.gf2mul(); + } + if (len%16!==0) this.status=ROM.GCM_NOT_ACCEPTING_MORE; + return true; + }, + +/* Add Plaintext - included and encrypted */ + add_plain: function(plain,len) + { + var i,j=0; + var B=[]; + var b=[]; + var cipher=[]; + + if (this.status==ROM.GCM_ACCEPTING_HEADER) this.status=ROM.GCM_ACCEPTING_CIPHER; + if (this.status!=ROM.GCM_ACCEPTING_CIPHER) return cipher; + + while (j<len) + { + + b[0]=this.a.f[12]; b[1]=this.a.f[13]; b[2]=this.a.f[14]; b[3]=this.a.f[15]; + this.counter=GCM.pack(b); + this.counter++; + b=GCM.unpack(this.counter); + this.a.f[12]=b[0]; this.a.f[13]=b[1]; this.a.f[14]=b[2]; this.a.f[15]=b[3]; /* increment counter */ + for (i=0;i<16;i++) B[i]=this.a.f[i]; + this.a.ecb_encrypt(B); /* encrypt it */ + + for (i=0;i<16 && j<len;i++) + { + cipher[j]=(plain[j]^B[i]); + this.stateX[i]^=cipher[j++]; + this.lenC[1]++; this.lenC[1]|=0; if (this.lenC[1]===0) this.lenC[0]++; + } + this.gf2mul(); + } + if (len%16!==0) this.status=ROM.GCM_NOT_ACCEPTING_MORE; + return cipher; + }, + +/* Add Ciphertext - decrypts to plaintext */ + add_cipher: function(cipher,len) + { + var i,j=0; + var B=[]; + var b=[]; + var plain=[]; + + if (this.status==ROM.GCM_ACCEPTING_HEADER) this.status=ROM.GCM_ACCEPTING_CIPHER; + if (this.status!=ROM.GCM_ACCEPTING_CIPHER) return plain; + + while (j<len) + { + b[0]=this.a.f[12]; b[1]=this.a.f[13]; b[2]=this.a.f[14]; b[3]=this.a.f[15]; + this.counter=GCM.pack(b); + this.counter++; + b=GCM.unpack(this.counter); + this.a.f[12]=b[0]; this.a.f[13]=b[1]; this.a.f[14]=b[2]; this.a.f[15]=b[3]; /* increment counter */ + for (i=0;i<16;i++) B[i]=this.a.f[i]; + this.a.ecb_encrypt(B); /* encrypt it */ + for (i=0;i<16 && j<len;i++) + { + var oc=cipher[j]; + plain[j]=(cipher[j]^B[i]); + this.stateX[i]^=oc; j++; + this.lenC[1]++; this.lenC[1]|=0; if (this.lenC[1]===0) this.lenC[0]++; + } + this.gf2mul(); + } + if (len%16!==0) this.status=ROM.GCM_NOT_ACCEPTING_MORE; + return plain; + }, + +/* Finish and extract Tag */ + finish: function(extract) + { /* Finish off GHASH and extract tag (MAC) */ + var i; + var tag=[]; + + this.wrap(); +/* extract tag */ + if (extract) + { + this.a.ecb_encrypt(this.Y_0); /* E(K,Y0) */ + for (i=0;i<16;i++) this.Y_0[i]^=this.stateX[i]; + for (i=0;i<16;i++) {tag[i]=this.Y_0[i];this.Y_0[i]=this.stateX[i]=0;} + } + this.status=ROM.GCM_FINISHED; + this.a.end(); + return tag; + } + +}; + +GCM.pack= function(b) +{ /* pack 4 bytes into a 32-bit Word */ + return (((b[0])&0xff)<<24)|((b[1]&0xff)<<16)|((b[2]&0xff)<<8)|(b[3]&0xff); +}; + +GCM.unpack=function(a) +{ /* unpack bytes from a word */ + var b=[]; + b[3]=(a&0xff); + b[2]=((a>>>8)&0xff); + b[1]=((a>>>16)&0xff); + b[0]=((a>>>24)&0xff); + return b; +}; + +GCM.hex2bytes=function(s) +{ + var len = s.length; + var data = []; + for (var i = 0; i < len; i += 2) + data[i / 2] = parseInt(s.substr(i,2),16); + + return data; +}; http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/HASH256.js ---------------------------------------------------------------------- diff --git a/version22/js/HASH256.js b/version22/js/HASH256.js new file mode 100644 index 0000000..a683916 --- /dev/null +++ b/version22/js/HASH256.js @@ -0,0 +1,180 @@ +/* + 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. +*/ + +var HASH256 = function() { + this.length=[]; + this.h=[]; + this.w=[]; + this.init(); +}; + +HASH256.prototype={ + + /* functions */ + + transform: function() + { /* basic transformation step */ + var a,b,c,d,e,f,g,hh,t1,t2; + var j; + for (j=16;j<64;j++) + this.w[j]=(HASH256.theta1(this.w[j-2])+this.w[j-7]+HASH256.theta0(this.w[j-15])+this.w[j-16])|0; + + a=this.h[0]; b=this.h[1]; c=this.h[2]; d=this.h[3]; + e=this.h[4]; f=this.h[5]; g=this.h[6]; hh=this.h[7]; + + for (j=0;j<64;j++) + { /* 64 times - mush it up */ + t1=(hh+HASH256.Sig1(e)+HASH256.Ch(e,f,g)+HASH256.HK[j]+this.w[j])|0; + t2=(HASH256.Sig0(a)+HASH256.Maj(a,b,c))|0; + hh=g; g=f; f=e; + e=(d+t1)|0; // Need to knock these back down to prevent 52-bit overflow + d=c; + c=b; + b=a; + a=(t1+t2)|0; + + } + this.h[0]+=a; this.h[1]+=b; this.h[2]+=c; this.h[3]+=d; + this.h[4]+=e; this.h[5]+=f; this.h[6]+=g; this.h[7]+=hh; + + }, + +/* Initialise Hash function */ + init: function() + { /* initialise */ + var i; + for (i=0;i<64;i++) this.w[i]=0; + this.length[0]=this.length[1]=0; + this.h[0]=HASH256.H[0]; + this.h[1]=HASH256.H[1]; + this.h[2]=HASH256.H[2]; + this.h[3]=HASH256.H[3]; + this.h[4]=HASH256.H[4]; + this.h[5]=HASH256.H[5]; + this.h[6]=HASH256.H[6]; + this.h[7]=HASH256.H[7]; + }, + +/* process a single byte */ + process: function(byt) + { /* process the next message byte */ + var cnt; + + cnt=(this.length[0]>>>5)%16; + this.w[cnt]<<=8; + this.w[cnt]|=(byt&0xFF); + this.length[0]+=8; + if ((this.length[0]&0xffffffff)===0) { this.length[1]++; this.length[0]=0; } + if ((this.length[0]%512)===0) this.transform(); + }, + +/* process an array of bytes */ + process_array: function(b) + { + for (var i=0;i<b.length;i++) this.process(b[i]); + }, + +/* process a 32-bit integer */ + process_num: function(n) + { + this.process((n>>24)&0xff); + this.process((n>>16)&0xff); + this.process((n>>8)&0xff); + this.process(n&0xff); + }, + + hash: function() + { /* pad message and finish - supply digest */ + var i; + var digest=[]; + var len0,len1; + len0=this.length[0]; + len1=this.length[1]; + this.process(0x80); + while ((this.length[0]%512)!=448) this.process(0); + + this.w[14]=len1; + this.w[15]=len0; + this.transform(); + + for (i=0;i<HASH256.len;i++) + { /* convert to bytes */ + digest[i]=((this.h[i>>>2]>>(8*(3-i%4))) & 0xff); + } + this.init(); + return digest; + } +}; + +/* static functions */ + +HASH256.S= function(n,x) +{ + return (((x)>>>n) | ((x)<<(32-n))); +}; + +HASH256.R= function(n,x) +{ + return ((x)>>>n); +}; + +HASH256.Ch= function(x,y,z) +{ + return ((x&y)^(~(x)&z)); +}; + +HASH256.Maj= function(x,y,z) +{ + return ((x&y)^(x&z)^(y&z)); +}; + +HASH256.Sig0= function(x) +{ + return (HASH256.S(2,x)^HASH256.S(13,x)^HASH256.S(22,x)); +}; + +HASH256.Sig1= function(x) +{ + return (HASH256.S(6,x)^HASH256.S(11,x)^HASH256.S(25,x)); +}; + +HASH256.theta0= function(x) +{ + return (HASH256.S(7,x)^HASH256.S(18,x)^HASH256.R(3,x)); +}; + +HASH256.theta1= function(x) +{ + return (HASH256.S(17,x)^HASH256.S(19,x)^HASH256.R(10,x)); +}; + +/* constants */ +HASH256.len= 32; + +HASH256.H = [0x6A09E667,0xBB67AE85,0x3C6EF372,0xA54FF53A,0x510E527F,0x9B05688C,0x1F83D9AB,0x5BE0CD19]; + +HASH256.HK = [0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, + 0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, + 0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, + 0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, + 0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, + 0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, + 0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, + 0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2]; + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/HASH384.js ---------------------------------------------------------------------- diff --git a/version22/js/HASH384.js b/version22/js/HASH384.js new file mode 100644 index 0000000..1aa89a1 --- /dev/null +++ b/version22/js/HASH384.js @@ -0,0 +1,238 @@ +/* + 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. +*/ + +var HASH384 = function() { + this.length=[]; + this.h=[]; + this.w=[]; + this.init(); +}; + +HASH384.prototype={ +/* constants */ + + + transform: function() + { /* basic transformation step */ + var a,b,c,d,e,ee,zz,f,g,hh,t1,t2; + var j,r; + for (j=16;j<80;j++) + this.w[j]=HASH384.theta1(this.w[j-2]).add(this.w[j-7]).add(HASH384.theta0(this.w[j-15])).add(this.w[j-16]); + + a=this.h[0].copy(); b=this.h[1].copy(); c=this.h[2].copy(); d=this.h[3].copy(); + e=this.h[4].copy(); f=this.h[5].copy(); g=this.h[6].copy(); hh=this.h[7].copy(); + + for (j=0;j<80;j++) + { /* 80 times - mush it up */ + t1=hh.copy(); + t1.add(HASH384.Sig1(e)).add(HASH384.Ch(e,f,g)).add(HASH384.HK[j]).add(this.w[j]); + + t2=HASH384.Sig0(a); t2.add(HASH384.Maj(a,b,c)); + hh=g; g=f; f=e; + e=d.copy(); e.add(t1); + + d=c; + c=b; + b=a; + a=t1.copy(); a.add(t2); + } + + this.h[0].add(a); this.h[1].add(b); this.h[2].add(c); this.h[3].add(d); + this.h[4].add(e); this.h[5].add(f); this.h[6].add(g); this.h[7].add(hh); + }, + +/* Initialise Hash function */ + init: function() + { /* initialise */ + var i; + for (i=0;i<80;i++) this.w[i]=new UInt64(0,0); + this.length[0]=new UInt64(0,0); this.length[1]=new UInt64(0,0); + this.h[0]=HASH384.H[0].copy(); + this.h[1]=HASH384.H[1].copy(); + this.h[2]=HASH384.H[2].copy(); + this.h[3]=HASH384.H[3].copy(); + this.h[4]=HASH384.H[4].copy(); + this.h[5]=HASH384.H[5].copy(); + this.h[6]=HASH384.H[6].copy(); + this.h[7]=HASH384.H[7].copy(); + }, + +/* process a single byte */ + process: function(byt) + { /* process the next message byte */ + var cnt; + cnt=(this.length[0].bot>>>6)%16; + this.w[cnt].shlb(); + this.w[cnt].bot|=(byt&0xFF); + + var e=new UInt64(0,8); + this.length[0].add(e); + if (this.length[0].top===0 && this.length[0].bot==0) { e=new UInt64(0,1); this.length[1].add(e); } + if ((this.length[0].bot%1024)===0) this.transform(); + }, + +/* process an array of bytes */ + process_array: function(b) + { + for (var i=0;i<b.length;i++) this.process(b[i]); + }, + +/* process a 32-bit integer */ + process_num: function(n) + { + this.process((n>>24)&0xff); + this.process((n>>16)&0xff); + this.process((n>>8)&0xff); + this.process(n&0xff); + }, + + hash: function() + { /* pad message and finish - supply digest */ + var i; + var digest=[]; + var len0,len1; + len0=this.length[0].copy(); + len1=this.length[1].copy(); + this.process(0x80); + while ((this.length[0].bot%1024)!=896) this.process(0); + + this.w[14]=len1; + this.w[15]=len0; + this.transform(); + + for (i=0;i<HASH384.len;i++) + { /* convert to bytes */ + digest[i]=HASH384.R(8*(7-i%8),this.h[i>>>3]).bot&0xff; + } + + this.init(); + return digest; + } +}; + + +/* static functions */ +HASH384.S= function(n,x) +{ + if (n==0) return x; + if (n<32) + return new UInt64((x.top>>>n) | (x.bot<<(32-n)), (x.bot>>>n) | (x.top << (32-n))); + else + return new UInt64((x.bot>>>(n-32)) | (x.top << (64-n)),(x.top>>>(n-32)) | (x.bot<<(64-n))); + +}; + +HASH384.R= function(n,x) +{ + if (n==0) return x; + if (n<32) + return new UInt64((x.top>>>n),(x.bot>>>n | (x.top << (32-n)))); + else + return new UInt64(0,x.top >>> (n-32)); +}; + +HASH384.Ch= function(x,y,z) +{ + return new UInt64((x.top&y.top)^(~(x.top)&z.top),(x.bot&y.bot)^(~(x.bot)&z.bot)); +}; + +HASH384.Maj= function(x,y,z) +{ + return new UInt64((x.top&y.top)^(x.top&z.top)^(y.top&z.top),(x.bot&y.bot)^(x.bot&z.bot)^(y.bot&z.bot)); +}; + +HASH384.Sig0= function(x) +{ + var r1=HASH384.S(28,x); + var r2=HASH384.S(34,x); + var r3=HASH384.S(39,x); + return new UInt64(r1.top^r2.top^r3.top,r1.bot^r2.bot^r3.bot); +}; + +HASH384.Sig1= function(x) +{ + var r1=HASH384.S(14,x); + var r2=HASH384.S(18,x); + var r3=HASH384.S(41,x); + return new UInt64(r1.top^r2.top^r3.top,r1.bot^r2.bot^r3.bot); +}; + +HASH384.theta0= function(x) +{ + var r1=HASH384.S(1,x); + var r2=HASH384.S(8,x); + var r3=HASH384.R(7,x); + return new UInt64(r1.top^r2.top^r3.top,r1.bot^r2.bot^r3.bot); +}; + +HASH384.theta1= function(x) +{ + var r1=HASH384.S(19,x); + var r2=HASH384.S(61,x); + var r3=HASH384.R(6,x); + return new UInt64(r1.top^r2.top^r3.top,r1.bot^r2.bot^r3.bot); +}; + +HASH384.len= 48; + +HASH384.H = [new UInt64(0xcbbb9d5d,0xc1059ed8), new UInt64(0x629a292a,0x367cd507), + new UInt64(0x9159015a,0x3070dd17), new UInt64(0x152fecd8,0xf70e5939), + new UInt64(0x67332667,0xffc00b31), new UInt64(0x8eb44a87,0x68581511), + new UInt64(0xdb0c2e0d,0x64f98fa7), new UInt64(0x47b5481d,0xbefa4fa4)]; + +HASH384.HK = [new UInt64(0x428a2f98, 0xd728ae22), new UInt64(0x71374491, 0x23ef65cd), + new UInt64(0xb5c0fbcf, 0xec4d3b2f), new UInt64(0xe9b5dba5, 0x8189dbbc), + new UInt64(0x3956c25b, 0xf348b538), new UInt64(0x59f111f1, 0xb605d019), + new UInt64(0x923f82a4, 0xaf194f9b), new UInt64(0xab1c5ed5, 0xda6d8118), + new UInt64(0xd807aa98, 0xa3030242), new UInt64(0x12835b01, 0x45706fbe), + new UInt64(0x243185be, 0x4ee4b28c), new UInt64(0x550c7dc3, 0xd5ffb4e2), + new UInt64(0x72be5d74, 0xf27b896f), new UInt64(0x80deb1fe, 0x3b1696b1), + new UInt64(0x9bdc06a7, 0x25c71235), new UInt64(0xc19bf174, 0xcf692694), + new UInt64(0xe49b69c1, 0x9ef14ad2), new UInt64(0xefbe4786, 0x384f25e3), + new UInt64(0x0fc19dc6, 0x8b8cd5b5), new UInt64(0x240ca1cc, 0x77ac9c65), + new UInt64(0x2de92c6f, 0x592b0275), new UInt64(0x4a7484aa, 0x6ea6e483), + new UInt64(0x5cb0a9dc, 0xbd41fbd4), new UInt64(0x76f988da, 0x831153b5), + new UInt64(0x983e5152, 0xee66dfab), new UInt64(0xa831c66d, 0x2db43210), + new UInt64(0xb00327c8, 0x98fb213f), new UInt64(0xbf597fc7, 0xbeef0ee4), + new UInt64(0xc6e00bf3, 0x3da88fc2), new UInt64(0xd5a79147, 0x930aa725), + new UInt64(0x06ca6351, 0xe003826f), new UInt64(0x14292967, 0x0a0e6e70), + new UInt64(0x27b70a85, 0x46d22ffc), new UInt64(0x2e1b2138, 0x5c26c926), + new UInt64(0x4d2c6dfc, 0x5ac42aed), new UInt64(0x53380d13, 0x9d95b3df), + new UInt64(0x650a7354, 0x8baf63de), new UInt64(0x766a0abb, 0x3c77b2a8), + new UInt64(0x81c2c92e, 0x47edaee6), new UInt64(0x92722c85, 0x1482353b), + new UInt64(0xa2bfe8a1, 0x4cf10364), new UInt64(0xa81a664b, 0xbc423001), + new UInt64(0xc24b8b70, 0xd0f89791), new UInt64(0xc76c51a3, 0x0654be30), + new UInt64(0xd192e819, 0xd6ef5218), new UInt64(0xd6990624, 0x5565a910), + new UInt64(0xf40e3585, 0x5771202a), new UInt64(0x106aa070, 0x32bbd1b8), + new UInt64(0x19a4c116, 0xb8d2d0c8), new UInt64(0x1e376c08, 0x5141ab53), + new UInt64(0x2748774c, 0xdf8eeb99), new UInt64(0x34b0bcb5, 0xe19b48a8), + new UInt64(0x391c0cb3, 0xc5c95a63), new UInt64(0x4ed8aa4a, 0xe3418acb), + new UInt64(0x5b9cca4f, 0x7763e373), new UInt64(0x682e6ff3, 0xd6b2b8a3), + new UInt64(0x748f82ee, 0x5defb2fc), new UInt64(0x78a5636f, 0x43172f60), + new UInt64(0x84c87814, 0xa1f0ab72), new UInt64(0x8cc70208, 0x1a6439ec), + new UInt64(0x90befffa, 0x23631e28), new UInt64(0xa4506ceb, 0xde82bde9), + new UInt64(0xbef9a3f7, 0xb2c67915), new UInt64(0xc67178f2, 0xe372532b), + new UInt64(0xca273ece, 0xea26619c), new UInt64(0xd186b8c7, 0x21c0c207), + new UInt64(0xeada7dd6, 0xcde0eb1e), new UInt64(0xf57d4f7f, 0xee6ed178), + new UInt64(0x06f067aa, 0x72176fba), new UInt64(0x0a637dc5, 0xa2c898a6), + new UInt64(0x113f9804, 0xbef90dae), new UInt64(0x1b710b35, 0x131c471b), + new UInt64(0x28db77f5, 0x23047d84), new UInt64(0x32caab7b, 0x40c72493), + new UInt64(0x3c9ebe0a, 0x15c9bebc), new UInt64(0x431d67c4, 0x9c100d4c), + new UInt64(0x4cc5d4be, 0xcb3e42b6), new UInt64(0x597f299c, 0xfc657e2a), + new UInt64(0x5fcb6fab, 0x3ad6faec), new UInt64(0x6c44198c, 0x4a475817)]; \ No newline at end of file
