What motivated the creation of RSA and ECDH?

Question

Recently I've been learning about cryptography and so far I am loving it. However, there are some things I do not comprehend.

As far as I know, RSA was published in 1979 while New Directions on Cryptography by Diffie and Hellman was published in 1976. What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure? Or was it because it was designed for other purposes which couldn't be accomplished with Diffie-Hellman?

On the other hand, it was not until 1985 that Neal Koblitz proposed cryptography based on elliptic curves. I've been told that elliptic curves offer more security than classic Diffie-Hellman but I'd like to understand and know how. I don't know much about security level. I've seen expressions like "$n$-bit keys give $m$-bit security" but I do not fully understand what do they mean. I see that ECDH offers more bit security than DH, but how can that be measured if attacks for both are not the same?

Thank you! And don't worry about throwing some math, I will probably understand.

Answer 1

What I wonder is, what motivated the creation of RSA? Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure?

The New Directions In Cryptography paper introduced the idea of public-key cryptography (though it had been proposed by Merkle before), and public-key cryptography was intended to solve two major problems: The key distribution problem, and the problem of authentication which is now referred to as "digital signatures".

Besides the general excitement of an entire new field of research being opened up, one of the motivations for RSA was to define a primitive that solved both problems of key distribution (or public-key encryption) as well as digital signatures. This is actually easy to see from just the title of the original RSA paper: "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems".

Their paper explicitly states this (emphasis mine):

... This method provides an implementation of a “public-key cryptosystem,” an elegant concept invented by Diffie and Hellman. Their article motivated our research, since they presented the concept but not any practical implementation of such a system.

Was it because they wanted to create something more secure than Diffie-Hellman? And if so, why is it more secure?

So as you can see, the answer to this question is "no" - it was simply a matter of accomplishing the feat at all, in general. The question of a given amount of security for a given amount of efficiency doesn't arise until after you at least have working examples of the concept.

Or was it because it was designed for other purposes which couldn't be accomplished with Diffie-Hellman?

As shown in the previous quotation, yes. Though, the world would later develop techniques that allow public-key encryption and digital signatures without requiring a trapdoor function/permutation.

---

As for the second part of your question, this other answer attempts to go into detail.

But basically, Diffie-Hellman works (as in correctness is guaranteed) for any finite cyclic group, (only a semigroup is actually required as inverses and identities are not used). There are generic attacks that apply irrespective of the actual group that you use, but for a given group there might exist attacks that are more efficient than the generic attacks. In finite field Diffie-Hellman (e.g. classic or "regular" Diffie-Hellman) there are non-generic attacks that do not apply or not known to have equivalents in the elliptic curve setting.

Answer 2

Sadly I'd like to know an answer for your first question as well.

For your second question, you just need to see the difference between the description of a protocol and an actual instantiation of it (meaning, a cryptographic scheme). Diffie-Hellman is a cryptographic protocol, describing a way for two parties to exchange a common element in fixed ambient abelian finite group $G$, with cardinality $p$ (usually, a prime number). The security of DH will then be essentially defined as the smallest amount of operations in the group you can do to break the protocol. Brute forcing is the the most natural way to go: enumerate all possible solutions and you'll find the correct one. At worst, you will need to enumerate all $p$ elements. These guys are represented by binary strings of size $\log p$, so the computer will take $p = 2^{\log p}$ operations, an exponential number in the size of the input. If we cannot do better, then this protocol is "secure" and gives you $\log p$ bits of security. Take $p \approx 2^{128}$ and you have a 128-bits secure key-exhange... That is if you could not do better than brute-force.

Let's say you do not have any information about the said group $G$ apart from computing its group law and testing for equality (this is an informal way of saying that you consider your group as a generic group). Then the best way to recover the shared element if you're not one of the two parties is to solve a discrete logarithm problem in $G$: given $g$ a generator, and $h = g^x$, compute $x$. I hope not to be burnt alive by people noticing that DLP and ECDH are not exactly the same problem, but for the sake of this discussion, let's say they are.

It is known (a theorem by Shoup, or Nechaev if you can read russian) that you will need (at least) $\Omega(\sqrt p)$ group operations to compute $x$. In fact, there are well-known algorithms that run in $O(\sqrt{p})$ to do that: Big-step-Giant-steps, or $\rho$-Pollard style random walks. These algorithms are therefore optimal in the generic group "model", and you can see that they require exponential time in the size of the group elements. To achieve 128 bits of security, you would need a $256$ bits prime.

Now in real life, you will instantiate $G$ to some actual group. For example, you could chose $(\mathbb Z/p\mathbb Z, +)$. However, the DLP here is trivial to solve: it's essentially extended Euclid algorithm which runs in $O(\log^2 p)$: this is quadratic in the size of the group elements, therefore you will definitely not do crypto with this: your prime would need to be absurdly huge to guarantee 128 bits of security (and then all inputs would be of the size of this prime).

But you could also select the group of rational points of an elliptic curve defined over a prime field: this is commonly defined as ECDH. In this latter group, in the current state-of-the-art, we do not know a better algorithm that the ones I gave you in the generic model (apart from very special cases that are irrelevant nowadays since they can be avoided easily). In other words, the best known algorithms to solve ECDH run in exponential-time. So compared to, say, DH over $\mathbb Z/p\mathbb Z$, it "gives more security", but notice that this is relevant to the group, not the protocol itself.

There are other possible instantiations. Invertible of finite fields, elliptic curves over extension fields, more complicated algebraic groups. Elliptic curves give a very nice combination of efficiency and security.