Why can we not use the group $Z_p^*$ for cryptography?
Why can we not use the group $Z_p^*$ for cryptography?
Sorry if this is a noob question, but for instance in ECDSA, we start by considering the field $mathbb F_p$, whose the elements also form a group under multiplication. Why don't we just use this group instead of the one that is generated by the solutions of an elliptic curve equation lying in this field? I.E. choose an element lying in this field $g$ and choose a random number $n$ as a private key, and let $g^n$ be the public key. Is is just because of the reduction in key size? It seems like a high price to pay for the additional structure imposed by the curve equation.
$begingroup$
Rather about ElGamal v.s. ECDSA, I think
$endgroup$
– Erik
Sep 17 '18 at 11:37
$begingroup$
I was almost sure we already had a question like "why use ECDSA instead of plain DSA?" lying around, but it looks like we don't. The closest thing I could find was this, which is not quite it.
$endgroup$
– Ilmari Karonen
Sep 17 '18 at 11:43
$begingroup$
...although we do also have this general question with some pretty nice answers.
$endgroup$
– Ilmari Karonen
Sep 17 '18 at 11:46
1 Answer
1
You can use the multiplicative group $mathbbZ_p^*$, provided you use a key long enough to be secure.
Diffie-Hellman key exchange, DSA and the ElGamal cryptosystem were originally defined based on the hardness of the Discrete Logarithm Problem (DLP) over finite fields.
The challenge is that since then several methods have been found to reduce the complexity of the DLP (e.g. number field sieve, Pohlig-Hellman algorithm, Pollard's Rho algorithm). Consequently for these algorithms to be secure today it is necessary to use long (>3072 bits) prime fields. Additionally, since the scaling of hardness is sub-exponential in p, doubling the hardness of the problem requires that p is increased by much more than 2 (so secure key lengths will grow near-exponentially over time).
The advantage of using cryptography over elliptic curve groups is that you end up with smaller key lengths and ciphertexts for equivalent hardness (e.g. 256-bit ECC versus 3072 bit) and it scales better (so doubling the complexity means adding a single bit instead of adding many bits).
Thanks for contributing an answer to Cryptography Stack Exchange!
But avoid …
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Required, but never shown
Required, but never shown
By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy
$begingroup$
Are you specifically asking about DSA vs ECDSA?
$endgroup$
– mikeazo
Sep 17 '18 at 11:05