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.

Can you post the line where you initialize the Random object used to create Xa? — Vito Gentile, Mar 18 '13 at 18:05
Edited original @VitoShadow - I've outputted the random number and it works. — Adam Hinx, Mar 18 '13 at 18:07
You're probably better off using `BigInteger` and not `int` or `long`... — Louis Wasserman, Mar 18 '13 at 18:24
What are the values of G and P? I think you are overflowing double in your exponent and getting infinity resulting in the same result every time. — Trevor Freeman, Mar 18 '13 at 18:26
486^200 will get infinity with doubles, so 486^(random(10000)) will be infinity most of the time, resulting in the same value for your expression (see my answer below). — Trevor Freeman, Mar 18 '13 at 18:31
You should certainly be using [javax.crypto.KeyAgreement](http://docs.oracle.com/javase/7/docs/api/javax/crypto/KeyAgreement.html) for this task rather than doing it by hand. — user207421, Mar 19 '13 at 06:08

Vito Gentile · Answer 1 · 2013-03-18T18:15:58.623

3

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.

edited Mar 18 '13 at 18:15

answered Mar 18 '13 at 18:08

Vito Gentile

13,336
9
61
96

So if i've understood correctly - does the seed now come from an internal clock? – Adam Hinx Mar 18 '13 at 18:13
I'm also getting the error "no suitable method found for nextInt(long). – Adam Hinx Mar 18 '13 at 18:15
Yes, this is a tipical trick used to create random number from pseudo-random ones. – Vito Gentile Mar 18 '13 at 18:15
Fantastic thanks. Would you mind telling me, What would be the advantages of using this over SecureRandom() as stated above? I have edited the code to the one you listed above, but it still seems to output the same number each time. – Adam Hinx Mar 18 '13 at 18:16
From this page: http://docs.oracle.com/javase/6/docs/api/java/security/SecureRandom.html SecureRandom provides a cryptographically strong random number generator. It means that it includes some mechanisms to avoid initialization based of the current time. – Vito Gentile Mar 18 '13 at 18:19
2

You should use `SecureRandom` and not `Random` if this is for encryption purposes. – Trevor Freeman Mar 18 '13 at 18:21
I've tried using SecureRandom but it's outputting the same number. http://pastebin.com/kS5Bq3QE – Adam Hinx Mar 18 '13 at 18:24
It is outputting the same number because your exponentiation is overflowing to infinity, not because the random number is the same. – Trevor Freeman Mar 18 '13 at 18:36

score 3 · Answer 2 · edited Jul 26 '22 at 15:46

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-Hellman 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:

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

Cheers @2to1mux - Thats made it more clear. I've been following a tutorial on the web. (http://www.codeproject.com/Articles/70330/Implementation-of-Diffie-Hellman-Algorithm-of-Key) — Adam Hinx, Mar 18 '13 at 18:26

Trevor Freeman · Accepted Answer · 2013-03-18T18:53:13.573

2

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);

edited Mar 18 '13 at 18:53

answered Mar 18 '13 at 18:14

Trevor Freeman

7,112
2
21
40

I have the exact same code, only with P being 26 and G being 42. Still generating the same number? (random.nextInt being 100). – Adam Hinx Mar 18 '13 at 18:42
That's due to the second problem with the code (just fixed above), where you need to do the modula before the cast. Added parenthesis above to make it work. – Trevor Freeman Mar 18 '13 at 18:48
Tried that - still no luck. I'm stumped. – Adam Hinx Mar 18 '13 at 18:49
See my edit above with debugging and full code.. works for me. – Trevor Freeman Mar 18 '13 at 18:54
The above code works for me also. Strange. Could it be to do with the fact i'm doing the power and mod in one sum? Thanks anyway @increment1 – Adam Hinx Mar 18 '13 at 18:57
You need the parentheses in order to ensure you do the `%` before the `(int)` since `(int)` binds tighter than `%`. – Trevor Freeman Mar 18 '13 at 19:00

score 1 · Answer 4 · edited Mar 18 '13 at 18:13

1

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();

edited Mar 18 '13 at 18:13

Leigh

28,765
10
55
103

answered Mar 18 '13 at 18:11

scharette

605
1
9
25

Diffie-Hellman Private Key

4 Answers4

Linked