VerifyJS demo <--- Drag to bookmarks toolbar

2012-08-02

This is a proof-of-concept for code signing and loading in Javascript using bookmarklets that link to data:text/html URIs. I was inspired by @kaepora's Cryptocat and the resulting discussions with @moxie and @ioerror whether it's possible to deploy secure apps in the browser.

There are many obstacles to such, but the big one is this: Every time you open the app, it is effectively reinstalling fresh from the server. Even if you deliver over HTTPS, this means your app can be no more secure than HTTPS. And a server compromise will also compromise your users by allowing an attacker to deliver malicious code.

Native apps improve on this situation by holding their code signing keys offline, and having discrete, numbered releases that can at least in theory be audited individually.

VerifyJS takes a similar approach. You save a bookmarklet once, and afterwards always access the app via bookmarklet. The bookmarklet contains an ECDSA implementation borrowed from Cryptocat. It loads an iframe on a provider host, and that iframe uses window.postMessage to send a signed JS payload. The bookmarklet only evaluates the payload if the signature validates according to the public key that is baked into it. At this point the evaluated JS takes over the page context to do with what it likes.

This means that you only have to trust the network at one point: when you install the bookmarklet. After that the provider host is completely untrusted, but it is still possible for the author to deploy new versions of their app, so long as they sign it.

It's possible to build complex apps this way. HTML and CSS can be compiled into JS strings to be inserted in the page dynamically. Images can be compiled into data: URIs. It is important to remember, of course, that you must bundle all of your dependencies into the signed JS.

This approach works on (at least) the latest versions of Chrome, Firefox, and Safari. It does not work on Internet Explorer.

Caveat: Since the app is hosted on a data: URI, it cannot store data in cookies or localStorage. User-specific information (like keypairs) can be baked into the bookmarklet at install time, but cannot be changed afterwards.

Caveat: All communication with remote origin must be handled using an iframe and postMessage. The host document isn't on any origin so can't use XmlHTTPRequest, and JSONP is unsafe.

Rejected approach: Using HTML5 appcache to cache the app's contents offline and never update them except with signed code. This doesn't work because appcache contents can get reloaded any time the cache manifest changes, which leaves you with the same old server vulnerabilities. The cache manifest must be same-origin with the app page, so the manifest URL cannot be a data: URI.

Below is a textarea containing the exact code the will be inserted into your bookmarklet. It's live, so if you want to make tweaks and try them out, just edit inline and drag the link above onto your bookmarks toolbar. See also the signer and provider pages.

Feedback welcome. I'm @j4cob on Twitter. Or comment on github.

Update May 2014: Here's the Twitter thread that resulted. Note: The crypto code below was taken from an old version of CryptoCat. Make sure to use up-to-date and valid crypto code.

