2 Cryptography

Historically, cryptography was placed in the realm of espionage, diplomacy, and warfare. Etymologically, the name goes back to the Greek words kryptos (κρυπτoζ , hidden) and graphein (γραφϵιν,writing). Although some people considered the mathematics of devising and breaking codes, for a long time it remained a discipline on the fringe of mathematics. Several things changed this view. During the Second World War, sophisticated mathematical techniques were developed to break the Enigma code of the German forces. The following Cold War and the widespread usage of computers and the advent of the Internet led to the need of sending financial and other sensitive information over public channels. This sparked an intensive development in mathematical cryptography, both symmetric and public key. Besides the classical intention of protecting messages and data against unauthorized reading, cryptography has nowadays a much wider range of applications. These include digital signatures and electronic obligations. A digital signature is to be thought of as an analog of a written signature but for electronic or digital messages. Digital commitments are a common component in many cryptographic protocols. They allow a decision to be fixed, but it is only revealed at some later time; however, changing your mind is impossible.

Applications of cryptography include the protection of privacy in e-mail conversations, secure online banking, Internet shopping, electronic voting, digital money remittance, dated stamps, and secret sharings among several people. The study of cryptography also includes methods to attack and to break encrypted systems (cryptanalysis) as well as (more or less) open codes. The latter has no sharp borderline with slang or jargon. The typical example for this is French argot, originally spoken by thieves to prevent outsiders from understanding their conversations. Nowadays, argot plays a role of jargon without a primary intention of secrecy.

Cryptography also provides mental exercises, often in the form of puzzles; for example, the following correspondence between Frederick the Great (1712–1786) and Voltaire (1694–1778) has been handed down. Frederick the Great sent the following message to Voltaire:2

The scheme is described in Figure 2.1. We note that, in the context of cryptography, source encoding (i.e., data compression) does not have the aim of data compaction but rather the removal of redundancies. In order to not leak any information about the original text (for instance whether or not it is highly compressible), one can append some random data before encryption; this has the additional good property that the same message is never encrypted in the same way.

2.1 Symmetric encryption methods

A classical symmetric cryptographic system (or symmetric cryptosystem for short) uses the same keys for encryption and decryption. It consists of the following components:

It is also common to use the term encryption function for the encoding function and, similarly, decryption function for the decoding function. For the purpose of illustration, we usually consider a communication between two persons A and B, named Alice and Bob. One reason for these names is that “she” always refers to the person A while “he” always refers to B. Sometimes we need more people in the examples, for example, the opponent Oscar. Whenever Alice and Bob use a symmetric cryptosystem, they must agree on a secret key k. Typically, the length of k ∈ K is much smaller than that of the transmitted message, so we can put some effort into transferring k. Even more important, the transfer of k can be separated in space and time from the encrypted transmission of the message. In the following, we discuss some basic aspects of symmetric cryptosystems; for a more detailed exposition we refer to [4, 14]. In our investigation of symmetric cryptosystems, we generally assume that initially only Alice and Bob know the key k. We should realize that there are several ways to compromise a cryptographic communication:

Generally, when investigating the possible types of attack, our conservative assumption is that the attacker at least knows the cryptographic systems being used. This assumption is known as Kerckhoffs’ principle (named after Auguste Kerckhoffs, 1835–1903). In the following, we will distinguish between different cases with respect to

Oscar’s knowledge and abilities:

Ciphertext-Only: Oscar only knows ciphertexts.

Known-Plaintext: Oscar knows pairs of plain and ciphertexts.

Chosen-Plaintext: Oscar is able to have selected texts encrypted.

Chosen-Ciphertext: Oscar is able to have ciphertexts decrypted.

Since attack and defense are usually closely related, we can similarly characterize the levels of security against attacks by opponents with mere knowledge of the encrypted message:

Perfect or absolute security: Decryption is provably impossible regardless of the applied effort.

Computational security: Decryption requires efforts that are provably infeasible in practice.

Relative computational security: Decryption is not easier than the solution of a problem which is generally considered to be hard.

Pragmatic security: Despite intensive efforts, no efficient method for decryption is known. In short, the encryption method “appears to be secure.”

In practice, classic cryptography is based on pragmatic security. The problem with this approach, however, is that the encryption methods are often easier to break than expected.Moreover, security depends on the honesty of the creator, but the creator might hide some “trapdoor” within the cryptosystem. This trapdoor might be not obvious, but it might be included intentionally to allow a restricted possibility of breaking the code.

