OK, Just throwing this out there...
EASY PRIME GENERATION IN C#.NET
I think this approach will be far more useful to most readers than some of the suggestions above. Forgive me, but after reading this thread I figured that this little trick is sorely missing from the discussion. I don't normally post here.
Before we begin, this method does have limitations...
it cannot make really small primes. It can, however make huge primes, even over 16,000 bits without any fuss.
Personally I think not being able to make tiny primes is a limitation most of us can probably live with, yes? If you DO need tiny primes, then the table or random methods above are manageable... and you can use both techniques if you need all sizes ...
- a table or a random search for primes less than 384 bits, and;
- this code for primes between 284 bits and 16,384 bits.
I think you'll agree that it's a really simple and safe method. Let's get stuck in :
First,
using system.security.cryptography
As a quick test, you could create an instance of the RSACryptoServiceProvider class... as this exposes the range of primes that are valid when creating an RSA key. Like this...
using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider)
{
int min = myRSA.LegalKeySizes.MinSize;
int max = myRSA.LegalKeySizes.MaxSize;
int step = myRSA.LegalKeySizes.StepSize;
}
These numbers are not likely to change, so feel free to ignore the above - I include it only to show the primes you can produce. Once you have identified a size (between min and max, with a step size of 8) ... you can ask c# to create a key of that specific size!
Delete the above code, and let's start generating primes...
Use DotNets RSA implementation to generate a large prime
Let's begin with a nice small 1024 bit prime number...
using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider(1024))
{
String xml = myRsa.ToXmlString(true);
}
Yep... just 2 lines of code! To convert it to a BigInt is about 5 lines of code. Feel free to donate beer.
Here is the format of the xml,
all values are Base64 encoded ...
<RSAKeyValue>
<Modulus> ... </Modulus>
<Exponent> ... </Exponent>
<P> Your prime 'P' of the required size </P>
<Q> another useful prime 'Q', close in size to 'P' </Q>
<DP> ... </DP>
<DQ> ... </DQ>
<InverseQ> ... </InverseQ>
<D> ... </D>
</RSAKeyValue>
Now, I have deliberately avoided showing how to parse the Base64 as only you know where you want to store this number. But, there are plenty of snippets here on CodeProject which show how to parse XML (or, alternatively, split up strings) and decode Base64 into binary bytes. It's not a big deal.
One warning though... if you are going to put it into a container that is unsigned, you need to follow the rules - as the representation you get from the Base64 will be UNsigned but MIGHT have the most significant bit set.
So, if you want to put it into a
System.Numerics.BigInteger ... remember that you should make the byte array
one byte larger than the number requires. This is because the byte array
needs to have an added zero to ensure that BigInteger doesn't consider it to be negative.
And, that's that : )
Now you know how to generate large primes between 48 bytes (384 bits) and 2048 bytes (16,384 bits) without messing around with guessing games or using large tables of primes... and all in just a few lines of code.
And, all we had to do was abuse the RSACryptoServiceProvider class into doing our bidding ; )
Hope that helps someone.
EDIT: Answer extended - Quick & dirty example of parsing into a BigInteger
using system.security.cryptography;
using system.numerics;
using (RSACryptoServiceProvider myRsa = new RSACryptoServiceProvider(1024))
{
byte[] sbin;
byte[] ubin;
String xml = myRsa.ToXmlString(true);
int s = xml.IndexOf("<P>")+3;
int l = xml.IndexOf("<",s)-s;
sbin = Convert.FromBase64String(xml.Substring(s, l));
ubin = new byte[sbin.Length + 1]; ubin[sbin.Length] = 0;
Buffer.BlockCopy(sbin, 0, ubin, 0, sbin.Length);
BigInteger bigprime = new BigInteger(ubin);
Console.WriteLine(bigprime);
}