3
$\begingroup$

I tried to learn the algorithmic process behind ECDSA and it's pretty challenging. I'm wondering what motivation or thought process might have led to the discovery in the first place. What properties do elliptic curves possess that make them resilient to attack?

Predecessor RSA seems somewhat more intuitive and reasonable to discover.

$\endgroup$
1
  • $\begingroup$ Do you mean that the invention of RSA was a reasonable development or that the original RSA is easier to understand than ECC? $\endgroup$
    – Patriot
    Aug 4 at 5:30
4
$\begingroup$

I'm wondering what motivation or thought process might have led to the discovery in the first place. What properties do elliptic curves possess that make them resilient to attack?

Well, in the first place, Elliptic Curves were studied by mathematicians long before their use in cryptography was realized; I believe much of the foundational work was done in the 1800's. Hence, what Koblitz and Miller (two researchers who suggested them independently) did was not invent elliptic curves, but rather note that they had cryptographical potential.

Why would this be? Well, elliptic curves have less "structure" than finite field groups; with finite field groups, there is an algorithm that can take any element, and have a nontrivial probability of being able to express that element as a combination of a small set of fixed elements; it turns out that algorithm is quite useful for computing discrete logarithms, and is a significant reason why we have to make those groups so large. There is no known algorithm that solves this problem for elliptic curves; hence we can use a much smaller elliptic curve group.

$\endgroup$
3
$\begingroup$

I'm wondering what motivation or thought process might have led to (ECDSA)

ECDSA evolved from ElGamal signature. This was originally defined in the multiplicative group $\mathbb Z_p^*$ for prime $p$. This is somewhat similar to the multiplicative group $\mathbb Z_n^*$ for composite $n$ used by RSA. There was two separate evolutionary steps:

  1. DSA (circa 1991). That uses a subgroup of $\mathbb Z_p^*$ with much smaller order, allowing much shorter signature than in ElGamal. Such subgroup was used by the similar Schnorr signature (circa 1989), for that same purpose, and is known as a Schnorr group.
  2. ECDSA (circa 2000). This essentially replaces the Schnorr group by an elliptic curve group, in order to speed up calculations and shorten the public key. Use of such group rather than (some subgroup of) $\mathbb Z_p^*$ was suggested by Miller and independently by Koblittz as early as 1985, first in the context of Diffie-Hellman key exchange. Miller quotes Lentra's elliptic curve factorization as the inspiration for using an elliptic curve group. Lentra used elliptic curves as a tool to attack RSA, which brought elliptic curves into the field of cryptography. It had been known for over a century that elliptic curves on a field can be used to construct a group. If the field is finite, the group is finite (a necessary characteristic for use in cryptography).

What properties do elliptic curves possess that make them resilient to attack?

Elliptic curves are not more resilient to attack than Schnorr groups of equal group size. If it was only for signature size and security, we would not need elliptic curves, and would use the much simpler DSA rather than ECDSA. The reason elliptic curves are preferred is that they allow shorter representation of group elements, thus shorter public keys, and faster computations (at the expense of complexity), at equivalent group/signature size and security.

The reason elliptic curve groups can get away with shorter representation of group elements than a Schnorr group is that they are not embedded in some field (with the law of the group the second law of the field). In other words, there is no operation in an Elliptic Curve group that's analog to addition modulo $p$ is to the group $\mathbb Z_p^*$. Therefore, there is no known analog working in the Elliptic Curve group to the index calculus algorithm, which allows to compute discrete logarithms in $\mathbb Z_p^*$ faster than generic methods working in any group, such as baby-step/giant-step or Pollard's rho.

$\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.