http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/AES.js ---------------------------------------------------------------------- diff --git a/version22/js/AES.js b/version22/js/AES.js new file mode 100644 index 0000000..140e9c3 --- /dev/null +++ b/version22/js/AES.js @@ -0,0 +1,634 @@ +/* + 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 AES = function() { + this.Nk=0; + this.Nr=0; + this.mode=0; + this.fkey=[]; + this.rkey=[]; + this.f=[]; +}; + +AES.prototype={ +/* reset cipher */ + reset:function(m,iv) + { /* reset mode, or reset iv */ + var i; + this.mode=m; + for (i=0;i<16;i++) + this.f[i]=0; + if (this.mode!=ROM.ECB && iv!==null) + for (i=0;i<16;i++) + this.f[i]=iv[i]; + }, + + getreg:function() + { + var ir=[]; + for (var i=0;i<16;i++) ir[i]=this.f[i]; + return ir; + }, + + increment:function() + { + for (var i=0;i<16;i++) + { + this.f[i]++; + if ((this.f[i]&0xff)!=0) break; + } + }, + +/* Initialise cipher */ + init: function(m,nk,key,iv) + { /* Key=16 bytes */ + /* Key Scheduler. Create expanded encryption key */ + var i,j,k,N,nr; + var CipherKey= []; + var b=[]; + nk/=4; + + if (nk!=4 && nk!=6 && nk!=8) return false; + + nr=6+nk; + + this.Nk=nk; this.Nr=nr; + + + this.reset(m,iv); + N=4*(nr+1); + + for (i=j=0;i<nk;i++,j+=4) + { + for (k=0;k<4;k++) b[k]=key[j+k]; + CipherKey[i]=AES.pack(b); + } + for (i=0;i<nk;i++) this.fkey[i]=CipherKey[i]; + for (j=nk,k=0;j<N;j+=nk,k++) + { + this.fkey[j]=this.fkey[j-nk]^AES.SubByte(AES.ROTL24(this.fkey[j-1]))^(AES.rco[k])&0xff; + for (i=1;i<nk && (i+j)<N;i++) + this.fkey[i+j]=this.fkey[i+j-nk]^this.fkey[i+j-1]; + } + + /* now for the expanded decrypt key in reverse order */ + + for (j=0;j<4;j++) this.rkey[j+N-4]=this.fkey[j]; + for (i=4;i<N-4;i+=4) + { + k=N-4-i; + for (j=0;j<4;j++) this.rkey[k+j]=AES.InvMixCol(this.fkey[i+j]); + } + for (j=N-4;j<N;j++) this.rkey[j-N+4]=this.fkey[j]; + }, + +/* Encrypt a single block */ + ecb_encrypt: function(buff) + { + var i,j,k; + var t; + var b=[]; + var p=[]; + var q=[]; + + for (i=j=0;i<4;i++,j+=4) + { + for (k=0;k<4;k++) b[k]=buff[j+k]; + p[i]=AES.pack(b); + p[i]^=this.fkey[i]; + } + + k=4; + +/* State alternates between p and q */ + for (i=1;i<this.Nr;i++) + { + q[0]=this.fkey[k]^AES.ftable[p[0]&0xff]^ + AES.ROTL8(AES.ftable[(p[1]>>>8)&0xff])^ + AES.ROTL16(AES.ftable[(p[2]>>>16)&0xff])^ + AES.ROTL24(AES.ftable[(p[3]>>>24)&0xff]); + q[1]=this.fkey[k+1]^AES.ftable[p[1]&0xff]^ + AES.ROTL8(AES.ftable[(p[2]>>>8)&0xff])^ + AES.ROTL16(AES.ftable[(p[3]>>>16)&0xff])^ + AES.ROTL24(AES.ftable[(p[0]>>>24)&0xff]); + q[2]=this.fkey[k+2]^AES.ftable[p[2]&0xff]^ + AES.ROTL8(AES.ftable[(p[3]>>>8)&0xff])^ + AES.ROTL16(AES.ftable[(p[0]>>>16)&0xff])^ + AES.ROTL24(AES.ftable[(p[1]>>>24)&0xff]); + q[3]=this.fkey[k+3]^AES.ftable[p[3]&0xff]^ + AES.ROTL8(AES.ftable[(p[0]>>>8)&0xff])^ + AES.ROTL16(AES.ftable[(p[1]>>>16)&0xff])^ + AES.ROTL24(AES.ftable[(p[2]>>>24)&0xff]); + + k+=4; + for (j=0;j<4;j++) + { + t=p[j]; p[j]=q[j]; q[j]=t; + } + } + +/* Last Round */ + + q[0]=this.fkey[k]^(AES.fbsub[p[0]&0xff]&0xff)^ + AES.ROTL8(AES.fbsub[(p[1]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.fbsub[(p[2]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.fbsub[(p[3]>>>24)&0xff]&0xff); + + q[1]=this.fkey[k+1]^(AES.fbsub[p[1]&0xff]&0xff)^ + AES.ROTL8(AES.fbsub[(p[2]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.fbsub[(p[3]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.fbsub[(p[0]>>>24)&0xff]&0xff); + + q[2]=this.fkey[k+2]^(AES.fbsub[p[2]&0xff]&0xff)^ + AES.ROTL8(AES.fbsub[(p[3]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.fbsub[(p[0]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.fbsub[(p[1]>>>24)&0xff]&0xff); + + q[3]=this.fkey[k+3]^(AES.fbsub[(p[3])&0xff]&0xff)^ + AES.ROTL8(AES.fbsub[(p[0]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.fbsub[(p[1]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.fbsub[(p[2]>>>24)&0xff]&0xff); + + for (i=j=0;i<4;i++,j+=4) + { + b=AES.unpack(q[i]); + for (k=0;k<4;k++) buff[j+k]=b[k]; + } + }, + +/* Decrypt a single block */ + ecb_decrypt: function(buff) + { + var i,j,k; + var t; + var b=[]; + var p=[]; + var q=[]; + + for (i=j=0;i<4;i++,j+=4) + { + for (k=0;k<4;k++) b[k]=buff[j+k]; + p[i]=AES.pack(b); + p[i]^=this.rkey[i]; + } + + k=4; + +/* State alternates between p and q */ + for (i=1;i<this.Nr;i++) + { + q[0]=this.rkey[k]^AES.rtable[p[0]&0xff]^ + AES.ROTL8(AES.rtable[(p[3]>>>8)&0xff])^ + AES.ROTL16(AES.rtable[(p[2]>>>16)&0xff])^ + AES.ROTL24(AES.rtable[(p[1]>>>24)&0xff]); + q[1]=this.rkey[k+1]^AES.rtable[p[1]&0xff]^ + AES.ROTL8(AES.rtable[(p[0]>>>8)&0xff])^ + AES.ROTL16(AES.rtable[(p[3]>>>16)&0xff])^ + AES.ROTL24(AES.rtable[(p[2]>>>24)&0xff]); + q[2]=this.rkey[k+2]^AES.rtable[p[2]&0xff]^ + AES.ROTL8(AES.rtable[(p[1]>>>8)&0xff])^ + AES.ROTL16(AES.rtable[(p[0]>>>16)&0xff])^ + AES.ROTL24(AES.rtable[(p[3]>>>24)&0xff]); + q[3]=this.rkey[k+3]^AES.rtable[p[3]&0xff]^ + AES.ROTL8(AES.rtable[(p[2]>>>8)&0xff])^ + AES.ROTL16(AES.rtable[(p[1]>>>16)&0xff])^ + AES.ROTL24(AES.rtable[(p[0]>>>24)&0xff]); + + k+=4; + for (j=0;j<4;j++) + { + t=p[j]; p[j]=q[j]; q[j]=t; + } + } + +/* Last Round */ + + q[0]=this.rkey[k]^(AES.rbsub[p[0]&0xff]&0xff)^ + AES.ROTL8(AES.rbsub[(p[3]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.rbsub[(p[2]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.rbsub[(p[1]>>>24)&0xff]&0xff); + q[1]=this.rkey[k+1]^(AES.rbsub[p[1]&0xff]&0xff)^ + AES.ROTL8(AES.rbsub[(p[0]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.rbsub[(p[3]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.rbsub[(p[2]>>>24)&0xff]&0xff); + q[2]=this.rkey[k+2]^(AES.rbsub[p[2]&0xff]&0xff)^ + AES.ROTL8(AES.rbsub[(p[1]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.rbsub[(p[0]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.rbsub[(p[3]>>>24)&0xff]&0xff); + q[3]=this.rkey[k+3]^(AES.rbsub[p[3]&0xff]&0xff)^ + AES.ROTL8(AES.rbsub[(p[2]>>>8)&0xff]&0xff)^ + AES.ROTL16(AES.rbsub[(p[1]>>>16)&0xff]&0xff)^ + AES.ROTL24(AES.rbsub[(p[0]>>>24)&0xff]&0xff); + + for (i=j=0;i<4;i++,j+=4) + { + b=AES.unpack(q[i]); + for (k=0;k<4;k++) buff[j+k]=b[k]; + } + + }, + +/* Encrypt using selected mode of operation */ + encrypt: function(buff) + { + var j,bytes; + var st=[]; + var fell_off; + +// Supported Modes of Operation + + fell_off=0; + + switch (this.mode) + { + case ROM.ECB: + this.ecb_encrypt(buff); + return 0; + case ROM.CBC: + for (j=0;j<16;j++) buff[j]^=this.f[j]; + this.ecb_encrypt(buff); + for (j=0;j<16;j++) this.f[j]=buff[j]; + return 0; + + case ROM.CFB1: + case ROM.CFB2: + case ROM.CFB4: + bytes=this.mode-ROM.CFB1+1; + for (j=0;j<bytes;j++) fell_off=(fell_off<<8)|this.f[j]; + for (j=0;j<16;j++) st[j]=this.f[j]; + for (j=bytes;j<16;j++) this.f[j-bytes]=this.f[j]; + this.ecb_encrypt(st); + for (j=0;j<bytes;j++) + { + buff[j]^=st[j]; + this.f[16-bytes+j]=buff[j]; + } + return fell_off; + + case ROM.OFB1: + case ROM.OFB2: + case ROM.OFB4: + case ROM.OFB8: + case ROM.OFB16: + + bytes=this.mode-ROM.OFB1+1; + this.ecb_encrypt(this.f); + for (j=0;j<bytes;j++) buff[j]^=this.f[j]; + return 0; + + case ROM.CTR1: + case ROM.CTR2: + case ROM.CTR4: + case ROM.CTR8: + case ROM.CTR16: + + bytes=this.mode-ROM.CTR1+1; + for (j=0;j<16;j++) st[j]=this.f[j]; + this.ecb_encrypt(st); + for (j=0;j<bytes;j++) buff[j]^=st[j]; + this.increment(); + + default: + return 0; + } + }, + +/* Decrypt using selected mode of operation */ + decrypt: function(buff) + { + var j,bytes; + var st=[]; + var fell_off; + + // Supported modes of operation + fell_off=0; + switch (this.mode) + { + case ROM.ECB: + this.ecb_decrypt(buff); + return 0; + case ROM.CBC: + for (j=0;j<16;j++) + { + st[j]=this.f[j]; + this.f[j]=buff[j]; + } + this.ecb_decrypt(buff); + for (j=0;j<16;j++) + { + buff[j]^=st[j]; + st[j]=0; + } + return 0; + case ROM.CFB1: + case ROM.CFB2: + case ROM.CFB4: + bytes=this.mode-ROM.CFB1+1; + for (j=0;j<bytes;j++) fell_off=(fell_off<<8)|this.f[j]; + for (j=0;j<16;j++) st[j]=this.f[j]; + for (j=bytes;j<16;j++) this.f[j-bytes]=this.f[j]; + this.ecb_encrypt(st); + for (j=0;j<bytes;j++) + { + this.f[16-bytes+j]=buff[j]; + buff[j]^=st[j]; + } + return fell_off; + case ROM.OFB1: + case ROM.OFB2: + case ROM.OFB4: + case ROM.OFB8: + case ROM.OFB16: + bytes=this.mode-ROM.OFB1+1; + this.ecb_encrypt(this.f); + for (j=0;j<bytes;j++) buff[j]^=this.f[j]; + return 0; + + case ROM.CTR1: + case ROM.CTR2: + case ROM.CTR4: + case ROM.CTR8: + case ROM.CTR16: + bytes=this.mode-ROM.CTR1+1; + for (j=0;j<16;j++) st[j]=this.f[j]; + this.ecb_encrypt(st); + for (j=0;j<bytes;j++) buff[j]^=st[j]; + this.increment(); + default: + return 0; + } + }, + +/* Clean up and delete left-overs */ + end: function() + { // clean up + var i; + for (i=0;i<4*(this.Nr+1);i++) + this.fkey[i]=this.rkey[i]=0; + for (i=0;i<16;i++) + this.f[i]=0; + } + +}; + +/* static functions */ + +AES.ROTL8=function(x) +{ + return (((x)<<8)|((x)>>>24)); +}; + +AES.ROTL16=function(x) +{ + return (((x)<<16)|((x)>>>16)); +}; + +AES.ROTL24=function(x) +{ + return (((x)<<24)|((x)>>>8)); +}; + +AES.pack= function(b) +{ /* pack 4 bytes into a 32-bit Word */ + return (((b[3])&0xff)<<24)|((b[2]&0xff)<<16)|((b[1]&0xff)<<8)|(b[0]&0xff); +}; + +AES.unpack=function(a) +{ /* unpack bytes from a word */ + var b=[]; + b[0]=(a&0xff); + b[1]=((a>>>8)&0xff); + b[2]=((a>>>16)&0xff); + b[3]=((a>>>24)&0xff); + return b; +}; + +AES.bmul=function(x,y) +{ /* x.y= AntiLog(Log(x) + Log(y)) */ + + var ix=(x&0xff); + var iy=(y&0xff); + var lx=(AES.ltab[ix])&0xff; + var ly=(AES.ltab[iy])&0xff; + if (x!==0 && y!==0) return AES.ptab[(lx+ly)%255]; + else return 0; +}; + +// if (x && y) + +AES.SubByte=function(a) +{ + var b=AES.unpack(a); + b[0]=AES.fbsub[b[0]&0xff]; + b[1]=AES.fbsub[b[1]&0xff]; + b[2]=AES.fbsub[b[2]&0xff]; + b[3]=AES.fbsub[b[3]&0xff]; + return AES.pack(b); +}; + +AES.product=function(x,y) +{ /* dot product of two 4-byte arrays */ + var xb=AES.unpack(x); + var yb=AES.unpack(y); + return (AES.bmul(xb[0],yb[0])^AES.bmul(xb[1],yb[1])^AES.bmul(xb[2],yb[2])^AES.bmul(xb[3],yb[3]))&0xff; +}; + +AES.InvMixCol=function(x) +{ /* matrix Multiplication */ + var y,m; + var b=[]; + m=AES.pack(AES.InCo); + b[3]=AES.product(m,x); + m=AES.ROTL24(m); + b[2]=AES.product(m,x); + m=AES.ROTL24(m); + b[1]=AES.product(m,x); + m=AES.ROTL24(m); + b[0]=AES.product(m,x); + y=AES.pack(b); + return y; +}; + +AES.InCo=[0xB,0xD,0x9,0xE]; /* Inverse Coefficients */ +AES.rco=[1,2,4,8,16,32,64,128,27,54,108,216,171,77,154,47]; + +AES.ptab=[ + 1,3,5,15,17,51,85,255,26,46,114,150,161,248,19,53, + 95,225,56,72,216,115,149,164,247,2,6,10,30,34,102,170, + 229,52,92,228,55,89,235,38,106,190,217,112,144,171,230,49, + 83,245,4,12,20,60,68,204,79,209,104,184,211,110,178,205, + 76,212,103,169,224,59,77,215,98,166,241,8,24,40,120,136, + 131,158,185,208,107,189,220,127,129,152,179,206,73,219,118,154, + 181,196,87,249,16,48,80,240,11,29,39,105,187,214,97,163, + 254,25,43,125,135,146,173,236,47,113,147,174,233,32,96,160, + 251,22,58,78,210,109,183,194,93,231,50,86,250,21,63,65, + 195,94,226,61,71,201,64,192,91,237,44,116,156,191,218,117, + 159,186,213,100,172,239,42,126,130,157,188,223,122,142,137,128, + 155,182,193,88,232,35,101,175,234,37,111,177,200,67,197,84, + 252,31,33,99,165,244,7,9,27,45,119,153,176,203,70,202, + 69,207,74,222,121,139,134,145,168,227,62,66,198,81,243,14, + 18,54,90,238,41,123,141,140,143,138,133,148,167,242,13,23, + 57,75,221,124,132,151,162,253,28,36,108,180,199,82,246,1 + ]; +AES.ltab=[ + 0,255,25,1,50,2,26,198,75,199,27,104,51,238,223,3, + 100,4,224,14,52,141,129,239,76,113,8,200,248,105,28,193, + 125,194,29,181,249,185,39,106,77,228,166,114,154,201,9,120, + 101,47,138,5,33,15,225,36,18,240,130,69,53,147,218,142, + 150,143,219,189,54,208,206,148,19,92,210,241,64,70,131,56, + 102,221,253,48,191,6,139,98,179,37,226,152,34,136,145,16, + 126,110,72,195,163,182,30,66,58,107,40,84,250,133,61,186, + 43,121,10,21,155,159,94,202,78,212,172,229,243,115,167,87, + 175,88,168,80,244,234,214,116,79,174,233,213,231,230,173,232, + 44,215,117,122,235,22,11,245,89,203,95,176,156,169,81,160, + 127,12,246,111,23,196,73,236,216,67,31,45,164,118,123,183, + 204,187,62,90,251,96,177,134,59,82,161,108,170,85,41,157, + 151,178,135,144,97,190,220,252,188,149,207,205,55,63,91,209, + 83,57,132,60,65,162,109,71,20,42,158,93,86,242,211,171, + 68,17,146,217,35,32,46,137,180,124,184,38,119,153,227,165, + 103,74,237,222,197,49,254,24,13,99,140,128,192,247,112,7 + ]; +AES.fbsub=[ + 99,124,119,123,242,107,111,197,48,1,103,43,254,215,171,118, + 202,130,201,125,250,89,71,240,173,212,162,175,156,164,114,192, + 183,253,147,38,54,63,247,204,52,165,229,241,113,216,49,21, + 4,199,35,195,24,150,5,154,7,18,128,226,235,39,178,117, + 9,131,44,26,27,110,90,160,82,59,214,179,41,227,47,132, + 83,209,0,237,32,252,177,91,106,203,190,57,74,76,88,207, + 208,239,170,251,67,77,51,133,69,249,2,127,80,60,159,168, + 81,163,64,143,146,157,56,245,188,182,218,33,16,255,243,210, + 205,12,19,236,95,151,68,23,196,167,126,61,100,93,25,115, + 96,129,79,220,34,42,144,136,70,238,184,20,222,94,11,219, + 224,50,58,10,73,6,36,92,194,211,172,98,145,149,228,121, + 231,200,55,109,141,213,78,169,108,86,244,234,101,122,174,8, + 186,120,37,46,28,166,180,198,232,221,116,31,75,189,139,138, + 112,62,181,102,72,3,246,14,97,53,87,185,134,193,29,158, + 225,248,152,17,105,217,142,148,155,30,135,233,206,85,40,223, + 140,161,137,13,191,230,66,104,65,153,45,15,176,84,187,22 + ]; +AES.rbsub=[ + 82,9,106,213,48,54,165,56,191,64,163,158,129,243,215,251, + 124,227,57,130,155,47,255,135,52,142,67,68,196,222,233,203, + 84,123,148,50,166,194,35,61,238,76,149,11,66,250,195,78, + 8,46,161,102,40,217,36,178,118,91,162,73,109,139,209,37, + 114,248,246,100,134,104,152,22,212,164,92,204,93,101,182,146, + 108,112,72,80,253,237,185,218,94,21,70,87,167,141,157,132, + 144,216,171,0,140,188,211,10,247,228,88,5,184,179,69,6, + 208,44,30,143,202,63,15,2,193,175,189,3,1,19,138,107, + 58,145,17,65,79,103,220,234,151,242,207,206,240,180,230,115, + 150,172,116,34,231,173,53,133,226,249,55,232,28,117,223,110, + 71,241,26,113,29,41,197,137,111,183,98,14,170,24,190,27, + 252,86,62,75,198,210,121,32,154,219,192,254,120,205,90,244, + 31,221,168,51,136,7,199,49,177,18,16,89,39,128,236,95, + 96,81,127,169,25,181,74,13,45,229,122,159,147,201,156,239, + 160,224,59,77,174,42,245,176,200,235,187,60,131,83,153,97, + 23,43,4,126,186,119,214,38,225,105,20,99,85,33,12,125 + ]; +AES.ftable=[ + 0xa56363c6,0x847c7cf8,0x997777ee,0x8d7b7bf6,0xdf2f2ff,0xbd6b6bd6, + 0xb16f6fde,0x54c5c591,0x50303060,0x3010102,0xa96767ce,0x7d2b2b56, + 0x19fefee7,0x62d7d7b5,0xe6abab4d,0x9a7676ec,0x45caca8f,0x9d82821f, + 0x40c9c989,0x877d7dfa,0x15fafaef,0xeb5959b2,0xc947478e,0xbf0f0fb, + 0xecadad41,0x67d4d4b3,0xfda2a25f,0xeaafaf45,0xbf9c9c23,0xf7a4a453, + 0x967272e4,0x5bc0c09b,0xc2b7b775,0x1cfdfde1,0xae93933d,0x6a26264c, + 0x5a36366c,0x413f3f7e,0x2f7f7f5,0x4fcccc83,0x5c343468,0xf4a5a551, + 0x34e5e5d1,0x8f1f1f9,0x937171e2,0x73d8d8ab,0x53313162,0x3f15152a, + 0xc040408,0x52c7c795,0x65232346,0x5ec3c39d,0x28181830,0xa1969637, + 0xf05050a,0xb59a9a2f,0x907070e,0x36121224,0x9b80801b,0x3de2e2df, + 0x26ebebcd,0x6927274e,0xcdb2b27f,0x9f7575ea,0x1b090912,0x9e83831d, + 0x742c2c58,0x2e1a1a34,0x2d1b1b36,0xb26e6edc,0xee5a5ab4,0xfba0a05b, + 0xf65252a4,0x4d3b3b76,0x61d6d6b7,0xceb3b37d,0x7b292952,0x3ee3e3dd, + 0x712f2f5e,0x97848413,0xf55353a6,0x68d1d1b9,0x0,0x2cededc1, + 0x60202040,0x1ffcfce3,0xc8b1b179,0xed5b5bb6,0xbe6a6ad4,0x46cbcb8d, + 0xd9bebe67,0x4b393972,0xde4a4a94,0xd44c4c98,0xe85858b0,0x4acfcf85, + 0x6bd0d0bb,0x2aefefc5,0xe5aaaa4f,0x16fbfbed,0xc5434386,0xd74d4d9a, + 0x55333366,0x94858511,0xcf45458a,0x10f9f9e9,0x6020204,0x817f7ffe, + 0xf05050a0,0x443c3c78,0xba9f9f25,0xe3a8a84b,0xf35151a2,0xfea3a35d, + 0xc0404080,0x8a8f8f05,0xad92923f,0xbc9d9d21,0x48383870,0x4f5f5f1, + 0xdfbcbc63,0xc1b6b677,0x75dadaaf,0x63212142,0x30101020,0x1affffe5, + 0xef3f3fd,0x6dd2d2bf,0x4ccdcd81,0x140c0c18,0x35131326,0x2fececc3, + 0xe15f5fbe,0xa2979735,0xcc444488,0x3917172e,0x57c4c493,0xf2a7a755, + 0x827e7efc,0x473d3d7a,0xac6464c8,0xe75d5dba,0x2b191932,0x957373e6, + 0xa06060c0,0x98818119,0xd14f4f9e,0x7fdcdca3,0x66222244,0x7e2a2a54, + 0xab90903b,0x8388880b,0xca46468c,0x29eeeec7,0xd3b8b86b,0x3c141428, + 0x79dedea7,0xe25e5ebc,0x1d0b0b16,0x76dbdbad,0x3be0e0db,0x56323264, + 0x4e3a3a74,0x1e0a0a14,0xdb494992,0xa06060c,0x6c242448,0xe45c5cb8, + 0x5dc2c29f,0x6ed3d3bd,0xefacac43,0xa66262c4,0xa8919139,0xa4959531, + 0x37e4e4d3,0x8b7979f2,0x32e7e7d5,0x43c8c88b,0x5937376e,0xb76d6dda, + 0x8c8d8d01,0x64d5d5b1,0xd24e4e9c,0xe0a9a949,0xb46c6cd8,0xfa5656ac, + 0x7f4f4f3,0x25eaeacf,0xaf6565ca,0x8e7a7af4,0xe9aeae47,0x18080810, + 0xd5baba6f,0x887878f0,0x6f25254a,0x722e2e5c,0x241c1c38,0xf1a6a657, + 0xc7b4b473,0x51c6c697,0x23e8e8cb,0x7cdddda1,0x9c7474e8,0x211f1f3e, + 0xdd4b4b96,0xdcbdbd61,0x868b8b0d,0x858a8a0f,0x907070e0,0x423e3e7c, + 0xc4b5b571,0xaa6666cc,0xd8484890,0x5030306,0x1f6f6f7,0x120e0e1c, + 0xa36161c2,0x5f35356a,0xf95757ae,0xd0b9b969,0x91868617,0x58c1c199, + 0x271d1d3a,0xb99e9e27,0x38e1e1d9,0x13f8f8eb,0xb398982b,0x33111122, + 0xbb6969d2,0x70d9d9a9,0x898e8e07,0xa7949433,0xb69b9b2d,0x221e1e3c, + 0x92878715,0x20e9e9c9,0x49cece87,0xff5555aa,0x78282850,0x7adfdfa5, + 0x8f8c8c03,0xf8a1a159,0x80898909,0x170d0d1a,0xdabfbf65,0x31e6e6d7, + 0xc6424284,0xb86868d0,0xc3414182,0xb0999929,0x772d2d5a,0x110f0f1e, + 0xcbb0b07b,0xfc5454a8,0xd6bbbb6d,0x3a16162c + ]; +AES.rtable=[ + 0x50a7f451,0x5365417e,0xc3a4171a,0x965e273a,0xcb6bab3b,0xf1459d1f, + 0xab58faac,0x9303e34b,0x55fa3020,0xf66d76ad,0x9176cc88,0x254c02f5, + 0xfcd7e54f,0xd7cb2ac5,0x80443526,0x8fa362b5,0x495ab1de,0x671bba25, + 0x980eea45,0xe1c0fe5d,0x2752fc3,0x12f04c81,0xa397468d,0xc6f9d36b, + 0xe75f8f03,0x959c9215,0xeb7a6dbf,0xda595295,0x2d83bed4,0xd3217458, + 0x2969e049,0x44c8c98e,0x6a89c275,0x78798ef4,0x6b3e5899,0xdd71b927, + 0xb64fe1be,0x17ad88f0,0x66ac20c9,0xb43ace7d,0x184adf63,0x82311ae5, + 0x60335197,0x457f5362,0xe07764b1,0x84ae6bbb,0x1ca081fe,0x942b08f9, + 0x58684870,0x19fd458f,0x876cde94,0xb7f87b52,0x23d373ab,0xe2024b72, + 0x578f1fe3,0x2aab5566,0x728ebb2,0x3c2b52f,0x9a7bc586,0xa50837d3, + 0xf2872830,0xb2a5bf23,0xba6a0302,0x5c8216ed,0x2b1ccf8a,0x92b479a7, + 0xf0f207f3,0xa1e2694e,0xcdf4da65,0xd5be0506,0x1f6234d1,0x8afea6c4, + 0x9d532e34,0xa055f3a2,0x32e18a05,0x75ebf6a4,0x39ec830b,0xaaef6040, + 0x69f715e,0x51106ebd,0xf98a213e,0x3d06dd96,0xae053edd,0x46bde64d, + 0xb58d5491,0x55dc471,0x6fd40604,0xff155060,0x24fb9819,0x97e9bdd6, + 0xcc434089,0x779ed967,0xbd42e8b0,0x888b8907,0x385b19e7,0xdbeec879, + 0x470a7ca1,0xe90f427c,0xc91e84f8,0x0,0x83868009,0x48ed2b32, + 0xac70111e,0x4e725a6c,0xfbff0efd,0x5638850f,0x1ed5ae3d,0x27392d36, + 0x64d90f0a,0x21a65c68,0xd1545b9b,0x3a2e3624,0xb1670a0c,0xfe75793, + 0xd296eeb4,0x9e919b1b,0x4fc5c080,0xa220dc61,0x694b775a,0x161a121c, + 0xaba93e2,0xe52aa0c0,0x43e0223c,0x1d171b12,0xb0d090e,0xadc78bf2, + 0xb9a8b62d,0xc8a91e14,0x8519f157,0x4c0775af,0xbbdd99ee,0xfd607fa3, + 0x9f2601f7,0xbcf5725c,0xc53b6644,0x347efb5b,0x7629438b,0xdcc623cb, + 0x68fcedb6,0x63f1e4b8,0xcadc31d7,0x10856342,0x40229713,0x2011c684, + 0x7d244a85,0xf83dbbd2,0x1132f9ae,0x6da129c7,0x4b2f9e1d,0xf330b2dc, + 0xec52860d,0xd0e3c177,0x6c16b32b,0x99b970a9,0xfa489411,0x2264e947, + 0xc48cfca8,0x1a3ff0a0,0xd82c7d56,0xef903322,0xc74e4987,0xc1d138d9, + 0xfea2ca8c,0x360bd498,0xcf81f5a6,0x28de7aa5,0x268eb7da,0xa4bfad3f, + 0xe49d3a2c,0xd927850,0x9bcc5f6a,0x62467e54,0xc2138df6,0xe8b8d890, + 0x5ef7392e,0xf5afc382,0xbe805d9f,0x7c93d069,0xa92dd56f,0xb31225cf, + 0x3b99acc8,0xa77d1810,0x6e639ce8,0x7bbb3bdb,0x97826cd,0xf418596e, + 0x1b79aec,0xa89a4f83,0x656e95e6,0x7ee6ffaa,0x8cfbc21,0xe6e815ef, + 0xd99be7ba,0xce366f4a,0xd4099fea,0xd67cb029,0xafb2a431,0x31233f2a, + 0x3094a5c6,0xc066a235,0x37bc4e74,0xa6ca82fc,0xb0d090e0,0x15d8a733, + 0x4a9804f1,0xf7daec41,0xe50cd7f,0x2ff69117,0x8dd64d76,0x4db0ef43, + 0x544daacc,0xdf0496e4,0xe3b5d19e,0x1b886a4c,0xb81f2cc1,0x7f516546, + 0x4ea5e9d,0x5d358c01,0x737487fa,0x2e410bfb,0x5a1d67b3,0x52d2db92, + 0x335610e9,0x1347d66d,0x8c61d79a,0x7a0ca137,0x8e14f859,0x893c13eb, + 0xee27a9ce,0x35c961b7,0xede51ce1,0x3cb1477a,0x59dfd29c,0x3f73f255, + 0x79ce1418,0xbf37c773,0xeacdf753,0x5baafd5f,0x146f3ddf,0x86db4478, + 0x81f3afca,0x3ec468b9,0x2c342438,0x5f40a3c2,0x72c31d16,0xc25e2bc, + 0x8b493c28,0x41950dff,0x7101a839,0xdeb30c08,0x9ce4b4d8,0x90c15664, + 0x6184cb7b,0x70b632d5,0x745c6c48,0x4257b8d0 + ]; + +
http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/BIG.js ---------------------------------------------------------------------- diff --git a/version22/js/BIG.js b/version22/js/BIG.js new file mode 100644 index 0000000..11a7fa1 --- /dev/null +++ b/version22/js/BIG.js @@ -0,0 +1,1037 @@ +/* + 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 BIG number class */ + +/* General purpose Constructor */ +var BIG = function(x) { + this.w=new Array(ROM.NLEN); + switch (typeof(x)) + { + case "object": + this.copy(x); + break; + case "number": + this.zero(); + this.w[0]=x; + break; + default: + this.zero(); + } +}; + +BIG.prototype={ +/* set to zero */ + zero: function() + { + for (var i=0;i<ROM.NLEN;i++) this.w[i]=0; + return this; + }, +/* set to one */ + one: function() + { + this.w[0]=1; + for (var i=1;i<ROM.NLEN;i++) this.w[i]=0; + return this; + }, + + get: function(i) + { + return this.w[i]; + }, + + set: function(i,x) + { + this.w[i]=x; + }, +/* test for zero */ + iszilch: function() + { + for (var i=0;i<ROM.NLEN;i++) + if (this.w[i]!==0) return false; + return true; + }, +/* test for unity */ + isunity: function() + { + for (var i=1;i<ROM.NLEN;i++) + if (this.w[i]!==0) return false; + if (this.w[0]!=1) return false; + return true; + }, + +/* Conditional swap of two bigs depending on d using XOR - no branches */ + cswap: function(b,d) + { + var i; + var t,c=d; + c=~(c-1); + + for (i=0;i<ROM.NLEN;i++) + { + t=c&(this.w[i]^b.w[i]); + this.w[i]^=t; + b.w[i]^=t; + } + }, + +/* Conditional move of big depending on d using XOR - no branches */ + cmove: function(b,d) + { + var i; + var c=d; + c=~(c-1); + + for (i=0;i<ROM.NLEN;i++) + { + this.w[i]^=(this.w[i]^b.w[i])&c; + } + }, + +/* copy from another BIG */ + copy: function(y) + { + for (var i=0;i<ROM.NLEN;i++) + this.w[i]=y.w[i]; + return this; + }, +/* copy from bottom half of DBIG */ + hcopy: function(y) + { + for (var i=0;i<ROM.NLEN;i++) + this.w[i]=y.w[i]; + return this; + }, +/* copy from ROM */ + rcopy: function(y) + { + for (var i=0;i<ROM.NLEN;i++) + this.w[i]=y[i]; + return this; + }, + + xortop: function(x) + { + this.w[ROM.NLEN-1]^=x; + }, + + ortop: function(x) + { + this.w[ROM.NLEN-1]|=x; + }, + +/* normalise BIG - force all digits < 2^BASEBITS */ + norm: function() + { + var d,carry=0; + for (var i=0;i<ROM.NLEN-1;i++) + { + d=this.w[i]+carry; + this.w[i]=d&ROM.BMASK; + carry=d>>ROM.BASEBITS; + } + this.w[ROM.NLEN-1]=(this.w[ROM.NLEN-1]+carry); + + return (this.w[ROM.NLEN-1]>>((8*ROM.MODBYTES)%ROM.BASEBITS)); + + }, +/* quick shift right by less than a word */ + fshr: function(k) + { + var r=this.w[0]&((1<<k)-1); /* shifted out part */ + for (var i=0;i<ROM.NLEN-1;i++) + this.w[i]=(this.w[i]>>k)|((this.w[i+1]<<(ROM.BASEBITS-k))&ROM.BMASK); + this.w[ROM.NLEN-1]=this.w[ROM.NLEN-1]>>k; + return r; + }, +/* General shift right by k bits */ + shr: function(k) + { + var n=k%ROM.BASEBITS; + var m=Math.floor(k/ROM.BASEBITS); + for (var i=0;i<ROM.NLEN-m-1;i++) + this.w[i]=(this.w[m+i]>>n)|((this.w[m+i+1]<<(ROM.BASEBITS-n))&ROM.BMASK); + this.w[ROM.NLEN-m-1]=this.w[ROM.NLEN-1]>>n; + for (i=ROM.NLEN-m;i<ROM.NLEN;i++) this.w[i]=0; + return this; + }, +/* quick shift left by less than a word */ + fshl: function(k) + { + this.w[ROM.NLEN-1]=((this.w[ROM.NLEN-1]<<k))|(this.w[ROM.NLEN-2]>>(ROM.BASEBITS-k)); + for (var i=ROM.NLEN-2;i>0;i--) + this.w[i]=((this.w[i]<<k)&ROM.BMASK)|(this.w[i-1]>>(ROM.BASEBITS-k)); + this.w[0]=(this.w[0]<<k)&ROM.BMASK; + + return (this.w[ROM.NLEN-1]>>((8*ROM.MODBYTES)%ROM.BASEBITS)); /* return excess - only used in FF.java */ + }, +/* General shift left by k bits */ + shl: function(k) + { + var i,n=k%ROM.BASEBITS; + var m=Math.floor(k/ROM.BASEBITS); + + this.w[ROM.NLEN-1]=(this.w[ROM.NLEN-1-m]<<n); + if (ROM.NLEN>m+2) this.w[ROM.NLEN-1]|=(this.w[ROM.NLEN-m-2]>>(ROM.BASEBITS-n)); + for (i=ROM.NLEN-2;i>m;i--) + this.w[i]=((this.w[i-m]<<n)&ROM.BMASK)|(this.w[i-m-1]>>(ROM.BASEBITS-n)); + this.w[m]=(this.w[0]<<n)&ROM.BMASK; + for (i=0;i<m;i++) this.w[i]=0; + return this; + }, +/* return length in bits */ + nbits: function() + { + var bts,k=ROM.NLEN-1; + var c; + this.norm(); + while (k>=0 && this.w[k]===0) k--; + if (k<0) return 0; + bts=ROM.BASEBITS*k; + c=this.w[k]; + while (c!==0) {c=Math.floor(c/2); bts++;} + return bts; + }, +/* convert this to string */ + toString: function() + { + var b; + var s=""; + var len=this.nbits(); + if (len%4===0) len=Math.floor(len/4); + else {len=Math.floor(len/4); len++;} + if (len<ROM.MODBYTES*2) len=ROM.MODBYTES*2; + for (var i=len-1;i>=0;i--) + { + b=new BIG(0); + b.copy(this); + b.shr(i*4); + s+=(b.w[0]&15).toString(16); + } + return s; + }, +/* this+=y */ + add: function(y) + { + for (var i=0;i<ROM.NLEN;i++) this.w[i]+=y.w[i]; + return this; + }, +/* return this+x */ + plus: function(x) + { + var s=new BIG(0); + for (var i=0;i<ROM.NLEN;i++) + s.w[i]=this.w[i]+x.w[i]; + return s; + }, +/* this+=i, where i is int */ + inc: function(i) + { + this.norm(); + this.w[0]+=i; + return this; + }, +/* this-=y */ + sub: function(y) + { + for (var i=0;i<ROM.NLEN;i++) this.w[i]-=y.w[i]; + return this; + }, + +/* reverse subtract this=x-this */ + rsub: function(x) + { + for (var i=0;i<ROM.NLEN;i++) + this.w[i]=x.w[i]-this.w[i]; + return this; + }, +/* this-=i, where i is int */ + dec: function(i) + { + this.norm(); + this.w[0]-=i; + return this; + }, +/* return this-x */ + minus: function(x) { + var d=new BIG(0); + for (var i=0;i<ROM.NLEN;i++) + d.w[i]=this.w[i]-x.w[i]; + return d; + }, +/* multiply by small integer */ + imul: function(c) + { + for (var i=0;i<ROM.NLEN;i++) this.w[i]*=c; + return this; + }, +/* convert this BIG to byte array */ + tobytearray: function(b,n) + { + this.norm(); + var c=new BIG(0); + c.copy(this); + + for (var i=ROM.MODBYTES-1;i>=0;i--) + { + b[i+n]=c.w[0]&0xff; + c.fshr(8); + } + return this; + }, +/* convert this to byte array */ + toBytes: function(b) + { + this.tobytearray(b,0); + }, + +/* set this[i]+=x*y+c, and return high part */ + muladd: function(x,y,c,i) + { + var prod=x*y+c+this.w[i]; + this.w[i]=prod&ROM.BMASK; + return ((prod-this.w[i])*ROM.MODINV); + }, +/* multiply by larger int */ + pmul: function(c) + { + var ak,carry=0; + this.norm(); + for (var i=0;i<ROM.NLEN;i++) + { + ak=this.w[i]; + this.w[i]=0; + carry=this.muladd(ak,c,carry,i); + } + return carry; + }, +/* multiply by still larger int - results requires a DBIG */ + pxmul: function(c) + { + var m=new DBIG(0); + var carry=0; + for (var j=0;j<ROM.NLEN;j++) + carry=m.muladd(this.w[j],c,carry,j); + m.w[ROM.NLEN]=carry; + return m; + }, +/* divide by 3 */ + div3: function() + { + var ak,base,carry=0; + this.norm(); + base=(1<<ROM.BASEBITS); + for (var i=ROM.NLEN-1;i>=0;i--) + { + ak=(carry*base+this.w[i]); + this.w[i]=Math.floor(ak/3); + carry=ak%3; + } + return carry; + }, + +/* set x = x mod 2^m */ + mod2m: function(m) + { + var i,wd,bt; + var msk; + wd=Math.floor(m/ROM.BASEBITS); + bt=m%ROM.BASEBITS; + msk=(1<<bt)-1; + this.w[wd]&=msk; + for (i=wd+1;i<ROM.NLEN;i++) this.w[i]=0; + }, + +/* a=1/a mod 2^256. This is very fast! */ + invmod2m: function() + { + var U=new BIG(0); + var b=new BIG(0); + var c=new BIG(0); + + U.inc(BIG.invmod256(this.lastbits(8))); + + for (var i=8;i<ROM.BIGBITS;i<<=1) + { + b.copy(this); b.mod2m(i); + var t1=BIG.smul(U,b); t1.shr(i); + c.copy(this); c.shr(i); c.mod2m(i); + + var t2=BIG.smul(U,c); t2.mod2m(i); + t1.add(t2); + b=BIG.smul(t1,U); t1.copy(b); + t1.mod2m(i); + + t2.one(); t2.shl(i); t1.rsub(t2); t1.norm(); + t1.shl(i); + U.add(t1); + } + U.mod2m(ROM.BIGBITS); + this.copy(U); + this.norm(); + }, + +/* reduce this mod m */ + mod: function(m) + { + var k=0; + var r=new BIG(0); + + this.norm(); + if (BIG.comp(this,m)<0) return; + do + { + m.fshl(1); + k++; + } while (BIG.comp(this,m)>=0); + + while (k>0) + { + m.fshr(1); + + r.copy(this); + r.sub(m); + r.norm(); + this.cmove(r,(1-((r.w[ROM.NLEN-1]>>(ROM.CHUNK-1))&1))); + +/* + if (BIG.comp(this,m)>=0) + { + this.sub(m); + this.norm(); + } */ + k--; + } + }, +/* this/=m */ + div: function(m) + { + var k=0; + var d=0; + this.norm(); + var e=new BIG(1); + var b=new BIG(0); + var r=new BIG(0); + b.copy(this); + this.zero(); + + while (BIG.comp(b,m)>=0) + { + e.fshl(1); + m.fshl(1); + k++; + } + + while (k>0) + { + m.fshr(1); + e.fshr(1); + + r.copy(b); + r.sub(m); + r.norm(); + d=(1-((r.w[ROM.NLEN-1]>>(ROM.CHUNK-1))&1)); + b.cmove(r,d); + r.copy(this); + r.add(e); + r.norm(); + this.cmove(r,d); + +/* + if (BIG.comp(b,m)>=0) + { + this.add(e); + this.norm(); + b.sub(m); + b.norm(); + } */ + + + k--; + } + }, +/* return parity of this */ + parity: function() + { + return this.w[0]%2; + }, +/* return n-th bit of this */ + bit: function(n) + { + if ((this.w[Math.floor(n/ROM.BASEBITS)]&(1<<(n%ROM.BASEBITS)))>0) return 1; + else return 0; + }, +/* return last n bits of this */ + lastbits: function(n) + { + var msk=(1<<n)-1; + this.norm(); + return (this.w[0])&msk; + }, +/* Jacobi Symbol (this/p). Returns 0, 1 or -1 */ + jacobi: function(p) + { + var n8,k,m=0; + var t=new BIG(0); + var x=new BIG(0); + var n=new BIG(0); + var zilch=new BIG(0); + var one=new BIG(1); + if (p.parity()===0 || BIG.comp(this,zilch)===0 || BIG.comp(p,one)<=0) return 0; + this.norm(); + x.copy(this); + n.copy(p); + x.mod(p); + + while (BIG.comp(n,one)>0) + { + if (BIG.comp(x,zilch)===0) return 0; + n8=n.lastbits(3); + k=0; + while (x.parity()===0) + { + k++; + x.shr(1); + } + if (k%2==1) m+=(n8*n8-1)/8; + m+=(n8-1)*(x.lastbits(2)-1)/4; + t.copy(n); + t.mod(x); + n.copy(x); + x.copy(t); + m%=2; + + } + if (m===0) return 1; + else return -1; + }, +/* this=1/this mod p. Binary method */ + invmodp: function(p) + { + this.mod(p); + var u=new BIG(0); + u.copy(this); + var v=new BIG(0); + v.copy(p); + var x1=new BIG(1); + var x2=new BIG(0); + var t=new BIG(0); + var one=new BIG(1); + + while (BIG.comp(u,one)!==0 && BIG.comp(v,one)!==0) + { + while (u.parity()===0) + { + u.shr(1); + if (x1.parity()!==0) + { + x1.add(p); + x1.norm(); + } + x1.shr(1); + } + while (v.parity()===0) + { + v.shr(1); + if (x2.parity()!==0) + { + x2.add(p); + x2.norm(); + } + x2.shr(1); + } + if (BIG.comp(u,v)>=0) + { + u.sub(v); + u.norm(); + if (BIG.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 (BIG.comp(x2,x1)>=0) x2.sub(x1); + else + { + t.copy(p); + t.sub(x1); + x2.add(t); + } + x2.norm(); + } + } + if (BIG.comp(u,one)===0) this.copy(x1); + else this.copy(x2); + }, +/* return this^e mod m */ + powmod:function(e,m) + { + var bt; + this.norm(); + e.norm(); + var a=new BIG(1); + var z=new BIG(0); + z.copy(e); + var s=new BIG(0); + s.copy(this); + var i=0; + while (true) + { + i++; + bt=z.parity(); + z.fshr(1); + if (bt==1) a=BIG.modmul(a,s,m); +//ROM.debug=false; + if (z.iszilch()) break; + s=BIG.modsqr(s,m); + } + return a; + } + +}; +/* convert from byte array to BIG */ +BIG.frombytearray=function(b,n) +{ + var m=new BIG(0); + + for (var i=0;i<ROM.MODBYTES;i++) + { + m.fshl(8); m.w[0]+=b[i+n]&0xff; + //m.inc(b[i]&0xff); + } + return m; +}; + +BIG.fromBytes=function(b) +{ + return BIG.frombytearray(b,0); +}; + +/* return a*b where product fits a BIG */ +BIG.smul=function(a,b) +{ + var carry; + var c=new BIG(0); + for (var i=0;i<ROM.NLEN;i++) + { + carry=0; + for (var j=0;j<ROM.NLEN;j++) + if (i+j<ROM.NLEN) carry=c.muladd(a.w[i],b.w[j],carry,i+j); + } + return c; +}; +/* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */ +BIG.comp=function(a,b) +{ + for (var i=ROM.NLEN-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; +}; + +/* get 8*MODBYTES size random number */ +BIG.random=function(rng) +{ + var m=new BIG(0); + var i,b,j=0,r=0; + +/* generate random BIG */ + for (i=0;i<8*ROM.MODBYTES;i++) + { + if (j===0) r=rng.getByte(); + else r>>=1; + + b=r&1; + m.shl(1); m.w[0]+=b;// m.inc(b); + j++; j&=7; + } + return m; +}; + +/* Create random BIG in portable way, one bit at a time */ +BIG.randomnum=function(q,rng) +{ + var d=new DBIG(0); + var i,b,j=0,r=0; + for (i=0;i<2*ROM.MODBITS;i++) + { + if (j===0) r=rng.getByte(); + else r>>=1; + + b=r&1; + d.shl(1); d.w[0]+=b; + j++; j&=7; + } + + var m=d.mod(q); + + return m; +}; + +/* return NAF value as +/- 1, 3 or 5. x and x3 should be normed. +nbs is number of bits processed, and nzs is number of trailing 0s detected */ +/* +BIG.nafbits=function(x,x3,i) +{ + var n=[]; + var nb=x3.bit(i)-x.bit(i); + var j; + n[1]=1; + n[0]=0; + if (nb===0) {n[0]=0; return n;} + if (i===0) {n[0]=nb; return n;} + if (nb>0) n[0]=1; + else n[0]=(-1); + + for (j=i-1;j>0;j--) + { + n[1]++; + n[0]*=2; + nb=x3.bit(j)-x.bit(j); + if (nb>0) n[0]+=1; + if (nb<0) n[0]-=1; + if (n[0]>5 || n[0]<-5) break; + } + + if (n[0]%2!==0 && j!==0) + { // backtrack + if (nb>0) n[0]=(n[0]-1)/2; + if (nb<0) n[0]=(n[0]+1)/2; + n[1]--; + } + while (n[0]%2===0) + { // remove trailing zeros + n[0]/=2; + n[2]++; + n[1]--; + } + return n; +}; +*/ +/* return a*b as DBIG */ +BIG.mul=function(a,b) +{ + var n,c=new DBIG(0); +// a.norm(); +// b.norm(); + + var d=[]; + var s,t; + + for (var i=0;i<ROM.NLEN;i++) + d[i]=a.w[i]*b.w[i]; + + s=d[0]; + t=s; c.w[0]=t; + + for (var k=1;k<ROM.NLEN;k++) + { + s+=d[k]; t=s; for (i=k;i>=1+Math.floor(k/2);i--) t+=(a.w[i]-a.w[k-i])*(b.w[k-i]-b.w[i]); c.w[k]=t; + } + for (var k=ROM.NLEN;k<2*ROM.NLEN-1;k++) + { + s-=d[k-ROM.NLEN]; t=s; for (i=ROM.NLEN-1;i>=1+Math.floor(k/2);i--) t+=(a.w[i]-a.w[k-i])*(b.w[k-i]-b.w[i]); c.w[k]=t; + } + + var co=0; + for (var i=0;i<ROM.DNLEN-1;i++) + { + n=c.w[i]+co; + c.w[i]=n&ROM.BMASK; + co=(n-c.w[i])*ROM.MODINV; + } + c.w[ROM.DNLEN-1]=co; + + +/* + for (var j=0;j<ROM.NLEN;j++) + { + t=0; for (var i=0;i<=j;i++) t+=a.w[j-i]*b.w[i]; + c.w[j]=t; + } + for (var j=ROM.NLEN;j<ROM.DNLEN-2;j++) + { + t=0; for (var i=j-ROM.NLEN+1;i<ROM.NLEN;i++) t+=a.w[j-i]*b.w[i]; + c.w[j]=t; + } + t=a.w[ROM.NLEN-1]*b.w[ROM.NLEN-1]; + c.w[ROM.DNLEN-2]=t; + var co=0; + for (var i=0;i<ROM.DNLEN-1;i++) + { + n=c.w[i]+co; + c.w[i]=n&ROM.BMASK; + co=(n-c.w[i])*ROM.MODINV; + } + c.w[ROM.DNLEN-1]=co; +*/ + return c; +}; + +/* return a^2 as DBIG */ +BIG.sqr=function(a) +{ + var n,c=new DBIG(0); +// a.norm(); + + c.w[0]=a.w[0]*a.w[0]; + t=a.w[1]*a.w[0]; t+=t; c.w[1]=t; + + var last=ROM.NLEN-ROM.NLEN%2; + for (j=2;j<last;j+=2) + { + t=a.w[j]*a.w[0]; for (var i=1;i<(j+1)>>1;i++) t+=a.w[j-i]*a.w[i]; t+=t; t+=a.w[j>>1]*a.w[j>>1]; + c.w[j]=t; + t=a.w[j+1]*a.w[0]; for (var i=1;i<(j+2)>>1;i++) t+=a.w[j+1-i]*a.w[i]; t+=t; + c.w[j+1]=t; + } + j=last; + if (ROM.NLEN%2==1) + { + t=a.w[j]*a.w[0]; for (var i=1;i<(j+1)>>1;i++) t+=a.w[j-i]*a.w[i]; t+=t; t+=a.w[j>>1]*a.w[j>>1]; + c.w[j]=t; j++; + t=a.w[ROM.NLEN-1]*a.w[j-ROM.NLEN+1]; for (var i=j-ROM.NLEN+2;i<(j+1)>>1;i++) t+=a.w[j-i]*a.w[i]; t+=t; + c.w[j]=t; j++; + } + +// j=ROM.NLEN; +// t=a.w[ROM.NLEN-1]*a.w[j-ROM.NLEN+1]; for (var i=j-ROM.NLEN+2;i<(j+1)>>1;i++) t+=a.w[j-i]*a.w[i]; t+=t; +// c.w[j]=t; + + + for (;j<ROM.DNLEN-2;j+=2) + { + t=a.w[ROM.NLEN-1]*a.w[j-ROM.NLEN+1]; for (var i=j-ROM.NLEN+2;i<(j+1)>>1;i++) t+=a.w[j-i]*a.w[i]; t+=t; t+=a.w[j>>1]*a.w[j>>1]; + c.w[j]=t; + t=a.w[ROM.NLEN-1]*a.w[j-ROM.NLEN+2]; for (var i=j-ROM.NLEN+3;i<(j+2)>>1;i++) t+=a.w[j+1-i]*a.w[i]; t+=t; + c.w[j+1]=t; + } + + t=a.w[ROM.NLEN-1]*a.w[ROM.NLEN-1]; + c.w[ROM.DNLEN-2]=t; + + var co=0; + for (var i=0;i<ROM.DNLEN-1;i++) + { + n=c.w[i]+co; + c.w[i]=n&ROM.BMASK; + co=(n-c.w[i])*ROM.MODINV; + } + c.w[ROM.DNLEN-1]=co; + return c; +}; + +/* reduce a DBIG to a BIG using a "special" modulus */ +BIG.mod=function(d) +{ + var i,j,b=new BIG(0); + if (ROM.MODTYPE==ROM.PSEUDO_MERSENNE) + { + var v,tw; + var t=d.split(ROM.MODBITS); + b.hcopy(d); + + if (ROM.MConst!=1) + v=t.pmul(ROM.MConst); + else v=0; + tw=t.w[ROM.NLEN-1]; + t.w[ROM.NLEN-1]&=ROM.TMASK; + t.inc(ROM.MConst*((tw>>ROM.TBITS)+(v<<(ROM.BASEBITS-ROM.TBITS)))); + b.add(t); + } + + if (ROM.MODTYPE==ROM.MONTGOMERY_FRIENDLY) + { + for (i=0;i<ROM.NLEN;i++) + d.w[ROM.NLEN+i]+=d.muladd(d.w[i],ROM.MConst-1,d.w[i],ROM.NLEN+i-1); + for (i=0;i<ROM.NLEN;i++) + b.w[i]=d.w[ROM.NLEN+i]; + } + + if (ROM.MODTYPE==ROM.GENERALISED_MERSENNE) + { // GoldiLocks Only + var t=d.split(ROM.MODBITS); + b.hcopy(d); + b.add(t); + var dd=new DBIG(0); + dd.hcopy(t); + dd.shl(ROM.MODBITS/2); + + var tt=dd.split(ROM.MODBITS); + var lo=new BIG(); + lo.hcopy(dd); + + b.add(tt); + b.add(lo); + //b.norm(); + tt.shl(ROM.MODBITS/2); + b.add(tt); + + var carry=b.w[ROM.NLEN-1]>>ROM.TBITS; + b.w[ROM.NLEN-1]&=ROM.TMASK; + b.w[0]+=carry; + + b.w[Math.floor(224/ROM.BASEBITS)]+=carry<<(224%ROM.BASEBITS); + } + + if (ROM.MODTYPE==ROM.NOT_SPECIAL) + { + + var m=new BIG(0); + var v=[]; + var dd=[]; + var s,c,t; + + m.rcopy(ROM.Modulus); + + + t=d.w[0]; v[0]=((t&ROM.BMASK)*ROM.MConst)&ROM.BMASK; t+=v[0]*m.w[0]; + c=d.w[1]+(t*ROM.MODINV); s=0; + + for (var k=1;k<ROM.NLEN;k++) + { + t=c+s+v[0]*m.w[k]; + for (i=k-1;i>Math.floor(k/2);i--) t+=(v[k-i]-v[i])*(m.w[i]-m.w[k-i]); + v[k]=((t&ROM.BMASK)*ROM.MConst)&ROM.BMASK; t+=v[k]*m.w[0]; + c=(t*ROM.MODINV)+d.w[k+1]; + + dd[k]=v[k]*m.w[k]; s+=dd[k]; + } + for (var k=ROM.NLEN;k<2*ROM.NLEN-1;k++) + { + t=c+s; + for (i=ROM.NLEN-1;i>=1+Math.floor(k/2);i--) t+=(v[k-i]-v[i])*(m.w[i]-m.w[k-i]); + b.w[k-ROM.NLEN]=t&ROM.BMASK; + c=((t-b.w[k-ROM.NLEN])*ROM.MODINV)+d.w[k+1]; + + s-=dd[k-ROM.NLEN+1]; + } + b.w[ROM.NLEN-1]=c&ROM.BMASK; + + +/* + var md=new BIG(0); + md.rcopy(ROM.Modulus); + var sum; + + sum=d.w[0]; + for (j=0;j<ROM.NLEN;j++) + { + for (i=0;i<j;i++) sum+=d.w[i]*md.w[j-i]; + d.w[j]=((sum&ROM.BMASK)*ROM.MConst)&ROM.BMASK; sum+=d.w[j]*md.w[0]; + sum=d.w[j+1]+(sum*ROM.MODINV); + } + + + for (j=ROM.NLEN;j<ROM.DNLEN-2;j++) + { + for (i=j-ROM.NLEN+1;i<ROM.NLEN;i++) sum+=d.w[i]*md.w[j-i]; + d.w[j]=sum&ROM.BMASK; + sum=d.w[j+1]+((sum-d.w[j])*ROM.MODINV); + } + + sum+=d.w[ROM.NLEN-1]*md.w[ROM.NLEN-1]; + d.w[ROM.DNLEN-2]=sum&ROM.BMASK; + sum=d.w[ROM.DNLEN-1]+((sum-d.w[ROM.DNLEN-2])*ROM.MODINV); + d.w[ROM.DNLEN-1]=sum&ROM.BMASK; + for (i=0;i<ROM.NLEN;i++) + b.w[i]=d.w[ROM.NLEN+i]; +*/ + } + b.norm(); + return b; +}; + +/* return a*b mod m */ +BIG.modmul=function(a,b,m) +{ + a.mod(m); + b.mod(m); + var d=BIG.mul(a,b); + return d.mod(m); +}; + +/* return a^2 mod m */ +BIG.modsqr=function(a,m) +{ + a.mod(m); + var d=BIG.sqr(a); + return d.mod(m); +}; + +/* return -a mod m */ +BIG.modneg=function(a,m) +{ + a.mod(m); + return m.minus(a); +}; + +/* calculate Field Excess */ +BIG.EXCESS=function(a) +{ + return ((a.w[ROM.NLEN-1]&ROM.OMASK)>>(ROM.MODBITS%ROM.BASEBITS)); +}; + +/* Arazi and Qi inversion mod 256 */ +BIG.invmod256=function(a) +{ + var U,t1,t2,b,c; + t1=0; + c=(a>>1)&1; + t1+=c; + t1&=1; + t1=2-t1; + t1<<=1; + U=t1+1; + +// i=2 + b=a&3; + t1=U*b; t1>>=2; + c=(a>>2)&3; + t2=(U*c)&3; + t1+=t2; + t1*=U; t1&=3; + t1=4-t1; + t1<<=2; + U+=t1; + +// i=4 + b=a&15; + t1=U*b; t1>>=4; + c=(a>>4)&15; + t2=(U*c)&15; + t1+=t2; + t1*=U; t1&=15; + t1=16-t1; + t1<<=4; + U+=t1; + + return U; +}; + http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/BenchtestEC.html ---------------------------------------------------------------------- diff --git a/version22/js/BenchtestEC.html b/version22/js/BenchtestEC.html new file mode 100644 index 0000000..49ca241 --- /dev/null +++ b/version22/js/BenchtestEC.html @@ -0,0 +1,162 @@ +<!DOCTYPE HTML> +<html> +<head> +<title>JavaScript Elliptic Curve Benchtest</title> +</head> +<body> +<h1>JavaScript Benchmark ECC and RSA</h1> +<script type="text/javascript" src="DBIG.js"></script> +<script type="text/javascript" src="BIG.js"></script> +<script type="text/javascript" src="FP.js"></script> +<script type="text/javascript" src="ROM.js"></script> +<script type="text/javascript" src="FF.js"></script> +<script type="text/javascript" src="ECP.js"></script> +<script type="text/javascript" src="RSA.js"></script> +<script type="text/javascript" src="HASH256.js"></script> +<script type="text/javascript" src="RAND.js"></script> +<script> +/* test driver and function exerciser ECC functions */ + var i,j; + var result; + var MIN_ITERS=10; + var MIN_TIME=10; + var pub=new rsa_public_key(ROM.FFLEN); + var priv=new rsa_private_key(ROM.HFLEN); + var fail=false; + + var RAW=[]; + var M=[]; + var C=[]; + var P=[]; + + var rng=new RAND(); + + rng.clean(); + for (i=0;i<100;i++) RAW[i]=i; + + rng.seed(100,RAW); + + if (ROM.CURVETYPE==ROM.WEIERSTRASS) + { + window.document.write("Weierstrass parameterization "+ "<br>"); + } + if (ROM.CURVETYPE==ROM.EDWARDS) + { + window.document.write("Edwards parameterization"+ "<br>"); + } + if (ROM.CURVETYPE==ROM.MONTGOMERY) + { + window.document.write("Montgomery parameterization"+ "<br>"); + } + + if (ROM.MODTYPE==ROM.PSEUDO_MERSENNE) + { + window.document.write("Pseudo-Mersenne Modulus"+ "<br>"); + } + if (ROM.MODTYPE==ROM.MONTGOMERY_FRIENDLY) + { + window.document.write("Montgomery friendly Modulus"+ "<br>"); + } + if (ROM.MODTYPE==ROM.GENERALISED_MERSENNE) + { + window.document.write("Generalised-Mersenne Modulus"+ "<br>"); + } + if (ROM.MODTYPE==ROM.NOT_SPECIAL) + { + window.document.write("Not special Modulus"+ "<br>"); + } + + window.document.write("Modulus size "+ROM.MODBITS+ " bits"+ "<br>"); + window.document.write(ROM.CHUNK + " bit build"+ "<br>"); + var r,gx,gy,s; + var G,WP; + var res=0; + + G=new ECP(0); + + gx=new BIG(0); gx.rcopy(ROM.CURVE_Gx); + + if (ROM.CURVETYPE!=ROM.MOMTGOMERY) + { + gy=new BIG(0); gy.rcopy(ROM.CURVE_Gy); + G.setxy(gx,gy); + } + else G.setx(gx); + + r=new BIG(0); r.rcopy(ROM.CURVE_Order); + s=BIG.randomnum(r,rng); + + WP=G.mul(r); + if (!WP.is_infinity()) + { + alert("FAILURE - rG!=O"); + fail=true; + } + var elapsed; + var start = performance.now(); + iterations=0; + do { + WP=G.mul(s); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("EC mul - " + iterations + " iterations "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + window.document.write("Generating " +ROM.FFLEN*ROM.BIGBITS + " - bit RSA public/private key pair"+ "<br>"); + + MIN_ITERS=1; + start = performance.now(); + iterations=0; + do { + RSA.KEY_PAIR(rng,65537,priv,pub); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("RSA gen - " + iterations + " iteration "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + MIN_ITERS=10; + + for (i=0;i<RSA.RFS;i++) M[i]=(i%128); + + start = performance.now(); + iterations=0; + do { + RSA.ENCRYPT(pub,M,C); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("RSA enc - " + iterations + " iterations "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + start = performance.now(); + iterations=0; + do { + RSA.DECRYPT(priv,C,P); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("RSA dec - " + iterations + " iterations "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + var cmp=true; + for (i=0;i<RSA.RFS;i++) + { + if (P[i]!=M[i]) cmp=false; + } + + if (!cmp) + { + alert("FAILURE - RSA decryption"); + fail=true; + } + if (!fail) window.document.write("All tests pass"+ "<br>"); + +</script> +</body> +</html> http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/BenchtestPAIR.html ---------------------------------------------------------------------- diff --git a/version22/js/BenchtestPAIR.html b/version22/js/BenchtestPAIR.html new file mode 100644 index 0000000..b6a9bb5 --- /dev/null +++ b/version22/js/BenchtestPAIR.html @@ -0,0 +1,226 @@ +<!DOCTYPE HTML> +<html> +<head> +<title>JavaScript PAIRing Benchtest</title> +</head> +<body> +<h1>JavaScript Benchmark Pairings</h1> +<script type="text/javascript" src="DBIG.js"></script> +<script type="text/javascript" src="BIG.js"></script> +<script type="text/javascript" src="FP.js"></script> +<script type="text/javascript" src="ROM.js"></script> +<script type="text/javascript" src="UInt64.js"></script> +<script type="text/javascript" src="HASH256.js"></script> +<script type="text/javascript" src="HASH384.js"></script> +<script type="text/javascript" src="HASH512.js"></script> +<script type="text/javascript" src="RAND.js"></script> +<script type="text/javascript" src="AES.js"></script> +<script type="text/javascript" src="GCM.js"></script> +<script type="text/javascript" src="ECP.js"></script> +<script type="text/javascript" src="FP2.js"></script> +<script type="text/javascript" src="ECP2.js"></script> +<script type="text/javascript" src="FP4.js"></script> +<script type="text/javascript" src="FP12.js"></script> +<script type="text/javascript" src="PAIR.js"></script> + +<script> +/* test driver and function exerciser for PAIRING Functions */ + + var i; + var result; + var MIN_ITERS=1; + var MIN_TIME=10; + var RAW=[]; + var fail=false; + var G=new ECP(0); + var Q=new ECP2(0); + + var rng=new RAND(); + rng.clean(); + + for (i=0;i<100;i++) RAW[i]=i+1; + rng.seed(100,RAW); + + if (ROM.CURVE_PAIRING_TYPE==ROM.BN_CURVE) + { + window.document.write("BN Pairing-Friendly Curve"+ "<br>"); + } + if (ROM.CURVE_PAIRING_TYPE==ROM.BLS_CURVE) + { + window.document.write("BLS Pairing-Friendly Curve"+ "<br>"); + } + + window.document.write("Modulus size " + ROM.MODBITS + " bits"+ "<br>"); + window.document.write(ROM.CHUNK + " bit build"+ "<br>"); + + var gx=new BIG(0); gx.rcopy(ROM.CURVE_Gx); + var gy=new BIG(0); gy.rcopy(ROM.CURVE_Gy); + G.setxy(gx,gy); + + r=new BIG(0); r.rcopy(ROM.CURVE_Order); + s=BIG.randomnum(r,rng); + + var P=PAIR.G1mul(G,r); + + if (!P.is_infinity()) + { + alert("FAILURE - rP!=O"); + fail=true; + } + + var elapsed; + var start = performance.now(); + iterations=0; + do { + P=PAIR.G1mul(G,s); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("G1 mul - " + iterations + " iterations "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + var A=new BIG(0); + var B=new BIG(0); + A.rcopy(ROM.CURVE_Pxa); B.rcopy(ROM.CURVE_Pxb); + var QX=new FP2(0); QX.bset(A,B); + A.rcopy(ROM.CURVE_Pya); B.rcopy(ROM.CURVE_Pyb); + var QY=new FP2(0); QY.bset(A,B); + Q.setxy(QX,QY); + + W=PAIR.G2mul(Q,r); + + if (!W.is_infinity()) + { + alert("FAILURE - rQ!=O"); + fail=true; + } + + start = performance.now(); + iterations=0; + do { + W=PAIR.G2mul(Q,s); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("G2 mul - " + iterations + " iteration "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + var w=PAIR.ate(Q,P); + w=PAIR.fexp(w); + + var g=PAIR.GTpow(w,r); + + if (!g.isunity()) + { + alert("FAILURE - g^r!=1"); + fail=true; + } + + start = performance.now(); + iterations=0; + do { + g=PAIR.GTpow(w,s); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("GT pow - " + iterations + " iteration "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + var fa=new BIG(0); fa.rcopy(ROM.CURVE_Fra); + var fb=new BIG(0); fb.rcopy(ROM.CURVE_Frb); + var f=new FP2(fa,fb); //f.bset(fa,fb); + + q=new BIG(0); q.rcopy(ROM.Modulus); + + var m=new BIG(q); + m.mod(r); + + var a=new BIG(s); + a.mod(m); + + var b=new BIG(s); + b.div(m); + + g.copy(w); + var c=g.trace(); + + g.frob(f); + var cp=g.trace(); + + w.conj(); + g.mul(w); + var cpm1=g.trace(); + g.mul(w); + var cpm2=g.trace(); + + var cr; + start = performance.now(); + iterations=0; + do { + cr=c.xtr_pow2(cp,cpm1,cpm2,a,b); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("GT pow (compressed) - " + iterations + " iteration "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + start = performance.now(); + iterations=0; + do { + w=PAIR.ate(Q,P); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("PAIRing ATE - " + iterations + " iteration "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + start = performance.now(); + iterations=0; + do { + g=PAIR.fexp(w); + iterations++; + elapsed=(performance.now()-start); + } while (elapsed<MIN_TIME*1000 || iterations<MIN_ITERS); + dur=elapsed/iterations; + window.document.write("PAIRing FEXP - " + iterations + " iteration "); + window.document.write(dur.toFixed(2) + " ms per iteration"+ "<br>"); + + P.copy(G); + Q.copy(W); + + P=PAIR.G1mul(P,s); + g=PAIR.ate(Q,P); + g=PAIR.fexp(g); + + P.copy(G); + Q=PAIR.G2mul(Q,s); + w=PAIR.ate(Q,P); + w=PAIR.fexp(w); + + if (!g.equals(w)) + { + alert("FAILURE - e(sQ,p)!=e(Q,sP)"); + fail=true; + } + + Q.copy(W); + g=PAIR.ate(Q,P); + g=PAIR.fexp(g); + g=PAIR.GTpow(g,s); + + if (!g.equals(w)) + { + alert("FAILURE - e(sQ,p)!=e(Q,P)^s"); + fail=true; + } + + if (!fail) window.document.write("All tests pass"+ "<br>"); + +</script> +</body> +</html> http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/DBIG.js ---------------------------------------------------------------------- diff --git a/version22/js/DBIG.js b/version22/js/DBIG.js new file mode 100644 index 0000000..38ff462 --- /dev/null +++ b/version22/js/DBIG.js @@ -0,0 +1,284 @@ +/* + 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 */ + +/* constructor */ +var DBIG = function(x) { + this.w=[]; + this.zero(); + this.w[0]=x; +}; + +DBIG.prototype={ + +/* set this=0 */ + zero: function() + { + for (var i=0;i<ROM.DNLEN;i++) this.w[i]=0; + return this; + }, + +/* set this=b */ + copy: function(b) + { + for (var i=0;i<ROM.DNLEN;i++) this.w[i]=b.w[i]; + return this; + }, + + +/* copy from BIG */ + hcopy: function(b) + { + var i; + for (i=0;i<ROM.NLEN;i++) this.w[i]=b.w[i]; + for (i=ROM.NLEN;i<ROM.DNLEN;i++) this.w[i]=0; + return this; + }, + +/* normalise this */ + norm: function() + { + var d,carry=0; + for (var i=0;i<ROM.DNLEN-1;i++) + { + d=this.w[i]+carry; + this.w[i]=d&ROM.BMASK; + carry=d>>ROM.BASEBITS; + } + this.w[ROM.DNLEN-1]=(this.w[ROM.DNLEN-1]+carry); + return this; + }, + +/* set this[i]+=x*y+c, and return high part */ + muladd: function(x,y,c,i) + { + var prod=x*y+c+this.w[i]; + this.w[i]=prod&ROM.BMASK; + return ((prod-this.w[i])*ROM.MODINV); + }, + +/* shift this right by k bits */ + shr: function(k) + { + var i,n=k%ROM.BASEBITS; + var m=Math.floor(k/ROM.BASEBITS); + for (i=0;i<ROM.DNLEN-m-1;i++) + this.w[i]=(this.w[m+i]>>n)|((this.w[m+i+1]<<(ROM.BASEBITS-n))&ROM.BMASK); + this.w[ROM.DNLEN-m-1]=this.w[ROM.DNLEN-1]>>n; + for (i=ROM.DNLEN-m;i<ROM.DNLEN;i++) this.w[i]=0; + return this; + }, + +/* shift this left by k bits */ + shl: function(k) + { + var i,n=k%ROM.BASEBITS; + var m=Math.floor(k/ROM.BASEBITS); + + this.w[ROM.DNLEN-1]=((this.w[ROM.DNLEN-1-m]<<n))|(this.w[ROM.DNLEN-m-2]>>(ROM.BASEBITS-n)); + for (i=ROM.DNLEN-2;i>m;i--) + this.w[i]=((this.w[i-m]<<n)&ROM.BMASK)|(this.w[i-m-1]>>(ROM.BASEBITS-n)); + this.w[m]=(this.w[0]<<n)&ROM.BMASK; + for (i=0;i<m;i++) this.w[i]=0; + return this; + }, + +/* Conditional move of big depending on d using XOR - no branches */ + cmove: function(b,d) + { + var i; + var c=d; + c=~(c-1); + + for (i=0;i<ROM.DNLEN;i++) + { + this.w[i]^=(this.w[i]^b.w[i])&c; + } + }, + + +/* this+=x */ + add: function(x) + { + for (var i=0;i<ROM.DNLEN;i++) + this.w[i]+=x.w[i]; + }, + +/* this-=x */ + sub: function(x) + { + for (var i=0;i<ROM.DNLEN;i++) + this.w[i]-=x.w[i]; + }, + +/* return number of bits in this */ + nbits: function() + { + var bts,k=ROM.DNLEN-1; + var c; + this.norm(); + while (k>=0 && this.w[k]===0) k--; + if (k<0) return 0; + bts=ROM.BASEBITS*k; + c=this.w[k]; + while (c!==0) {c=Math.floor(c/2); bts++;} + return bts; + }, + +/* convert this to string */ + toString: function() + { + + var b; + var s=""; + var len=this.nbits(); + if (len%4===0) len=Math.floor(len/4); + else {len=Math.floor(len/4); len++;} + + for (var i=len-1;i>=0;i--) + { + b=new DBIG(0); + b.copy(this); + b.shr(i*4); + s+=(b.w[0]&15).toString(16); + } + return s; + }, + +/* reduces this DBIG mod a BIG, and returns the BIG */ + mod: function(c) + { + var k=0; + this.norm(); + var m=new DBIG(0); + var dr=new DBIG(0); + m.hcopy(c); + var r=new BIG(0); + r.hcopy(this); + + if (DBIG.comp(this,m)<0) return r; + + do + { + m.shl(1); + k++; + } + while (DBIG.comp(this,m)>=0); + + while (k>0) + { + m.shr(1); + + dr.copy(this); + dr.sub(m); + dr.norm(); + this.cmove(dr,(1-((dr.w[ROM.DNLEN-1]>>(ROM.CHUNK-1))&1))); + +/* + if (DBIG.comp(this,m)>=0) + { + this.sub(m); + this.norm(); + } */ + k--; + } + + r.hcopy(this); + return r; + }, + +/* this/=c */ + div: function(c) + { + var d=0; + var k=0; + var m=new DBIG(0); m.hcopy(c); + var dr=new DBIG(0); + var r=new BIG(0); + var a=new BIG(0); + var e=new BIG(1); + this.norm(); + + while (DBIG.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=(1-((dr.w[ROM.DNLEN-1]>>(ROM.CHUNK-1))&1)); + this.cmove(dr,d); + r.copy(a); + r.add(e); + r.norm(); + a.cmove(r,d); +/* + if (DBIG.comp(this,m)>0) + { + a.add(e); + a.norm(); + this.sub(m); + this.norm(); + } */ + k--; + } + return a; + }, + +/* split this DBIG at position n, return higher half, keep lower half */ + split: function(n) + { + var t=new BIG(0); + var nw,m=n%ROM.BASEBITS; + var carry=this.w[ROM.DNLEN-1]<<(ROM.BASEBITS-m); + + + for (var i=ROM.DNLEN-2;i>=ROM.NLEN-1;i--) + { + nw=(this.w[i]>>m)|carry; + carry=(this.w[i]<<(ROM.BASEBITS-m))&ROM.BMASK; + t.w[i-ROM.NLEN+1]=nw; + } + this.w[ROM.NLEN-1]&=((1<<m)-1); + + return t; + } + +}; + +/* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */ +DBIG.comp=function(a,b) +{ + for (var 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; +}; http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/ECDH.js ---------------------------------------------------------------------- diff --git a/version22/js/ECDH.js b/version22/js/ECDH.js new file mode 100644 index 0000000..326d90d --- /dev/null +++ b/version22/js/ECDH.js @@ -0,0 +1,585 @@ +/* + 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 ECDH = { + + INVALID_PUBLIC_KEY:-2, + ERROR:-3, + INVALID:-4, + EFS:ROM.MODBYTES, + EGS:ROM.MODBYTES, + EAS:16, + EBS:16, + SHA256:32, + SHA384:48, + SHA512:64, + + HASH_TYPE:64, + + /* Convert Integer to n-byte array */ + inttobytes: function(n,len) + { + var i; + var b=[]; + + for (i=0;i<len;i++) b[i]=0; + i=len; + while (n>0 && i>0) + { + i--; + b[i]=(n&0xff); + n=Math.floor(n/256); + } + return b; + }, + + bytestostring: function(b) + { + var s=""; + var len=b.length; + var ch; + + for (var i=0;i<len;i++) + { + ch=b[i]; + s+=((ch>>>4)&15).toString(16); + s+=(ch&15).toString(16); + + } + return s; + }, + + stringtobytes: function(s) + { + var b=[]; + for (var i=0;i<s.length;i++) + b.push(s.charCodeAt(i)); + return b; + }, + + hashit: function(sha,A,n,B,pad) + { + var R=[]; + if (sha==this.SHA256) + { + var 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==this.SHA384) + { + 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==this.SHA512) + { + 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.length==0) return null; + + if (pad==0) return R; + var W=[]; + if (pad<=sha) + { + for (var i=0;i<pad;i++) W[i]=R[i]; + } + else + { + for (var i=0;i<sha;i++) W[i]=R[i]; + for (var i=sha;i<pad;i++) W[i]=0; + } + return W; + }, + + KDF1: function(sha,Z,olen) + { +/* NOTE: the parameter olen is the length of the output K in bytes */ + var i,hlen=sha; + var K=[]; + + var B=[]; + var counter,cthreshold,k=0; + + for (i=0;i<K.length;i++) K[i]=0; // redundant? + + cthreshold=Math.floor(olen/hlen); if (olen%hlen!==0) cthreshold++; + + for (counter=0;counter<cthreshold;counter++) + { + B=this.hashit(sha,Z,counter,null,0); + if (k+hlen>olen) for (i=0;i<olen%hlen;i++) K[k++]=B[i]; + else for (i=0;i<hlen;i++) K[k++]=B[i]; + } + return K; + }, + + KDF2: function(sha,Z,P,olen) + { +/* NOTE: the parameter olen is the length of the output k in bytes */ + var i,hlen=sha; + var K=[]; + + var B=[]; + var counter,cthreshold,k=0; + + for (i=0;i<K.length;i++) K[i]=0; // redundant? + + cthreshold=Math.floor(olen/hlen); if (olen%hlen!==0) cthreshold++; + + for (counter=1;counter<=cthreshold;counter++) + { + B=this.hashit(sha,Z,counter,P,0); + if (k+hlen>olen) for (i=0;i<olen%hlen;i++) K[k++]=B[i]; + else for (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 */ + + PBKDF2: function(sha,Pass,Salt,rep,olen) + { + var i,j,k,d,opt; + d=Math.floor(olen/sha); if (olen%sha!==0) d++; + var F=new Array(sha); + var U=[]; + var S=[]; + + var K=[]; + opt=0; + + for (i=1;i<=d;i++) + { + for (j=0;j<Salt.length;j++) S[j]=Salt[j]; + var N=this.inttobytes(i,4); + for (j=0;j<4;j++) S[Salt.length+j]=N[j]; + this.HMAC(sha,S,Pass,F); + for (j=0;j<sha;j++) U[j]=F[j]; + for (j=2;j<=rep;j++) + { + this.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]; + } + var key=[]; + for (i=0;i<olen;i++) key[i]=K[i]; + return key; + }, + + HMAC: function(sha,M,K,tag) + { + /* Input is from an octet m * + * olen is requested output length in bytes. k is the key * + * The output is the calculated tag */ + var i,b; + var B=[]; + b=64; + if (sha>32) b=128; + var K0=new Array(b); + var olen=tag.length; + + //b=K0.length; + if (olen<4 ) return 0; + + for (i=0;i<b;i++) K0[i]=0; + + if (K.length > b) + { + B=this.hashit(sha,K,0,null,0); + for (i=0;i<sha;i++) K0[i]=B[i]; + } + else + for (i=0;i<K.length;i++) K0[i]=K[i]; + + for (i=0;i<b;i++) K0[i]^=0x36; + B=this.hashit(sha,K0,0,M,0); + + for (i=0;i<b;i++) K0[i]^=0x6a; + B=this.hashit(sha,K0,0,B,olen); + + for (i=0;i<olen;i++) tag[i]=B[i]; + + return 1; + }, + +/* AES encryption/decryption */ + + AES_CBC_IV0_ENCRYPT: function(K,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 */ + var a=new AES(); + var fin; + var i,j,ipt,opt; + var buff=[]; + /*var clen=16+(Math.floor(M.length/16))*16;*/ + + var C=[]; + var padlen; + + a.init(ROM.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]=padlen; + a.encrypt(buff); + for (i=0;i<16;i++) + C[opt++]=buff[i]; + a.end(); + return C; + }, + + AES_CBC_IV0_DECRYPT: function(K,C) + { /* padding is removed */ + var a=new AES(); + var i,ipt,opt,ch; + var buff=[]; + var MM=[]; + var fin,bad; + var padlen; + ipt=opt=0; + + a.init(ROM.CBC,K.length,K,null); + + if (C.length===0) return []; + ch=C[ipt++]; + + fin=false; + + for(;;) + { + for (i=0;i<16;i++) + { + buff[i]=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]; + + var M=[]; + if (bad) return M; + + for (i=0;i<opt;i++) M[i]=MM[i]; + return M; + }, + + KEY_PAIR_GENERATE: function(RNG,S,W) + { + var r,gx,gy,s; + var G,WP; + var res=0; +// var T=[]; + G=new ECP(0); + + gx=new BIG(0); gx.rcopy(ROM.CURVE_Gx); + + if (ROM.CURVETYPE!=ROM.MONTGOMERY) + { + gy=new BIG(0); gy.rcopy(ROM.CURVE_Gy); + G.setxy(gx,gy); + } + else G.setx(gx); + + r=new BIG(0); r.rcopy(ROM.CURVE_Order); + + if (RNG===null) + { + s=BIG.fromBytes(S); + s.mod(r); + } + else + { + s=BIG.randomnum(r,RNG); + + // s.toBytes(T); + // for (var i=0;i<this.EGS;i++) S[i]=T[i]; + } + if (ROM.AES_S>0) + { + s.mod2m(2*ROM.AES_S); + } + s.toBytes(S); + + WP=G.mul(s); + WP.toBytes(W); + + return res; + }, + + PUBLIC_KEY_VALIDATE: function(full,W) + { + var r; + var WP=ECP.fromBytes(W); + var res=0; + + r=new BIG(0); r.rcopy(ROM.CURVE_Order); + + if (WP.is_infinity()) res=this.INVALID_PUBLIC_KEY; + + if (res===0 && full) + { + WP=WP.mul(r); + if (!WP.is_infinity()) res=this.INVALID_PUBLIC_KEY; + } + return res; + }, + + ECPSVDP_DH: function(S,WD,Z) + { + var r,s; + var W; + var res=0; + var T=[]; + + s=BIG.fromBytes(S); + + W=ECP.fromBytes(WD); + if (W.is_infinity()) res=this.ERROR; + + if (res===0) + { + r=new BIG(0); r.rcopy(ROM.CURVE_Order); + s.mod(r); + W=W.mul(s); + if (W.is_infinity()) res=this.ERROR; + else + { + W.getX().toBytes(T); + for (var i=0;i<this.EFS;i++) Z[i]=T[i]; + } + } + return res; + }, + + ECPSP_DSA: function(sha,RNG,S,F,C,D) + { + var T=[]; + var i,gx,gy,r,s,f,c,d,u,vx,w; + var G,V; + + var B=this.hashit(sha,F,0,null,ROM.MODBYTES); + + gx=new BIG(0); gx.rcopy(ROM.CURVE_Gx); + gy=new BIG(0); gy.rcopy(ROM.CURVE_Gy); + + G=new ECP(0); + G.setxy(gx,gy); + r=new BIG(0); r.rcopy(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=BIG.modmul(u,w,r); + u.invmodp(r); + d=BIG.modmul(s,c,r); + d.add(f); + d=BIG.modmul(d,w,r); + d=BIG.modmul(u,d,r); + } while (d.iszilch()); + + c.toBytes(T); + for (i=0;i<this.EFS;i++) C[i]=T[i]; + d.toBytes(T); + for (i=0;i<this.EFS;i++) D[i]=T[i]; + return 0; + }, + + ECPVP_DSA: function(sha,W,F,C,D) + { + var B=[]; + var r,gx,gy,f,c,d,h2; + var res=0; + var G,WP,P; + + B=this.hashit(sha,F,0,null,ROM.MODBYTES); + + gx=new BIG(0); gx.rcopy(ROM.CURVE_Gx); + gy=new BIG(0); gy.rcopy(ROM.CURVE_Gy); + + G=new ECP(0); + G.setxy(gx,gy); + r=new BIG(0); r.rcopy(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=this.INVALID; + + if (res===0) + { + d.invmodp(r); + f=BIG.modmul(f,d,r); + h2=BIG.modmul(c,d,r); + + WP=ECP.fromBytes(W); + if (WP.is_infinity()) res=this.ERROR; + else + { + P=new ECP(); + P.copy(WP); + P=P.mul2(h2,G,f); + if (P.is_infinity()) res=this.INVALID; + else + { + d=P.getX(); + d.mod(r); + if (BIG.comp(d,c)!==0) res=this.INVALID; + } + } + } + + return res; + }, + + ECIES_ENCRYPT: function(sha,P1,P2,RNG,W,M,V,T) + { + var i; + + var Z=[]; + var VZ=[]; + var K1=[]; + var K2=[]; + var U=[]; + var C=[]; + + if (this.KEY_PAIR_GENERATE(RNG,U,V)!==0) return C; + if (this.ECPSVDP_DH(U,W,Z)!==0) return C; + + for (i=0;i<2*this.EFS+1;i++) VZ[i]=V[i]; + for (i=0;i<this.EFS;i++) VZ[2*this.EFS+1+i]=Z[i]; + + + var K=this.KDF2(sha,VZ,P1,EFS); + + for (i=0;i<this.EAS;i++) {K1[i]=K[i]; K2[i]=K[this.EAS+i];} + + C=this.AES_CBC_IV0_ENCRYPT(K1,M); + + var L2=this.inttobytes(P2.length,8); + + var AC=[]; + 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]; + + this.HMAC(sha,AC,K2,T); + + return C; + }, + + ECIES_DECRYPT: function(sha,P1,P2,V,C,T,U) + { + + var i; + + var Z=[]; + var VZ=[]; + var K1=[]; + var K2=[]; + var TAG=new Array(T.length); + var M=[]; + + if (this.ECPSVDP_DH(U,V,Z)!==0) return M; + + for (i=0;i<2*this.EFS+1;i++) VZ[i]=V[i]; + for (i=0;i<this.EFS;i++) VZ[2*this.EFS+1+i]=Z[i]; + + var K=this.KDF2(sha,VZ,P1,this.EFS); + + for (i=0;i<this.EAS;i++) {K1[i]=K[i]; K2[i]=K[this.EAS+i];} + + M=this.AES_CBC_IV0_DECRYPT(K1,C); + + if (M.length===0) return M; + + var L2=this.inttobytes(P2.length,8); + + var AC=[]; + + 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]; + + this.HMAC(sha,AC,K2,TAG); + + var same=true; + for (i=0;i<T.length;i++) if (T[i]!=TAG[i]) same=false; + if (!same) return []; + + return M; + } +}; http://git-wip-us.apache.org/repos/asf/incubator-milagro-crypto/blob/c25f9e5c/version22/js/ECP.js ---------------------------------------------------------------------- diff --git a/version22/js/ECP.js b/version22/js/ECP.js new file mode 100644 index 0000000..ade058b --- /dev/null +++ b/version22/js/ECP.js @@ -0,0 +1,903 @@ +/* + 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 */ + +/* Constructor */ +var ECP = function() +{ + this.x=new FP(0); + this.y=new FP(1); + this.z=new FP(1); + this.INF=true; +}; + +ECP.prototype={ +/* test this=O point-at-infinity */ + is_infinity: function() + { + if (ROM.CURVETYPE==ROM.EDWARDS) + { + this.x.reduce(); this.y.reduce(); this.z.reduce(); + return (this.x.iszilch() && this.y.equals(this.z)); + } + else return this.INF; + }, + + +/* conditional swap of this and Q dependant on d */ + cswap: function(Q,d) + { + this.x.cswap(Q.x,d); + if (ROM.CURVETYPE!=ROM.MONTGOMERY) this.y.cswap(Q.y,d); + this.z.cswap(Q.z,d); + if (ROM.CURVETYPE!=ROM.EDWARDS) + { + var bd=(d!==0)?true:false; + bd=bd&(this.INF^Q.INF); + this.INF^=bd; + Q.INF^=bd; + } + }, + +/* conditional move of Q to P dependant on d */ + cmove: function(Q,d) + { + this.x.cmove(Q.x,d); + if (ROM.CURVETYPE!=ROM.MONTGOMERY) this.y.cmove(Q.y,d); + this.z.cmove(Q.z,d); + if (ROM.CURVETYPE!=ROM.EDWARDS) + { + 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 ECP(); + var m=b>>31; + var babs=(b^m)-m; + + babs=(babs-1)/2; + + this.cmove(W[0],ECP.teq(babs,0)); // conditional move + this.cmove(W[1],ECP.teq(babs,1)); + this.cmove(W[2],ECP.teq(babs,2)); + this.cmove(W[3],ECP.teq(babs,3)); + this.cmove(W[4],ECP.teq(babs,4)); + this.cmove(W[5],ECP.teq(babs,5)); + this.cmove(W[6],ECP.teq(babs,6)); + this.cmove(W[7],ECP.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; + if (ROM.CURVETYPE==ROM.WEIERSTRASS) + { + var zs2=new FP(0); zs2.copy(this.z); zs2.sqr(); + var zo2=new FP(0); zo2.copy(Q.z); zo2.sqr(); + var zs3=new FP(0); zs3.copy(zs2); zs3.mul(this.z); + var zo3=new FP(0); 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; + } + else + { + var a=new FP(0); + var b=new FP(0); + a.copy(this.x); a.mul(Q.z); a.reduce(); + b.copy(Q.x); b.mul(this.z); b.reduce(); + if (!a.equals(b)) return false; + if (ROM.CURVETYPE==ROM.EDWARDS) + { + a.copy(this.y); a.mul(Q.z); a.reduce(); + b.copy(Q.y); b.mul(this.z); b.reduce(); + if (!a.equals(b)) return false; + } + } + return true; + }, +/* copy this=P */ + copy: function(P) + { + this.x.copy(P.x); + if (ROM.CURVETYPE!=ROM.MONTGOMERY) this.y.copy(P.y); + this.z.copy(P.z); + this.INF=P.INF; + }, +/* this=-this */ + neg: function() + { + if (this.is_infinity()) return; + if (ROM.CURVETYPE==ROM.WEIERSTRASS) + { + this.y.neg(); this.y.norm(); + } + if (ROM.CURVETYPE==ROM.EDWARDS) + { + this.x.neg(); this.x.norm(); + } + return; + }, +/* set this=O */ + inf: function() + { + this.INF=true; + this.x.zero(); + this.y=new FP(1); + this.z=new FP(1); + }, +/* set this=(x,y) where x and y are BIGs */ + setxy: function(ix,iy) + { + + this.x=new FP(0); this.x.bcopy(ix); + var bx=this.x.redc(); + + this.y=new FP(0); this.y.bcopy(iy); + this.z=new FP(1); + var rhs=ECP.RHS(this.x); + + if (ROM.CURVETYPE==ROM.MONTGOMERY) + { + if (rhs.jacobi()==1) this.INF=false; + else this.inf(); + } + else + { + var y2=new FP(0); y2.copy(this.y); + y2.sqr(); + if (y2.equals(rhs)) this.INF=false; + else this.inf(); + + } + }, +/* set this=x, where x is BIG, y is derived from sign s */ + setxi: function(ix,s) + { + this.x=new FP(0); this.x.bcopy(ix); + var rhs=ECP.RHS(this.x); + this.z=new FP(1); + if (rhs.jacobi()==1) + { + var ny=rhs.sqrt(); + if (ny.redc().parity()!=s) ny.neg(); + this.y=ny; + this.INF=false; + } + else this.inf(); + }, +/* set this=x, y calcuated from curve equation */ + setx: function(ix) + { + this.x=new FP(0); this.x.bcopy(ix); + var rhs=ECP.RHS(this.x); + this.z=new FP(1); + if (rhs.jacobi()==1) + { + if (ROM.CURVETYPE!=ROM.MONTGOMERY) this.y=rhs.sqrt(); + this.INF=false; + } + else this.INF=true; + }, +/* set this to affine - from (x,y,z) to (x,y) */ + affine: function() + { + if (this.is_infinity()) return; + var one=new FP(1); + if (this.z.equals(one)) return; + this.z.inverse(); + if (ROM.CURVETYPE==ROM.WEIERSTRASS) + { + var z2=new FP(0); 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; + } + if (ROM.CURVETYPE==ROM.EDWARDS) + { + this.x.mul(this.z); this.x.reduce(); + this.y.mul(this.z); this.y.reduce(); + this.z=one; + } + if (ROM.CURVETYPE==ROM.MONTGOMERY) + { + this.x.mul(this.z); this.x.reduce(); + this.z=one; + } + }, +/* extract x as BIG */ + getX: function() + { + this.affine(); + return this.x.redc(); + }, +/* extract y as BIG */ + getY: function() + { + this.affine(); + return this.y.redc(); + }, + +/* get sign of Y */ + getS: function() + { + this.affine(); + var y=this.getY(); + return y.parity(); + }, +/* extract x as FP */ + getx: function() + { + return this.x; + }, +/* extract y as FP */ + gety: function() + { + return this.y; + }, +/* extract z as FP */ + getz: function() + { + return this.z; + }, +/* convert to byte array */ + toBytes: function(b) + { + var i,t=[]; + if (ROM.CURVETYPE!=ROM.MONTGOMERY) b[0]=0x04; + else b[0]=0x02; + + this.affine(); + this.x.redc().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) b[i+1]=t[i]; + if (ROM.CURVETYPE!=ROM.MONTGOMERY) + { + this.y.redc().toBytes(t); + for (i=0;i<ROM.MODBYTES;i++) b[i+ROM.MODBYTES+1]=t[i]; + } + }, +/* convert to hex string */ + toString: function() + { + if (this.is_infinity()) return "infinity"; + this.affine(); + if (ROM.CURVETYPE==ROM.MONTGOMERY) return "("+this.x.redc().toString()+")"; + else return "("+this.x.redc().toString()+","+this.y.redc().toString()+")"; + }, + +/* this+=this */ + dbl: function() + { + if (ROM.CURVETYPE==ROM.WEIERSTRASS) + { + if (this.INF) return; + if (this.y.iszilch()) + { + this.inf(); + return; + } + + var w1=new FP(0); w1.copy(this.x); + var w6=new FP(0); w6.copy(this.z); + var w2=new FP(0); + var w3=new FP(0); w3.copy(this.x); + var w8=new FP(0); w8.copy(this.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(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(); + } + if (ROM.CURVETYPE==ROM.EDWARDS) + { + var C=new FP(0); C.copy(this.x); + var D=new FP(0); D.copy(this.y); + var H=new FP(0); H.copy(this.z); + var J=new FP(0); + + this.x.mul(this.y); this.x.add(this.x); + C.sqr(); + D.sqr(); + if (ROM.CURVE_A==-1) C.neg(); + this.y.copy(C); this.y.add(D); + H.sqr(); H.add(H); + this.z.copy(this.y); + J.copy(this.y); J.sub(H); + this.x.mul(J); + C.sub(D); + this.y.mul(C); + this.z.mul(J); + + this.x.norm(); + this.y.norm(); + this.z.norm(); + } + if (ROM.CURVETYPE==ROM.MONTGOMERY) + { + var A=new FP(0); A.copy(this.x); + var B=new FP(0); B.copy(this.x); + var AA=new FP(0); + var BB=new FP(0); + var C=new FP(0); + + if (this.INF) return; + + A.add(this.z); + AA.copy(A); AA.sqr(); + B.sub(this.z); + BB.copy(B); BB.sqr(); + C.copy(AA); C.sub(BB); + + this.x.copy(AA); this.x.mul(BB); + + A.copy(C); A.imul((ROM.CURVE_A+2)>>2); + + BB.add(A); + this.z.copy(BB); this.z.mul(C); + this.x.norm(); + this.z.norm(); + } + return; + }, + +/* this+=Q */ + add: function(Q) + { + if (ROM.CURVETYPE==ROM.WEIERSTRASS) + { + if (this.INF) + { + this.copy(Q); + return; + } + if (Q.INF) return; + + var aff=false; + var one=new FP(1); + if (Q.z.equals(one)) aff=true; + + var A,C; + var B=new FP(this.z); + var D=new FP(this.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(this.x); + C.mul(this.y); + } + else + { + A=new FP(this.x); + C=new FP(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; + } + else + { + this.INF=true; + return; + } + } + + if (!aff) this.z.mul(Q.z); + this.z.mul(B); + + var e=new FP(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(); + + } + if (ROM.CURVETYPE==ROM.EDWARDS) + { + var b=new FP(0); b.rcopy(ROM.CURVE_B); + var A=new FP(0); A.copy(this.z); + var B=new FP(0); + var C=new FP(0); C.copy(this.x); + var D=new FP(0); D.copy(this.y); + var E=new FP(0); + var F=new FP(0); + var G=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(this.x); B.add(this.y); + D.copy(Q.x); D.add(Q.y); + B.mul(D); + B.sub(C); + B.mul(F); + this.x.copy(A); this.x.mul(B); + + if (ROM.CURVE_A==1) + { + C.copy(E); C.mul(G); + } + if (ROM.CURVE_A==-1) + { + C.mul(G); + } + this.y.copy(A); this.y.mul(C); + this.z.copy(F); this.z.mul(G); + this.x.norm(); this.y.norm(); this.z.norm(); + } + return; + }, + +/* Differential Add for Montgomery curves. this+=Q where W is this-Q and is affine. */ + dadd: function(Q,W) + { + var A=new FP(0); A.copy(this.x); + var B=new FP(0); B.copy(this.x); + var C=new FP(0); C.copy(Q.x); + var D=new FP(0); D.copy(Q.x); + var DA=new FP(0); + var CB=new FP(0); + + A.add(this.z); + B.sub(this.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(); + + this.x.copy(A); + this.z.copy(W.x); this.z.mul(B); + + if (this.z.iszilch()) this.inf(); + else this.INF=false; + + this.x.norm(); + }, + +/* this-=Q */ + sub: function(Q) { + Q.neg(); + this.add(Q); + Q.neg(); + }, + +/* constant time multiply by small integer of length bts - use ladder */ + pinmul: function(e,bts) { + if (ROM.CURVETYPE==ROM.MONTGOMERY) + return this.mul(new BIG(e)); + else + { + var nb,i,b; + var P=new ECP(); + var R0=new ECP(); + var 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 - SPA immune, using Ladder */ + + mul: function(e) + { + if (e.iszilch() || this.is_infinity()) return new ECP(); + var P=new ECP(); + if (ROM.CURVETYPE==ROM.MONTGOMERY) + { /* use ladder */ + var nb,i,b; + var D=new ECP(); + var R0=new ECP(); R0.copy(this); + var 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 + var i,b,nb,m,s,ns; + var mt=new BIG(); + var t=new BIG(); + var Q=new ECP(); + var C=new ECP(); + var W=[]; + var w=[]; + + this.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) + ECP.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; + }, + +/* Return e.this+f.Q */ + + mul2: function(e,Q,f) { + var te=new BIG(); + var tf=new BIG(); + var mt=new BIG(); + var S=new ECP(); + var T=new ECP(); + var C=new ECP(); + var W=[]; + var w=[]; + var i,s,ns,nb; + var a,b; + + this.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) + ECP.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+Math.floor((mt.nbits()+1)/2); + +// convert exponent to signed 2-bit window + for (i=0;i<nb;i++) + { + a=(te.lastbits(3)-4); + te.dec(a); te.norm(); + te.fshr(2); + b=(tf.lastbits(3)-4); + tf.dec(b); tf.norm(); + tf.fshr(2); + w[i]=(4*a+b); + } + w[nb]=(4*te.lastbits(3)+tf.lastbits(3)); + S.copy(W[Math.floor((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; + } + +}; + +ECP.multiaffine=function(m,P) +{ + var i; + var t1=new FP(0); + var t2=new FP(0); + var work=[]; + + 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); + } +}; + +/* return 1 if b==c, no branching */ +ECP.teq=function(b,c) +{ + var x=b^c; + x-=1; // if x=0, x now -1 + return ((x>>31)&1); +}; + +/* convert from byte array to ECP */ +ECP.fromBytes= function(b) +{ + var i,t=[]; + var P=new ECP(); + var p=new BIG(0); p.rcopy(ROM.Modulus); + + for (i=0;i<ROM.MODBYTES;i++) t[i]=b[i+1]; + var px=BIG.fromBytes(t); + if (BIG.comp(px,p)>=0) return P; + + if (b[0]==0x04) + { + for (i=0;i<ROM.MODBYTES;i++) t[i]=b[i+ROM.MODBYTES+1]; + var py=BIG.fromBytes(t); + if (BIG.comp(py,p)>=0) return P; + P.setxy(px,py); + return P; + } + else + { + P.setx(px); + return P; + } +}; + +/* Calculate RHS of curve equation */ +ECP.RHS= function(x) +{ + x.norm(); + var r=new FP(0); r.copy(x); + r.sqr(); + + if (ROM.CURVETYPE==ROM.WEIERSTRASS) + { // x^3+Ax+B + var b=new FP(0); b.rcopy(ROM.CURVE_B); + r.mul(x); + if (ROM.CURVE_A==-3) + { + var cx=new FP(0); cx.copy(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) + var b=new FP(0); b.rcopy(ROM.CURVE_B); + + var 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 + var 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; +};
