使用伪造(或其他 JavaScript 方法)生成随机大素数 [英] Generate a random big prime number with forge (or another JavaScript approach)

问题描述

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

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).

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

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

推荐答案

Update 06/11/2014:现在，使用 forge 0.6.6 版，您可以使用这个:

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

<小时>

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

---

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.

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

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:

1. 生成具有所需位数的随机数(确保设置了 MSB).
2. 在 30k+1 边界上对齐数字，因为所有素数都具有此属性.
3. 对您的号码进行素性测试(较慢的部分)；如果它通过，你就完成了，如果没有，添加到下一个 30k+1 边界并重复.快速"素性测试是检查低素数，然后使用 Miller-Rabin(参见 应用密码学手册 4.24).

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

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.

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

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

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

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 还有一个用于生成 RSA 密钥的 Web Worker 实现，旨在通过让多个线程使用不同的输入运行素性测试来加快进程.您可以查看 forge 源代码(例如 prime.worker.js)以查看其实际效果，但它本身就是一个可以正常工作的项目.不过，IMO 是加快速度的最佳方式.

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.

这篇关于使用伪造(或其他 JavaScript 方法)生成随机大素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！