2.2 Monoalphabetic cipher

Monoalphabetic substitutions belong to the earliest and simplest cryptographic methods. The set of letters is identified with the elements of the ring ℤ/26ℤ. For simplicity, we omit special and capital letters.

Now, symbols can be added and subtracted modulo 26. So let X = Y = K = {a, . . . , z}. Then the shift cipher is given by c(x, k) = x + k mod 26 and d(y, k) = y − k mod 26.

The special case k = 3 is known as Caesar’s cipher because it reportedly was used by Julius Caesar (100–44 BC). Here is an example

The encoding is given in the upper line and the plaintext is in the lower one. The plaintext refers to a Latin phrase in which Laocoön warns the Trojans not to accept the gift from the Greek: the Trojan Horse. Due to the linear number of keys (here 26), a bruteforce attack on a shift cipher is simple. This type of coding is a special case of permuting the alphabet. The general idea is to allow all permutations of the alphabet as keys. These are the monoalphabetic substitutions and there is an enormous number of them: 26! ≈ 4 × 1026. If one was able to test a million keys per second, an exhaustive search would take more than 1013 years. This is much longer than the age of the Universe which is currently estimated to be about 13.8 × 109 years old, dating from the Big Bang. Exhaustively searching for the key of a monoalphabetic substitution is impossible, so other methods are used, like frequency analysis, which use the fact that, in natural language, letters have a characteristic frequency.

A nice presentation of a substitution encryption can be found in the short story The Gold-Bug by Edgar Allan Poe (1809–1849), published in 1843. The story is about Legrand’s search for the treasure of Captain Kidd where the following coded message plays a central role:

The chief character Legrand infers from the name “Kidd” that the plaintext is written in English. Then, he identifies the following frequencies of the occurring symbols:

