KevBurnsJr

Asynchronous RSA key generation in Javascript

Posted November 25, 2011

Source on GitHub – https://github.com/KevBurnsJr/rsasync
–

Generating RSA keys is a characteristically CPU intensive operation. This presents problems when operating on weak devices (such as the iPhone 3G) in environments under strict computation restrictions (such as safari mobile’s 10 second javascript execution timeout).

What is needed is an RSA key generation library that operates asynchronously in order to chug through the 2+ minutes of computation time required to generate a 512 RSA key on a weak device without bumping against the computation restrictions enforced by the safari mobile execution environment.

Some nearly suitable libraries do exist, but all of them fall short in some fashion.

Probably the closest is this asynchronous keygen from Atsushi Oka
http://ats.oka.nu/titaniumcore/js/crypto/readme.txt
However, the interface for Ats Oka’s library is not simple and the architecture of the code leaves something to be desired.
Cryptico is another library featuring RSA key generation which is also touted as a sort of all-in-one solution
http://code.google.com/p/cryptico/
However, this library really just glues together a bunch of already-available libraries and packages them as a unit.
jsbn is the underlying RSA key generator packaged with Cryptico and is available on its own
http://www-cs-students.stanford.edu/~tjw/jsbn/
This library has a fairly simple interface and is relatively fast and compact meeting most of my requirements.
However, this library doesn’t do asynchronous key generation.

But we can fix that.

jsbn RSA keygen times out after 11 seconds on the iPhone 3G for even a 256 bit key but with a little fenangling and a lot of setTimeouts, we can get it to handle a key of virtually any size for which the user has the patience to wait.

Here’s an example of the new async interface:

key = new RSAKey();
key.generateAsync(512, "03", function(){
    var pubKey = hex2b64(key.n.toString(16));
    alert(pubKey);
});

This was a great exercise in how to turn synchronous javascript into asynchronous javascript. Taking procedural code and breaking those for loops into recursive functions was a mind bender but once I figured out how it generally ought to work, each function became easier to port.

Originally I did it all inline, but later I ripped it all out into a separate file which extends Tom Wu’s jsbn.

// Copyright (c) 2011  Kevin M Burns Jr.
// All Rights Reserved.
// See "LICENSE" for details.
//
// Extension to jsbn which adds facilities for asynchronous RSA key generation
// Primarily created to avoid execution timeout on mobile devices
//
// http://www-cs-students.stanford.edu/~tjw/jsbn/
//
// ---
 
