Introduction to public-key cryptography

In this chapter we introduce the basic building blocks for cryptography based on the discrete logarithm problem that will constitute the main motivation for considering the groups studied in this book. We also briefly introduce the RSA cryptosystem as for use in practice it is still an important public-key cryptosystem. Assume a situation where two people, called Alice and Bob in the sequel (the names had been used since the beginning of cryptography because they allow using the letters A and B as handy abbreviations), want to communicate via an insecure channel in a secure manner. In other words, an eavesdropper Eve (abbreviated as E) listening to the encrypted conversation should not be able to read the cleartext or change it. To achieve these aims one uses cryptographic primitives based on a problem that should be easy to set up by either Alice, or Bob, or by both, but impossible to solve for Eve. Loosely speaking, infeasibility means computational infeasibility for Eve if she does not have at least partial access to the secret information exploited by Alice and Bob to set up the problem. Examples of such primitives are RSA, cf. [PKCS], which could be solved if the integer factorization problem was easy, i.e., if one could find a nontrivial factor of a composite integer n, and the discrete logarithm problem, i.e., the problem of finding an integer k with [k]P = Q where P is a generator of a cyclic group (G,¿) and Q ¿ G. These primitives are reviewed in Sections 1.4.3 and 1.5. They are applied in a prescribed way given by protocols. We will only briefly state the necessary problems and hardness assumptions in Section 1.6 but not go into the details. Then we go briefly into issues of primality proving and integer factorization. The next section is devoted to discrete logarithm systems. This is the category of cryptographic primitives in which elliptic and hyperelliptic curves are applied. Finally, we consider protocols, i.e., algorithms using the cryptographic primitive to establish a common key, encrypt a message for a receiver, or sign electronically.