He correctly conjectures that 8 codes the most common letter e. Then, Legrand looks for a possible encoding of the word “the” for which “;48 ” looks promising. After the last “;48” one finds “;(88.” From“;(88” he reconstructs the word “tree.” By further considerations, one can eventually reconstruct the full table of the decoding function.

This yields the following plaintext in a readable form with spacing and special characters:

With a telescope (here good glass) you can see the place almost before your eyes when sitting in the Bishop’s hostel.

2.3 Polyalphabetic cipher

As mentioned above, monoalphabetic substitution can be broken by frequency analysis. That is, one can exploit the frequency of individual symbols in order to decode the text. One idea to prevent such an attack is to periodically use different shifts of the alphabet.

This is the so-called Vigenère cipher (Blaise de Vigenère, 1523–1596). Keys in this method are words over the alphabet ℤ/26ℤ. For encryption, we first choose a fixed word k = k0 ⋅⋅ ⋅ kd−1 with ki ∈ ℤ/26ℤ. Then, we encrypt our plaintext x = x0 ⋅⋅ ⋅ xn−1 by c0(x0) ⋅⋅ ⋅ cn−1(xn−1) using the encryption function:

Poe’s text from The Gold-Bug encrypted with the Vigenère cipher using the key k = gold then becomes

Counting the frequencies of the symbols in the ciphertext yields:

In comparison to monoalphabetic substitutions, we see a much more uniform distribution of the symbols and, moreover, there are no longer any telltale combinations like “th.”

For a long time, this method was considered invulnerable because a frequency analysis is not (directly) applicable. But the problem arises that repeatedly appearing pieces in the text are encrypted equally, whenever the distance between them is a multiple of the key length d. Let us once again have a look at the above example in order to illustrate the problem.

Here, we see that the word “the” in the fourth line is encrypted by “hsh” twice.

Under the assumption that the key length or a multiple of it is known, we can break the Vigenère cipher as follows. Let the known key length (or multiple of it) be denoted by d. We perform frequency analysis by column, that is, we record d columns in such away that column i includes all encoded symbols whose position is congruent to i modulo d. Now, all characters in a column are encoded by the same symbol, and we can attack the encryption of each column via brute force, frequency analysis, or the like.

As a first step to protect against this kind of attack, we should keep the key length d secret. In fact, there are more relatively simple methods to hamper attacks by frequency analysis. One such possibility is lossless data compression (often referred to as source encoding). Because of the included elimination of redundancy, a compressed text appears as a random string; all symbols have roughly the same frequency. In order to not leak any information due to the compression ratio, augmenting a sufficient amount of random bits after compression is recommended.

2.4 Frequency analysis and coincidence index

We have already seen the frequency analysis method, whichwe used to break monoalphabetic substitutions. Now we extend this method. We have seen how to break the Vigenère cipher using frequency analysis if the key length, or a multiple thereof, is known. The attack by the coincidence index now just tries to determine a multiple of the key length. Let x = x1 ⋅⋅ ⋅ xn and be two texts of length n over the alphabet Σ. The according coincidence index κ(x, x) is defined to be

Here, δ is the so-called Kronecker delta (Leopold Kronecker, 1823–1891), defined as follows:

The coincidence index measures the relative frequency of coincidence of the same symbol in the same position in the texts x and x. If we assume x and x' to be chosen from a uniform distribution, then we obtain where E denotes the expected value and N = |Σ| the alphabet size. If the symbols are not distributed uniformly, then the probability for a match increases. Thus, for random texts on an arbitrary distribution of symbols, we obtain

In the concrete case of an alphabet with N = 26 uniformly distributed symbols, we obtain the value E [κ] = 3.8%. In experiments with natural language texts from the same language, an expectation of E [κ] ≈ 7% is obtained, a significantly higher value than in the random case above. An important fact for substitution ciphers, however, is that the coincidence index of two texts does not change when both are encoded with the same encryption key

Now we want to take advantage of this fact to determine d. Let the ciphertext y be given. Then, at first for ℓ ∈ ℕ, we determine the value κℓ = κ(y, σℓ(y)), where σℓ(y) is the cyclic shift of y by ℓ symbols to the left. If the value ℓ is a multiple of d, then κℓ measures the coincidence of two natural texts encrypted with the same key. Thus, we expect κℓ to be in the range of 7%; otherwise, the value will be less. Here is an example to illustrate this technique.

The text from “The Gold-Bug” has length n = 203. If y is the Vigenère encryption of this text with the secret key gold, then

As described above, the local maxima are probably the key length or multiples thereof; here, peaks at ℓ = 4, 8, 12 give strong hints on d = 4.

An attack using the coincidence criterion is also feasible for more general polyalphabetic substitutions. Thus, a polyalphabetic substitution is easy to attack. Nevertheless, this encryption method is still relevant today. For example, commercial software with this method is still available, and for cell phones in the United States, this method with a key length of 160 bits is the only approved one.

2.5 Perfect security and the Vernam one-time pad

Perfectly secure encryption methods have been known at least since 1918, and shortly thereafter they were in use. Nevertheless, the term perfect security was only precisely defined mathematically by Claude Elwood Shannon (1916–2001) [96]. Following his definition, an encryption is perfectly secure if the probability for the occurrence of a ciphertext y is independent of the plaintext x. In other words, the conditional probability Pr[y | x] has to be equal to Pr[y]. In this case, the occurrence of a ciphertext does not provide any information about the plaintext x. It should be noted that certain aspects of information are not covered by this model; for example, some facts about the message cannot be hidden from Oscar, such as when the message was sent, how big the message is, or who sent and who received the message.

In principle, it is very easy to design an abstract cryptosystem which is perfectly secure. Let X be a set of texts and let texts x ∈ X occurwith probability Pr [x] > 0. Alice and Bob choose a finite group G to be the set of ciphers Y as well as the set of keys K. The group G is public, but it has to be large enough that we can embed X as a subset in G. Bob chooses a secret key k ∈ G uniformly at random. Then he communicates the key k to Alice over a secure channel. For example, Alice and Bob meet personally before the decision about the text x is taken. WhenBob intends to inform Alice about x, he sends the product y = xk over a public channel. Alice recovers x by computing x = yk−1. The probability for each ciphertext y is now Pr[y] = Σx Pr[x−1y] Pr[x] = 1/|G| and thus independent of x ∈ X. The problem is that an observer Oscar knows y and perhaps later, for example, from Alice’s reaction, he might know x as well. Knowing x and y reveals k. So, the key k is good for one time, only. (Even if Oscar does not know x, he could detect that the same message was sent again unless k is changed.)

An advantage is that the method is valid in any group that is large enough, so we are free to choose the group structure. A reasonable simplification is to demand k = k−1 for all k ∈ G because then no inverses have to be computed and encryption and decryption methods are identical. Now k = k−1 is equivalent to k2 = 1. So we can, for example, choose G = (ℤ/2ℤ)n for n ∈ ℕ with log2 |X| < n. The elements of G are then the bit strings y ∈ n = {0, 1}n and the group operation is the bitwise exclusive-or ⊕. Therefore, encryption and decryption in this case can be performed very efficiently. For this special case, we obtain the cryptosystem using the so-called Vernam one-time pad by Gilbert Vernam (1890–1960) who published it in 1918 and had it patented shortly thereafter. It is an encryption scheme with a “one-time key” because, for each message x, a new key must be chosen to guarantee the security. One can view the Vernam one-time pad as a generalization of the Vigenère cipher. The subjects of encryption are bit sequences of length n. Here, X ⊆ n = Y = K. Encryption and decryption using the key k ∈ n then work as follows:

From the above discussion, it is clear that one-time encryption with the Vernam one-time pad is perfectly secure. But this guarantee is lost if the key is used twice. This is why the scheme is called a one-time pad. As noted above, an attacker can determine the key in a known-plaintext scenario: knowing a plaintext x and its corresponding ciphertext c(x, k) the attacker can compute the key k by x ⊕ c(x, k) = x ⊕ x ⊕ k = k.

A Vernam one-time pad is used whenever perfect security is required so that the efforts of key generation and transmission become secondary issues.3A major problem is that the number of different keys is not smaller than that of the plaintexts. So, if we can transmit the key secretly, why can we not simply use this transmission for x instead? The point is that the key generation is completely decoupled from the text: Alice and Bob can agree on k in advance, before x is fixed. The difficulty due to the large number of keys cannot be avoided by the next theorem.

Theorem 2.1. Let X denote a set of texts with Pr[x] > 0 for all x ∈ X, let K be a set of keys, and suppose that the ciphertexts Y satisfy Pr[y] > 0 for all y ∈ Y. If the underlying cryptosystem is perfectly secure, then |X| ≤ |Y| ≤ |K|.

Proof: First, for each key k ∈ K, the encoding function x ↦ c(x, k) is an injective mapping from X to Y, which implies |X| ≤ |Y|. Then, because of the perfect security property, for a fixed x0 ∈ X and each y ∈ Y, there has to be a key k ∈ K with y = c(x0, k). Otherwise, we have Pr[y | x0] = 0 ≠ Pr[y], contradicting the perfect security property. Therefore, k ↦ c(x0, k) is a surjective mapping from K to Y and thus |K| ≥ |Y|.

□

With a large number of keys, a design for a uniformly distributed random key selection is not obvious. Theorem 2.1 shows that the key length cannot be reduced without sacrificing perfect security. Nowwe can show that the uniform distribution is also essential if the key generation is independent of the text. Therefore, we must not rely on the so-called pseudo-random generators in the key generation for the Vernamone-time pad, or the system is not perfectly secure anymore.

Theorem 2.2. Let |X| = |Y| = |K| such that Pr[x] > 0 for all x ∈ X. If keys are chosen independently of plaintexts, then the following statements are equivalent:

Proof: From Pr[k] = 1/|K|, we obtain Pr[y | x] = Pr[kxy | x] = Pr[kxy] = 1/|K|, and then Pr[y] = ΣxPr[x] Pr[y | x] = (ΣxPr[x])/|K| = 1/|K|. Thus, the cryptosystem is perfectly secure. Conversely, let Pr[y] = Pr[y | x]. Suppose that c(x, k1) = y = c(x, k2) for two different keys k1, k2 ∈ K. Then, since |K| = |Y|, there exists some ciphertext y' ∈ Y such that there is no k ∈ K with c(x, k) = y'. Thus, Pr[y'] = Pr[y' | x] = 0, a contradiction to |X| = |Y|. Therefore, for every x and every y there exists a unique key kxy ∈ K with c(x, kxy) = y. Similarly, for every key k ∈ K and every cipher y ∈ Y, there exists a unique x ∈ X with k = kxy. This yields Pr[k] = Pr[kxy] = Pr[y | x] = Pr[y]. In particular, we have Pr[k1] = Pr[y] = Pr[k2] for all k1, k2 ∈ K. Consequently, Pr[k] = 1/|K| for all k ∈ K.

□

2.6 Asymmetric encryption methods

The cryptosystems considered so far are symmetric, as they use the same key for encryption and decryption. Therefore, before the communication, Alice and Bob need to agree on a key which is unknown to an attacker. For a key exchange, Alice andBob can, for example, meet in a café and exchange the key personally. Back home again, they can exchange messages over an insecure channel with the help of the key. But what is to be done when no café is available at the right time?

The problem can be solved by using different keys for encryption and decryption, which leads to the concept of asymmetric cryptosystems. The idea was first published in 1976 by Diffie and Hellman. Alice uses two keys for the communication. The first one is a public key that is made visible to anyone. However, the second key is private and secret, known solely to Alice. If Bob wants to send a message to Alice, he uses her public key for encryption. Alice in turn uses her private key to decrypt Bob’s message. This scheme elegantly solves the problem of key exchange because the communicated key is Alice’s public key, but nothing else. This is why the method is also called a public-key cryptosystem. Even if Oscar eavesdrops on the conversation, his only possibility is to decode Bob’s message based on the public key and the ciphertext. Therefore, methods of this kind have to be designed in such a way that this attack by Oscar cannot be performed efficiently. The problem is that we hardly know any way to prove such a statement rigorously. In public-key cryptography, you have to be content with relative computational security or even with pragmatic security.

There is another danger: Oscar pretends to be Alice by exchanging his public key with hers. Then he may receive and decrypt messages that were meant for Alice. This scenario is often referred to as man-in-the-middle attack. In Section 2.12, we present a method for Alice to label her key with some kind of signature to prevent these attacks.

The main goal in public-key cryptography is to ensure that Oscar is not able to determine the original message from the ciphertext along with the public key. One relies on relative computational security for this, meaning that Oscar could decrypt messages in principle, but his resources in time or energy, according to our current knowledge, are not sufficient to do so. Therefore, public-key systems are based on a computational problem which is believed to be not efficiently solvable from a practical point of view. We consider the following asymmetric encryption methods:

RSA: This is probably the best known and most successful asymmetric method. It is based on the factorization of large integers.

Rabin: This is related to the Rivest–Shamir–Adleman (RSA) system and it also relies on integer factorization.

Diffie-Hellman: The method is not directly designed for encryption, but it is a method of exchanging keys for symmetric cryptosystems. Its security is based on the computation of discrete logarithms.

ElGamal: This cryptosystem is related to the Diffie–Hellman key exchange. Its security is also based on the discrete logarithm.

Merkle–Hellman: It is based on the NP-complete knapsack problem. However, Shamir was able to show that it is not secure. We present Shamir’s attack at the end of this chapter.

Even though it is widely believed that the factorization of large numbers and the discrete logarithm problem cannot be solved efficiently, no proof is known for these conjectures. Therefore, we are always interested in new cryptosystems based on different computational problems: for instance, group-based cryptography uses non-commutative groups as a platform and algebraic operations like conjugacy to design cryptographic schemes. So far, theses schemes have not fulfilled initial promises and, at present, practical applications are rare. This might drastically change if simple schemes like RSA become insecure due to more efficient factorizations algorithms.

2.7 RSA cryptosystem

The best-known public-key encryption method is RSA. It is named after the last names of its inventors Ronald Linn Rivest (born 1947), Adi Shamir (born 1952), and Leonard Adleman (born 1945). In RSA, Alice chooses two distinct primes p and q and computes the product n = pq. Next, Alice computes two numbers e, s ≥ 3 such that es ≡ 1 mod (p−1)(q−1). Typically, Alice chooses e, say e = 17 in case that 17 ∤ φ(n), and then she computes s using the extended Euclidean algorithm. A small number e, like e = 17, is not a problem as long as we take care that no message x is encrypted with xe ≤ n. However, the number s should be large; otherwise, the private key (n, s) is insecure due to an attack of Michael J.Wiener [110]. If s has less than one-quarter as many bits as the modulus n, then, in typical cases, this attack may discover the secret s. The public key is the pair (n, e); and encryption is done by x ↦ xe mod n. Alice decrypts by y ↦ ys mod n. Let y = xe mod n. If es = 1 + (p − 1)k, then

by Fermat’s little theorem. Analogously, one can show that ys ≡ x mod q. In other words, both p and q divide ys − x. Since p and q are coprime, n = pq divides ys − x and, hence, we have ys ≡ x mod n. If x ∈ {0, . . . , n − 1}, then we obtain ys mod n = x. Thus, every encrypted message is decrypted correctly.

In Chapter 3, we show how to find large primes p and q (Section 3.4), what properties p and q should have in order to ensure that n cannot be factorized easily (Section 3.6), how xe mod n can be computed efficiently (Section 3.2), and that the number n can easily be factorized as soon as one knows the secret key s (end of Section 3.4.4). Since we assume that factorization cannot be done efficiently, this implies that the secret key is secure. However, it is not known whether the decryption of the RSA method is secure. It is conceivable that, even without the knowledge of s, an attacker could decrypt the ciphertext. It is not possible to unambiguously assign a secret key s to the decryption function. So one can determine s' by knowing the rule es' ≡ 1 mod lcm(p −1, q−1); since p −1 and q−1 are even, clearly lcm(p−1, q−1) < (p − 1)(q − 1). Consequently, y ↦ ys mod n and y ↦ ys' mod n define the same mappings on {0, . . . , n − 1}. But in general, s ≠ s. For example, y ↦ y23 mod 55 and y ↦ y3 mod 55 define the same mappings on {0, . . . ,54}; they satisfy 7 ⋅ 23 ≡ 1 mod 20 and 7 ⋅ 3 ≡ 1 mod 20.

One of the problems in RSA, and in many similar cryptosystems, occurswhen only a few messages are likely to be sent. Then Oscar simply encrypts all these messages with the public key (n, e). For each of these messages, he stores the pair consisting of plaintext and corresponding ciphertext. Later, if Oscar eavesdrops on a message encrypted by (n, e), he compares it to his list of messages. If the ciphertext occurs in his list, then he knows the corresponding plaintext. To prevent this type of attack, a sufficient amount of random bits is usually appended to each message. In practice, 128–256 random bits are considered to be secure. It can be useful to insert the random bits at various (fixed) positions of each message.

2.8 Rabin cryptosystem

In the Rabin cryptosystem (developed by Michael Oser Rabin, born 1931), a message is encrypted by squaring it in the quotient ring modulo n = pq for two large prime numbers p and q. The method was published in 1979. It should be noted that the decryption is ambiguous: indeed, if Bob sends the value y ∈ {0, . . . , n−1} to Alice, where x2 ≡ y mod n, then Alice finds four different square roots of y and she has to decide which is the correct one for x. The number of choices can be reduced to 2 by requiring the selection of x in the set because x2 ≡ (n − x)2 mod n. But this does not resolve ambiguity completely. This disadvantage is partly compensated by the fact that the decryption can be proved to be essentially as hard as the factorization of n. No such statement is known for RSA.

It is easy to put more assumptions on x so that the encryption is very likely to be unique. As a typical example, you can require the first k bits of a message to match the last k bits. However, with additional assumptions about the encrypted messages, the connection between the hardness of decryption and that of integer factorization may become more and more incoherent. It seems to be a principle dilemma with Rabin’smethod. Still, the mathematical and philosophical consequences are interesting enough to justify discussing the Rabin cryptosystem. The system works as follows:

To prove the correctness of the method, we have to show that one of the four possible values of z equals x. From x2 ≡ y mod n, we can conclude x2 ≡ y mod p and x2 ≡ y mod q. Since p and q are prime, each of the equations X2 ≡ y mod p and X2 ≡ y mod q has at most two solutions ±xp ∈ ℤ/pℤ and ±xq ∈ ℤ/qℤ, respectively. In particular, x satisfies x ≡ ±xp mod p and x ≡ ±xq mod q. By symmetry, it suffices to show that mod p, because then {−zp , +zp} = {−xp, +xp}. For p | y, nothing has to be shown. So let x, y ∈ (ℤ/pℤ)∗. From Fermat’s little theorem, we have mod p. This yields

and thus the correctness of the Rabin method.

As mentioned before, Alice has to be able to identify the original message x out of the four possible values for z. For this purpose, it is customary to limit the space of plaintexts in order to make it possible for Alice to choose the right one with high probability. Therefore, the first and the last k bits of a message x are often required to coincide; say k = 20 or k = 64.

If n can be factorized, then it becomes easy to decrypt a message y by performing the same steps as Alice does. However, an attacker does not have to proceed this way to decrypt y, but might be able to determine the original message x in an entirely different way. Suppose there is an efficient algorithm R such that, on input y ∈ { x2 | x ∈ ℤ/nℤ}, it computes R(y) with R(y)2 ≡ y mod n. The idea is that a potential attacker will use R for deciphering. We show that R can be used to factorize n. First, we choose x ∈ {2, . . . , n − 1} at random. If gcd(x, n) ≠ 1, then we have factorized n. So let gcd(x, n) = 1 and z = R(x2 mod n). There are four possibilities which are equally likely:

In each of the cases (b) and (c), the computation of gcd(x + z, n) yields a nontrivial factor of n, and gcd(x − z, n) gives the other factor of n. Therefore, we factorized n with a success probability of 1/2. The success probability can be increased arbitrarily by repeating this algorithm for several rounds. Therefore, if we can compute square roots modulo n, then we can factorize n. So, under the assumption that factorizing n is not possible, no attacker can have an algorithm for deciphering messages in the Rabin cryptosystem.

If we are using the variant where the first and the last k bits of x coincide, then an attacker only needs to have an algorithm R which, on input

computes R(y) with R(y)2 ≡ y mod n. In this setting, you still choose x ∈ {2, . . . , n − 1} at random (choosing x such that the first and the last k bits coincide is pointless since the result will be z = x); and you can assume that gcd(x, n) = 1. The element y = x2 mod n is in the domain of R with a probability in the order of magnitude of 2−k. Therefore, after expectedly 2k rounds, we find y in the domain of R and we can proceed with z = R(y) as before. Therefore, with increasing k, this reduction becomes increasingly loose. So, from a practical point of view, the reduction still works fork = 20, but it fails for k = 64. Some other reduction might work even for k = 64, but to date no such approach is known.

2.9 Diffie–Hellman key exchange

Consider the following scenario where Alice and Bob wish to establish an encrypted communication over the Internet. For efficiency reasons, they want to use a symmetric encryption method and thus they need a common secret key. Agreement on such a key can be performed securely and efficiently using the Diffie–Hellman key exchange (Bailey Whitfield Diffie, born 1944; Martin Edward Hellman, born 1945).

Alice and Bob agree on a prime number p and a number g mod p generating a sufficiently large subgroup of Since is cyclic, there are φ(p − 1) generators of Therefore, it is often required for g to generate the whole group For practical applications, however, a weaker assumption is sufficient. You can choose p such that p − 1 is divided by a large prime number q. For a randomly chosen value of g, we have g(p−1)/q ≢ 1 mod p with probability 1 − 1 /q. Thus, a random element g almost surely passes the test g(p−1)/q ≢ 1 mod p,where q is a divisor of the order of g. If g ∈ (ℤ/pℤ)∗ passes the test, then q divides the order of g.

Alice and Bob agree on the values of p and g. These need not be kept secret. So they may communicate via e-mail. Then Alice and Bob produce secret random numbers a and b in {2, . . . , p − 1}, respectively. Alice computes A = ga mod p and Bob B = gb mod p.NowAlicepubliclysends A to Bob, and Bob publicly sends B back to Alice. Since Ab ≡ gab ≡ Ba mod p, they can use the key K = (Ab mod p) = (Ba mod p) ∈ {1, . . . , p − 1} for their subsequent communication. For instance, they could use K as a secret key in some symmetric cryptosystem.

The following example uses very small numbers, in particular q = 11. In realistic applications, numbers with several hundred decimals are used.

Example 2.3. Alice and Bob agree on p = 23 and g = 5. Then, g2 ≡ 2 mod 23. Therefore, the order of g in (ℤ/23ℤ)∗ is at least 11. In fact, g generates (ℤ/23ℤ)∗ and thus its order is 22. Alice chooses (randomly) a = 6, Bob chooses b = 13. Alice computes A ≡ 56 ≡ 8 mod 23 andsends A = 8 to Bob. Bob in turn computes B ≡ 513 ≡ 21 mod 23 and sends B = 21 to Alice. Alice computes K = 216 mod 23 = 18. Bob computes K = 813 mod 23 = 18. Everyone may see the numbers 23, 5, 8, and 21, but the secret key K = 18 remains hidden.

◊

The security of this method depends on the difficulty of computing the discrete logarithm. In practice, very large primes are used. The prime number q is maximal with respect to p if q = (p−1)/2 is also a prime. In this case, q is called a Sophie Germain prime (Sophie Germain, 1776–1831), and g can be chosen to be 2. The values of p, g, A, B are known to any eavesdropper, but the Diffie–Hellman problem is to compute K. The Diffie–Hellman problem is solvable if the discrete logarithm a of A ≡ ga mod p or b ofB ≡ gb mod p can be computed. So far, no efficient algorithm for the Diffie–Hellman problem is known.

However, a third party Oscar could try to get between Alice and Bob, and then pretend to be Alice communicating with Bob, and to be Bob communicating with Alice, without them realizing that. To prevent this man-in-the-middle attack, Alice and Bob can provide signatures for all messages sent. Digital signatures are discussed in Section 2.12.

2.10 ElGamal cryptosystem

The ElGamal method was developed in 1985 by Taher ElGamal (born 1955) and is used for both digital signatures and encryption [40]. Like RSA, the ElGamal method is an asymmetric encryption algorithm using a public and a private key. While the security of the RSA algorithm is based on the fact that no efficient factorization algorithm is known, ElGamal uses the discrete logarithm problem. The basic idea is simple: multiply a message with the key obtained from the Diffie–Hellman key exchange. Again, a prime number p with a large prime factor q of p − 1 is needed. Typically, one first chooses q, a sufficiently large prime, and then checks primality of p = kq + 1 for some relatively small even number k.

If gk ≢ 1 mod p for g ∈ (ℤ/pℤ)∗, then q divides the order of g. A random element satisfies this property with a probability of 1 − 1 /q. Alice chooses a random number a ∈ {2, . . . , p − 2} as secret key and computes

The public key consists of the triple (p, g, A). The encryption of a message m by Bob to Alice is performed blockwise, so we can assume that the plaintext m is from the set {0, . . . , p − 1}. Bob chooses a random number b ∈ {2, . . . , p − 2} and computes

The ciphertext consists of the pair (B, c). Alice decrypts the text by multiplying c by Bp−1−a in p∗. This leads to the correct result

Example 2.4. Let p be the Sophie Germain prime 11 and g = 2. Let the secret key be a = 4. Alice publishes the triple (p, g, A) = (11, 2, 5). Bob wants to send the message m = 7 and has chosen b = 3 and thus B = 8. He computes c ≡ 53 ⋅ 7 ≡ 6 mod 11 and sends the pair (8, 6) to Alice. She obtains 86 ⋅ 6 ≡ 7 mod 11, which is the correct plaintext.

◊

A disadvantage of the ElGamal method is that the ciphertext is twice as long as the plaintext. Moreover, Bob needs to use a new random number b for each message m. Otherwise, Oscar can easily decrypt all messages as soon as he knows at least one pair of a plaintext and a ciphertext. If (B, c) and (B, c') are ciphertexts corresponding to messages m and m', respectively, and if Oscar knows (B, c) and (B, c') as well as m, he obtains m' ≡ mc−1c' mod p. Typically, secret messages do not remain secret very long. For example, Oscar may simply assume that the first message is Hello Alice.

In an analogous manner, ElGamal encryption can be done over any finite cyclic group. In particular, this can be done over a cyclic subgroup of an elliptic curve. Thus, it serves as the basis for elliptic curve cryptography (see, e.g., [5]). We discuss elliptic curves and their groups in Section 5.

2.11 Cryptographic hash functions

One of the applications of cryptographic hash functions is digital signatures, as described in the next section. In general, the alphabet in this section is' = {0, 1}; however, the concepts introduced here can be adapted to arbitrary finite alphabets. A hash function is a mapping

for n ∈ ℕ. A compression function is a mapping

for natural numbers m > n; so a hash function maps words of arbitrary length to words of fixed length n. A compression function is a function that maps words of a given length to words of a fixed smaller length. Neither hash functions nor compression functions are injective. To be able to efficiently use hash functions in cryptography, we require h(x) to be easily computable for all x. However, it is crucial that one cannot efficiently find an x for a given s ∈ n with h(x) = s. A mapping having these two properties is called a one-way function. From the current state of research it is not known whether one-way functions exist at all. Based on the principle of relative computational security, however, there are many mappings for which it is generally assumed that finding preimages is hard. A function where no efficient method for finding preimages is currently known, is the exponentiation in finite groups. Here, computing preimages means just solving the discrete logarithm problem; see Section 3.7.

A collision is a pair (x, x') such that h(x) = h(x') and x ≠ x'. A function h is called collision resistant if it is computationally hard to find a collision (x, x'). All hash and compression functions have collisions since they are not injective. Collision-resistant hash functions are one-way functions: if an algorithm can compute the preimage x of an image y, then one can randomly choose an x' and compute y = h(x') and some preimage x ∈ h−1(y). Now, (x, x') is a collision if x ≠ x'. The probability for this is high enough since f is far from being injective. Thus, if collisions cannot be computed efficiently, then preimages also cannot be determined efficiently.

An encryption function ck : n →n with key k ∈ n yields the following canonical compression functions g : 2n →n: