javascript - 使用 forge(或其他 JavaScript 方法)生成随机大素数

Question

我需要在 JavaScript 中生成一个随机的大(大约 4096 位)质数，我已经在使用 forge。 Forge 必须为此类任务提供某种生成器，因为它实现了同样依赖于随机素数的 RSA。但是，当您只想获得一个随机素数时，我没有在 forge 的文档中找到任何东西(比如 var myRandomPrime = forge.random.getPrime(4096); 会很棒)。

那么在 JavaScript 中获得这样一个质数(有或没有伪造)的最佳方法是什么？

Answer 1

2014 年 6 月 11 日更新:现在，使用 forge 版本 0.6.6，您可以使用:

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

---

在 JavaScript 中查找大素数很困难——它很慢，而且您不想阻塞主线程。它需要一些相当定制的代码才能正确执行，而 forge 中的代码专门用于 RSA key 生成。没有 API 调用来简单地生成一个大的随机素数。

Forge 中的 RSA 代码运行了一些额外的操作，如果您只是寻找单个质数，则不需要这些操作。也就是说，这个过程中最慢的部分是实际找到素数，而不是那些额外的操作。但是，RSA 代码还会生成两个素数(当您只需要一个素数时)，并且它们与您要查找的位数不同。因此，如果您使用的是 forge API，则必须传递 8196 位大小(我相信……这超出了我的脑海，所以它可能不准确)才能获得 4096 位素数。

寻找大随机素数的一种方法如下:

1. 生成一个具有所需位数的随机数(确保已设置 MSB)。
2. 将数字对齐到 30k+1 边界，因为所有质数都具有此属性。
3. 对您的数字进行素性测试(慢的部分)；如果通过，你就完成了，如果没有，添加到下一个 30k+1 边界的数字并重复。 “快速”素数测试是检查低素数，然后使用 Miller-Rabin(参见 Handbook of Applied Cryptography 4.24)。

第 3 步可能会运行很长时间——这对于 JavaScript(带节点或在浏览器中)来说通常是非常不受欢迎的。为了缓解这种情况，您可以尝试将进行素性测试所花费的时间限制在某个可接受的时间段(N 毫秒)内，或者您可以使用 Web Workers 来后台处理该过程。当然，这两种方法都会使代码复杂化。

下面是一些代码，用于生成不应阻塞主线程的 4096 位随机素数:

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);
  });
}

可以根据您的需要进行各种调整，例如设置运行素性测试器的时间(这只是一个估计值)，然后在下一次计划的 tick 上再次尝试。每次退出时，您可能都需要某种 UI 反馈。如果您使用的是节点或支持 setImmediate 的浏览器，您也可以使用它来代替 setTimeout 以避免限制以加快速度。但是，请注意，在 JavaScript 中生成 4096 位随机素数需要一段时间(至少在撰写本文时)。

Forge 还有一个用于生成 RSA key 的 Web Worker 实现，旨在通过让多个线程使用不同的输入运行素数测试来加速该过程。您可以查看 forge 源代码(例如 prime.worker.js)以查看实际效果，但它本身就是一个项目才能正常工作。不过，在 IMO 看来，这是加快速度的最佳方式。

无论如何，希望上面的代码对你有所帮助。我会以较小的位大小运行它来测试它。