RSA随机生成大素数C语言,使用伪造(或其他JavaScript方法)生成随机大素数

Myth丶恋晨 2022-10-15 15:58 156阅读 0赞

更新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密钥.没有API调用只是简单地产生一个大的随机素数.

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

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

>生成具有所需位数的随机数(确保设置了MSB).

>将数字对齐在30k 1边界上,因为所有素数都具有此属性.

>对你的号码进行素性测试(慢速部分);如果它通过,你就完成了,如果没有,加上数字到达下一个30k 1边界并重复. “快速”素性测试是检查低素数,然后使用Miller-Rabin(参见Handbook of Applied Cryptography 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);

\});

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

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

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