更新 06/11/2014:现在,在 forge 版本 0.6.6 中,您可以使用以下命令:
var bits = 1024;
forge.prime.generateProbablePrime(bits, function(err, num) {
console.log('random prime', num.toString(16));
});
在 JavaScript 中查找大素数很困难——它很慢,而且您不想阻塞主线程。它需要一些相当定制的代码才能正确执行,并且 forge 中的代码专门用于 RSA 密钥生成。没有 API 调用来简单地生成一个大的随机素数。
Forge 中的 RSA 代码会运行一些额外的操作,如果您只是寻找单个素数,则不需要这些操作。话虽这么说,这个过程中最慢的部分是实际找到素数,而不是那些额外的操作。然而,RSA 代码也会生成两个素数(当您只需要一个素数时),并且它们与您正在寻找的位数不同。因此,如果您使用 Forge API,则必须传递 8196 位大小(我相信……这超出了我的想象,因此可能不准确)才能获得 4096 位素数。
查找大随机素数的一种方法如下:
- 生成具有所需位数的随机数(确保设置了 MSB)。
- 将数字对齐 30k+1 边界,因为所有素数都具有此属性。
- 对您的号码运行素性测试(缓慢的部分);如果通过,则完成,如果未通过,则添加该数字以到达下一个 30k+1 边界并重复。 “快速”素数测试是检查低素数,然后使用 Miller-Rabin(请参阅应用密码学手册 4.24 http://cacr.uwaterloo.ca/hac/about/chap4.pdf).
步骤 #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);
});
}
可以进行各种调整来根据您的需要进行调整,例如设置运行素性测试程序的时间(这只是估计),然后再尝试下一个计划的刻度。每次退出时您可能都需要某种 UI 反馈。如果您使用的是节点或支持的浏览器setImmediate
你可以用它来代替setTimeout
以及避免夹紧以加快速度。但是,请注意,在 JavaScript 中生成 4096 位随机素数需要一段时间(至少在撰写本文时)。
Forge 还有一个用于生成 RSA 密钥的 Web Worker 实现,旨在通过让多个线程使用不同的输入运行素性测试来加速该过程。您可以查看伪造源(prime.worker.js
例如)来看看它的实际情况,但这本身就是一个项目,需要它才能正常工作。不过,在我看来,这是加快速度的最佳方法。
无论如何,希望上面的代码能对您有所帮助。我会用较小的位大小运行它来测试它。