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.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Can you provide a link to the reference you're looking at? $\endgroup$– Mike OunsworthSep 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$– chirondSep 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$– Mike OunsworthSep 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$– chirondSep 5, 2018 at 20:57
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
answered Sep 5, 2018 at 20:58
-
$\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$– ponchoSep 5, 2018 at 21:29
-
$\begingroup$
$\endgroup$
3
"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.
-
$\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 ♦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$– ponchoSep 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 ♦Sep 7, 2018 at 6:57