(function(){
 
// Generate a new random private key B bits long, using public expt E
var RSAGenerateAsync = function (B, E, callback) {
    //var rng = new SeededRandom();
    var rng = new SecureRandom();
    var qs = B >> 1;
    this.e = parseInt(E, 16);
    var ee = new BigInteger(E, 16);
    var rsa = this;
    // These functions have non-descript names because they were originally for(;;) loops.
    // I don't know about cryptography to give them better names than loop1-4.
    var loop1 = function() {
        var loop4 = function() {
            if (rsa.p.compareTo(rsa.q) <= 0) {
                var t = rsa.p;
                rsa.p = rsa.q;
                rsa.q = t;
            }
            var p1 = rsa.p.subtract(BigInteger.ONE);
            var q1 = rsa.q.subtract(BigInteger.ONE);
            var phi = p1.multiply(q1);
            if (phi.gcd(ee).compareTo(BigInteger.ONE) == 0) {
                rsa.n = rsa.p.multiply(rsa.q);
                rsa.d = ee.modInverse(phi);
                rsa.dmp1 = rsa.d.mod(p1);
                rsa.dmq1 = rsa.d.mod(q1);
                rsa.coeff = rsa.q.modInverse(rsa.p);
                setTimeout(function(){callback()},0); // escape
            } else {
                setTimeout(loop1,0);
            }
        };
        var loop3 = function() {
            rsa.q = nbi();
            rsa.q.fromNumberAsync(qs, 1, rng, function(){
                rsa.q.subtract(BigInteger.ONE).gcda(ee, function(r){
                    if (r.compareTo(BigInteger.ONE) == 0 && rsa.q.isProbablePrime(10)) {
                        setTimeout(loop4,0);
                    } else {
                        setTimeout(loop3,0);
                    }
                });
            });
        };
        var loop2 = function() {
            rsa.p = nbi();
            rsa.p.fromNumberAsync(B - qs, 1, rng, function(){
                rsa.p.subtract(BigInteger.ONE).gcda(ee, function(r){
                    if (r.compareTo(BigInteger.ONE) == 0 && rsa.p.isProbablePrime(10)) {
                        setTimeout(loop3,0);
                    } else {
                        setTimeout(loop2,0);
                    }
                });
            });
        };
        setTimeout(loop2,0);
    };
    setTimeout(loop1,0);
};
RSAKey.prototype.generateAsync = RSAGenerateAsync;
 
// Public API method
var bnGCDAsync = function (a, callback) {
    var x = (this.s < 0) ? this.negate() : this.clone();
    var y = (a.s < 0) ? a.negate() : a.clone();
    if (x.compareTo(y) < 0) {
        var t = x;
        x = y;
        y = t;
    }
    var i = x.getLowestSetBit(),
        g = y.getLowestSetBit();
    if (g < 0) {
        callback(x);
        return;
    }
    if (i < g) g = i;
    if (g > 0) {
        x.rShiftTo(g, x);
        y.rShiftTo(g, y);
    }
    // Workhorse of the algorithm, gets called 200 - 800 times per 512 bit keygen.
    var gcda1 = function() {
        if ((i = x.getLowestSetBit()) > 0){ x.rShiftTo(i, x); }
        if ((i = y.getLowestSetBit()) > 0){ y.rShiftTo(i, y); }
        if (x.compareTo(y) >= 0) {
            x.subTo(y, x);
            x.rShiftTo(1, x);
        } else {
            y.subTo(x, y);
            y.rShiftTo(1, y);
        }
        if(!(x.signum() > 0)) {
            if (g > 0) y.lShiftTo(g, y);
            setTimeout(function(){callback(y)},0); // escape
        } else {
            setTimeout(gcda1,0);
        }
    };
    setTimeout(gcda1,10);
};
BigInteger.prototype.gcda = bnGCDAsync;
 
// (protected) alternate constructor
var bnpFromNumberAsync = function (a,b,c,callback) {
  if("number" == typeof b) {
    if(a < 2) {
        this.fromInt(1);
    } else {
      this.fromNumber(a,c);
      if(!this.testBit(a-1)){
        this.bitwiseTo(BigInteger.ONE.shiftLeft(a-1),op_or,this);
      }
      if(this.isEven()) {
        this.dAddOffset(1,0);
      }
      var bnp = this;
      var bnpfn1 = function(){
        bnp.dAddOffset(2,0);
        if(bnp.bitLength() > a) bnp.subTo(BigInteger.ONE.shiftLeft(a-1),bnp);
        if(bnp.isProbablePrime(b)) {
            setTimeout(function(){callback()},0); // escape
        } else {
            setTimeout(bnpfn1,0);
        }
      };
      setTimeout(bnpfn1,0);
    }
  } else {
    var x = new Array(), t = a&7;
    x.length = (a>>3)+1;
    b.nextBytes(x);
    if(t > 0) x[0] &= ((1<<t)-1); else x[0] = 0;
    this.fromString(x,256);
  }
};
BigInteger.prototype.fromNumberAsync = bnpFromNumberAsync;
 
})();

I’m also adding a few functions for sleeping a public or private RSA key object to a simple JSON Transport Object (for storage) and waking it again.

