In some suggested solutions I see that the private keys are generated with the help of randomized int64. Isn’t it supposed to be up to primeP in size, which can be larger than a int64 max?
This exercise is about the fundamental mechanisms of Finite Field Diffie-Hellman.
I believe its main goal is to demonstrate how math can make public-key crytography possible, to show that it’s not magic, and to provide some basic hands-on experience. It’s goal is not implementing a high-quality crypto library that is ready to be used in production.
AFAIK there’s no ready-to-use random number generator for BigInteger in .NET, you would have to write it yourself (see StackOverflow).
And for real cryptography you wouldn’t use a Pseudo Random Number Generator like System.Random but a real random number generator like System.Security.Cryptography.RandomNumberGenerator.
I think to generate a real random number between 2 and primeP - 1 you would have to do something like this:
byte[] bytes = primeP.ToByteArray();
while (true) {
System.Security.Cryptography.RandomNumberGenerator.Fill(bytes);
bytes[bytes.Length - 1] &= (byte)0x7F;
BigInteger r = new BigInteger(bytes);
if (1 < r && r < primeP)
return r;
};
Also, testing code that uses random number generators is hard.
If PrivateKey(BigInteger.Parse("723807132971731304202930150293")) returns 100 how would you know that this was generated in a way that all numbers from 2 to 723807132971731304202930150292 are possible outcomes or if it were generated by return new System.Random().Next(2, (int) primeP);?
tl;dr I think requiring random numbers beyond Int64.MaxValue - 1 would make shift the focus of this exercise, would make it harder, would make it harder to test, and would make the tests harder to read.
I’m not sure if the authors of this exercise would agree to these changes.
Disclaimer: I’m neither a C# programmer nor involved in the creation of this exercise nor in mentoring or maintaining the C# track, so this is just speculation.
BTW: These are questions that you could discuss with a mentor during a code review. I’ve had some really nice conversations while exploring aspects beyond the original scope of an exercise.
Hi @siebenschlaefer!
I was unsure if there was something I’d misunderstood around the Diffie-Hellman or the exercise. From you discussion I’ve gotten insights both on how I can think about exercises here, and on the specifics of this one, like testing random numbers for example. Thanks for the great answer!