C# A random BigInt generator

Question

Hi, I'm about to implement the DSA algorithm, but there is a problem:

choose "p", a prime number with L bits, where 512 <= L <= 1024 and L is a multiple of 64

How to implement a random generator of that number? Int64 has "only" 63 bits length

Answer 1

You can generate a random number with n bits using this code:

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

BigInteger p = new BigInteger(bytes);

The result is, of course, random and not necessarily a prime.

The BigInteger class was introduced in the .NET 4.0 Framework.

---

For generating large prime numbers, Wikipedia says:

For the large primes used in cryptography, it is usual to use a modified form of sieving: a randomly-chosen range of odd numbers of the desired size is sieved against a number of relatively small odd primes (typically all primes less than 65,000). The remaining candidate primes are tested in random order with a standard primality test such as the Miller-Rabin primality test for probable primes.

So you could do something like this:

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

Answer 2

If you are implementing DSA as a homework, or self learning or other educational purpose then you can use small keys, Int64 (or even Int32) will be enough.

If you are writing production code them use DSACryptoServiceProvider and save your time.