8
Elliptic Curves
In the previous chapter, we got some first insights into how public-key cryptography can solve the key distribution problem even if Alice and Bob have never met before. More specifically, we learned how public-key cryptosystems can be built on two well-known problems from number theory: the discrete logarithm problem and the integer factorization problem.
Even after studying these problems for centuries – integer factorization, for example, was first investigated by the ancient Greeks – there are no known polynomial-time algorithms for these problems - at least not on conventional, non-quantum computers. For the time being, we therefore consider them to be computationally secure.
Nevertheless, to be secure in practice, cryptosystems based on the computational hardness of integer factorization or the discrete logarithm problem must operate on huge numbers. As an example, to achieve a security level equivalent to a 128-bit block cipher, the RSA cryptosystem...