Diffie-Hellman Private Key

Question

I have the line of code below to generate a private key:

int Xa = randomNo.nextInt(10000);
int Ya = (int) Math.pow(G, Xa) % P;

G and P are static numbers. Whereas Xa is randomly generated. Every time I run the program, it gives me the same result for Ya. Is this correct for Diffie-Hellman? I thought the private key had to be changed every time the algorithm was run.

Answer 1

I think the problem may be that you are overflowing double with your exponentiation, resulting in infinity, resulting in the same value every time (unless you are lucky enough to end up with a very low number returned for your exponent).

Also, be sure to use secure random to get your random value:

Random random = new SecureRandom();

// If you use more than 100 here, then
// with your value of 486 for G you will
// end up with infinity when doing Math.pow(G,Xa).
// Of course, this does not provide enough possible
// values to be cryptographically secure.
int Xa = random.nextInt(100);
int Ya = (int) (Math.pow(G, Xa) % P);

Edit: Code with debugging (the below works for me):

double G = 42;
int P = 26;


Random random = new SecureRandom();
int Xa = random.nextInt(100);
double val = Math.pow(G, Xa);
System.out.println("Xa: " + Xa);
System.out.println("(double) Math.pow: " + val + " (int): " + (int) val);
int Ya = (int) (val % P);
System.out.println("Ya: " + Ya);

Answer 2

This can only give different results if Xa is different. How did you generate the value of Xa? Chances are you've used a pseudo-random generator that typically need to be seeded. If you take the default seed each time (same seed each time) it will always return the same sequence of random numbers.

Try seeding your generator with System.currentTimeMillis();

Answer 3

Other people seem to have given good answers on the issue with your generation of random numbers, so I'll respond to your question "Is this correct for Diffie-Hellman?"

Your understanding of Diffie-Helman is a bit off I think. For one thing, you keep using the term 'private key' as though there is also a 'public key'. Diffie-Hellman key exchange is a technique used for exchanging one symmetric key. There isn't a private key and a public key, there is just a key that both parties are going to use to encrypt their messages. Moreover, you said that this is code for 'generating' a key. With Diffie-Hellman, it takes two to tango. This code isn't enough to generate the final product of the key. You'll need to send Ya to a 2nd party and get something back from that second party to finish the process. See below for more info.

Your formula for generating Ya is correct, assuming that Xa is what it is supposed to be. I'm a little concerned about your understanding of what you're supposed to do with Xa because you're reassigning it to a random value after you've generated Ya. You will need to hang on to Xa in order to create the final version of the key.

After you've generated Ya, you should be sending that to the other party. The other party will send you back some number in return (let's call that R). In order for you to create the final version of the symmetric key (let's call it SK), you will need to calculate it as

SK = (int)Math.pow(R, Xa) % P;

So in a nutshell, don't recalculate Xa after you've calculated Ya, otherwise you won't be able to generate the key. The process goes:

1. Generate Ya (I'm just using this variable name because it's what you used).
2. Send Ya to some person.
3. Receive some number from the person you sent Ya to (called this number R in example above).
4. Calculate what the symmetric-key should be that you'll be using for encryption using R, Xa, and P. (See formula above for SK)

Answer 4

The problem is that the Random class in Java has a constructor with one long argument (called seed) that allows you to start the pseudorandom number sequence in a particular way.

If you always use the same seed, you will always obtain the same sequence.

To solve the problem, try this:

Random randomNo = new Random(System.nanoTime());
int Xa = randomNo.nextInt(10000);

In this way, the seed is always different, and the sequence changes everytime you call the above line.