6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you specifically asking about DSA vs ECDSA? $\endgroup$ – mikeazo Sep 17 '18 at 11:05
  • $\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
9
$\begingroup$

You can use the multiplicative group $\mathbb{Z}_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).

$\endgroup$

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.