C#随机BigInt生成器

Question

我即将实施DSA算法,但是存在一个问题:

选择"p",一个带L位的素数,其中512 <= L <= 1024,L是64的倍数

如何实现该数字的随机生成器？Int64具有"仅"63位长度.

Answer 1

您可以n使用以下代码生成带位的随机数:

var rng = new RNGCryptoServiceProvider();
byte[] bytes = new byte[n / 8];
rng.GetBytes(bytes);

BigInteger p = new BigInteger(bytes);

结果当然是随机的,而不一定是素数.

该BigInteger的类是在.NET 4.0框架介绍.

为了生成大素数,维基百科说:

对于密码学中使用的大质数,通常使用修改形式的筛选:将随机选择的所需大小的奇数范围与一些相对较小的奇数素数(通常所有素数小于65,000)进行筛选.剩余的候选素数以随机顺序用标准素性测试进行测试,例如可能素数的米勒 - 拉宾素性测试.

所以你可以这样做:

var p = Enumerable.Range(0, numberOfCandidates)
                  .Select(i => RandomOddNumber(bits))
                  .Where(x => !primesLessThan65000.Contains(x))
                  .Where(x => PrimalityTest(x))
                  .FirstOrDefault();