Introduction to Cryptography

Cryptography is the science of keeping secrets secret. Assume a sender referred to here and in what follows as Alice (as is commonly used) wants to send a message m to a receiver referred to as Bob. She uses an insecure communication channel. For example, the channel could be a computer network or a telephone line. There is a problem if the message contains confidential information. The message could be intercepted and read by an eavesdropper. Or even worse, the adversary, as usual referred to here as Eve, might be able to modify the message during transmission in such a way that the legitimate recipient Bob does not detect the manipulation.

Symmetric-key encryption schemes provide secure communication for a pair of communication partners. An adversary who intercepts a message should not get any significant information about its content. In this chapter, we give a short introduction to symmetric-key encryption. We explain the notions of stream and block ciphers. The operation modes of block ciphers are studied and, as a prominent example for block ciphers, the DES is described.

The basic idea of public-key cryptography are public keys. Each person’s key is separated into two parts: a public key for encryption available to everyone and a secret key for decryption which is kept secret by the owner. In this chapter we introduce the concept of public-key cryptography. Then we discuss some of the most important examples of public-key cryptosystems, such as the RSA, ElGamal and Rabin cryptosystems. These all provide encryption and digital signatures.

One of the major contributions of modern cryptography is the development of advanced protocols providing high-level cryptographic services, such as secure user identification, voting schemes and digital cash. Cryptographic protocols use cryptographic mechanisms — such as encryption algorithms and digital signature schemes — as basic components.

Probabilistic algorithms are important in cryptography. On the one hand, the algorithms used in encryption and digital signature schemes often include random choices (as in Vernam’s one-time pad or the DSA) and therefore are probabilistic. On the other hand, when studying the security of cryptographic schemes, adversaries are usually modeled as probabilistic algorithms The subsequent chapters, which deal with provable security properties, require a thorough understanding of this notion. Therefore, we clarify what is meant precisely by a probabilistic algorithm, and discuss the underlying probabilistic model.

In Chapter 3 we introduced the notion of one-way functions. As the examples of RSA encryption and Rabin signatures show, one-way functions play the key role in asymmetric cryptography.

Let f: X → Y be a bijective one-way function and let x ∈ X. Sometimes it is possible to compute some bits of x from f (x) without inverting f. A function f does not necessarily hide everything about x, even if f is one way. Let b be a bit of x. We call b a secure bit of f if it is as difficult to compute b from f (x) as it is to compute x from f (x). We prove that the most-significant bit of x is a secure bit of Exp, and that the least-significant bit is a secure bit of RSA and Square.

There is a close relationship between encryption and randomness. The security of encryption algorithms usually depends on the random choice of keys and bit sequences. A famous example is Shannon’s result. Ciphers with perfect secrecy require randomly chosen key strings, which are of the same length as the encrypted message. In Chapter 9, we will study the classical Shannon approach to provable security, together with more recent notions of security. One main problem is that truly random bit sequences of sufficient length are not available in most practical situations. Therefore, one works with pseudorandom bit sequences. They appear to be random, but actually they are generated by an algorithm. Such algorithms are called pseudorandom bit generators. They output, given a short random input value (called the seed), a long pseudorandom bit sequence. Classical techniques for the generation of pseudorandom bits or numbers (see [Knuth98]) yield well-distributed sequences. Therefore, they are well-suited for Monte Carlo simulations. However, they are often cryptographically insecure. For example, in linear congruential pseudorandom number generators or linear feedback shift registers (see, e.g., [MenOorVan96]), the secret parameters and hence the complete pseudorandom sequence can be efficiently computed from a small number of outputs.

This chapter deals with provable security. It is desirable that mathematical proofs show that a given cryptosystem resists certain types of attacks. The security of cryptographic schemes and randomness are closely related. An encryption method provides secrecy only if the ciphertexts appear sufficiently random to the adversary. Therefore, probabilistic encryption algorithms are required. The pioneering work of Shannon on provable security, based on his information theory, is discussed in Section 9.1. For example, we prove that Vernam’s one-time pad is a perfectly secret encryption. Shannon’s notion of perfect secrecy may be interpreted in terms of probabilistic attacking algorithms, which try to distinguish between two candidate plaintexts (Section 9.2). Unfortunately, Vernam’s one-time pad is not practical in most situations. In Section 9.3, we give important examples of probabilistic encryption algorithms that are practical. One-way permutations with hard-core predicates yield computationally perfect pseudorandom bit generators (Chapter 8), and these can be used to define “public-key pseudorandom one-time pads”, by analogy to Vernam’s one-time pad: the plaintext bits are XORed with pseudorandom bits generated from a short, truly random (one-time) seed. More recent notions of provable security, which include the computational complexity of attacking algorithms, are considered in Section 9.4. The computational analogue of Shannon’s perfect secrecy is defined. A typical security proof for probabilistic public-key encryption schemes is given. We show that the public-key one-time pads, introduced in Section 9.3, provide computationally perfect secrecy. Finally, a short introduction to some results of the “unconditional security approach” is given in Section 9.5. In this approach, the goal is to design practical cryptosystems which provably come close to perfect information-theoretic security, without relying on unproven assumptions about problems from computational number theory.

In previous sections we discussed signature schemes (PSS and PSS-R in Section 3.4.3; the Fiat-Shamir signature scheme in Section 4.2.5) that include a hash function h and whose security can be proven in the random oracle model. It is assumed that the hash function h is a random oracle, i.e. it behaves like a perfectly random function. More precisely, this means that the map h: X → Y is randomly chosen from the set F(X, Y) of all functions from X to Y. In general,.F(X, Y) is tremendously large. For example, if X = {0, 1} ⁿ and Y = {0, 1} ^k , then \(\left| F(X,Y) \right|={{2}^{k{{2}^{n}}}}\) Thus, it is obvious that perfectly random oracles cannot be implemented. To construct hash functions which approximate a random oracle, or to prove that a hash function comes close to a random oracle, appears to be very hard. Security in the random oracle model might not in all cases imply the security of the implemented scheme (see [CanGolHal98]). Therefore, it is desirable to have signature schemes whose security can be proven solely under standard assumptions (like the RSA or the discrete logarithm assumption). Examples of such signature schemes are given in this chapter.

Public-key cryptosystems are based on modular arithmetic. In this section, we summarize the concepts and results from algebra and number theory which are necessary for an understanding of the cryptographic methods. Textbooks on number theory and modular arithmetic include [HarWri79], [IreRos82], [Rose94], [Forster96] and [Rosen2000]. This section is also intended to establish notation. We assume that the reader is familiar with the elementary notions of algebra, such as groups, rings and fields.

We review some basic notions and results using in this book concerning probability, probability spaces and random variables. This chapter is also intended to establish notation. There are many textbooks on probability theory, including [Bauer96], [Feller68], [GanYlv67], [Gordon97] and [Rényi70].