ztest-rsa.js

"use strict";
/*RSA、AES、SHA1*/

!function(){var i="0000000000000000";window.AES=function(t,e,r){return A.AES.encrypt(t||"",A.enc.Utf8.parse(((e||"")+i).substr(0,16)),{iv:A.enc.Utf8.parse(((r||"")+i).substr(0,16))})+""},AES.Decode=function(t,e,r){return A.AES.decrypt(t||"",A.enc.Utf8.parse(((e||"")+i).substr(0,16)),{iv:A.enc.Utf8.parse(((r||"")+i).substr(0,16))}).toString(A.enc.Utf8)},window.SHA1=function(t){return(A.SHA1(t)+"").toUpperCase()};var t,a,e,r,n,h,s,o,c,f,u,p,A=AES.CryptoJS=A||function(c,t){var e={},r=e.lib={},i=function(){},n=r.Base={extend:function(t){i.prototype=this;var e=new i;return t&&e.mixIn(t),e.hasOwnProperty("init")||(e.init=function(){e.$super.init.apply(this,arguments)}),(e.init.prototype=e).$super=this,e},create:function(){var t=this.extend();return t.init.apply(t,arguments),t},init:function(){},mixIn:function(t){for(var e in t)t.hasOwnProperty(e)&&(this[e]=t[e]);t.hasOwnProperty("toString")&&(this.toString=t.toString)},clone:function(){return this.init.prototype.extend(this)}},a=r.WordArray=n.extend({init:function(t,e){t=this.words=t||[],this.sigBytes=null!=e?e:4*t.length},toString:function(t){return(t||o).stringify(this)},concat:function(t){var e=this.words,r=t.words,i=this.sigBytes;if(t=t.sigBytes,this.clamp(),i%4)for(var n=0;n<t;n++)e[i+n>>>2]|=(r[n>>>2]>>>24-n%4*8&255)<<24-(i+n)%4*8;else if(65535<r.length)for(n=0;n<t;n+=4)e[i+n>>>2]=r[n>>>2];else e.push.apply(e,r);return this.sigBytes+=t,this},clamp:function(){var t=this.words,e=this.sigBytes;t[e>>>2]&=4294967295<<32-e%4*8,t.length=c.ceil(e/4)},clone:function(){var t=n.clone.call(this);return t.words=this.words.slice(0),t},random:function(t){for(var e=[],r=0;r<t;r+=4)e.push(4294967296*c.random()|0);return new a.init(e,t)}}),s=e.enc={},o=s.Hex={stringify:function(t){var e=t.words;t=t.sigBytes;for(var r=[],i=0;i<t;i++){var n=e[i>>>2]>>>24-i%4*8&255;r.push((n>>>4).toString(16)),r.push((15&n).toString(16))}return r.join("")},parse:function(t){for(var e=t.length,r=[],i=0;i<e;i+=2)r[i>>>3]|=parseInt(t.substr(i,2),16)<<24-i%8*4;return new a.init(r,e/2)}},h=s.Latin1={stringify:function(t){var e=t.words;t=t.sigBytes;for(var r=[],i=0;i<t;i++)r.push(String.fromCharCode(e[i>>>2]>>>24-i%4*8&255));return r.join("")},parse:function(t){for(var e=t.length,r=[],i=0;i<e;i++)r[i>>>2]|=(255&t.charCodeAt(i))<<24-i%4*8;return new a.init(r,e)}},f=s.Utf8={stringify:function(t){try{return decodeURIComponent(escape(h.stringify(t)))}catch(t){throw Error("Malformed UTF-8 data")}},parse:function(t){return h.parse(unescape(encodeURIComponent(t)))}},u=r.BufferedBlockAlgorithm=n.extend({reset:function(){this._data=new a.init,this._nDataBytes=0},_append:function(t){"string"==typeof t&&(t=f.parse(t)),this._data.concat(t),this._nDataBytes+=t.sigBytes},_process:function(t){var e=this._data,r=e.words,i=e.sigBytes,n=this.blockSize,s=i/(4*n);if(t=(s=t?c.ceil(s):c.max((0|s)-this._minBufferSize,0))*n,i=c.min(4*t,i),t){for(var o=0;o<t;o+=n)this._doProcessBlock(r,o);o=r.splice(0,t),e.sigBytes-=i}return new a.init(o,i)},clone:function(){var t=n.clone.call(this);return t._data=this._data.clone(),t},_minBufferSize:0});r.Hasher=u.extend({cfg:n.extend(),init:function(t){this.cfg=this.cfg.extend(t),this.reset()},reset:function(){u.reset.call(this),this._doReset()},update:function(t){return this._append(t),this._process(),this},finalize:function(t){return t&&this._append(t),this._doFinalize()},blockSize:16,_createHelper:function(r){return function(t,e){return new r.init(e).finalize(t)}},_createHmacHelper:function(r){return function(t,e){return new p.HMAC.init(r,e).finalize(t)}}});var p=e.algo={};return e}(Math);a=(t=A).lib.WordArray,t.enc.Base64={stringify:function(t){var e=t.words,r=t.sigBytes,i=this._map;t.clamp(),t=[];for(var n=0;n<r;n+=3)for(var s=(e[n>>>2]>>>24-n%4*8&255)<<16|(e[n+1>>>2]>>>24-(n+1)%4*8&255)<<8|e[n+2>>>2]>>>24-(n+2)%4*8&255,o=0;o<4&&n+.75*o<r;o++)t.push(i.charAt(s>>>6*(3-o)&63));if(e=i.charAt(64))for(;t.length%4;)t.push(e);return t.join("")},parse:function(t){var e=t.length,r=this._map;(i=r.charAt(64))&&-1!=(i=t.indexOf(i))&&(e=i);for(var i=[],n=0,s=0;s<e;s++)if(s%4){var o=r.indexOf(t.charAt(s-1))<<s%4*2,c=r.indexOf(t.charAt(s))>>>6-s%4*2;i[n>>>2]|=(o|c)<<24-n%4*8,n++}return a.create(i,n)},_map:"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/="},function(s){function k(t,e,r,i,n,s,o){return((t=t+(e&r|~e&i)+n+o)<<s|t>>>32-s)+e}function w(t,e,r,i,n,s,o){return((t=t+(e&i|r&~i)+n+o)<<s|t>>>32-s)+e}function z(t,e,r,i,n,s,o){return((t=t+(e^r^i)+n+o)<<s|t>>>32-s)+e}function E(t,e,r,i,n,s,o){return((t=t+(r^(e|~i))+n+o)<<s|t>>>32-s)+e}for(var t=A,e=(i=t.lib).WordArray,r=i.Hasher,i=t.algo,C=[],n=0;n<64;n++)C[n]=4294967296*s.abs(s.sin(n+1))|0;i=i.MD5=r.extend({_doReset:function(){this._hash=new e.init([1732584193,4023233417,2562383102,271733878])},_doProcessBlock:function(t,e){for(var r=0;r<16;r++){var i=t[o=e+r];t[o]=16711935&(i<<8|i>>>24)|4278255360&(i<<24|i>>>8)}r=this._hash.words;var n,s,o=t[e+0],c=(i=t[e+1],t[e+2]),a=t[e+3],h=t[e+4],f=t[e+5],u=t[e+6],p=t[e+7],d=t[e+8],l=t[e+9],_=t[e+10],y=t[e+11],v=t[e+12],g=t[e+13],B=t[e+14],S=t[e+15],m=r[0],x=E(x=E(x=E(x=E(x=z(x=z(x=z(x=z(x=w(x=w(x=w(x=w(x=k(x=k(x=k(x=k(x=r[1],s=k(s=r[2],n=k(n=r[3],m=k(m,x,s,n,o,7,C[0]),x,s,i,12,C[1]),m,x,c,17,C[2]),n,m,a,22,C[3]),s=k(s,n=k(n,m=k(m,x,s,n,h,7,C[4]),x,s,f,12,C[5]),m,x,u,17,C[6]),n,m,p,22,C[7]),s=k(s,n=k(n,m=k(m,x,s,n,d,7,C[8]),x,s,l,12,C[9]),m,x,_,17,C[10]),n,m,y,22,C[11]),s=k(s,n=k(n,m=k(m,x,s,n,v,7,C[12]),x,s,g,12,C[13]),m,x,B,17,C[14]),n,m,S,22,C[15]),s=w(s,n=w(n,m=w(m,x,s,n,i,5,C[16]),x,s,u,9,C[17]),m,x,y,14,C[18]),n,m,o,20,C[19]),s=w(s,n=w(n,m=w(m,x,s,n,f,5,C[20]),x,s,_,9,C[21]),m,x,S,14,C[22]),n,m,h,20,C[23]),s=w(s,n=w(n,m=w(m,x,s,n,l,5,C[24]),x,s,B,9,C[25]),m,x,a,14,C[26]),n,m,d,20,C[27]),s=w(s,n=w(n,m=w(m,x,s,n,g,5,C[28]),x,s,c,9,C[29]),m,x,p,14,C[30]),n,m,v,20,C[31]),s=z(s,n=z(n,m=z(m,x,s,n,f,4,C[32]),x,s,d,11,C[33]),m,x,y,16,C[34]),n,m,B,23,C[35]),s=z(s,n=z(n,m=z(m,x,s,n,i,4,C[36]),x,s,h,11,C[37]),m,x,p,16,C[38]),n,m,_,23,C[39]),s=z(s,n=z(n,m=z(m,x,s,n,g,4,C[40]),x,s,o,11,C[41]),m,x,a,16,C[42]),n,m,u,23,C[43]),s=z(s,n=z(n,m=z(m,x,s,n,l,4,C[44]),x,s,v,11,C[45]),m,x,S,16,C[46]),n,m,c,23,C[47]),s=E(s,n=E(n,m=E(m,x,s,n,o,6,C[48]),x,s,p,10,C[49]),m,x,B,15,C[50]),n,m,f,21,C[51]),s=E(s,n=E(n,m=E(m,x,s,n,v,6,C[52]),x,s,a,10,C[53]),m,x,_,15,C[54]),n,m,i,21,C[55]),s=E(s,n=E(n,m=E(m,x,s,n,d,6,C[56]),x,s,S,10,C[57]),m,x,u,15,C[58]),n,m,g,21,C[59]),s=E(s,n=E(n,m=E(m,x,s,n,h,6,C[60]),x,s,y,10,C[61]),m,x,c,15,C[62]),n,m,l,21,C[63]);r[0]=r[0]+m|0,r[1]=r[1]+x|0,r[2]=r[2]+s|0,r[3]=r[3]+n|0},_doFinalize:function(){var t=this._data,e=t.words,r=8*this._nDataBytes,i=8*t.sigBytes;e[i>>>5]|=128<<24-i%32;var n=s.floor(r/4294967296);for(e[15+(i+64>>>9<<4)]=16711935&(n<<8|n>>>24)|4278255360&(n<<24|n>>>8),e[14+(i+64>>>9<<4)]=16711935&(r<<8|r>>>24)|4278255360&(r<<24|r>>>8),t.sigBytes=4*(e.length+1),this._process(),e=(t=this._hash).words,r=0;r<4;r++)i=e[r],e[r]=16711935&(i<<8|i>>>24)|4278255360&(i<<24|i>>>8);return t},clone:function(){var t=r.clone.call(this);return t._hash=this._hash.clone(),t}}),t.MD5=r._createHelper(i),t.HmacMD5=r._createHmacHelper(i)}(Math),n=(e=(r=A).lib).Base,h=e.WordArray,s=(e=r.algo).EvpKDF=n.extend({cfg:n.extend({keySize:4,hasher:e.MD5,iterations:1}),init:function(t){this.cfg=this.cfg.extend(t)},compute:function(t,e){for(var r=(o=this.cfg).hasher.create(),i=h.create(),n=i.words,s=o.keySize,o=o.iterations;n.length<s;){c&&r.update(c);var c=r.update(t).finalize(e);r.reset();for(var a=1;a<o;a++)c=r.finalize(c),r.reset();i.concat(c)}return i.sigBytes=4*s,i}}),r.EvpKDF=function(t,e,r){return s.create(r).compute(t,e)},A.lib.Cipher||function(t){var e=(d=A).lib,r=e.Base,o=e.WordArray,i=e.BufferedBlockAlgorithm,n=d.enc.Base64,s=d.algo.EvpKDF,c=e.Cipher=i.extend({cfg:r.extend(),createEncryptor:function(t,e){return this.create(this._ENC_XFORM_MODE,t,e)},createDecryptor:function(t,e){return this.create(this._DEC_XFORM_MODE,t,e)},init:function(t,e,r){this.cfg=this.cfg.extend(r),this._xformMode=t,this._key=e,this.reset()},reset:function(){i.reset.call(this),this._doReset()},process:function(t){return this._append(t),this._process()},finalize:function(t){return t&&this._append(t),this._doFinalize()},keySize:4,ivSize:4,_ENC_XFORM_MODE:1,_DEC_XFORM_MODE:2,_createHelper:function(i){return{encrypt:function(t,e,r){return("string"==typeof e?l:p).encrypt(i,t,e,r)},decrypt:function(t,e,r){return("string"==typeof e?l:p).decrypt(i,t,e,r)}}}});e.StreamCipher=c.extend({_doFinalize:function(){return this._process(!0)},blockSize:1});var a=d.mode={},h=function(t,e,r){var i=this._iv;i?this._iv=void 0:i=this._prevBlock;for(var n=0;n<r;n++)t[e+n]^=i[n]},f=(e.BlockCipherMode=r.extend({createEncryptor:function(t,e){return this.Encryptor.create(t,e)},createDecryptor:function(t,e){return this.Decryptor.create(t,e)},init:function(t,e){this._cipher=t,this._iv=e}})).extend();f.Encryptor=f.extend({processBlock:function(t,e){var r=this._cipher,i=r.blockSize;h.call(this,t,e,i),r.encryptBlock(t,e),this._prevBlock=t.slice(e,e+i)}}),f.Decryptor=f.extend({processBlock:function(t,e){var r=this._cipher,i=r.blockSize,n=t.slice(e,e+i);r.decryptBlock(t,e),h.call(this,t,e,i),this._prevBlock=n}}),a=a.CBC=f,f=(d.pad={}).Pkcs7={pad:function(t,e){for(var r,i=(r=(r=4*e)-t.sigBytes%r)<<24|r<<16|r<<8|r,n=[],s=0;s<r;s+=4)n.push(i);r=o.create(n,r),t.concat(r)},unpad:function(t){t.sigBytes-=255&t.words[t.sigBytes-1>>>2]}},e.BlockCipher=c.extend({cfg:c.cfg.extend({mode:a,padding:f}),reset:function(){c.reset.call(this);var t=(e=this.cfg).iv,e=e.mode;if(this._xformMode==this._ENC_XFORM_MODE)var r=e.createEncryptor;else r=e.createDecryptor,this._minBufferSize=1;this._mode=r.call(e,this,t&&t.words)},_doProcessBlock:function(t,e){this._mode.processBlock(t,e)},_doFinalize:function(){var t=this.cfg.padding;if(this._xformMode==this._ENC_XFORM_MODE){t.pad(this._data,this.blockSize);var e=this._process(!0)}else e=this._process(!0),t.unpad(e);return e},blockSize:4});var u=e.CipherParams=r.extend({init:function(t){this.mixIn(t)},toString:function(t){return(t||this.formatter).stringify(this)}}),p=(a=(d.format={}).OpenSSL={stringify:function(t){var e=t.ciphertext;return((t=t.salt)?o.create([1398893684,1701076831]).concat(t).concat(e):e).toString(n)},parse:function(t){var e=(t=n.parse(t)).words;if(1398893684==e[0]&&1701076831==e[1]){var r=o.create(e.slice(2,4));e.splice(0,4),t.sigBytes-=16}return u.create({ciphertext:t,salt:r})}},e.SerializableCipher=r.extend({cfg:r.extend({format:a}),encrypt:function(t,e,r,i){i=this.cfg.extend(i);var n=t.createEncryptor(r,i);return e=n.finalize(e),n=n.cfg,u.create({ciphertext:e,key:r,iv:n.iv,algorithm:t,mode:n.mode,padding:n.padding,blockSize:t.blockSize,formatter:i.format})},decrypt:function(t,e,r,i){return i=this.cfg.extend(i),e=this._parse(e,i.format),t.createDecryptor(r,i).finalize(e.ciphertext)},_parse:function(t,e){return"string"==typeof t?e.parse(t,this):t}})),d=(d.kdf={}).OpenSSL={execute:function(t,e,r,i){return i||(i=o.random(8)),t=s.create({keySize:e+r}).compute(t,i),r=o.create(t.words.slice(e),4*r),t.sigBytes=4*e,u.create({key:t,iv:r,salt:i})}},l=e.PasswordBasedCipher=p.extend({cfg:p.cfg.extend({kdf:d}),encrypt:function(t,e,r,i){return r=(i=this.cfg.extend(i)).kdf.execute(r,t.keySize,t.ivSize),i.iv=r.iv,(t=p.encrypt.call(this,t,e,r.key,i)).mixIn(r),t},decrypt:function(t,e,r,i){return i=this.cfg.extend(i),e=this._parse(e,i.format),r=i.kdf.execute(r,t.keySize,t.ivSize,e.salt),i.iv=r.iv,p.decrypt.call(this,t,e,r.key,i)}})}(),function(){for(var t=A,e=t.lib.BlockCipher,r=t.algo,o=[],i=[],n=[],s=[],c=[],a=[],h=[],f=[],u=[],p=[],d=[],l=0;l<256;l++)d[l]=l<128?l<<1:l<<1^283;var _=0,y=0;for(l=0;l<256;l++){var v=(v=y^y<<1^y<<2^y<<3^y<<4)>>>8^255&v^99;o[_]=v;var g=d[i[v]=_],B=d[g],S=d[B],m=257*d[v]^16843008*v;n[_]=m<<24|m>>>8,s[_]=m<<16|m>>>16,c[_]=m<<8|m>>>24,a[_]=m,m=16843009*S^65537*B^257*g^16843008*_,h[v]=m<<24|m>>>8,f[v]=m<<16|m>>>16,u[v]=m<<8|m>>>24,p[v]=m,_?(_=g^d[d[d[S^g]]],y^=d[d[y]]):_=y=1}var x=[0,1,2,4,8,16,32,64,128,27,54];r=r.AES=e.extend({_doReset:function(){for(var t=(r=this._key).words,e=r.sigBytes/4,r=4*((this._nRounds=e+6)+1),i=this._keySchedule=[],n=0;n<r;n++)if(n<e)i[n]=t[n];else{var s=i[n-1];n%e?6<e&&4==n%e&&(s=o[s>>>24]<<24|o[s>>>16&255]<<16|o[s>>>8&255]<<8|o[255&s]):(s=o[(s=s<<8|s>>>24)>>>24]<<24|o[s>>>16&255]<<16|o[s>>>8&255]<<8|o[255&s],s^=x[n/e|0]<<24),i[n]=i[n-e]^s}for(t=this._invKeySchedule=[],e=0;e<r;e++)n=r-e,s=e%4?i[n]:i[n-4],t[e]=e<4||n<=4?s:h[o[s>>>24]]^f[o[s>>>16&255]]^u[o[s>>>8&255]]^p[o[255&s]]},encryptBlock:function(t,e){this._doCryptBlock(t,e,this._keySchedule,n,s,c,a,o)},decryptBlock:function(t,e){var r=t[e+1];t[e+1]=t[e+3],t[e+3]=r,this._doCryptBlock(t,e,this._invKeySchedule,h,f,u,p,i),r=t[e+1],t[e+1]=t[e+3],t[e+3]=r},_doCryptBlock:function(t,e,r,i,n,s,o,c){for(var a=this._nRounds,h=t[e]^r[0],f=t[e+1]^r[1],u=t[e+2]^r[2],p=t[e+3]^r[3],d=4,l=1;l<a;l++){var _=i[h>>>24]^n[f>>>16&255]^s[u>>>8&255]^o[255&p]^r[d++],y=i[f>>>24]^n[u>>>16&255]^s[p>>>8&255]^o[255&h]^r[d++],v=i[u>>>24]^n[p>>>16&255]^s[h>>>8&255]^o[255&f]^r[d++];p=i[p>>>24]^n[h>>>16&255]^s[f>>>8&255]^o[255&u]^r[d++],h=_,f=y,u=v}_=(c[h>>>24]<<24|c[f>>>16&255]<<16|c[u>>>8&255]<<8|c[255&p])^r[d++],y=(c[f>>>24]<<24|c[u>>>16&255]<<16|c[p>>>8&255]<<8|c[255&h])^r[d++],v=(c[u>>>24]<<24|c[p>>>16&255]<<16|c[h>>>8&255]<<8|c[255&f])^r[d++],p=(c[p>>>24]<<24|c[h>>>16&255]<<16|c[f>>>8&255]<<8|c[255&u])^r[d++],t[e]=_,t[e+1]=y,t[e+2]=v,t[e+3]=p},keySize:8});t.AES=e._createHelper(r)}(),c=(p=(o=A).lib).WordArray,f=p.Hasher,u=[],p=o.algo.SHA1=f.extend({_doReset:function(){this._hash=new c.init([1732584193,4023233417,2562383102,271733878,3285377520])},_doProcessBlock:function(t,e){for(var r=this._hash.words,i=r[0],n=r[1],s=r[2],o=r[3],c=r[4],a=0;a<80;a++){if(a<16)u[a]=0|t[e+a];else{var h=u[a-3]^u[a-8]^u[a-14]^u[a-16];u[a]=h<<1|h>>>31}h=(i<<5|i>>>27)+c+u[a],h=a<20?h+(1518500249+(n&s|~n&o)):a<40?h+(1859775393+(n^s^o)):a<60?h+((n&s|n&o|s&o)-1894007588):h+((n^s^o)-899497514),c=o,o=s,s=n<<30|n>>>2,n=i,i=h}r[0]=r[0]+i|0,r[1]=r[1]+n|0,r[2]=r[2]+s|0,r[3]=r[3]+o|0,r[4]=r[4]+c|0},_doFinalize:function(){var t=this._data,e=t.words,r=8*this._nDataBytes,i=8*t.sigBytes;return e[i>>>5]|=128<<24-i%32,e[14+(i+64>>>9<<4)]=Math.floor(r/4294967296),e[15+(i+64>>>9<<4)]=r,t.sigBytes=4*e.length,this._process(),this._hash},clone:function(){var t=f.clone.call(this);return t._hash=this._hash.clone(),t}}),o.SHA1=f._createHelper(p),o.HmacSHA1=f._createHmacHelper(p)}();