(function(){
 
// Cast to private Transport Object
var RSAPrivTPO = function () {
    return {
        'n'     : hex2b64(this.n.toString(16)),
        'e'     : hex2b64(this.e.toString(16)),
        'd'     : hex2b64(this.d.toString(16)),
        'p'     : hex2b64(this.p.toString(16)),
        'q'     : hex2b64(this.q.toString(16)),
        'dmp1'  : hex2b64(this.dmp1.toString(16)),
        'dmq1'  : hex2b64(this.dmq1.toString(16)),
        'coeff' : hex2b64(this.coeff.toString(16))
    }
}
RSAKey.prototype.privTPO = RSAPrivTPO;
 
// Hydrate from private Transport Object
var RSAFromPrivTPO = function (tpo) {
    this.setPrivateEx(
        b64tohex(tpo.n), 
        b64tohex(tpo.e), 
        b64tohex(tpo.d), 
        b64tohex(tpo.p), 
        b64tohex(tpo.q), 
        b64tohex(tpo.dmp1), 
        b64tohex(tpo.dmq1), 
        b64tohex(tpo.coeff)
    );
    return this;
};
RSAKey.prototype.fromPrivTPO = RSAFromPrivTPO;
 
// Cast to public Transport Object
var RSAPubTPO = function () {
    return {
        'n' : hex2b64(this.n.toString(16)),
        'e' : hex2b64(this.e.toString(16))
    }
};
RSAKey.prototype.pubTPO = RSAPubTPO;
 
// Hydrate from public Transport Object
var RSAFromPubTPO = function (tpo) {
    this.setPublic(
        b64tohex(tpo.n), 
        b64tohex(tpo.e)
    );
    return this;
};
RSAKey.prototype.fromPubTPO = RSAFromPubTPO;
 
})();

Source on GitHub – https://github.com/KevBurnsJr/rsasync

8 Comments so far

james on March 5th, 2012

Hey – did you know you don’t have any way to contact you on your website? No email – nothing. This is all i found.

I saw this page (i’m implementing RSA in the browser as well) and wanted to say thank you – this place will have to do. This post – but more importantly the bit about storing keys as json – was really illuminating! being new to the subject at the time, the ability to store keys as anything other then pkcs1 (or another padding scheme) seemed completely skipped over. Like no one even considered storing a key anywhere other then the browser! I don’t get it, but i did get this, and, I thank you, kind sir.
Eden Ridgway on August 3rd, 2012

Thank you very much for doing this and sharing it. I see you have reserved all rights to the code, but you refer to a “LICENSE” for details. Unfortunately I couldn’t find any license on Github. What are your license terms for this code?

Thanks again!
KevBurnsJr on August 3rd, 2012

Here is the license:

Go nuts bro.
Eden Ridgway on August 7th, 2012

Hahaha.. Awesome! Thanks.
Manik on December 14th, 2012

A full demo would be excellent. Trying to use your library with jsbn but getting Uncaught TypeError: Object # has no method ‘fromNumber’ rsasync.js:123
Can you find why this comes?
ronbravo on December 29th, 2012

@Manik. I had the same problem as you where I was getting

“TypeError: this.fromNumber is not a function
this.fromNumber(a,c);

rsasync.js (line 123)”

It seems like you have to look at the jsbn.js file that comes with the jsbn library. After comparing that file with the jsbn.js that came with Ziyan Zhou modified library, one can see there are some function missing from jsbn.js.

What I did to fix the error was just copy the contents from Ziyan Zhou’s jsbn.js file into the jsbn.js I got from the standford site. Then everything worked like a charm. Give that a shot and I hope that helps. Here is a link to Zhou’s blog post referencing the library:

Ziyan Zhou: http://www.ziyan.net/2008/10/javascript-rsa.html

@ Mr. Kev Burns Jr, thank you very much for your work in this as it solved an issue I was having. I also saved this page since there is no license document in the github, so I just use this page as reference to your permission for use. Thank you again and I hope your trip to jungles of Brazil was fun. Take care and C ya.
dlongley on May 9th, 2013

Just a heads up that something similar to this was part of a WebID demo written back in 2010. That code has since evolved a JS crypto library and TLS implementation called Forge. Here’s a link to the rsa module and function that does key generation:

https://github.com/digitalbazaar/forge/blob/master/js/rsa.js#L652
KevBurnsJr on May 10th, 2013

You’re right, that is quite similar.

Interesting that it also has support for web workers.

I will check it out

Asynchronous RSA key generation in Javascript

8 Comments so far

Leave a reply