使用伪造(或其他JavaScript方法)生成随机大素数

Jey*_*ork 5 javascript random primes

我需要在JavaScript中生成一个随机的大(大约4096位)素数,我已经在使用伪造了.Forge必须有某种生成器用于执行这样的任务,因为它实现了RSA,RSA也依赖于随机素数.但是,当你只是想获得一个随机的素数时,我还没有在伪造的文档中找到一些东西(类似的东西var myRandomPrime = forge.random.getPrime(4096);会很棒).

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

dlo*_*ley 7

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

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

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

如果您只是寻找单个素数,那么运行中的RSA代码会运行一些额外的操作,而您不需要这些操作.话虽这么说,过程中最慢的部分是实际找到素数,而不是那些额外的操作.但是,RSA代码还会生成两个素数(当您只需要一个素数时),它们与您正在寻找的不同.因此,如果你正在使用伪造的API,你必须传递一个8196的比特(我相信......这是我的头脑,所以它可能是不准确的)获得4096位素数.

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

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

步骤#3可以运行很长时间 - 这对于JavaScript(w/node或浏览器)来说通常是不可取的.为了缓解这种情况,您可以尝试将执行素性测试所花费的时间限制在某个可接受的时间段(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);
  });
}
Run Code Online (Sandbox Code Playgroud)

可以进行各种调整以根据您的需要进行调整,例如设置时间量(这只是一个估计值)来运行素数测试器,然后再次尝试下一个计划的滴答.每次保释时,您可能都需要某种UI反馈.如果你正在使用节点或支持setImmediate你的浏览器,那么可以使用它而不是使用setTimeout钳位来加快速度.但是,请注意,在JavaScript中生成4096位随机素数需要一段时间(至少在撰写本文时).

Forge还有一个用于生成RSA密钥的Web Worker实现,旨在通过让多个线程使用不同的输入运行素性测试来加速进程.您可以查看伪造源(prime.worker.js例如)以查看实际操作,但这本身就是一个项目才能正常工作.不过,IMO是加快速度的最佳方式.

无论如何,希望上面的代码可以帮助你.我用较小的比特来运行它来测试它.