19
$\begingroup$

Yesterday I was thinking about elliptic curve variants of popular protocols/algorithms (ECDH, ECES[1], etc) and the thought occured that I had never seen an elliptic curve variant of RSA. My understanding of RSA and elliptic curves told me that it should be possible.

After some searching I found the following explanation (similar quote):

As we have mentioned, there are elliptic curve analogs to RSA but it turns out that these are chiefly of academic interest since they offer essentially no practical advantages over RSA. This is primarily the case because elliptic curve variants of RSA actually rely for their security on the same underlying problem as RSA, namely that of integer factorization.

This got me thinking. I had thought that the discrete log based systems I mentioned earlier were also based on the same underlying problem, the discrete log. But the article had this to say:

The situation is different with variants of discrete logarithm cryptosystems. The security of the elliptic curve variants of discrete logarithm cryptosystems depends on a restatement of the conventional discrete logarithm problem for elliptic curves. This restatement is such that current algorithms that solve the conventional discrete logarithm problem in what is termed sub-exponential time are of little value in attacking the analogous elliptic curve problem. Instead the only available algorithms for solving these elliptic curve problems are more general techniques that run in what is termed exponential time.

So now, to my question: Why are we able to restate the discrete log problem to make it more practical on elliptic curves but not the RSA problem?

1. ECES is the elliptic curve variant of ElGamal

$\endgroup$

1 Answer 1

23
$\begingroup$

The generic discrete logarithm problem is this:

Given a group $(G, ·)$ with generator $g$ and $y \in G$, find $x \in \mathbb N$ such that $y = g^x$.

The "classic" discrete logarithm problem (the one used in "classic" DSA and ECDSA) is this with some subgroup of the (multiplicative) group of a prime field, i.e. $(\mathbb Z/p \mathbb Z)^*$:

Given a prime number $p$, a generator $g$ (of some large subgroup) and $y \in \left<g\right>$, find $x \in \mathbb N$ such that $y = g^x \bmod p$.

The elliptic curve discrete logarithm problem is this with a subgroup of an elliptic curve group:

Given an elliptic curve $(E, +)$, a generator $G$ of some large subgroup, and $y \in \left<G\right>$, find $x \in \mathbb N$ such that $y = x · G$.

There are generic algorithms (such that the baby-step giant-step algorithm) for solving the discrete logarithm in any group (assuming a computable group law, or even just oracle access to the group law), and these work just fine for elliptic curve groups, as well as for the classic prime field. The average running time of these algorithms usually depends on the size of the group, like $O(\sqrt{|G|})$ for baby-step-giant-step. This is still exponential in the input size (since the input size is in $O(\log|G|)$, if one doesn't select really stupid encodings).

But for some special groups the discrete logarithm is easier, since they have some more (and known) structure. As an extreme case, consider the additive group $(\mathbb Z/n \mathbb Z, +)$ (for any positive integer $n$), with any generator. It is very easy to solve this problem even for quite large $n$ – we need only a single modular division, i.e. one execution of the extended euclidean algorithm. (And if the generator is fixed, we even can calculate its multiplicative inverse once and reuse it later, then it gets down to one multiplication per problem.)

The multiplicative group of the prime fields is harder. There is no known polynomial time algorithms, but there are still algorithms faster than the generic ones, using subexponential time. (Yes, there is some gap between exponential and polynomial.) The number field sieve for factoring integers can actually also be used to calculate discrete logarithms in prime groups (and needs similar running time for similar input sizes of both problems).

Thus we need larger prime field groups than we would need for a generic group for a same "security level".

For some elliptic curves, it looks like the discrete logarithm is almost as hard as for a generic group of the same size, which means that there are no specialized algorithms which are much faster than the generic ones. (When there are, one calls the corresponding group "broken". )

The effect is that for a similar security level, we can use quite smaller elliptic curve groups than prime groups (and it turns out that for these smaller groups, the calculation is also faster).


On the other hand, have a look at the RSA problem. It is about this:

Given $n$ (a product of two large unknown primes), $e$ (with $\operatorname{gcd}(m,e) = 1)$ and $x < n$, we look for $m$ such that $x = m^e \bmod n$.

The most efficient known method to solve this (other than maybe a brute force attack on $m$ when it comes from a small sub space) is by factoring the modulus, then calculating the private key $d$ and decrypt it. So the hard problem here is factoring the modulus.

It is not really clear how to generalize this to any group (or what other kind of structure). I found A semantically secure elliptic curve RSA scheme with small expansion factor (2002), and it refers to (and includes an description of) an earlier work (N. Demytko. A new elliptic curve based analogue of RSA. EUROCRYPT ’93, LNCS 765 40–49 (1993).)

Demytko's scheme works on an elliptic curve (and its twists) over the ring $\mathbb Z/n\mathbb Z$ (where $n$ is still a product of two large primes), and encrypts using $c = e \star m$, which is the $x$-coordinate of $e·(m,y)$ for some $y$ such that this is on the curve, and decrypts a ciphertext $c$ as $m = d \star c$, where $d$ is one of four inverses of $e$, and it depends on $c$ which one to use.

The second one even works in a curve over $\mathbb Z/n^2 \mathbb Z$ (but claims to be semantically secure, as it incorporates a random component).

In both cases it looks like the easiest way to break this is to factor $n$ (in the natural numbers), not some analogous problem in an elliptic curve based structure.

This means $n$ must be just as large as for RSA, and thus we have correspondingly large curves – not really an advantage of using elliptic curves here.

$\endgroup$
2
  • 8
    $\begingroup$ Or shorter, if Elliptic Curves are used within the RSA problem then the key size needs to be as large as the traditional RSA key size, thus negating the size and time advantages of Elliptic Curve cryptography. Or was that stated too simply? $\endgroup$
    – Maarten Bodewes
    Oct 6, 2012 at 10:40
  • 1
    $\begingroup$ Great answer! One question that comes from your answer. Are there other groups that we know of (besides groups based on elliptic curves) which can be used and still gain this advantage? $\endgroup$
    – mikeazo
    Oct 9, 2012 at 12:46

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.