//rsa 源码http://www-cs-students.stanford.edu/~tjw/jsbn/


!function(){var t,n="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/",h="=";function u(t){var i,r,o="";for(t.length%2&&(t="0"+t),i=0;i+3<=t.length;i+=3)r=parseInt(t.substring(i,i+3),16),o+=n.charAt(r>>6)+n.charAt(63&r);for(i+1==t.length?(r=parseInt(t.substring(i,i+1),16),o+=n.charAt(r<<2)):i+2==t.length&&(r=parseInt(t.substring(i,i+2),16),o+=n.charAt(r>>2)+n.charAt((3&r)<<4));0<(3&o.length);)o+=h;return o}function o(t){var i,r,o,s="",e=0;for(i=0;i<t.length&&t.charAt(i)!=h;++i)(o=n.indexOf(t.charAt(i)))<0||(0==e?(s+=f(o>>2),r=3&o,e=1):1==e?(s+=f(r<<2|o>>4),r=15&o,e=2):2==e?(s+=f(r),s+=f(o>>2),r=3&o,e=3):(s+=f(r<<2|o>>4),s+=f(15&o),e=0));return 1==e&&(s+=f(r<<2)),s}function g(t,i,r){null!=t&&("number"==typeof t?this.fromNumber(t,i,r):null==i&&"string"!=typeof t?this.fromString(t,256):this.fromString(t,i))}function b(){return new g(null)}"Microsoft Internet Explorer"==navigator.appName?(g.prototype.am=function(t,i,r,o,s,e){for(var n=32767&i,h=i>>15;0<=--e;){var u=32767&this[t],f=this[t++]>>15,p=h*u+f*n;s=((u=n*u+((32767&p)<<15)+r[o]+(1073741823&s))>>>30)+(p>>>15)+h*f+(s>>>30),r[o++]=1073741823&u}return s},t=30):"Netscape"!=navigator.appName?(g.prototype.am=function(t,i,r,o,s,e){for(;0<=--e;){var n=i*this[t++]+r[o]+s;s=Math.floor(n/67108864),r[o++]=67108863&n}return s},t=26):(g.prototype.am=function(t,i,r,o,s,e){for(var n=16383&i,h=i>>14;0<=--e;){var u=16383&this[t],f=this[t++]>>14,p=h*u+f*n;s=((u=n*u+((16383&p)<<14)+r[o]+s)>>28)+(p>>14)+h*f,r[o++]=268435455&u}return s},t=28),g.prototype.DB=t,g.prototype.DM=(1<<t)-1,g.prototype.DV=1<<t;g.prototype.FV=Math.pow(2,52),g.prototype.F1=52-t,g.prototype.F2=2*t-52;var i,r,s="0123456789abcdefghijklmnopqrstuvwxyz",e=new Array;for(i="0".charCodeAt(0),r=0;r<=9;++r)e[i++]=r;for(i="a".charCodeAt(0),r=10;r<36;++r)e[i++]=r;for(i="A".charCodeAt(0),r=10;r<36;++r)e[i++]=r;function f(t){return s.charAt(t)}function p(t,i){var r=e[t.charCodeAt(i)];return null==r?-1:r}function v(t){var i=b();return i.fromInt(t),i}function B(t){var i,r=1;return 0!=(i=t>>>16)&&(t=i,r+=16),0!=(i=t>>8)&&(t=i,r+=8),0!=(i=t>>4)&&(t=i,r+=4),0!=(i=t>>2)&&(t=i,r+=2),0!=(i=t>>1)&&(t=i,r+=1),r}function T(t){this.m=t}function d(t){this.m=t,this.mp=t.invDigit(),this.mpl=32767&this.mp,this.mph=this.mp>>15,this.um=(1<<t.DB-15)-1,this.mt2=2*t.t}function a(t,i){return t&i}function c(t,i){return t|i}function l(t,i){return t^i}function m(t,i){return t&~i}function y(t){if(0==t)return-1;var i=0;return 0==(65535&t)&&(t>>=16,i+=16),0==(255&t)&&(t>>=8,i+=8),0==(15&t)&&(t>>=4,i+=4),0==(3&t)&&(t>>=2,i+=2),0==(1&t)&&++i,i}function D(t){for(var i=0;0!=t;)t&=t-1,++i;return i}function S(){}function w(t){return t}function E(t){this.r2=b(),this.q3=b(),g.ONE.dlShiftTo(2*t.t,this.r2),this.mu=this.r2.divide(t),this.m=t}T.prototype.convert=function(t){return t.s<0||0<=t.compareTo(this.m)?t.mod(this.m):t},T.prototype.revert=function(t){return t},T.prototype.reduce=function(t){t.divRemTo(this.m,null,t)},T.prototype.mulTo=function(t,i,r){t.multiplyTo(i,r),this.reduce(r)},T.prototype.sqrTo=function(t,i){t.squareTo(i),this.reduce(i)},d.prototype.convert=function(t){var i=b();return t.abs().dlShiftTo(this.m.t,i),i.divRemTo(this.m,null,i),t.s<0&&0<i.compareTo(g.ZERO)&&this.m.subTo(i,i),i},d.prototype.revert=function(t){var i=b();return t.copyTo(i),this.reduce(i),i},d.prototype.reduce=function(t){for(;t.t<=this.mt2;)t[t.t++]=0;for(var i=0;i<this.m.t;++i){var r=32767&t[i],o=r*this.mpl+((r*this.mph+(t[i]>>15)*this.mpl&this.um)<<15)&t.DM;for(t[r=i+this.m.t]+=this.m.am(0,o,t,i,0,this.m.t);t[r]>=t.DV;)t[r]-=t.DV,t[++r]++}t.clamp(),t.drShiftTo(this.m.t,t),0<=t.compareTo(this.m)&&t.subTo(this.m,t)},d.prototype.mulTo=function(t,i,r){t.multiplyTo(i,r),this.reduce(r)},d.prototype.sqrTo=function(t,i){t.squareTo(i),this.reduce(i)},g.prototype.copyTo=function(t){for(var i=this.t-1;0<=i;--i)t[i]=this[i];t.t=this.t,t.s=this.s},g.prototype.fromInt=function(t){this.t=1,this.s=t<0?-1:0,0<t?this[0]=t:t<-1?this[0]=t+this.DV:this.t=0},g.prototype.fromString=function(t,i){var r;if(16==i)r=4;else if(8==i)r=3;else if(256==i)r=8;else if(2==i)r=1;else if(32==i)r=5;else{if(4!=i)return void this.fromRadix(t,i);r=2}this.t=0,this.s=0;for(var o=t.length,s=!1,e=0;0<=--o;){var n=8==r?255&t[o]:p(t,o);n<0?"-"==t.charAt(o)&&(s=!0):(s=!1,0==e?this[this.t++]=n:e+r>this.DB?(this[this.t-1]|=(n&(1<<this.DB-e)-1)<<e,this[this.t++]=n>>this.DB-e):this[this.t-1]|=n<<e,(e+=r)>=this.DB&&(e-=this.DB))}8==r&&0!=(128&t[0])&&(this.s=-1,0<e&&(this[this.t-1]|=(1<<this.DB-e)-1<<e)),this.clamp(),s&&g.ZERO.subTo(this,this)},g.prototype.clamp=function(){for(var t=this.s&this.DM;0<this.t&&this[this.t-1]==t;)--this.t},g.prototype.dlShiftTo=function(t,i){var r;for(r=this.t-1;0<=r;--r)i[r+t]=this[r];for(r=t-1;0<=r;--r)i[r]=0;i.t=this.t+t,i.s=this.s},g.prototype.drShiftTo=function(t,i){for(var r=t;r<this.t;++r)i[r-t]=this[r];i.t=Math.max(this.t-t,0),i.s=this.s},g.prototype.lShiftTo=function(t,i){var r,o=t%this.DB,s=this.DB-o,e=(1<<s)-1,n=Math.floor(t/this.DB),h=this.s<<o&this.DM;for(r=this.t-1;0<=r;--r)i[r+n+1]=this[r]>>s|h,h=(this[r]&e)<<o;for(r=n-1;0<=r;--r)i[r]=0;i[n]=h,i.t=this.t+n+1,i.s=this.s,i.clamp()},g.prototype.rShiftTo=function(t,i){i.s=this.s;var r=Math.floor(t/this.DB);if(r>=this.t)i.t=0;else{var o=t%this.DB,s=this.DB-o,e=(1<<o)-1;i[0]=this[r]>>o;for(var n=r+1;n<this.t;++n)i[n-r-1]|=(this[n]&e)<<s,i[n-r]=this[n]>>o;0<o&&(i[this.t-r-1]|=(this.s&e)<<s),i.t=this.t-r,i.clamp()}},g.prototype.subTo=function(t,i){for(var r=0,o=0,s=Math.min(t.t,this.t);r<s;)o+=this[r]-t[r],i[r++]=o&this.DM,o>>=this.DB;if(t.t<this.t){for(o-=t.s;r<this.t;)o+=this[r],i[r++]=o&this.DM,o>>=this.DB;o+=this.s}else{for(o+=this.s;r<t.t;)o-=t[r],i[r++]=o&this.DM,o>>=this.DB;o-=t.s}i.s=o<0?-1:0,o<-1?i[r++]=this.DV+o:0<o&&(i[r++]=o),i.t=r,i.clamp()},g.prototype.multiplyTo=function(t,i){var r=this.abs(),o=t.abs(),s=r.t;for(i.t=s+o.t;0<=--s;)i[s]=0;for(s=0;s<o.t;++s)i[s+r.t]=r.am(0,o[s],i,s,0,r.t);i.s=0,i.clamp(),this.s!=t.s&&g.ZERO.subTo(i,i)},g.prototype.squareTo=function(t){for(var i=this.abs(),r=t.t=2*i.t;0<=--r;)t[r]=0;for(r=0;r<i.t-1;++r){var o=i.am(r,i[r],t,2*r,0,1);(t[r+i.t]+=i.am(r+1,2*i[r],t,2*r+1,o,i.t-r-1))>=i.DV&&(t[r+i.t]-=i.DV,t[r+i.t+1]=1)}0<t.t&&(t[t.t-1]+=i.am(r,i[r],t,2*r,0,1)),t.s=0,t.clamp()},g.prototype.divRemTo=function(t,i,r){var o=t.abs();if(!(o.t<=0)){var s=this.abs();if(s.t<o.t)return null!=i&&i.fromInt(0),void(null!=r&&this.copyTo(r));null==r&&(r=b());var e=b(),n=this.s,h=t.s,u=this.DB-B(o[o.t-1]);0<u?(o.lShiftTo(u,e),s.lShiftTo(u,r)):(o.copyTo(e),s.copyTo(r));var f=e.t,p=e[f-1];if(0!=p){var a=p*(1<<this.F1)+(1<f?e[f-2]>>this.F2:0),c=this.FV/a,l=(1<<this.F1)/a,m=1<<this.F2,y=r.t,v=y-f,T=null==i?b():i;for(e.dlShiftTo(v,T),0<=r.compareTo(T)&&(r[r.t++]=1,r.subTo(T,r)),g.ONE.dlShiftTo(f,T),T.subTo(e,e);e.t<f;)e[e.t++]=0;for(;0<=--v;){var d=r[--y]==p?this.DM:Math.floor(r[y]*c+(r[y-1]+m)*l);if((r[y]+=e.am(0,d,r,v,0,f))<d)for(e.dlShiftTo(v,T),r.subTo(T,r);r[y]<--d;)r.subTo(T,r)}null!=i&&(r.drShiftTo(f,i),n!=h&&g.ZERO.subTo(i,i)),r.t=f,r.clamp(),0<u&&r.rShiftTo(u,r),n<0&&g.ZERO.subTo(r,r)}}},g.prototype.invDigit=function(){if(this.t<1)return 0;var t=this[0];if(0==(1&t))return 0;var i=3&t;return 0<(i=(i=(i=(i=i*(2-(15&t)*i)&15)*(2-(255&t)*i)&255)*(2-((65535&t)*i&65535))&65535)*(2-t*i%this.DV)%this.DV)?this.DV-i:-i},g.prototype.isEven=function(){return 0==(0<this.t?1&this[0]:this.s)},g.prototype.exp=function(t,i){if(4294967295<t||t<1)return g.ONE;var r=b(),o=b(),s=i.convert(this),e=B(t)-1;for(s.copyTo(r);0<=--e;)if(i.sqrTo(r,o),0<(t&1<<e))i.mulTo(o,s,r);else{var n=r;r=o,o=n}return i.revert(r)},g.prototype.toString=function(t){if(this.s<0)return"-"+this.negate().toString(t);var i;if(16==t)i=4;else if(8==t)i=3;else if(2==t)i=1;else if(32==t)i=5;else{if(4!=t)return this.toRadix(t);i=2}var r,o=(1<<i)-1,s=!1,e="",n=this.t,h=this.DB-n*this.DB%i;if(0<n--)for(h<this.DB&&0<(r=this[n]>>h)&&(s=!0,e=f(r));0<=n;)h<i?(r=(this[n]&(1<<h)-1)<<i-h,r|=this[--n]>>(h+=this.DB-i)):(r=this[n]>>(h-=i)&o,h<=0&&(h+=this.DB,--n)),0<r&&(s=!0),s&&(e+=f(r));return s?e:"0"},g.prototype.negate=function(){var t=b();return g.ZERO.subTo(this,t),t},g.prototype.abs=function(){return this.s<0?this.negate():this},g.prototype.compareTo=function(t){var i=this.s-t.s;if(0!=i)return i;var r=this.t;if(0!=(i=r-t.t))return this.s<0?-i:i;for(;0<=--r;)if(0!=(i=this[r]-t[r]))return i;return 0},g.prototype.bitLength=function(){return this.t<=0?0:this.DB*(this.t-1)+B(this[this.t-1]^this.s&this.DM)},g.prototype.mod=function(t){var i=b();return this.abs().divRemTo(t,null,i),this.s<0&&0<i.compareTo(g.ZERO)&&t.subTo(i,i),i},g.prototype.modPowInt=function(t,i){var r;return r=t<256||i.isEven()?new T(i):new d(i),this.exp(t,r)},g.ZERO=v(0),g.ONE=v(1),S.prototype.convert=w,S.prototype.revert=w,S.prototype.mulTo=function(t,i,r){t.multiplyTo(i,r)},S.prototype.sqrTo=function(t,i){t.squareTo(i)},E.prototype.convert=function(t){if(t.s<0||t.t>2*this.m.t)return t.mod(this.m);if(t.compareTo(this.m)<0)return t;var i=b();return t.copyTo(i),this.reduce(i),i},E.prototype.revert=function(t){return t},E.prototype.reduce=function(t){for(t.drShiftTo(this.m.t-1,this.r2),t.t>this.m.t+1&&(t.t=this.m.t+1,t.clamp()),this.mu.multiplyUpperTo(this.r2,this.m.t+1,this.q3),this.m.multiplyLowerTo(this.q3,this.m.t+1,this.r2);t.compareTo(this.r2)<0;)t.dAddOffset(1,this.m.t+1);for(t.subTo(this.r2,t);0<=t.compareTo(this.m);)t.subTo(this.m,t)},E.prototype.mulTo=function(t,i,r){t.multiplyTo(i,r),this.reduce(r)},E.prototype.sqrTo=function(t,i){t.squareTo(i),this.reduce(i)};var M=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997],A=(1<<26)/M[M.length-1];function O(){this.i=0,this.j=0,this.S=new Array}g.prototype.chunkSize=function(t){return Math.floor(Math.LN2*this.DB/Math.log(t))},g.prototype.toRadix=function(t){if(null==t&&(t=10),0==this.signum()||t<2||36<t)return"0";var i=this.chunkSize(t),r=Math.pow(t,i),o=v(r),s=b(),e=b(),n="";for(this.divRemTo(o,s,e);0<s.signum();)n=(r+e.intValue()).toString(t).substr(1)+n,s.divRemTo(o,s,e);return e.intValue().toString(t)+n},g.prototype.fromRadix=function(t,i){this.fromInt(0),null==i&&(i=10);for(var r=this.chunkSize(i),o=Math.pow(i,r),s=!1,e=0,n=0,h=0;h<t.length;++h){var u=p(t,h);u<0?"-"==t.charAt(h)&&0==this.signum()&&(s=!0):(n=i*n+u,++e>=r&&(this.dMultiply(o),this.dAddOffset(n,0),n=e=0))}0<e&&(this.dMultiply(Math.pow(i,e)),this.dAddOffset(n,0)),s&&g.ZERO.subTo(this,this)},g.prototype.fromNumber=function(t,i,r){if("number"==typeof i)if(t<2)this.fromInt(1);else for(this.fromNumber(t,r),this.testBit(t-1)||this.bitwiseTo(g.ONE.shiftLeft(t-1),c,this),this.isEven()&&this.dAddOffset(1,0);!this.isProbablePrime(i);)this.dAddOffset(2,0),this.bitLength()>t&&this.subTo(g.ONE.shiftLeft(t-1),this);else{var o=new Array,s=7&t;o.length=1+(t>>3),i.nextBytes(o),0<s?o[0]&=(1<<s)-1:o[0]=0,this.fromString(o,256)}},g.prototype.bitwiseTo=function(t,i,r){var o,s,e=Math.min(t.t,this.t);for(o=0;o<e;++o)r[o]=i(this[o],t[o]);if(t.t<this.t){for(s=t.s&this.DM,o=e;o<this.t;++o)r[o]=i(this[o],s);r.t=this.t}else{for(s=this.s&this.DM,o=e;o<t.t;++o)r[o]=i(s,t[o]);r.t=t.t}r.s=i(this.s,t.s),r.clamp()},g.prototype.changeBit=function(t,i){var r=g.ONE.shiftLeft(t);return this.bitwiseTo(r,i,r),r},g.prototype.addTo=function(t,i){for(var r=0,o=0,s=Math.min(t.t,this.t);r<s;)o+=this[r]+t[r],i[r++]=o&this.DM,o>>=this.DB;if(t.t<this.t){for(o+=t.s;r<this.t;)o+=this[r],i[r++]=o&this.DM,o>>=this.DB;o+=this.s}else{for(o+=this.s;r<t.t;)o+=t[r],i[r++]=o&this.DM,o>>=this.DB;o+=t.s}i.s=o<0?-1:0,0<o?i[r++]=o:o<-1&&(i[r++]=this.DV+o),i.t=r,i.clamp()},g.prototype.dMultiply=function(t){this[this.t]=this.am(0,t-1,this,0,0,this.t),++this.t,this.clamp()},g.prototype.dAddOffset=function(t,i){if(0!=t){for(;this.t<=i;)this[this.t++]=0;for(this[i]+=t;this[i]>=this.DV;)this[i]-=this.DV,++i>=this.t&&(this[this.t++]=0),++this[i]}},g.prototype.multiplyLowerTo=function(t,i,r){var o,s=Math.min(this.t+t.t,i);for(r.s=0,r.t=s;0<s;)r[--s]=0;for(o=r.t-this.t;s<o;++s)r[s+this.t]=this.am(0,t[s],r,s,0,this.t);for(o=Math.min(t.t,i);s<o;++s)this.am(0,t[s],r,s,0,i-s);r.clamp()},g.prototype.multiplyUpperTo=function(t,i,r){--i;var o=r.t=this.t+t.t-i;for(r.s=0;0<=--o;)r[o]=0;for(o=Math.max(i-this.t,0);o<t.t;++o)r[this.t+o-i]=this.am(i-o,t[o],r,0,0,this.t+o-i);r.clamp(),r.drShiftTo(1,r)},g.prototype.modInt=function(t){if(t<=0)return 0;var i=this.DV%t,r=this.s<0?t-1:0;if(0<this.t)if(0==i)r=this[0]%t;else for(var o=this.t-1;0<=o;--o)r=(i*r+this[o])%t;return r},g.prototype.millerRabin=function(t){var i=this.subtract(g.ONE),r=i.getLowestSetBit();if(r<=0)return!1;var o=i.shiftRight(r);(t=t+1>>1)>M.length&&(t=M.length);for(var s=b(),e=0;e<t;++e){s.fromInt(M[Math.floor(Math.random()*M.length)]);var n=s.modPow(o,this);if(0!=n.compareTo(g.ONE)&&0!=n.compareTo(i)){for(var h=1;h++<r&&0!=n.compareTo(i);)if(0==(n=n.modPowInt(2,this)).compareTo(g.ONE))return!1;if(0!=n.compareTo(i))return!1}}return!0},g.prototype.clone=function(){var t=b();return this.copyTo(t),t},g.prototype.intValue=function(){if(this.s<0){if(1==this.t)return this[0]-this.DV;if(0==this.t)return-1}else{if(1==this.t)return this[0];if(0==this.t)return 0}return(this[1]&(1<<32-this.DB)-1)<<this.DB|this[0]},g.prototype.byteValue=function(){return 0==this.t?this.s:this[0]<<24>>24},g.prototype.shortValue=function(){return 0==this.t?this.s:this[0]<<16>>16},g.prototype.signum=function(){return this.s<0?-1:this.t<=0||1==this.t&&this[0]<=0?0:1},g.prototype.toByteArray=function(){var t=this.t,i=new Array;i[0]=this.s;var r,o=this.DB-t*this.DB%8,s=0;if(0<t--)for(o<this.DB&&(r=this[t]>>o)!=(this.s&this.DM)>>o&&(i[s++]=r|this.s<<this.DB-o);0<=t;)o<8?(r=(this[t]&(1<<o)-1)<<8-o,r|=this[--t]>>(o+=this.DB-8)):(r=this[t]>>(o-=8)&255,o<=0&&(o+=this.DB,--t)),0!=(128&r)&&(r|=-256),0==s&&(128&this.s)!=(128&r)&&++s,(0<s||r!=this.s)&&(i[s++]=r);return i},g.prototype.equals=function(t){return 0==this.compareTo(t)},g.prototype.min=function(t){return this.compareTo(t)<0?this:t},g.prototype.max=function(t){return 0<this.compareTo(t)?this:t},g.prototype.and=function(t){var i=b();return this.bitwiseTo(t,a,i),i},g.prototype.or=function(t){var i=b();return this.bitwiseTo(t,c,i),i},g.prototype.xor=function(t){var i=b();return this.bitwiseTo(t,l,i),i},g.prototype.andNot=function(t){var i=b();return this.bitwiseTo(t,m,i),i},g.prototype.not=function(){for(var t=b(),i=0;i<this.t;++i)t[i]=this.DM&~this[i];return t.t=this.t,t.s=~this.s,t},g.prototype.shiftLeft=function(t){var i=b();return t<0?this.rShiftTo(-t,i):this.lShiftTo(t,i),i},g.prototype.shiftRight=function(t){var i=b();return t<0?this.lShiftTo(-t,i):this.rShiftTo(t,i),i},g.prototype.getLowestSetBit=function(){for(var t=0;t<this.t;++t)if(0!=this[t])return t*this.DB+y(this[t]);return this.s<0?this.t*this.DB:-1},g.prototype.bitCount=function(){for(var t=0,i=this.s&this.DM,r=0;r<this.t;++r)t+=D(this[r]^i);return t},g.prototype.testBit=function(t){var i=Math.floor(t/this.DB);return i>=this.t?0!=this.s:0!=(this[i]&1<<t%this.DB)},g.prototype.setBit=function(t){return this.changeBit(t,c)},g.prototype.clearBit=function(t){return this.changeBit(t,m)},g.prototype.flipBit=function(t){return this.changeBit(t,l)},g.prototype.add=function(t){var i=b();return this.addTo(t,i),i},g.prototype.subtract=function(t){var i=b();return this.subTo(t,i),i},g.prototype.multiply=function(t){var i=b();return this.multiplyTo(t,i),i},g.prototype.divide=function(t){var i=b();return this.divRemTo(t,i,null),i},g.prototype.remainder=function(t){var i=b();return this.divRemTo(t,null,i),i},g.prototype.divideAndRemainder=function(t){var i=b(),r=b();return this.divRemTo(t,i,r),new Array(i,r)},g.prototype.modPow=function(t,i){var r,o,s=t.bitLength(),e=v(1);if(s<=0)return e;r=s<18?1:s<48?3:s<144?4:s<768?5:6,o=s<8?new T(i):i.isEven()?new E(i):new d(i);var n=new Array,h=3,u=r-1,f=(1<<r)-1;if(n[1]=o.convert(this),1<r){var p=b();for(o.sqrTo(n[1],p);h<=f;)n[h]=b(),o.mulTo(p,n[h-2],n[h]),h+=2}var a,c,l=t.t-1,m=!0,y=b();for(s=B(t[l])-1;0<=l;){for(u<=s?a=t[l]>>s-u&f:(a=(t[l]&(1<<s+1)-1)<<u-s,0<l&&(a|=t[l-1]>>this.DB+s-u)),h=r;0==(1&a);)a>>=1,--h;if((s-=h)<0&&(s+=this.DB,--l),m)n[a].copyTo(e),m=!1;else{for(;1<h;)o.sqrTo(e,y),o.sqrTo(y,e),h-=2;0<h?o.sqrTo(e,y):(c=e,e=y,y=c),o.mulTo(y,n[a],e)}for(;0<=l&&0==(t[l]&1<<s);)o.sqrTo(e,y),c=e,e=y,y=c,--s<0&&(s=this.DB-1,--l)}return o.revert(e)},g.prototype.modInverse=function(t){var i=t.isEven();if(this.isEven()&&i||0==t.signum())return g.ZERO;for(var r=t.clone(),o=this.clone(),s=v(1),e=v(0),n=v(0),h=v(1);0!=r.signum();){for(;r.isEven();)r.rShiftTo(1,r),i?(s.isEven()&&e.isEven()||(s.addTo(this,s),e.subTo(t,e)),s.rShiftTo(1,s)):e.isEven()||e.subTo(t,e),e.rShiftTo(1,e);for(;o.isEven();)o.rShiftTo(1,o),i?(n.isEven()&&h.isEven()||(n.addTo(this,n),h.subTo(t,h)),n.rShiftTo(1,n)):h.isEven()||h.subTo(t,h),h.rShiftTo(1,h);0<=r.compareTo(o)?(r.subTo(o,r),i&&s.subTo(n,s),e.subTo(h,e)):(o.subTo(r,o),i&&n.subTo(s,n),h.subTo(e,h))}return 0!=o.compareTo(g.ONE)?g.ZERO:0<=h.compareTo(t)?h.subtract(t):h.signum()<0?(h.addTo(t,h),h.signum()<0?h.add(t):h):h},g.prototype.pow=function(t){return this.exp(t,new S)},g.prototype.gcd=function(t){var i=this.s<0?this.negate():this.clone(),r=t.s<0?t.negate():t.clone();if(i.compareTo(r)<0){var o=i;i=r,r=o}var s=i.getLowestSetBit(),e=r.getLowestSetBit();if(e<0)return i;for(s<e&&(e=s),0<e&&(i.rShiftTo(e,i),r.rShiftTo(e,r));0<i.signum();)0<(s=i.getLowestSetBit())&&i.rShiftTo(s,i),0<(s=r.getLowestSetBit())&&r.rShiftTo(s,r),0<=i.compareTo(r)?(i.subTo(r,i),i.rShiftTo(1,i)):(r.subTo(i,r),r.rShiftTo(1,r));return 0<e&&r.lShiftTo(e,r),r},g.prototype.isProbablePrime=function(t){var i,r=this.abs();if(1==r.t&&r[0]<=M[M.length-1]){for(i=0;i<M.length;++i)if(r[0]==M[i])return!0;return!1}if(r.isEven())return!1;for(i=1;i<M.length;){for(var o=M[i],s=i+1;s<M.length&&o<A;)o*=M[s++];for(o=r.modInt(o);i<s;)if(o%M[i++]==0)return!1}return r.millerRabin(t)},g.prototype.square=function(){var t=b();return this.squareTo(t),t},O.prototype.init=function(t){var i,r,o;for(i=0;i<256;++i)this.S[i]=i;for(i=r=0;i<256;++i)r=r+this.S[i]+t[i%t.length]&255,o=this.S[i],this.S[i]=this.S[r],this.S[r]=o;this.i=0,this.j=0},O.prototype.next=function(){var t;return this.i=this.i+1&255,this.j=this.j+this.S[this.i]&255,t=this.S[this.i],this.S[this.i]=this.S[this.j],this.S[this.j]=t,this.S[t+this.S[this.i]&255]};var q,R,I,N=256;function L(){var t;t=(new Date).getTime(),R[I++]^=255&t,R[I++]^=t>>8&255,R[I++]^=t>>16&255,R[I++]^=t>>24&255,N<=I&&(I-=N)}function V(){if(null==q){for(L(),(q=new O).init(R),I=0;I<R.length;++I)R[I]=0;I=0}return q.next()}function x(){}function P(t,i){return new g(t,i)}function C(t){for(var i=t.toByteArray(),r=t.toString(16),o=i.length-r.length/2;1<=o--;)r="0"+r;return u(r)}function H(t){for(var i,r,o,s,e,n,h,u=this.n.bitLength()/8,f=u-11,p=[],a=t.length;0<a;){for(i=new Array,r=0,o=u;0<a&&0<o;){if((s=t.charCodeAt(a-1))<128){if(f<(r+=1))break;i[--o]=s}else if(127<s&&s<2048){if(f<(r+=2))break;i[--o]=63&s|128,i[--o]=s>>6|192}else{if(f<(r+=3))break;i[--o]=63&s|128,i[--o]=s>>6&63|128,i[--o]=s>>12|224}a--}for(i[--o]=0,e=new x,n=new Array;2<o;){for(n[0]=0;0==n[0];)e.nextBytes(n);i[--o]=n[0]}if(i[--o]=2,i[--o]=0,null==(s=new g(i).modPowInt(this.e,this.n)))return null;0==(1&(h=s.toString(16)).length)?p.push(h):p.push("0"+h)}return p.reverse(),this.HEXBytesToBase64(p.join(""))}function Z(t){t=this.Base64BytesToHEX(t);var i,r,o,s,e,n,h=this.n.bitLength()/8,u=[],f=t.length/2/h,p=0;if(0<t.length/2%h)return null;for(;0<f;){if(i=h,null==(r=P(t.substr(p,2*h),16).modPow(this.d,this.n)))return null;for(o=r.toByteArray(),s=0;s<o.length&&0==o[s];)++s;if(o.length-s!=i-1||2!=o[s])return null;for(++s;0!=o[s];)if(++s>=o.length)return null;for(e="";++s<o.length;)(n=255&o[s])<128?e+=String.fromCharCode(n):191<n&&n<224?(e+=String.fromCharCode((31&n)<<6|63&o[s+1]),++s):(e+=String.fromCharCode((15&n)<<12|(63&o[s+1])<<6|63&o[s+2]),s+=2);u.push(e),p+=2*h,f--}return u.join("")}function j(t,i){this.getKeyLoop?this.getKeyLoop++:this.getKeyLoop=1,(t<512||t%8)&&(t=2048);var r=new x,o=t>>1;this.e=P(i?this.Base64BytesToHEX(i):"10001",16);for(var s=new g(i?this.Base64BytesToHEX(i):"10001",16);;){for(;this.p=new g(t-o,1,r),0!=this.p.subtract(g.ONE).gcd(s).compareTo(g.ONE)||!this.p.isProbablePrime(10););for(;this.q=new g(o,1,r),0!=this.q.subtract(g.ONE).gcd(s).compareTo(g.ONE)||!this.q.isProbablePrime(10););if(this.p.compareTo(this.q)<=0){var e=this.p;this.p=this.q,this.q=e}var n=this.p.subtract(g.ONE),h=this.q.subtract(g.ONE),u=n.multiply(h);if(0==u.gcd(s).compareTo(g.ONE)){this.n=this.p.multiply(this.q),this.d=s.modInverse(u),this.dmp1=this.d.mod(n),this.dmq1=this.d.mod(h),this.coeff=this.q.modInverse(this.p);break}}if(this.modulusInt=this.n,this.publicInt=this.e,this.privateInt=this.d,this.n.bitLength()%8){if(this.getKeyLoop<3)return this.getKey(t,i);throw"生成密钥失败！"}return this.getKeyLoop=0,this}!function(){var t;if(R=new Array,I=0,window.crypto&&window.crypto.getRandomValues){var i=new Uint8Array(32);for(window.crypto.getRandomValues(i),t=0;t<32;++t)R[I++]=i[t]}if("Netscape"==navigator.appName&&navigator.appVersion<"5"&&window.crypto){var r=window.crypto.random(32);for(t=0;t<r.length;++t)R[I++]=255&r.charCodeAt(t)}for(;I<N;)t=Math.floor(65536*Math.random()),R[I++]=t>>>8,R[I++]=255&t;I=0,L()}(),x.prototype.nextBytes=function(t){var i;for(i=0;i<t.length;++i)t[i]=V()};var X={SHA1:"3021300906052b0e03021a05000414",SHA256:"3031300d060960864801650304020105000420"};function k(t,i){i=i||"SHA1";for(var r=this.n.bitLength()/4,o=window[i](t),s="00"+X[i]+o,e="",n=r-"0001".length-s.length,h=0;h<n;h+=2)e+="ff";return u(P("0001"+e+s,16).modPow(this.d,this.n).toString(16))}function F(t,i,r){return r=r||"SHA1",P(o(i),16).modPowInt(this.e,this.n).toString(16).replace(/^1f+00/,"").substring(X[r].length).toUpperCase()==window[r](t).toUpperCase()}var K,U=((K=function(t,i,r){this.n=null,this.e=0,this.d=null,this.p=null,this.q=null,this.dmp1=null,this.dmq1=null,this.coeff=null,"number"==typeof t?this.getKey(t,i):(t&&(this.n=P(this.Base64BytesToHEX(t),16)),i&&(this.e=P(this.Base64BytesToHEX(i),16)),r&&(this.d=P(this.Base64BytesToHEX(r),16))),this.modulusInt=this.n,this.publicInt=this.e,this.privateInt=this.d}).prototype={encrypt:H,decrypt:Z,sign:k,verify:F,getKey:j,getPublic:function(){return C(this.publicInt)},getPrivate:function(){return C(this.privateInt)},getModulus:function(){return C(this.modulusInt)},HEXBytesToBase64:u,Base64BytesToHEX:o},function(t,i,r){try{return new K(t,i,r)}catch(i){return null}});window.RSA=U}();