1
$\begingroup$

About the Diffie-Hellman key exchange, I have a question related to the key space, as far as I know the key space is of course all the possible keys to be used, for instance, say that $p$ and $\alpha$ are the large prime and primitive root respectively so the key is $K=\alpha^{xy}\pmod{p} $ for secret $a$ and $b$. Now, according to this, I'd say that the key space is the set $\mathbb{Z}_p$, which sounds good to me.

My problem comes now, since I was just reading about new techniques on key exchange using fractal methods that make a comparison between this new method and DH, it states at some point that "The DH key space for 128 bit is limited by how many primes existed in the finite field of $\mathbb{Z}_p$, where $p$ is the largest prime that can be represented by a 128-bit value", so I got a bit confused about what it really means.

$\endgroup$

1 Answer 1

8
$\begingroup$

"The DH key space for 128 bit is limited by how many primes existed in the finite field of Zp, where p is the largest prime that can be represented by a 128-bit value", so I got a bit confused about what it really means.

I believe that the appropriate meaning to the quote is "I have no clue about cryptography, here are some plausible sounding buzzwords that I've heard".

No one uses (or, should use) a 128 bit prime for Diffie Hellman; the current conventional wisdom to use (at least) a 2048 bit prime with a large prime subgroup; this is often done by using a "safe prime".

Now, sometimes we perform Diffie-Hellman based on an elliptic curve, which might also be based on a prime curve. However, even in this case, a 128 bit prime is still too small; the conventional wisdom is to use at least a circa 256 bit prime (Curve25519 comes close enough).

If the author of the fractal method isn't aware of this, well, that doesn't indicate that he knows all that much about cryptography. That would certainly call into question anything he has to say about his fractal key exchange.


BTW: "key space" isn't a very useful way to think about DH security. If the size of the large prime subgroup is $q$, then the "key space" size is $q$; however there are generic attacks that recover the shared secret in time $O(\sqrt{q})$, hence you aren't as secure as the size of the key space would indicate (and, for some groups, there may be even faster attacks).

$\endgroup$
0

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.