2
$\begingroup$

Diffie-Hellman groups tend to increment in key sizes as you'd expect up until group 21. Any idea why the key size is 521 rather than 512? I haven't been able to find an answer at all.

$\endgroup$
4
  • $\begingroup$ Can you provide a link to the reference you're looking at? $\endgroup$ Commented Sep 5, 2018 at 20:19
  • $\begingroup$ Many places. One example is here: cisco.com/c/en/us/about/security-center/…. Also seen in textbooks, course videos, and other sites. Also this forum (but it is a forum): community.cisco.com/t5/security-documents/diffie-hellman-groups/… $\endgroup$
    – chirond
    Commented Sep 5, 2018 at 20:41
  • $\begingroup$ Not that I'm doubting you, just that it's nice for people who click on your question to learn something if the question includes all the relevant background. The only hit I see on that page for "21" is "ECDSA-521" which is a signature algorithm, not DH. $\endgroup$ Commented Sep 5, 2018 at 20:45
  • $\begingroup$ Appreciate this. I've seen it in nearly every source where I've looked up DH groups. Unfortunately some sources can't be linked, and I haven't saved links to a lot of other sources. It does seem group 20 in that link is as far as it goes. I've found that link to be a very useful resource by the way. $\endgroup$
    – chirond
    Commented Sep 5, 2018 at 20:57

2 Answers 2

1
$\begingroup$

From your second link:

Diffie-Hellman group 21 - 521 bit elliptic curve

I agree that "521" would be an odd number for traditional Diffie Hellman, but you're talking about Elliptic Curve DH, which gets its size from the underlying curve.

EC curves don't really follow "power of two" sizes. For example, if you have a look here you'll see elliptic curves with the following bit lengths for the underlying field: 221, 222, 224, 251, 254, 255, 256, 382, 383, 384, 414, 448, 511, 521.

Why any particular polynomial was chosen as the base field for that curve would need a deeper mathematical analysis, but certainly it's not uncommon to see weird numbers for ECC field sizes.

$\endgroup$
2
  • $\begingroup$ Actually, there is no reason why the modulus for a traditional Diffie-Hellman needs to be a "power of two" size; it just happens to be the way we do things. $\endgroup$
    – poncho
    Commented Sep 5, 2018 at 21:29
  • $\begingroup$ @poncho Did I say it needed to be? $\endgroup$ Commented Sep 5, 2018 at 21:32
8
$\begingroup$

"Group 21" was originally used by IKE to refer to a specific elliptic curve group, which happens to use $2^{521}-1$ as the prime modulus.

Your question is "why did they use $2^{521}-1$ is their prime, rather than a prime closer to $2^{512}$?

Well, it turns out that using $2^{521}-1$ is more efficient than a slightly smaller prime. Most of the time implementing elliptic curve operations turns out to be performing modular multiplications, that is, given $a$ and $b$, compute $a \times b \bmod p$. There are some tricks we can use for $p = 2^{521} - 1$ that aren't available for $p \approx 2^{512}$ (specifically because of the special form of $p^{521}-1$ as a Mersenne prime); and so they just took advantage of it.

There are no similar Mersenne prime circa $2^{256}$ or $2^{384}$, and so a similar trick was not available for the smaller Elliptic Curve groups.

$\endgroup$
3
  • $\begingroup$ Besides the calculations being more efficient it is also likely that the random number generation is more efficient (private keys are between $1$ and $2^{521} - 1$ - the order of the curve - inclusive. So you can basically just generate 521 bits of randomness and convert it to a number to create the private key. $\endgroup$
    – Maarten Bodewes
    Commented Sep 6, 2018 at 10:29
  • $\begingroup$ @MaartenBodewes: actually, the order of the curve isn't precisely $2^{521}-1$; however it is "close" (in the Hasse interval), and just happens to be smaller. In any case, the time taken to generate private keys is trivial compared to the time taken by the modular multiply operation... $\endgroup$
    – poncho
    Commented Sep 6, 2018 at 12:24
  • $\begingroup$ That depends on the random number generator. If it blocks because of shortage of entropy then it will be slower. Dual EC will probably also be slower, but yeah... $\endgroup$
    – Maarten Bodewes
    Commented Sep 7, 2018 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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