Generate a random big prime number with forge (or

I need to generate a random big (around 4096 bit) prime number in JavaScript and I'm already using forge. Forge has to have some kind of generator for such tasks as it implements RSA which also relies on random prime numbers. However I haven't found something in the documentation of forge when you just want to get a random prime number (something like var myRandomPrime = forge.random.getPrime(4096); would have been great).

So what would be the best approach to get such a prime (with or without forge) in JavaScript?

回答1:

Update 06/11/2014: Now, with forge version 0.6.6 you can use this:

var bits = 1024;
forge.prime.generateProbablePrime(bits, function(err, num) {
    console.log('random prime', num.toString(16));
});

Finding large primes in JavaScript is difficult -- it's slow and you don't want to block the main thread. It requires some fairly customized code to do right and the code in forge is specialized for RSA key generation. There's no API call to simply produce a large random prime.

There are some extra operations that the RSA code in forge runs that you don't need if you're just looking for a single prime number. That being said, the slowest part of the process is in actually finding the primes, not in those extra operations. However, the RSA code also generates two primes (when you only need one) and they aren't the same bitsize you're looking for. So if you're using the forge API you'd have to pass a bitsize of 8196 (I believe ... that's off the top of my head, so it may be inaccurate) to get a 4096-bit prime.

One way to find a large random prime is as follows:

Generate a random number that has the desired number of bits (ensure the MSB is set).
Align the number on a 30k+1 boundary as all primes have this property.
Run a primality test (the slow part) on your number; if it passes, you're done, if not, add to the number to get to the next 30k+1 boundary and repeat. A "quick" primality test is to check against low primes and then use Miller-Rabin (see the Handbook of Applied Cryptography 4.24).

Step #3 can run for a long time -- and that's usually pretty undesirable with JavaScript (w/node or in the browser). To mitigate this, you can attempt to limit the amount time spent doing primality tests to some acceptable period of time (N milliseconds) or you can use Web Workers to background the process. Of course, both of these approaches complicate the code.

Here's some code for generating a 4096-bit random prime that shouldn't block the main thread:

var forge = require('node-forge');
var BigInteger = forge.jsbn.BigInteger;

// primes are 30k+i for i = 1, 7, 11, 13, 17, 19, 23, 29
var GCD_30_DELTA = [6, 4, 2, 4, 2, 4, 6, 2];
var THIRTY = new BigInteger(null);
THIRTY.fromInt(30);

// generate random BigInteger
var num = generateRandom(4096);

// find prime nearest to random number
findPrime(num, function(num) {
  console.log('random', num.toString(16));
});

function generateRandom(bits) {
  var rng = {
    // x is an array to fill with bytes
    nextBytes: function(x) {
      var b = forge.random.getBytes(x.length);
      for(var i = 0; i < x.length; ++i) {
        x[i] = b.charCodeAt(i);
      }
    }
  };
  var num = new BigInteger(bits, rng);

  // force MSB set
  var bits1 = bits - 1;
  if(!num.testBit(bits1)) {
    var op_or = function(x,y) {return x|y;};
    num.bitwiseTo(BigInteger.ONE.shiftLeft(bits1), op_or, num);
  }

  // align number on 30k+1 boundary
  num.dAddOffset(31 - num.mod(THIRTY).byteValue(), 0);

  return num;
}

function findPrime(num, callback) {
  /* Note: All primes are of the form 30k+i for i < 30 and gcd(30, i)=1. The
  number we are given is always aligned at 30k + 1. Each time the number is
  determined not to be prime we add to get to the next 'i', eg: if the number
  was at 30k + 1 we add 6. */
  var deltaIdx = 0;

  // find prime nearest to 'num' for 100ms
  var start = Date.now();
  while(Date.now() - start < 100) {
    // do primality test (only 2 iterations assumes at
    // least 1251 bits for num)
    if(num.isProbablePrime(2)) {
      return callback(num);
    }
    // get next potential prime
    num.dAddOffset(GCD_30_DELTA[deltaIdx++ % 8], 0);
  }

  // keep trying (setImmediate would be better here)
  setTimeout(function() {
    findPrime(num, callback);
  });
}

Various tweaks can be made to adjust it for your needs, like setting the amount of time (which is just an estimate) to run the primality tester before bailing to try again on the next scheduled tick. You'd probably want some kind of UI feedback each time it bails. If you're using node or a browser that supports setImmediate you can use that instead of setTimeout as well to avoid clamping to speed things up. But, note that it's going to take a while to generate a 4096-bit random prime in JavaScript (at least at the time of this writing).

Forge also has a Web Worker implementation for generating RSA keys that is intended to speed up the process by letting multiple threads run the primality test using different inputs. You can look at the forge source (prime.worker.js for instance) to see that in action, but it's a project in itself to get working properly. IMO, though, it's the best way to speed things up.

Anyway, hopefully the above code will help you. I'd run it with a smaller bitsize to test it.

回答2:

It does more work then you specifically require but you can always use forge to generate a key pair and extract one of the primes from that.

//generate a key pair of required size
var keyPair = forge.pki.rsa.generateKeyPair(4096);

//at this point we have 2 primes p and q in the privateKey
var p = keyPair.privateKey.p;
var q = keyPair.privateKey.q;

The type of p and q are BigInteger they have a p.toByteArray() method to access their representations as a byte array.

回答3:

If you decide to implement your own method, you may want to read Close to Uniform Prime Number Generation With Fewer Random Bits which has discussion and algorithms for faster generation of well-distributed large n-bit primes. The FIPS 186-4 publication also has a lot of information including algorithms for Shawe-Taylor proven prime construction.

dlongley's answer uses the "PRIMEINC" method, which is efficient but not a good distribution (this may or may not matter to you, and either way he's given a nice framework to use). Note that FIPS recommends a lot of M-R tests (this can be mitigated if your library includes a Lucas or BPSW test).

Re: proven primes, my experience using GMP is that up to at least 8192 bits, both Shawe-Taylor and Maurer's FastPrime are slower than using Fouque and Tibouchi algorithm A1 combined with BPSW + additional M-R tests. Your mileage may vary, and of course the proven prime methods get a proven prime as a result.