Selection of parameters in Diffie-Hellman

Question

Hello, maybe it's not so proper to ask this question here... anyway, I'm trying to use the gmp library for the implementation of DH, but the problem here I got is:

Once, when I was doing the tests to observe the output, although big values of prime and the private keys were selected:

• p was about more than 300 digits long in decimal
• a, b were about 100 digits long

finally I got a shared secret key which was extremely small, perhaps smaller than 10^8 in decimal...

This problem didn't show up many times, in fact, during all the observation, it appeared just once...but still, this was not so good at all.

So I wonder if there are some methods which can avoid this... Thanx a lot

Answer 1

The Diffie-Hellman key exchange is designed to generate a secret shared key.

By using large values of p, a and b, you ensure that the pool of potential shared keys is a very large one.

However, the actual value of the shared key can be any value within that pool. As a result, it could range from zero to (p - 1)... that's because, the Key is

G^(ab) mod p

Hence, you haven't discovered a problem here... your just seeing the instances when G^(ab) is close in value to a multiple of p, and hence the mod is a low number.

Answer 2

Part of the point of D-H is that the secret key could be any value within the range specified by p. At least in theory, eliminating some of those possibilities would make it less secure, not more so (realistically, as long as you leave a sufficiently large pool of keys, it makes little real difference).

It is true that if an attacker decided to try key-exhaustion (brute-force) attack, and started from 0 and just counted up, they'd hit this one relatively soon. Then again, if you decided on some other lower bound and (for example) re-negotiated the key if it was below that bound, it wouldn't do any real good -- instead of starting at 0, the attacker would start at the specified lower bound, and you'd have gained nothing.