<head></head><body><script> (function() { // This content is released under the MIT license // (http://opensource.org/licenses/MIT). var config = { providerOrigin: 'https://jacob.hoffman-andrews.com', // This iframe is expected to call // parent.postMessage('signature|payload', '*'); provider: '/verify-js/provide.html', // This is the public key used to sign (using ecdsaSign from cryptocat's // elliptic.js) the payload provided by the provider iframe. pubKey: '["KIs8XIF5aYdgMgXuCbkw0bpifutAYsk_V5sA6aSkI8","46b379sM_lH5EC=K6vepJfGy7TyMHp7aHQL368_c6nQ"]' }; function verifyAndLoad(data) { var signature = data.substr(0, data.indexOf('|')); var payload = data.substr(data.indexOf('|') + 1); var verified = ecdsaVerify(config.pubKey, signature, payload); if (verified) { eval(payload); } else { alert('signature failed to verify:' + signature + ' payload:' + payload); } } // This receives the postMessage call from the iframe created below. window.addEventListener('message', function(event) { // Verifying the origin of the postMessage call is slightly redundant // because we're also verifying signatures. But this prevents // a malicious actor who doesn't control our origin from posting // an older signed payload with known bugs. // Ideally we would have a "last seen" timestamp in the signed payload // to prevent such playback, but data: URIs can't use localStorage or cookies. if (event.origin == config.providerOrigin) { verifyAndLoad(event.data); } else { alert('origin check failed: ' + event.origin); } }, false); window.addEventListener('load', function() { var iframe = document.createElement('iframe'); iframe.src = config.providerOrigin + config.provider; document.body.appendChild(iframe); }, false); // End MIT-licensed code. Code below is public domain (bigint and whirlpool) or // AGPL (elliptic.js from Cryptocat). //////////////////////////////////////////////////////////////////////////////////////// // Big Integer Library v. 5.4 // Created 2000, last modified 2009 // Leemon Baird // www.leemon.com // // Version history: // v 5.4 3 Oct 2009 // - added "var i" to greaterShift() so i is not global. (Thanks to Pter Szab for finding that bug) // // v 5.3 21 Sep 2009 // - added randProbPrime(k) for probable primes // - unrolled loop in mont_ (slightly faster) // - millerRabin now takes a bigInt parameter rather than an int // // v 5.2 15 Sep 2009 // - fixed capitalization in call to int2bigInt in randBigInt // (thanks to Emili Evripidou, Reinhold Behringer, and Samuel Macaleese for finding that bug) // // v 5.1 8 Oct 2007 // - renamed inverseModInt_ to inverseModInt since it doesn't change its parameters // - added functions GCD and randBigInt, which call GCD_ and randBigInt_ // - fixed a bug found by Rob Visser (see comment with his name below) // - improved comments // // This file is public domain. You can use it for any purpose without restriction. // I do not guarantee that it is correct, so use it at your own risk. If you use // it for something interesting, I'd appreciate hearing about it. If you find // any bugs or make any improvements, I'd appreciate hearing about those too. // It would also be nice if my name and URL were left in the comments. But none // of that is required. // // This code defines a bigInt library for arbitrary-precision integers. // A bigInt is an array of integers storing the value in chunks of bpe bits, // little endian (buff[0] is the least significant word). // Negative bigInts are stored two's complement. Almost all the functions treat // bigInts as nonnegative. The few that view them as two's complement say so // in their comments. Some functions assume their parameters have at least one // leading zero element. Functions with an underscore at the end of the name put // their answer into one of the arrays passed in, and have unpredictable behavior // in case of overflow, so the caller must make sure the arrays are big enough to // hold the answer. But the average user should never have to call any of the // underscored functions. Each important underscored function has a wrapper function // of the same name without the underscore that takes care of the details for you. // For each underscored function where a parameter is modified, that same variable // must not be used as another argument too. So, you cannot square x by doing // multMod_(x,x,n). You must use squareMod_(x,n) instead, or do y=dup(x); multMod_(x,y,n). // Or simply use the multMod(x,x,n) function without the underscore, where // such issues never arise, because non-underscored functions never change // their parameters; they always allocate new memory for the answer that is returned. // // These functions are designed to avoid frequent dynamic memory allocation in the inner loop. // For most functions, if it needs a BigInt as a local variable it will actually use // a global, and will only allocate to it only when it's not the right size. This ensures // that when a function is called repeatedly with same-sized parameters, it only allocates // memory on the first call. // // Note that for cryptographic purposes, the calls to Math.random() must // be replaced with calls to a better pseudorandom number generator. // // In the following, "bigInt" means a bigInt with at least one leading zero element, // and "integer" means a nonnegative integer less than radix. In some cases, integer // can be negative. Negative bigInts are 2s complement. // // The following functions do not modify their inputs. // Those returning a bigInt, string, or Array will dynamically allocate memory for that value. // Those returning a boolean will return the integer 0 (false) or 1 (true). // Those returning boolean or int will not allocate memory except possibly on the first // time they're called with a given parameter size. // // bigInt add(x,y) //return (x+y) for bigInts x and y. // bigInt addInt(x,n) //return (x+n) where x is a bigInt and n is an integer. // string bigInt2str(x,base) //return a string form of bigInt x in a given base, with 2 <= base <= 95 // int bitSize(x) //return how many bits long the bigInt x is, not counting leading zeros // bigInt dup(x) //return a copy of bigInt x // boolean equals(x,y) //is the bigInt x equal to the bigint y? // boolean equalsInt(x,y) //is bigint x equal to integer y? // bigInt expand(x,n) //return a copy of x with at least n elements, adding leading zeros if needed // Array findPrimes(n) //return array of all primes less than integer n // bigInt GCD(x,y) //return greatest common divisor of bigInts x and y (each with same number of elements). // boolean greater(x,y) //is x>y? (x and y are nonnegative bigInts) // boolean greaterShift(x,y,shift)//is (x <<(shift*bpe)) > y? // bigInt int2bigInt(t,n,m) //return a bigInt equal to integer t, with at least n bits and m array elements // bigInt inverseMod(x,n) //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null // int inverseModInt(x,n) //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse // boolean isZero(x) //is the bigInt x equal to zero? // boolean millerRabin(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime? (b is bigInt, 1<b<x) // boolean millerRabinInt(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime? (b is int, 1<b<x) // bigInt mod(x,n) //return a new bigInt equal to (x mod n) for bigInts x and n. // int modInt(x,n) //return x mod n for bigInt x and integer n. // bigInt mult(x,y) //return x*y for bigInts x and y. This is faster when y<x. // bigInt multMod(x,y,n) //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x. // boolean negative(x) //is bigInt x negative? // bigInt powMod(x,y,n) //return (x**y mod n) where x,y,n are bigInts and ** is exponentiation. 0**0=1. Faster for odd n. // bigInt randBigInt(n,s) //return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1. // bigInt randTruePrime(k) //return a new, random, k-bit, true prime bigInt using Maurer's algorithm. // bigInt randProbPrime(k) //return a new, random, k-bit, probable prime bigInt (probability it's composite less than 2^-80). // bigInt str2bigInt(s,b,n,m) //return a bigInt for number represented in string s in base b with at least n bits and m array elements // bigInt sub(x,y) //return (x-y) for bigInts x and y. Negative answers will be 2s complement // bigInt trim(x,k) //return a copy of x with exactly k leading zero elements // // // The following functions each have a non-underscored version, which most users should call instead. // These functions each write to a single parameter, and the caller is responsible for ensuring the array // passed in is large enough to hold the result. // // void addInt_(x,n) //do x=x+n where x is a bigInt and n is an integer // void add_(x,y) //do x=x+y for bigInts x and y // void copy_(x,y) //do x=y on bigInts x and y // void copyInt_(x,n) //do x=n on bigInt x and integer n // void GCD_(x,y) //set x to the greatest common divisor of bigInts x and y, (y is destroyed). (This never overflows its array). // boolean inverseMod_(x,n) //do x=x**(-1) mod n, for bigInts x and n. Returns 1 (0) if inverse does (doesn't) exist // void mod_(x,n) //do x=x mod n for bigInts x and n. (This never overflows its array). // void mult_(x,y) //do x=x*y for bigInts x and y. // void multMod_(x,y,n) //do x=x*y mod n for bigInts x,y,n. // void powMod_(x,y,n) //do x=x**y mod n, where x,y,n are bigInts (n is odd) and ** is exponentiation. 0**0=1. // void randBigInt_(b,n,s) //do b = an n-bit random BigInt. if s=1, then nth bit (most significant bit) is set to 1. n>=1. // void randTruePrime_(ans,k) //do ans = a random k-bit true random prime (not just probable prime) with 1 in the msb. // void sub_(x,y) //do x=x-y for bigInts x and y. Negative answers will be 2s complement. // // The following functions do NOT have a non-underscored version. // They each write a bigInt result to one or more parameters. The caller is responsible for // ensuring the arrays passed in are large enough to hold the results. // // void addShift_(x,y,ys) //do x=x+(y<<(ys*bpe)) // void carry_(x) //do carries and borrows so each element of the bigInt x fits in bpe bits. // void divide_(x,y,q,r) //divide x by y giving quotient q and remainder r // int divInt_(x,n) //do x=floor(x/n) for bigInt x and integer n, and return the remainder. (This never overflows its array). // int eGCD_(x,y,d,a,b) //sets a,b,d to positive bigInts such that d = GCD_(x,y) = a*x-b*y // void halve_(x) //do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement. (This never overflows its array). // void leftShift_(x,n) //left shift bigInt x by n bits. n<bpe. // void linComb_(x,y,a,b) //do x=a*x+b*y for bigInts x and y and integers a and b // void linCombShift_(x,y,b,ys) //do x=x+b*(y<<(ys*bpe)) for bigInts x and y, and integers b and ys // void mont_(x,y,n,np) //Montgomery multiplication (see comments where the function is defined) // void multInt_(x,n) //do x=x*n where x is a bigInt and n is an integer. // void rightShift_(x,n) //right shift bigInt x by n bits. 0 <= n < bpe. (This never overflows its array). // void squareMod_(x,n) //do x=x*x mod n for bigInts x,n // void subShift_(x,y,ys) //do x=x-(y<<(ys*bpe)). Negative answers will be 2s complement. // // The following functions are based on algorithms from the _Handbook of Applied Cryptography_ // powMod_() = algorithm 14.94, Montgomery exponentiation // eGCD_,inverseMod_() = algorithm 14.61, Binary extended GCD_ // GCD_() = algorothm 14.57, Lehmer's algorithm // mont_() = algorithm 14.36, Montgomery multiplication // divide_() = algorithm 14.20 Multiple-precision division // squareMod_() = algorithm 14.16 Multiple-precision squaring // randTruePrime_() = algorithm 4.62, Maurer's algorithm // millerRabin() = algorithm 4.24, Miller-Rabin algorithm // // Profiling shows: // randTruePrime_() spends: // 10% of its time in calls to powMod_() // 85% of its time in calls to millerRabin() // millerRabin() spends: // 99% of its time in calls to powMod_() (always with a base of 2) // powMod_() spends: // 94% of its time in calls to mont_() (almost always with x==y) // // This suggests there are several ways to speed up this library slightly: // - convert powMod_ to use a Montgomery form of k-ary window (or maybe a Montgomery form of sliding window) // -- this should especially focus on being fast when raising 2 to a power mod n // - convert randTruePrime_() to use a minimum r of 1/3 instead of 1/2 with the appropriate change to the test // - tune the parameters in randTruePrime_(), including c, m, and recLimit // - speed up the single loop in mont_() that takes 95% of the runtime, perhaps by reducing checking // within the loop when all the parameters are the same length. // // There are several ideas that look like they wouldn't help much at all: // - replacing trial division in randTruePrime_() with a sieve (that speeds up something taking almost no time anyway) // - increase bpe from 15 to 30 (that would help if we had a 32*32->64 multiplier, but not with JavaScript's 32*32->32) // - speeding up mont_(x,y,n,np) when x==y by doing a non-modular, non-Montgomery square // followed by a Montgomery reduction. The intermediate answer will be twice as long as x, so that // method would be slower. This is unfortunate because the code currently spends almost all of its time // doing mont_(x,x,...), both for randTruePrime_() and powMod_(). A faster method for Montgomery squaring // would have a large impact on the speed of randTruePrime_() and powMod_(). HAC has a couple of poorly-worded // sentences that seem to imply it's faster to do a non-modular square followed by a single // Montgomery reduction, but that's obviously wrong. //////////////////////////////////////////////////////////////////////////////////////// //globals bpe=0; //bits stored per array element mask=0; //AND this with an array element to chop it down to bpe bits radix=mask+1; //equals 2^bpe. A single 1 bit to the left of the last bit of mask. //the digits for converting to different bases digitsStr='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}|;:,.<>/?`~ \\\'\"+-'; //initialize the global variables for (bpe=0; (1<<(bpe+1)) > (1<<bpe); bpe++); //bpe=number of bits in the mantissa on this platform bpe>>=1; //bpe=number of bits in one element of the array representing the bigInt mask=(1<<bpe)-1; //AND the mask with an integer to get its bpe least significant bits radix=mask+1; //2^bpe. a single 1 bit to the left of the first bit of mask one=int2bigInt(1,1,1); //constant used in powMod_() //the following global variables are scratchpad memory to //reduce dynamic memory allocation in the inner loop t=new Array(0); ss=t; //used in mult_() s0=t; //used in multMod_(), squareMod_() s1=t; //used in powMod_(), multMod_(), squareMod_() s2=t; //used in powMod_(), multMod_() s3=t; //used in powMod_() s4=t; s5=t; //used in mod_() s6=t; //used in bigInt2str() s7=t; //used in powMod_() T=t; //used in GCD_() sa=t; //used in mont_() mr_x1=t; mr_r=t; mr_a=t; //used in millerRabin() eg_v=t; eg_u=t; eg_A=t; eg_B=t; eg_C=t; eg_D=t; //used in eGCD_(), inverseMod_() md_q1=t; md_q2=t; md_q3=t; md_r=t; md_r1=t; md_r2=t; md_tt=t; //used in mod_() primes=t; pows=t; s_i=t; s_i2=t; s_R=t; s_rm=t; s_q=t; s_n1=t; s_a=t; s_r2=t; s_n=t; s_b=t; s_d=t; s_x1=t; s_x2=t, s_aa=t; //used in randTruePrime_() rpprb=t; //used in randProbPrimeRounds() (which also uses "primes") //////////////////////////////////////////////////////////////////////////////////////// //return array of all primes less than integer n function findPrimes(n) { var i,s,p,ans; s=new Array(n); for (i=0;i<n;i++) s[i]=0; s[0]=2; p=0; //first p elements of s are primes, the rest are a sieve for(;s[p]<n;) { //s[p] is the pth prime for(i=s[p]*s[p]; i<n; i+=s[p]) //mark multiples of s[p] s[i]=1; p++; s[p]=s[p-1]+1; for(; s[p]<n && s[s[p]]; s[p]++); //find next prime (where s[p]==0) } ans=new Array(p); for(i=0;i<p;i++) ans[i]=s[i]; return ans; } //does a single round of Miller-Rabin base b consider x to be a possible prime? //x is a bigInt, and b is an integer, with b<x function millerRabinInt(x,b) { if (mr_x1.length!=x.length) { mr_x1=dup(x); mr_r=dup(x); mr_a=dup(x); } copyInt_(mr_a,b); return millerRabin(x,mr_a); } //does a single round of Miller-Rabin base b consider x to be a possible prime? //x and b are bigInts with b<x function millerRabin(x,b) { var i,j,k,s; if (mr_x1.length!=x.length) { mr_x1=dup(x); mr_r=dup(x); mr_a=dup(x); } copy_(mr_a,b); copy_(mr_r,x); copy_(mr_x1,x); addInt_(mr_r,-1); addInt_(mr_x1,-1); //s=the highest power of two that divides mr_r k=0; for (i=0;i<mr_r.length;i++) for (j=1;j<mask;j<<=1) if (x[i] & j) { s=(k<mr_r.length+bpe ? k : 0); i=mr_r.length; j=mask; } else k++; if (s) rightShift_(mr_r,s); powMod_(mr_a,mr_r,x); if (!equalsInt(mr_a,1) && !equals(mr_a,mr_x1)) { j=1; while (j<=s-1 && !equals(mr_a,mr_x1)) { squareMod_(mr_a,x); if (equalsInt(mr_a,1)) { return 0; } j++; } if (!equals(mr_a,mr_x1)) { return 0; } } return 1; } //returns how many bits long the bigInt is, not counting leading zeros. function bitSize(x) { var j,z,w; for (j=x.length-1; (x[j]==0) && (j>0); j--); for (z=0,w=x[j]; w; (w>>=1),z++); z+=bpe*j; return z; } //return a copy of x with at least n elements, adding leading zeros if needed function expand(x,n) { var ans=int2bigInt(0,(x.length>n ? x.length : n)*bpe,0); copy_(ans,x); return ans; } //return a k-bit true random prime using Maurer's algorithm. function randTruePrime(k) { var ans=int2bigInt(0,k,0); randTruePrime_(ans,k); return trim(ans,1); } //return a k-bit random probable prime with probability of error < 2^-80 function randProbPrime(k) { if (k>=600) return randProbPrimeRounds(k,2); //numbers from HAC table 4.3 if (k>=550) return randProbPrimeRounds(k,4); if (k>=500) return randProbPrimeRounds(k,5); if (k>=400) return randProbPrimeRounds(k,6); if (k>=350) return randProbPrimeRounds(k,7); if (k>=300) return randProbPrimeRounds(k,9); if (k>=250) return randProbPrimeRounds(k,12); //numbers from HAC table 4.4 if (k>=200) return randProbPrimeRounds(k,15); if (k>=150) return randProbPrimeRounds(k,18); if (k>=100) return randProbPrimeRounds(k,27); return randProbPrimeRounds(k,40); //number from HAC remark 4.26 (only an estimate) } //return a k-bit probable random prime using n rounds of Miller Rabin (after trial division with small primes) function randProbPrimeRounds(k,n) { var ans, i, divisible, B; B=30000; //B is largest prime to use in trial division ans=int2bigInt(0,k,0); //optimization: try larger and smaller B to find the best limit. if (primes.length==0) primes=findPrimes(30000); //check for divisibility by primes <=30000 if (rpprb.length!=ans.length) rpprb=dup(ans); for (;;) { //keep trying random values for ans until one appears to be prime //optimization: pick a random number times L=2*3*5*...*p, plus a // random element of the list of all numbers in [0,L) not divisible by any prime up to p. // This can reduce the amount of random number generation. randBigInt_(ans,k,0); //ans = a random odd number to check ans[0] |= 1; divisible=0; //check ans for divisibility by small primes up to B for (i=0; (i<primes.length) && (primes[i]<=B); i++) if (modInt(ans,primes[i])==0 && !equalsInt(ans,primes[i])) { divisible=1; break; } //optimization: change millerRabin so the base can be bigger than the number being checked, then eliminate the while here. //do n rounds of Miller Rabin, with random bases less than ans for (i=0; i<n && !divisible; i++) { randBigInt_(rpprb,k,0); while(!greater(ans,rpprb)) //pick a random rpprb that's < ans randBigInt_(rpprb,k,0); if (!millerRabin(ans,rpprb)) divisible=1; } if(!divisible) return ans; } } //return a new bigInt equal to (x mod n) for bigInts x and n. function mod(x,n) { var ans=dup(x); mod_(ans,n); return trim(ans,1); } //return (x+n) where x is a bigInt and n is an integer. function addInt(x,n) { var ans=expand(x,x.length+1); addInt_(ans,n); return trim(ans,1); } //return x*y for bigInts x and y. This is faster when y<x. function mult(x,y) { var ans=expand(x,x.length+y.length); mult_(ans,y); return trim(ans,1); } //return (x**y mod n) where x,y,n are bigInts and ** is exponentiation. 0**0=1. Faster for odd n. function powMod(x,y,n) { var ans=expand(x,n.length); powMod_(ans,trim(y,2),trim(n,2),0); //this should work without the trim, but doesn't return trim(ans,1); } //return (x-y) for bigInts x and y. Negative answers will be 2s complement function sub(x,y) { var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); sub_(ans,y); return trim(ans,1); } //return (x+y) for bigInts x and y. function add(x,y) { var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); add_(ans,y); return trim(ans,1); } //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null function inverseMod(x,n) { var ans=expand(x,n.length); var s; s=inverseMod_(ans,n); return s ? trim(ans,1) : null; } //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x. function multMod(x,y,n) { var ans=expand(x,n.length); multMod_(ans,y,n); return trim(ans,1); } //generate a k-bit true random prime using Maurer's algorithm, //and put it into ans. The bigInt ans must be large enough to hold it. function randTruePrime_(ans,k) { var c,m,pm,dd,j,r,B,divisible,z,zz,recSize; if (primes.length==0) primes=findPrimes(30000); //check for divisibility by primes <=30000 if (pows.length==0) { pows=new Array(512); for (j=0;j<512;j++) { pows[j]=Math.pow(2,j/511.-1.); } } //c and m should be tuned for a particular machine and value of k, to maximize speed c=0.1; //c=0.1 in HAC m=20; //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits recLimit=20; //stop recursion when k <=recLimit. Must have recLimit >= 2 if (s_i2.length!=ans.length) { s_i2=dup(ans); s_R =dup(ans); s_n1=dup(ans); s_r2=dup(ans); s_d =dup(ans); s_x1=dup(ans); s_x2=dup(ans); s_b =dup(ans); s_n =dup(ans); s_i =dup(ans); s_rm=dup(ans); s_q =dup(ans); s_a =dup(ans); s_aa=dup(ans); } if (k <= recLimit) { //generate small random primes by trial division up to its square root pm=(1<<((k+2)>>1))-1; //pm is binary number with all ones, just over sqrt(2^k) copyInt_(ans,0); for (dd=1;dd;) { dd=0; ans[0]= 1 | (1<<(k-1)) | Math.floor(Math.random()*(1<<k)); //random, k-bit, odd integer, with msb 1 for (j=1;(j<primes.length) && ((primes[j]&pm)==primes[j]);j++) { //trial division by all primes 3...sqrt(2^k) if (0==(ans[0]%primes[j])) { dd=1; break; } } } carry_(ans); return; } B=c*k*k; //try small primes up to B (or all the primes[] array if the largest is less than B). if (k>2*m) //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits for (r=1; k-k*r<=m; ) r=pows[Math.floor(Math.random()*512)]; //r=Math.pow(2,Math.random()-1); else r=.5; //simulation suggests the more complex algorithm using r=.333 is only slightly faster. recSize=Math.floor(r*k)+1; randTruePrime_(s_q,recSize); copyInt_(s_i2,0); s_i2[Math.floor((k-2)/bpe)] |= (1<<((k-2)%bpe)); //s_i2=2^(k-2) divide_(s_i2,s_q,s_i,s_rm); //s_i=floor((2^(k-1))/(2q)) z=bitSize(s_i); for (;;) { for (;;) { //generate z-bit numbers until one falls in the range [0,s_i-1] randBigInt_(s_R,z,0); if (greater(s_i,s_R)) break; } //now s_R is in the range [0,s_i-1] addInt_(s_R,1); //now s_R is in the range [1,s_i] add_(s_R,s_i); //now s_R is in the range [s_i+1,2*s_i] copy_(s_n,s_q); mult_(s_n,s_R); multInt_(s_n,2); addInt_(s_n,1); //s_n=2*s_R*s_q+1 copy_(s_r2,s_R); multInt_(s_r2,2); //s_r2=2*s_R //check s_n for divisibility by small primes up to B for (divisible=0,j=0; (j<primes.length) && (primes[j]<B); j++) if (modInt(s_n,primes[j])==0 && !equalsInt(s_n,primes[j])) { divisible=1; break; } if (!divisible) //if it passes small primes check, then try a single Miller-Rabin base 2 if (!millerRabinInt(s_n,2)) //this line represents 75% of the total runtime for randTruePrime_ divisible=1; if (!divisible) { //if it passes that test, continue checking s_n addInt_(s_n,-3); for (j=s_n.length-1;(s_n[j]==0) && (j>0); j--); //strip leading zeros for (zz=0,w=s_n[j]; w; (w>>=1),zz++); zz+=bpe*j; //zz=number of bits in s_n, ignoring leading zeros for (;;) { //generate z-bit numbers until one falls in the range [0,s_n-1] randBigInt_(s_a,zz,0); if (greater(s_n,s_a)) break; } //now s_a is in the range [0,s_n-1] addInt_(s_n,3); //now s_a is in the range [0,s_n-4] addInt_(s_a,2); //now s_a is in the range [2,s_n-2] copy_(s_b,s_a); copy_(s_n1,s_n); addInt_(s_n1,-1); powMod_(s_b,s_n1,s_n); //s_b=s_a^(s_n-1) modulo s_n addInt_(s_b,-1); if (isZero(s_b)) { copy_(s_b,s_a); powMod_(s_b,s_r2,s_n); addInt_(s_b,-1); copy_(s_aa,s_n); copy_(s_d,s_b); GCD_(s_d,s_n); //if s_b and s_n are relatively prime, then s_n is a prime if (equalsInt(s_d,1)) { copy_(ans,s_aa); return; //if we've made it this far, then s_n is absolutely guaranteed to be prime } } } } } //Return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1. function randBigInt(n,s) { var a,b; a=Math.floor((n-1)/bpe)+2; //# array elements to hold the BigInt with a leading 0 element b=int2bigInt(0,0,a); randBigInt_(b,n,s); return b; } //Set b to an n-bit random BigInt. If s=1, then the most significant of those n bits is set to 1. //Array b must be big enough to hold the result. Must have n>=1 function randBigInt_(b,n,s) { var i,a; for (i=0;i<b.length;i++) b[i]=0; a=Math.floor((n-1)/bpe)+1; //# array elements to hold the BigInt for (i=0;i<a;i++) { b[i]=Math.floor(Math.random()*(1<<(bpe-1))); } b[a-1] &= (2<<((n-1)%bpe))-1; if (s==1) b[a-1] |= (1<<((n-1)%bpe)); } //Return the greatest common divisor of bigInts x and y (each with same number of elements). function GCD(x,y) { var xc,yc; xc=dup(x); yc=dup(y); GCD_(xc,yc); return xc; } //set x to the greatest common divisor of bigInts x and y (each with same number of elements). //y is destroyed. function GCD_(x,y) { var i,xp,yp,A,B,C,D,q,sing; if (T.length!=x.length) T=dup(x); sing=1; while (sing) { //while y has nonzero elements other than y[0] sing=0; for (i=1;i<y.length;i++) //check if y has nonzero elements other than 0 if (y[i]) { sing=1; break; } if (!sing) break; //quit when y all zero elements except possibly y[0] for (i=x.length;!x[i] && i>=0;i--); //find most significant element of x xp=x[i]; yp=y[i]; A=1; B=0; C=0; D=1; while ((yp+C) && (yp+D)) { q =Math.floor((xp+A)/(yp+C)); qp=Math.floor((xp+B)/(yp+D)); if (q!=qp) break; t= A-q*C; A=C; C=t; // do (A,B,xp, C,D,yp) = (C,D,yp, A,B,xp) - q*(0,0,0, C,D,yp) t= B-q*D; B=D; D=t; t=xp-q*yp; xp=yp; yp=t; } if (B) { copy_(T,x); linComb_(x,y,A,B); //x=A*x+B*y linComb_(y,T,D,C); //y=D*y+C*T } else { mod_(x,y); copy_(T,x); copy_(x,y); copy_(y,T); } } if (y[0]==0) return; t=modInt(x,y[0]); copyInt_(x,y[0]); y[0]=t; while (y[0]) { x[0]%=y[0]; t=x[0]; x[0]=y[0]; y[0]=t; } } //do x=x**(-1) mod n, for bigInts x and n. //If no inverse exists, it sets x to zero and returns 0, else it returns 1. //The x array must be at least as large as the n array. function inverseMod_(x,n) { var k=1+2*Math.max(x.length,n.length); if(!(x[0]&1) && !(n[0]&1)) { //if both inputs are even, then inverse doesn't exist copyInt_(x,0); return 0; } if (eg_u.length!=k) { eg_u=new Array(k); eg_v=new Array(k); eg_A=new Array(k); eg_B=new Array(k); eg_C=new Array(k); eg_D=new Array(k); } copy_(eg_u,x); copy_(eg_v,n); copyInt_(eg_A,1); copyInt_(eg_B,0); copyInt_(eg_C,0); copyInt_(eg_D,1); for (;;) { while(!(eg_u[0]&1)) { //while eg_u is even halve_(eg_u); if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if eg_A==eg_B==0 mod 2 halve_(eg_A); halve_(eg_B); } else { add_(eg_A,n); halve_(eg_A); sub_(eg_B,x); halve_(eg_B); } } while (!(eg_v[0]&1)) { //while eg_v is even halve_(eg_v); if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if eg_C==eg_D==0 mod 2 halve_(eg_C); halve_(eg_D); } else { add_(eg_C,n); halve_(eg_C); sub_(eg_D,x); halve_(eg_D); } } if (!greater(eg_v,eg_u)) { //eg_v <= eg_u sub_(eg_u,eg_v); sub_(eg_A,eg_C); sub_(eg_B,eg_D); } else { //eg_v > eg_u sub_(eg_v,eg_u); sub_(eg_C,eg_A); sub_(eg_D,eg_B); } if (equalsInt(eg_u,0)) { if (negative(eg_C)) //make sure answer is nonnegative add_(eg_C,n); copy_(x,eg_C); if (!equalsInt(eg_v,1)) { //if GCD_(x,n)!=1, then there is no inverse copyInt_(x,0); return 0; } return 1; } } } //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse function inverseModInt(x,n) { var a=1,b=0,t; for (;;) { if (x==1) return a; if (x==0) return 0; b-=a*Math.floor(n/x); n%=x; if (n==1) return b; //to avoid negatives, change this b to n-b, and each -= to += if (n==0) return 0; a-=b*Math.floor(x/n); x%=n; } } //this deprecated function is for backward compatibility only. function inverseModInt_(x,n) { return inverseModInt(x,n); } //Given positive bigInts x and y, change the bigints v, a, and b to positive bigInts such that: // v = GCD_(x,y) = a*x-b*y //The bigInts v, a, b, must have exactly as many elements as the larger of x and y. function eGCD_(x,y,v,a,b) { var g=0; var k=Math.max(x.length,y.length); if (eg_u.length!=k) { eg_u=new Array(k); eg_A=new Array(k); eg_B=new Array(k); eg_C=new Array(k); eg_D=new Array(k); } while(!(x[0]&1) && !(y[0]&1)) { //while x and y both even halve_(x); halve_(y); g++; } copy_(eg_u,x); copy_(v,y); copyInt_(eg_A,1); copyInt_(eg_B,0); copyInt_(eg_C,0); copyInt_(eg_D,1); for (;;) { while(!(eg_u[0]&1)) { //while u is even halve_(eg_u); if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if A==B==0 mod 2 halve_(eg_A); halve_(eg_B); } else { add_(eg_A,y); halve_(eg_A); sub_(eg_B,x); halve_(eg_B); } } while (!(v[0]&1)) { //while v is even halve_(v); if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if C==D==0 mod 2 halve_(eg_C); halve_(eg_D); } else { add_(eg_C,y); halve_(eg_C); sub_(eg_D,x); halve_(eg_D); } } if (!greater(v,eg_u)) { //v<=u sub_(eg_u,v); sub_(eg_A,eg_C); sub_(eg_B,eg_D); } else { //v>u sub_(v,eg_u); sub_(eg_C,eg_A); sub_(eg_D,eg_B); } if (equalsInt(eg_u,0)) { if (negative(eg_C)) { //make sure a (C)is nonnegative add_(eg_C,y); sub_(eg_D,x); } multInt_(eg_D,-1); ///make sure b (D) is nonnegative copy_(a,eg_C); copy_(b,eg_D); leftShift_(v,g); return; } } } //is bigInt x negative? function negative(x) { return ((x[x.length-1]>>(bpe-1))&1); } //is (x << (shift*bpe)) > y? //x and y are nonnegative bigInts //shift is a nonnegative integer function greaterShift(x,y,shift) { var i, kx=x.length, ky=y.length; k=((kx+shift)<ky) ? (kx+shift) : ky; for (i=ky-1-shift; i<kx && i>=0; i++) if (x[i]>0) return 1; //if there are nonzeros in x to the left of the first column of y, then x is bigger for (i=kx-1+shift; i<ky; i++) if (y[i]>0) return 0; //if there are nonzeros in y to the left of the first column of x, then x is not bigger for (i=k-1; i>=shift; i--) if (x[i-shift]>y[i]) return 1; else if (x[i-shift]<y[i]) return 0; return 0; } //is x > y? (x and y both nonnegative) function greater(x,y) { var i; var k=(x.length<y.length) ? x.length : y.length; for (i=x.length;i<y.length;i++) if (y[i]) return 0; //y has more digits for (i=y.length;i<x.length;i++) if (x[i]) return 1; //x has more digits for (i=k-1;i>=0;i--) if (x[i]>y[i]) return 1; else if (x[i]<y[i]) return 0; return 0; } //divide x by y giving quotient q and remainder r. (q=floor(x/y), r=x mod y). All 4 are bigints. //x must have at least one leading zero element. //y must be nonzero. //q and r must be arrays that are exactly the same length as x. (Or q can have more). //Must have x.length >= y.length >= 2. function divide_(x,y,q,r) { var kx, ky; var i,j,y1,y2,c,a,b; copy_(r,x); for (ky=y.length;y[ky-1]==0;ky--); //ky is number of elements in y, not including leading zeros //normalize: ensure the most significant element of y has its highest bit set b=y[ky-1]; for (a=0; b; a++) b>>=1; a=bpe-a; //a is how many bits to shift so that the high order bit of y is leftmost in its array element leftShift_(y,a); //multiply both by 1<<a now, then divide both by that at the end leftShift_(r,a); //Rob Visser discovered a bug: the following line was originally just before the normalization. for (kx=r.length;r[kx-1]==0 && kx>ky;kx--); //kx is number of elements in normalized x, not including leading zeros copyInt_(q,0); // q=0 while (!greaterShift(y,r,kx-ky)) { // while (leftShift_(y,kx-ky) <= r) { subShift_(r,y,kx-ky); // r=r-leftShift_(y,kx-ky) q[kx-ky]++; // q[kx-ky]++; } // } for (i=kx-1; i>=ky; i--) { if (r[i]==y[ky-1]) q[i-ky]=mask; else q[i-ky]=Math.floor((r[i]*radix+r[i-1])/y[ky-1]); //The following for(;;) loop is equivalent to the commented while loop, //except that the uncommented version avoids overflow. //The commented loop comes from HAC, which assumes r[-1]==y[-1]==0 // while (q[i-ky]*(y[ky-1]*radix+y[ky-2]) > r[i]*radix*radix+r[i-1]*radix+r[i-2]) // q[i-ky]--; for (;;) { y2=(ky>1 ? y[ky-2] : 0)*q[i-ky]; c=y2>>bpe; y2=y2 & mask; y1=c+q[i-ky]*y[ky-1]; c=y1>>bpe; y1=y1 & mask; if (c==r[i] ? y1==r[i-1] ? y2>(i>1 ? r[i-2] : 0) : y1>r[i-1] : c>r[i]) q[i-ky]--; else break; } linCombShift_(r,y,-q[i-ky],i-ky); //r=r-q[i-ky]*leftShift_(y,i-ky) if (negative(r)) { addShift_(r,y,i-ky); //r=r+leftShift_(y,i-ky) q[i-ky]--; } } rightShift_(y,a); //undo the normalization step rightShift_(r,a); //undo the normalization step } //do carries and borrows so each element of the bigInt x fits in bpe bits. function carry_(x) { var i,k,c,b; k=x.length; c=0; for (i=0;i<k;i++) { c+=x[i]; b=0; if (c<0) { b=-(c>>bpe); c+=b*radix; } x[i]=c & mask; c=(c>>bpe)-b; } } //return x mod n for bigInt x and integer n. function modInt(x,n) { var i,c=0; for (i=x.length-1; i>=0; i--) c=(c*radix+x[i])%n; return c; } //convert the integer t into a bigInt with at least the given number of bits. //the returned array stores the bigInt in bpe-bit chunks, little endian (buff[0] is least significant word) //Pad the array with leading zeros so that it has at least minSize elements. //There will always be at least one leading 0 element. function int2bigInt(t,bits,minSize) { var i,k; k=Math.ceil(bits/bpe)+1; k=minSize>k ? minSize : k; buff=new Array(k); copyInt_(buff,t); return buff; } //return the bigInt given a string representation in a given base. //Pad the array with leading zeros so that it has at least minSize elements. //If base=-1, then it reads in a space-separated list of array elements in decimal. //The array will always have at least one leading zero, unless base=-1. function str2bigInt(s,base,minSize) { var d, i, j, x, y, kk; var k=s.length; if (base==-1) { //comma-separated list of array elements in decimal x=new Array(0); for (;;) { y=new Array(x.length+1); for (i=0;i<x.length;i++) y[i+1]=x[i]; y[0]=parseInt(s,10); x=y; d=s.indexOf(',',0); if (d<1) break; s=s.substring(d+1); if (s.length==0) break; } if (x.length<minSize) { y=new Array(minSize); copy_(y,x); return y; } return x; } x=int2bigInt(0,base*k,0); for (i=0;i<k;i++) { d=digitsStr.indexOf(s.substring(i,i+1),0); if (base<=36 && d>=36) //convert lowercase to uppercase if base<=36 d-=26; if (d>=base || d<0) { //stop at first illegal character break; } multInt_(x,base); addInt_(x,d); } for (k=x.length;k>0 && !x[k-1];k--); //strip off leading zeros k=minSize>k+1 ? minSize : k+1; y=new Array(k); kk=k<x.length ? k : x.length; for (i=0;i<kk;i++) y[i]=x[i]; for (;i<k;i++) y[i]=0; return y; } //is bigint x equal to integer y? //y must have less than bpe bits function equalsInt(x,y) { var i; if (x[0]!=y) return 0; for (i=1;i<x.length;i++) if (x[i]) return 0; return 1; } //are bigints x and y equal? //this works even if x and y are different lengths and have arbitrarily many leading zeros function equals(x,y) { var i; var k=x.length<y.length ? x.length : y.length; for (i=0;i<k;i++) if (x[i]!=y[i]) return 0; if (x.length>y.length) { for (;i<x.length;i++) if (x[i]) return 0; } else { for (;i<y.length;i++) if (y[i]) return 0; } return 1; } //is the bigInt x equal to zero? function isZero(x) { var i; for (i=0;i<x.length;i++) if (x[i]) return 0; return 1; } //convert a bigInt into a string in a given base, from base 2 up to base 95. //Base -1 prints the contents of the array representing the number. function bigInt2str(x,base) { var i,t,s=""; if (s6.length!=x.length) s6=dup(x); else copy_(s6,x); if (base==-1) { //return the list of array contents for (i=x.length-1;i>0;i--) s+=x[i]+','; s+=x[0]; } else { //return it in the given base while (!isZero(s6)) { t=divInt_(s6,base); //t=s6 % base; s6=floor(s6/base); s=digitsStr.substring(t,t+1)+s; } } if (s.length==0) s="0"; return s; } //returns a duplicate of bigInt x function dup(x) { var i; buff=new Array(x.length); copy_(buff,x); return buff; } //do x=y on bigInts x and y. x must be an array at least as big as y (not counting the leading zeros in y). function copy_(x,y) { var i; var k=x.length<y.length ? x.length : y.length; for (i=0;i<k;i++) x[i]=y[i]; for (i=k;i<x.length;i++) x[i]=0; } //do x=y on bigInt x and integer y. function copyInt_(x,n) { var i,c; for (c=n,i=0;i<x.length;i++) { x[i]=c & mask; c>>=bpe; } } //do x=x+n where x is a bigInt and n is an integer. //x must be large enough to hold the result. function addInt_(x,n) { var i,k,c,b; x[0]+=n; k=x.length; c=0; for (i=0;i<k;i++) { c+=x[i]; b=0; if (c<0) { b=-(c>>bpe); c+=b*radix; } x[i]=c & mask; c=(c>>bpe)-b; if (!c) return; //stop carrying as soon as the carry is zero } } //right shift bigInt x by n bits. 0 <= n < bpe. function rightShift_(x,n) { var i; var k=Math.floor(n/bpe); if (k) { for (i=0;i<x.length-k;i++) //right shift x by k elements x[i]=x[i+k]; for (;i<x.length;i++) x[i]=0; n%=bpe; } for (i=0;i<x.length-1;i++) { x[i]=mask & ((x[i+1]<<(bpe-n)) | (x[i]>>n)); } x[i]>>=n; } //do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement function halve_(x) { var i; for (i=0;i<x.length-1;i++) { x[i]=mask & ((x[i+1]<<(bpe-1)) | (x[i]>>1)); } x[i]=(x[i]>>1) | (x[i] & (radix>>1)); //most significant bit stays the same } //left shift bigInt x by n bits. function leftShift_(x,n) { var i; var k=Math.floor(n/bpe); if (k) { for (i=x.length; i>=k; i--) //left shift x by k elements x[i]=x[i-k]; for (;i>=0;i--) x[i]=0; n%=bpe; } if (!n) return; for (i=x.length-1;i>0;i--) { x[i]=mask & ((x[i]<<n) | (x[i-1]>>(bpe-n))); } x[i]=mask & (x[i]<<n); } //do x=x*n where x is a bigInt and n is an integer. //x must be large enough to hold the result. function multInt_(x,n) { var i,k,c,b; if (!n) return; k=x.length; c=0; for (i=0;i<k;i++) { c+=x[i]*n; b=0; if (c<0) { b=-(c>>bpe); c+=b*radix; } x[i]=c & mask; c=(c>>bpe)-b; } } //do x=floor(x/n) for bigInt x and integer n, and return the remainder function divInt_(x,n) { var i,r=0,s; for (i=x.length-1;i>=0;i--) { s=r*radix+x[i]; x[i]=Math.floor(s/n); r=s%n; } return r; } //do the linear combination x=a*x+b*y for bigInts x and y, and integers a and b. //x must be large enough to hold the answer. function linComb_(x,y,a,b) { var i,c,k,kk; k=x.length<y.length ? x.length : y.length; kk=x.length; for (c=0,i=0;i<k;i++) { c+=a*x[i]+b*y[i]; x[i]=c & mask; c>>=bpe; } for (i=k;i<kk;i++) { c+=a*x[i]; x[i]=c & mask; c>>=bpe; } } //do the linear combination x=a*x+b*(y<<(ys*bpe)) for bigInts x and y, and integers a, b and ys. //x must be large enough to hold the answer. function linCombShift_(x,y,b,ys) { var i,c,k,kk; k=x.length<ys+y.length ? x.length : ys+y.length; kk=x.length; for (c=0,i=ys;i<k;i++) { c+=x[i]+b*y[i-ys]; x[i]=c & mask; c>>=bpe; } for (i=k;c && i<kk;i++) { c+=x[i]; x[i]=c & mask; c>>=bpe; } } //do x=x+(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys. //x must be large enough to hold the answer. function addShift_(x,y,ys) { var i,c,k,kk; k=x.length<ys+y.length ? x.length : ys+y.length; kk=x.length; for (c=0,i=ys;i<k;i++) { c+=x[i]+y[i-ys]; x[i]=c & mask; c>>=bpe; } for (i=k;c && i<kk;i++) { c+=x[i]; x[i]=c & mask; c>>=bpe; } } //do x=x-(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys. //x must be large enough to hold the answer. function subShift_(x,y,ys) { var i,c,k,kk; k=x.length<ys+y.length ? x.length : ys+y.length; kk=x.length; for (c=0,i=ys;i<k;i++) { c+=x[i]-y[i-ys]; x[i]=c & mask; c>>=bpe; } for (i=k;c && i<kk;i++) { c+=x[i]; x[i]=c & mask; c>>=bpe; } } //do x=x-y for bigInts x and y. //x must be large enough to hold the answer. //negative answers will be 2s complement function sub_(x,y) { var i,c,k,kk; k=x.length<y.length ? x.length : y.length; for (c=0,i=0;i<k;i++) { c+=x[i]-y[i]; x[i]=c & mask; c>>=bpe; } for (i=k;c && i<x.length;i++) { c+=x[i]; x[i]=c & mask; c>>=bpe; } } //do x=x+y for bigInts x and y. //x must be large enough to hold the answer. function add_(x,y) { var i,c,k,kk; k=x.length<y.length ? x.length : y.length; for (c=0,i=0;i<k;i++) { c+=x[i]+y[i]; x[i]=c & mask; c>>=bpe; } for (i=k;c && i<x.length;i++) { c+=x[i]; x[i]=c & mask; c>>=bpe; } } //do x=x*y for bigInts x and y. This is faster when y<x. function mult_(x,y) { var i; if (ss.length!=2*x.length) ss=new Array(2*x.length); copyInt_(ss,0); for (i=0;i<y.length;i++) if (y[i]) linCombShift_(ss,x,y[i],i); //ss=1*ss+y[i]*(x<<(i*bpe)) copy_(x,ss); } //do x=x mod n for bigInts x and n. function mod_(x,n) { if (s4.length!=x.length) s4=dup(x); else copy_(s4,x); if (s5.length!=x.length) s5=dup(x); divide_(s4,n,s5,x); //x = remainder of s4 / n } //do x=x*y mod n for bigInts x,y,n. //for greater speed, let y<x. function multMod_(x,y,n) { var i; if (s0.length!=2*x.length) s0=new Array(2*x.length); copyInt_(s0,0); for (i=0;i<y.length;i++) if (y[i]) linCombShift_(s0,x,y[i],i); //s0=1*s0+y[i]*(x<<(i*bpe)) mod_(s0,n); copy_(x,s0); } //do x=x*x mod n for bigInts x,n. function squareMod_(x,n) { var i,j,d,c,kx,kn,k; for (kx=x.length; kx>0 && !x[kx-1]; kx--); //ignore leading zeros in x k=kx>n.length ? 2*kx : 2*n.length; //k=# elements in the product, which is twice the elements in the larger of x and n if (s0.length!=k) s0=new Array(k); copyInt_(s0,0); for (i=0;i<kx;i++) { c=s0[2*i]+x[i]*x[i]; s0[2*i]=c & mask; c>>=bpe; for (j=i+1;j<kx;j++) { c=s0[i+j]+2*x[i]*x[j]+c; s0[i+j]=(c & mask); c>>=bpe; } s0[i+kx]=c; } mod_(s0,n); copy_(x,s0); } //return x with exactly k leading zero elements function trim(x,k) { var i,y; for (i=x.length; i>0 && !x[i-1]; i--); y=new Array(i+k); copy_(y,x); return y; } //do x=x**y mod n, where x,y,n are bigInts and ** is exponentiation. 0**0=1. //this is faster when n is odd. x usually needs to have as many elements as n. function powMod_(x,y,n) { var k1,k2,kn,np; if(s7.length!=n.length) s7=dup(n); //for even modulus, use a simple square-and-multiply algorithm, //rather than using the more complex Montgomery algorithm. if ((n[0]&1)==0) { copy_(s7,x); copyInt_(x,1); while(!equalsInt(y,0)) { if (y[0]&1) multMod_(x,s7,n); divInt_(y,2); squareMod_(s7,n); } return; } //calculate np from n for the Montgomery multiplications copyInt_(s7,0); for (kn=n.length;kn>0 && !n[kn-1];kn--); np=radix-inverseModInt(modInt(n,radix),radix); s7[kn]=1; multMod_(x ,s7,n); // x = x * 2**(kn*bp) mod n if (s3.length!=x.length) s3=dup(x); else copy_(s3,x); for (k1=y.length-1;k1>0 & !y[k1]; k1--); //k1=first nonzero element of y if (y[k1]==0) { //anything to the 0th power is 1 copyInt_(x,1); return; } for (k2=1<<(bpe-1);k2 && !(y[k1] & k2); k2>>=1); //k2=position of first 1 bit in y[k1] for (;;) { if (!(k2>>=1)) { //look at next bit of y k1--; if (k1<0) { mont_(x,one,n,np); return; } k2=1<<(bpe-1); } mont_(x,x,n,np); if (k2 & y[k1]) //if next bit is a 1 mont_(x,s3,n,np); } } //do x=x*y*Ri mod n for bigInts x,y,n, // where Ri = 2**(-kn*bpe) mod n, and kn is the // number of elements in the n array, not // counting leading zeros. //x array must have at least as many elemnts as the n array //It's OK if x and y are the same variable. //must have: // x,y < n // n is odd // np = -(n^(-1)) mod radix function mont_(x,y,n,np) { var i,j,c,ui,t,ks; var kn=n.length; var ky=y.length; if (sa.length!=kn) sa=new Array(kn); copyInt_(sa,0); for (;kn>0 && n[kn-1]==0;kn--); //ignore leading zeros of n for (;ky>0 && y[ky-1]==0;ky--); //ignore leading zeros of y ks=sa.length-1; //sa will never have more than this many nonzero elements. //the following loop consumes 95% of the runtime for randTruePrime_() and powMod_() for large numbers for (i=0; i<kn; i++) { t=sa[0]+x[i]*y[0]; ui=((t & mask) * np) & mask; //the inner "& mask" was needed on Safari (but not MSIE) at one time c=(t+ui*n[0]) >> bpe; t=x[i]; //do sa=(sa+x[i]*y+ui*n)/b where b=2**bpe. Loop is unrolled 5-fold for speed j=1; for (;j<ky-4;) { c+=sa[j]+ui*n[j]+t*y[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]+t*y[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]+t*y[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]+t*y[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]+t*y[j]; sa[j-1]=c & mask; c>>=bpe; j++; } for (;j<ky;) { c+=sa[j]+ui*n[j]+t*y[j]; sa[j-1]=c & mask; c>>=bpe; j++; } for (;j<kn-4;) { c+=sa[j]+ui*n[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]; sa[j-1]=c & mask; c>>=bpe; j++; c+=sa[j]+ui*n[j]; sa[j-1]=c & mask; c>>=bpe; j++; } for (;j<kn;) { c+=sa[j]+ui*n[j]; sa[j-1]=c & mask; c>>=bpe; j++; } for (;j<ks;) { c+=sa[j]; sa[j-1]=c & mask; c>>=bpe; j++; } sa[j-1]=c & mask; } if (!greater(n,sa)) sub_(sa,n); copy_(x,sa); } /*! Whirlpool Hashing Function v3.0 ~ Sean Catchpole - Copyright 2009 Public Domain */ /* Whirlpool was created by Paulo S.L.M. Barreto and Vincent Rijmen in 2000 This javascript implimentation of whirlpool could probably use a lot of impovement, please feel free to make it better in any way you can. Please note that javascript only supports 32bit bitwise operations so all the long(64) were converted into [int(32),int(32)] */ ;(function(){ var WP, R=10, C=[], rc=[], t, x, c, r, i, v1, v2, v4, v5, v8, v9, sbox= "\u1823\uc6E8\u87B8\u014F\u36A6\ud2F5\u796F\u9152"+ "\u60Bc\u9B8E\uA30c\u7B35\u1dE0\ud7c2\u2E4B\uFE57"+ "\u1577\u37E5\u9FF0\u4AdA\u58c9\u290A\uB1A0\u6B85"+ "\uBd5d\u10F4\ucB3E\u0567\uE427\u418B\uA77d\u95d8"+ "\uFBEE\u7c66\udd17\u479E\ucA2d\uBF07\uAd5A\u8333"+ "\u6302\uAA71\uc819\u49d9\uF2E3\u5B88\u9A26\u32B0"+ "\uE90F\ud580\uBEcd\u3448\uFF7A\u905F\u2068\u1AAE"+ "\uB454\u9322\u64F1\u7312\u4008\uc3Ec\udBA1\u8d3d"+ "\u9700\ucF2B\u7682\ud61B\uB5AF\u6A50\u45F3\u30EF"+ "\u3F55\uA2EA\u65BA\u2Fc0\udE1c\uFd4d\u9275\u068A"+ "\uB2E6\u0E1F\u62d4\uA896\uF9c5\u2559\u8472\u394c"+ "\u5E78\u388c\ud1A5\uE261\uB321\u9c1E\u43c7\uFc04"+ "\u5199\u6d0d\uFAdF\u7E24\u3BAB\ucE11\u8F4E\uB7EB"+ "\u3c81\u94F7\uB913\u2cd3\uE76E\uc403\u5644\u7FA9"+ "\u2ABB\uc153\udc0B\u9d6c\u3174\uF646\uAc89\u14E1"+ "\u163A\u6909\u70B6\ud0Ed\ucc42\u98A4\u285c\uF886"; for(t=8; t-->0;) C[t]=[]; for(x=0; x<256; x++) { c = sbox.charCodeAt(x/2); v1 = ((x & 1) == 0) ? c >>> 8 : c & 0xff; v2 = v1 << 1; if (v2 >= 0x100) v2 ^= 0x11d; v4 = v2 << 1; if (v4 >= 0x100) v4 ^= 0x11d; v5 = v4 ^ v1; v8 = v4 << 1; if (v8 >= 0x100) v8 ^= 0x11d; v9 = v8 ^ v1; // Build the circulant table C[0][x] = S[x].[1, 1, 4, 1, 8, 5, 2, 9]: C[0][x]=[0,0]; C[0][x][0] = (v1 << 24) | (v1 << 16) | (v4 << 8) | (v1); C[0][x][1] = (v8 << 24) | (v5 << 16) | (v2 << 8) | (v9); // Build the remaining circulant tables C[t][x] = C[0][x] rotr t for (var t=1; t<8; t++) { C[t][x]=[0,0]; C[t][x][0] = (C[t - 1][x][0] >>> 8) | ((C[t - 1][x][1] << 24)); C[t][x][1] = (C[t - 1][x][1] >>> 8) | ((C[t - 1][x][0] << 24)); } } // Build the round constants: rc[0] = [0,0]; for (r=1; r<=R; r++) { i = 8*(r - 1); rc[r]=[0,0]; rc[r][0] = (C[0][i ][0] & 0xff000000)^ (C[1][i + 1][0] & 0x00ff0000)^ (C[2][i + 2][0] & 0x0000ff00)^ (C[3][i + 3][0] & 0x000000ff); rc[r][1] = (C[4][i + 4][1] & 0xff000000)^ (C[5][i + 5][1] & 0x00ff0000)^ (C[6][i + 6][1] & 0x0000ff00)^ (C[7][i + 7][1] & 0x000000ff); } var bitLength=[], // [32] Global number of hashed bits (256-bit counter). buffer=[], // [64] Buffer of data to hash. bufferBits=0, // Current number of bits on the buffer. bufferPos=0, // Current (possibly incomplete) byte slot on the buffer. // The following longs are split into [int,int] hash=[], // [8] the hashing state K=[], // [8] the round key L=[], // [8] temp key? block=[], // [8] mu(buffer) state=[]; // [8] the chipher state // The core Whirlpool transform. var processBuffer = function(){ var i,j,r,s,t; // map the buffer to a block: for(i=0,j=0; i<8; i++,j+=8) { block[i]=[0,0]; block[i][0] = ((buffer[j ] & 0xff) << 24)^ ((buffer[j + 1] & 0xff) << 16)^ ((buffer[j + 2] & 0xff) << 8)^ ((buffer[j + 3] & 0xff) ); block[i][1] = ((buffer[j + 4] & 0xff) << 24)^ ((buffer[j + 5] & 0xff) << 16)^ ((buffer[j + 6] & 0xff) << 8)^ ((buffer[j + 7] & 0xff) ); } // compute and apply K^0 to the cipher state: for (i=0; i<8; i++) { state[i]=[0,0]; K[i]=[0,0]; state[i][0] = block[i][0] ^ (K[i][0] = hash[i][0]); state[i][1] = block[i][1] ^ (K[i][1] = hash[i][1]); } // iterate over all rounds: for (r=1; r<=R; r++) { // compute K^r from K^{r-1}: for (i=0; i<8; i++) { L[i]=[0,0]; for (t=0,s=56,j=0; t<8; t++,s-=8,j=s<32?1:0) { L[i][0] ^= C[t][(K[(i - t) & 7][j] >>> (s%32)) & 0xff][0]; L[i][1] ^= C[t][(K[(i - t) & 7][j] >>> (s%32)) & 0xff][1]; } } for (i=0; i<8; i++) { K[i][0] = L[i][0]; K[i][1] = L[i][1]; } K[0][0] ^= rc[r][0]; K[0][1] ^= rc[r][1]; // apply the r-th round transformation: for (i=0; i<8; i++) { L[i][0] = K[i][0]; L[i][1] = K[i][1]; for (t=0,s=56,j=0; t<8; t++,s-=8,j=s<32?1:0) { L[i][0] ^= C[t][(state[(i - t) & 7][j] >>> (s%32)) & 0xff][0]; L[i][1] ^= C[t][(state[(i - t) & 7][j] >>> (s%32)) & 0xff][1]; } } for (i=0; i<8; i++) { state[i][0] = L[i][0]; state[i][1] = L[i][1]; } } // apply the Miyaguchi-Preneel compression function: for (i=0; i<8; i++) { hash[i][0] ^= state[i][0] ^ block[i][0]; hash[i][1] ^= state[i][1] ^ block[i][1]; } }; WP = Whirlpool = function(str){ return WP.init().add(str).finalize(); }; WP.version = "3.0"; // Initialize the hashing state. WP.init = function(){ for(var i=32; i-->0;) bitLength[i]=0; bufferBits = bufferPos = 0; buffer = [0]; // it's only necessary to cleanup buffer[bufferPos]. for(i=8; i-->0;) hash[i]=[0,0]; return WP; }; // Convert string into byte array var convert = function(source){ var i,n,str=source.toString(); source=[]; for(i=0; i<str.length; i++) { n = str.charCodeAt(i); if(n>=256) source.push(n>>>8 & 0xFF); source.push(n & 0xFF); } return source; }; // Delivers input data to the hashing algorithm. Assumes bufferBits < 512 WP.add = function(source,sourceBits){ /* sourcePos | +-------+-------+------- ||||||||||||||||||||| source +-------+-------+------- +-------+-------+-------+-------+-------+------- |||||||||||||||||||||| buffer +-------+-------+-------+-------+-------+------- | bufferPos */ if(!source) return WP; if(!sourceBits) { source = convert(source); sourceBits = source.length*8; } var sourcePos = 0, // index of leftmost source byte containing data (1 to 8 bits). sourceGap = (8 - (sourceBits & 7)) & 7, // space on source[sourcePos]. bufferRem = bufferBits & 7, // occupied bits on buffer[bufferPos]. i, b, carry, value = sourceBits; for (i=31, carry=0; i>=0; i--) { // tally the length of the added data carry += (bitLength[i] & 0xff) + (value % 256); bitLength[i] = carry & 0xff; carry >>>= 8; value = Math.floor(value/256); } // process data in chunks of 8 bits: while (sourceBits > 8) { // at least source[sourcePos] and source[sourcePos+1] contain data. // take a byte from the source: b = ((source[sourcePos] << sourceGap) & 0xff) | ((source[sourcePos + 1] & 0xff) >>> (8 - sourceGap)); if (b < 0 || b >= 256) return "Whirlpool requires a byte array"; // process this byte: buffer[bufferPos++] |= b >>> bufferRem; bufferBits += 8 - bufferRem; // bufferBits = 8*bufferPos; if (bufferBits == 512) { processBuffer(); // process data block bufferBits = bufferPos = 0; buffer=[]; // reset buffer } buffer[bufferPos] = ((b << (8 - bufferRem)) & 0xff); bufferBits += bufferRem; // proceed to remaining data sourceBits -= 8; sourcePos++; } // now 0 <= sourceBits <= 8; // furthermore, all data (if any is left) is in source[sourcePos]. if (sourceBits > 0) { b = (source[sourcePos] << sourceGap) & 0xff; // bits are left-justified on b. buffer[bufferPos] |= b >>> bufferRem; // process the remaining bits } else { b = 0; } if (bufferRem + sourceBits < 8) { // all remaining data fits on buffer[bufferPos], and there still remains some space. bufferBits += sourceBits; } else { bufferPos++; // buffer[bufferPos] is full bufferBits += 8 - bufferRem; // bufferBits = 8*bufferPos; sourceBits -= 8 - bufferRem; // now 0 <= sourceBits < 8; furthermore, all data is in source[sourcePos]. if (bufferBits == 512) { processBuffer(); // process data block bufferBits = bufferPos = 0; buffer=[]; // reset buffer } buffer[bufferPos] = ((b << (8 - bufferRem)) & 0xff); bufferBits += sourceBits; } return WP; }; // Get the hash value from the hashing state. Assumes bufferBits < 512 WP.finalize = function(){ var i,j,h, str="", digest=[], hex="0123456789ABCDEF".split(''); buffer[bufferPos] |= 0x80 >>> (bufferBits & 7); // append a '1'-bit: bufferPos++; // all remaining bits on the current byte are set to zero. if(bufferPos > 32) { // pad with zero bits to complete 512N + 256 bits: while (bufferPos < 64) buffer[bufferPos++] = 0; processBuffer(); // process data block bufferPos = 0; buffer=[]; // reset buffer } while(bufferPos < 32) buffer[bufferPos++] = 0; buffer.push.apply(buffer,bitLength); // append bit length of hashed data processBuffer(); // process data block for(i=0,j=0; i<8; i++,j+=8) { // return the completed message digest h = hash[i][0]; digest[j ] = h >>> 24 & 0xFF; digest[j + 1] = h >>> 16 & 0xFF; digest[j + 2] = h >>> 8 & 0xFF; digest[j + 3] = h & 0xFF; h = hash[i][1]; digest[j + 4] = h >>> 24 & 0xFF; digest[j + 5] = h >>> 16 & 0xFF; digest[j + 6] = h >>> 8 & 0xFF; digest[j + 7] = h & 0xFF; } for(i=0; i<digest.length; i++) { str+=hex[digest[i] >>> 4]; str+=hex[digest[i] & 0xF]; } return str; }; })(); // elliptic.js from cryptocat: // https://github.com/kaepora/cryptocat/blob/master/src/common/js/elliptic.js // License is AGPL. // curve25519 // In order to generate a public value: // priv = randBigInt(256) // pub = scalarMult(priv, basePoint) // // In order to perform key agreement: // shared = scalarMult(myPrivate, theirPublic) /* Here's a test: this should print the same thing twice. var priv1 = randBigInt(256, 0) var priv2 = randBigInt(256, 0) var pub1 = scalarMult(priv1, basePoint) var pub2 = scalarMult(priv2, basePoint) print (scalarMult(priv1, pub2)) print (scalarMult(priv2, pub1)) */ // p22519 is the curve25519 prime: 2^255 - 19 var p25519 = str2bigInt("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", 16); // p25519Minus2 = 2^255 - 21 var p25519Minus2 = str2bigInt("7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffeb", 16); // a is a parameter of the elliptic curve var a = str2bigInt("486662", 10); // basePoint is the generator of the elliptic curve group var basePoint = str2bigInt("9", 10); // These variables are names for small, bigint constants. var eight = str2bigInt("8", 10); var four = str2bigInt("4", 10); var three = str2bigInt("3", 10); var two = str2bigInt("2", 10); // groupAdd adds two elements of the elliptic curve group in Montgomery form. function groupAdd(x1, xn, zn, xm, zm) { // x₃ = 4(x·x′ - z·z′)² · z1 var xx = multMod(xn, xm, p25519); var zz = multMod(zn, zm, p25519); var d; if (greater(xx, zz)) { d = sub(xx, zz); } else { d = sub(zz, xx); } var sq = multMod(d, d, p25519); var outx = multMod(sq, four, p25519); // z₃ = 4(x·z′ - z·x′)² · x1 var xz = multMod(xm, zn, p25519); var zx = multMod(zm, xn, p25519); var d; if (greater(xz, zx)) { d = sub(xz, zx); } else { d = sub(zx, xz); } var sq = multMod(d, d, p25519); var sq2 = multMod(sq, x1, p25519); var outz = multMod(sq2, four, p25519); return [outx, outz]; } // groupDouble doubles a point in the elliptic curve group. function groupDouble(x, z) { // x₂ = (x² - z²)² var xx = multMod(x, x, p25519); var zz = multMod(z, z, p25519); var d; if (greater(xx, zz)) { d = sub(xx, zz); } else { d = sub(zz, xx); } var outx = multMod(d, d, p25519); // z₂ = 4xz·(x² + Axz + z²) var s = add(xx, zz); var xz = multMod(x, z, p25519); var axz = mult(xz, a); s = add(s, axz); var fourxz = mult(xz, four); var outz = multMod(fourxz, s, p25519); return [outx, outz]; } // scalarMult calculates i*base in the elliptic curve. function scalarMult(i, base) { var scalar = expand(i, 18); scalar[0] &= (248 | 0x7f00); scalar[17] = 0; scalar[16] |= 0x4000; var x1 = str2bigInt("1", 10); var z1 = str2bigInt("0", 10); var x2 = base; var z2 = str2bigInt("1", 10); for (i = 17; i >= 0; i--) { var j = 14; if (i == 17) { j = 0; } for (; j >= 0; j--) { if (scalar[i]&0x4000) { var point = groupAdd(base, x1, z1, x2, z2); x1 = point[0]; z1 = point[1]; point = groupDouble(x2, z2); x2 = point[0]; z2 = point[1]; } else { var point = groupAdd(base, x1, z1, x2, z2); x2 = point[0]; z2 = point[1]; point = groupDouble(x1, z1); x1 = point[0]; z1 = point[1]; } scalar[i] <<= 1; } } var z1inv = powMod(z1, p25519Minus2, p25519); var x = multMod(z1inv, x1, p25519); return x; } // P256 // var priv = randBigInt(256) // var pub = scalarMultP256(p256Gx, p256Gy, priv) // var message = str2bigInt("2349623424239482634", 10) // var signature = ecdsaSign(priv, message) // print (ecdsaVerify(pub, signature, message)) // p256 is the p256 prime var p256 = str2bigInt("115792089210356248762697446949407573530086143415290314195533631308867097853951", 10); // n256 is the number of points in the group var n256 = str2bigInt("115792089210356248762697446949407573529996955224135760342422259061068512044369", 10); // b256 is a parameter of the curve var b256 = str2bigInt("5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16); // p256Gx and p256Gy is the generator of the group var p256Gx = str2bigInt("6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", 16); var p256Gy = str2bigInt("4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", 16); function privateKeyToString(p){ return bigInt2str(p, 64); } function privateKeyFromString(s){ return str2bigInt(s, 64); } function sigToString(p){ return JSON.stringify([bigInt2str(p[0], 64), bigInt2str(p[1], 64)]); } function sigFromString(s){ p = JSON.parse(s); p[0] = str2bigInt(p[0], 64); p[1] = str2bigInt(p[1], 64); return p; } function publicKeyToString(p){ return JSON.stringify([bigInt2str(p[0], 64), bigInt2str(p[1], 64)]); } function publicKeyFromString(s){ p = JSON.parse(s); p[0] = str2bigInt(p[0], 64); p[1] = str2bigInt(p[1], 64); return p; } function ecdsaGenPrivateKey(){ return privateKeyToString(randBigInt(256)); } function ecdsaGenPublicKey(privateKey){ return publicKeyToString(scalarMultP256(p256Gx, p256Gy, privateKeyFromString(privateKey))); } // isOnCurve returns true if the given point is on the curve. function isOnCurve(x, y) { // y² = x³ - 3x + b var yy = multMod(y, y, p); var xxx = multMod(x, mult(x, x), p); var threex = multMod(three, x, p); var s = add(xxx, b256); if (greater(threex, s)) { return false; } s = sub(s, threex); return equals(s, yy); } // subMod returns a-b mod m function subMod(a, b, m) { if (greater(a, b)) { return mod(sub(a, b), m); } tmp = mod(sub(b, a), m); return sub(m, tmp); } // addJacobian adds two elliptic curve points in Jacobian form. function addJacobian(x1, y1, z1, x2, y2, z2) { var z1z1 = multMod(z1, z1, p256); var z2z2 = multMod(z2, z2, p256); var u1 = multMod(x1, z2z2, p256); var u2 = multMod(x2, z1z1, p256); var s1 = multMod(y1, multMod(z2, z2z2, p256), p256); var s2 = multMod(y2, multMod(z1, z1z1, p256), p256); var h = subMod(u2, u1, p256); var i = mult(h, two); i = multMod(i, i, p256); j = multMod(h, i, p256) var r = subMod(s2, s1, p256); r = mult(r, two); var v = multMod(u1, i, p256); var x3 = mult(r, r); x3 = subMod(x3, j, p256); var twoV = mult(v, two); x3 = subMod(x3, twoV, p256); var tmp = subMod(v, x3, p256); tmp = mult(r, tmp); var y3 = mult(s1, j); y3 = mult(y3, two); y3 = subMod(tmp, y3, p256); var tmp = add(z1, z2); tmp = multMod(tmp, tmp, p256); tmp = subMod(tmp, z1z1, p256); tmp = subMod(tmp, z2z2, p256); var z3 = multMod(tmp, h, p256); return [x3, y3, z3]; } // doubleJacobian doubles an elliptic curve point in Jacobian form. function doubleJacobian(x, y, z) { var delta = multMod(z, z, p256); var gamma = multMod(y, y, p256); var beta = multMod(x, gamma, p256); var alpha = mult(three, mult(subMod(x, delta, p256), add(x, delta))); var x3 = subMod(multMod(alpha, alpha, p256), mult(eight, beta), p256); var tmp = add(y, z); tmp = mult(tmp, tmp); var z3 = subMod(subMod(tmp, gamma, p256), delta, p256); tmp = mult(eight, mult(gamma, gamma)); var y3 = subMod(multMod(alpha, subMod(mult(four, beta), x3, p256), p256), tmp, p256); return [x3, y3, z3]; } // affineFromJacobian returns the affine point corresponding to the given // Jacobian point. function affineFromJacobian(x, y, z) { var zinv = inverseMod(z, p256); var zinvsq = multMod(zinv, zinv, p256); var outx = multMod(x, zinvsq, p256); var zinv3 = multMod(zinvsq, zinv, p256); var outy = multMod(y, zinv3, p256); return [outx, outy]; } // scalarMultP256 returns in_k*(bx,by) function scalarMultP256(bx, by, in_k) { var bz = [1, 0]; var k = dup(in_k); // The Jacobian functions don't work with the point at infinity so we // start with 1, not zero. var x = bx; var y = by; var z = bz; var seenFirstTrue = false; for (var i = k.length-1; i >= 0; i--) { for (var j = 14; j >= 0; j--) { if (seenFirstTrue) { var point = doubleJacobian(x, y, z); x = point[0]; y = point[1]; z = point[2]; } if (k[i]&0x4000) { if (!seenFirstTrue) { seenFirstTrue = true; } else { var point = addJacobian(bx, by, bz, x, y, z); x = point[0]; y = point[1]; z = point[2]; } } k[i] <<= 1; } } if (!seenFirstTrue) { return [[0], [0]]; } return affineFromJacobian(x, y, z); } // ecdsaSign returns a signature of message as an array [r,s]. message is a // bigint, however it should be generated by hashing the true message and // converting it to bigint. Note: if attempting to interoperate you should be // careful because the NSA and SECG documents differ on how the conversion to // an interger occurs. SECG says that you should truncate to the big-length of // the curve first and that's what OpenSSL does. function ecdsaSign(privateKey, message) { var r; var s; priv = privateKeyFromString(privateKey); m = mod(Whirlpool(JSON.stringify(message)).substring(0,32), n256); while (true) { var k; while (true) { k = randBigInt(256); var point = scalarMultP256(p256Gx, p256Gy, k); var r = point[0]; r = mod(r, n256); if (!isZero(r)) { break; } } var s = multMod(priv, r, n256); s = add(s, m); kinv = inverseMod(k, n256); s = multMod(s, kinv, n256); if (!isZero(s)) { break; } } return sigToString([r,s]); } // ecdsaVerify returns true iff signature is a valid ECDSA signature for // message. See the comment above ecdsaSign about converting a message into the // bigint |message|. function ecdsaVerify(publicKey, signature, message) { pub = publicKeyFromString(publicKey); sig = sigFromString(signature); m = mod(Whirlpool(JSON.stringify(message)).substring(0,32), n256); var r = sig[0] var s = sig[1] if (isZero(r) || isZero(s)) { return false; } if (greater(r, n256) || greater(s, n256)) { return false; } var w = inverseMod(s, n256); var u1 = multMod(m, w, n256); var u2 = multMod(r, w, n256); var point1 = scalarMultP256(p256Gx, p256Gy, u1); var point2 = scalarMultP256(pub[0], pub[1], u2); if (equals(point1[0], point2[0])) { return false; } var one = [1, 0]; var point3 = addJacobian(point1[0], point1[1], one, point2[0], point2[1], one); var point4 = affineFromJacobian(point3[0], point3[1], point3[2]); mod(point3, n256); return equals(point4[0], r); } function ecDH(priv, pub) { if (typeof pub === "undefined") { return scalarMult(priv, basePoint); } else { return bigInt2str(scalarMult(priv, pub), 64); } } })(); </script>