0

Basically question is:
If we have pof size 2048 what sizes for private exponents should Alice and Bob choose and why?

  • 2
    This sort of looks like a homework question. What work have you done to try to answer this? How do you define p? – schroeder May 4 '16 at 16:39
  • 1
    Well it's definitely not a homework question :). After looking through the DH key-exchange I've found the requirements for p to be safe prime as well as the benefits of g to be the generator for p. What I didn't find is what are the requirements for the private key sizes. – d3day May 4 '16 at 17:08
4

IF (that's a big "if") the generator g and the public element from the peer can be assumed to be part of a subgroup of prime order, THEN it suffices for exponents to have size 2t bits, for a "security level" of t bits. In other words, 256 bits are fine.

Now if p is a so-called "strong prime" (i.e. p is prime and (p-1)/2 is also prime), then any integer modulo p (except 0, 1 and p-1) necessarily has order (p-1)/2 or p-1, and a 257-bit exponent is sufficient. In fact, it is overkill because solving discrete logarithm modulo p will be easier than that, academically speaking (but this is all far in the "technologically infeasible" realm anyway).

If you are using Diffie-Hellman with a truly ephemeral DH key pair, to establish a shared secret with a specific peer and never reusing that DH secret for anything else, then you can just assume the DH parameters to be fine, because, by virtue of discarding the private DH key after usage, whatever nasty tricks played by the peer will impact that key exchange only. However, if you plan to reuse the same DH key pair to make of DH instances (e.g. a TLS server with a "DHE_RSA" cipher suite, that renews DH key pairs only when the service is restarted), then you have to be more careful because peers may submit bogus DH public keys to try to extract information from your own DH private key, and use that to attack other connections.

  • Thanks for explanation. Could you please elaborate a bit more about the security level and how 256bit size of exponent was calculated for the p of 2048bit? – d3day May 4 '16 at 17:46
  • 2
    On a generic group, breaking discrete logarithm for 2t-bit exponents has cost 2^t. The tradition is to aim for breaking cost 2^128, as the conventional limit of infeasibility (with some margin). Now, when working modulo a prime p, you can break DL as you would with any group, but you can also do some smart maths (lookup "Index Calculus") that can break DL with a cost that depends on the size of p (the modulus, not the exponent). With a 2048-bit modulus, that cost is about 2^110 or so. Thus, any exponent size beyond 220 bits is "overkill". – Thomas Pornin May 4 '16 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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