Tell me more ×
IT Security Stack Exchange is a question and answer site for IT security professionals. It's 100% free, no registration required.
up vote 0 down vote favorite

As we know DH algorithm based upon 2 large prime numbers, which are used to be called as prime and base

I am writing app which implements DH key exchange algorithm. From security point of view should I take care for securing prime and base numbers? And what are implications if I wouldn't do that?

share|improve this question
Do you actually implement DH yourself, or do you use an existing library? – CodesInChaos Sep 12 '12 at 7:38
I'm implementing it myself – barmaley Sep 12 '12 at 7:43
1  
In that case, you'll need to be careful about stuff like timing-attacks. – CodesInChaos Sep 12 '12 at 7:44
could you drop good link to explanation of timing-attack? – barmaley Sep 12 '12 at 7:45
1  
@barmaley Are you implementing authenticated or non-authenticated DH KE? If authenticated, how are you planning to authenticate? This is actually the trickier part of using DH and requires care. – David Wachtfogel Sep 12 '12 at 8:40
show 1 more comment

2 Answers

up vote 3 down vote accepted

In Diffie-Hellman there is a large integer which is prime, but the other one needs not be large, and it needs not be prime either.

With DH, computations are done modulo a big prime p. A generator called g is also used: g "generates" the values gi mod p. If you (virtually) compute the gi modulo p, you will get back to 1 at some point; the smallest non-zero value i such that gi = 1 mod p is called the order of g (let's write it r). Necessarily, r divides p-1.

What DH needs is that:

  • p is large enough to make discrete logarithm hard; say, at least 1024 bits (current fashion is 2048 bits, because 1024 bits are now considered to be "a bit too weak" as in "unbreakable for now, but maybe in 20 years...").
  • r must have at least one prime factor q which is large enough to deter discrete logarithm; in this context, this means at least 170 bits (there again, fashions dictate 256 bits -- cryptographers just love powers of two).

q and r needs not be known by the people who do the DH. If you select a random p of appropriate size, and a random g (as a value between 2 and p-2, inclusive), then g will be fine with overwhelming probability (you will not know r, let alone q, but it would be extremely improbable that all prime factors of r are short).

Nevertheless, you could try a bit harder in the choice of p; for instance, you could select p such that p = 2t+1 where t is also prime. At this point, any g (between 2 and p-2) is guaranteed to have an order equal to either t or 2t, so you can choose g as you see fit. In particular, you can choose g = 2, which makes computations a bit faster.

None of the values above need to be secret. Indeed, both DH parties are assumed to know them beforehand, so they cannot be secret (if they were secret, it would be a shared secret and you would not need to do Diffie-Hellman at all, you could just use that shared secret as is). To save effort, you could reuse existing, published values for p and g, for instance these values.

share|improve this answer
up vote 3 down vote

Neither of them is secret. Only the users private key needs to be secret, the group parameters are public. I recommend using a standardized pair for them, and hardcode it into your protocol. Allowing participants in a protocol to choose the parameters themselves often leads to subtle attacks.

Alternatively you could use a standard elliptic curve. Those offer higher performance and smaller keys. For example you could use NIST P-256 or Curve25519.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.