This chapter introduces a number of cryptographic protocols and their underlying problems and algorithms. A typical cryptographic scenario is shown in Figure 7.1 (the design of Alice and Bob is due to Crépeau). Alice and Bob wish to exchange messages over an insecure channel, such as a public telephone line or via email over a computer network. Erich is eavesdropping on the channel. Knowing that their data transfer is being eavesdropped, Alice and Bob encrypt their messages using a cryptosystem.
In Section 7.1, various symmetric cryptosystems are presented. A cryptosystem is said to be symmetric if one and the same key is used for encryption and decryption. For symmetric systems, the question of key distribution is central: How can Alice and Bob agree on a joint secret key if they can communicate only via an insecure channel? For example, if Alice chooses some key and encrypts it like a message using a symmetric cryptosystem to send it to Bob, then which key should she use to encrypt this key?
This paradoxical situation is known as the secret-key agreement problem, and it was considered unsolvable for a long time. Its surprisingly simple, ingenious solution by Whitfield Diffie and Martin Hellman in 1976 is a milestone in the history of cryptography. They proposed a protocol that Alice and Bob can use to exchange a few messages after which they both can easily determine their joint secret key. Eavesdropper Erich, however, does not have clue about their key, even if he was able to intercept every single bit of their transferred messages. Section 7.2 presents the Diffie-Hellman secret-key agreement protocol.
It may be considered an irony of history that this protocol, which finally solved the long-standing secret-key agreement problem that is so important in symmetric cryptography, opened the door to public-key cryptography in which there is no need to distribute joint secret keys via insecure channels. In 1978, shortly after Diffie and Hellman had published their pathbreaking work in 1976, Rivest, Shamir, and Adleman developed their famous RSA system, the first public-key cryptosystem in the open literature. Section 7.3 describes the RSA cryptosystem and the related digital signature scheme. Using the latter protocol, Alice can sign her message to Bob such that he can verify that she indeed is the sender of the message. Digital signatures prevent Erich from forging Alice's messages.
The security of the Diffie-Hellman protocol rests on the assumption that computing discrete logarithms is computationally intractable. That is why modular exponentiation (the inverse function of which is the discrete logarithm) is considered to be a candidate of a one-way function. The security of RSA similarly rests on the assumption that a certain problem is computationally intractable, namely on the assumption that factoring large integers is computationally hard. However, the authorised receiver Bob is able to efficiently decrypt the ciphertext by employing the factorisation of some integer he has chosen in private, which is his private “trapdoor” information.
Section 7.4 introduces a secret-key agreement protocol developed by Rivest and Sherman, which is based on so-called strongly noninvertible associative one-way functions. This protocol can be modified to yield a digital signature scheme as well.
Section 7.5 introduces the fascinating area of interactive proof systems and zero-knowledge protocols that has practical applications in cryptography, especially for authentication issues. In particular, a zero-knowledge protocol for the graph isomorphism problem is presented. On the other hand, this area is also central to complexity theory and will be revisited in Chapter 8, again in connection to the graph isomorphism problem.
Cryptography is the art and science of designing secure cryptosystems, which are used to encrypt texts and messages so that they be kept secret and unauthorised decryption is prevented, whereas the authorised receiver is able to efficiently decrypt the ciphertext received. This section presents two classical symmetric cryptosystems. In subsequent sections, some important asymmetric cryptosystems and cryptographic protocols are introduced. A “protocol” is dialog between two (or more) parties, where a “party” may be either a human being or a computing machine. Cryptographic protocols can have various cryptographic purposes. They consist of algorithms that are jointly executed by more than one party.
Cryptanalysis is the art and science of (unauthorised) decryption of ciphertexts and of breaking existing cryptosystems. Cryptology captures both these fields, cryptography and cryptanalysis. In this chapter, we focus on cryptographic algorithms. Algorithms of cryptanalysis, which are used to break cryptographic protocols and systems, will be mentioned as well but will not be investigated in detail.
Figure 7.1 shows a typical scenario in cryptography: Alice and Bob communicate over an insecure channel that is eavesdropped by Erich, and thus they encrypt their messages using a cryptosystem.
1. , , and are finite sets, where is the plaintext space, is the ciphertext space, and is the key space. The elements of are called the plaintexts, and the elements of are called the ciphertexts. A message is a string of plaintext symbols.
2. is a family of functions , which are used for encryption. is a family of functions , which are used for decryption.
3. For each key , there exists some key such that for each plaintext ,
A cryptosystem is said to be symmetric (or private-key) if either or if at least can “easily” be determined from . A cryptosystem is said to be asymmetric (or public-key) if and it is “computationally infeasible” to determine the private key from the corresponding public key .
At times, we may use distinct key spaces for encryption and decryption, with the above definition modified accordingly.
We now introduce some easy examples of classical symmetric cryptosystems. Consider the alphabet , which will be used both for the plaintext space and for the ciphertext space. We identify with so as to be able to perform calculations with letters as if they were numbers. The number corresponds to the letter , the corresponds to , and so on. This coding of plaintext or ciphertext symbols by nonnegative integers is not part of the actual encryption or decryption.
Messages are elements of , where denotes the set of strings over . If some message is subdivided into blocks of length and is encrypted blockwise, as it is common in many cryptosystems, then each block of is viewed as an element of .
Example 7.1 [Shift Cipher] The first example is a monoalphabetic symmetric cryptosystem. Let . The shift cipher encrypts messages by shifting every plaintext symbol by the same number of letters in the alphabet modulo . Shifting each letter in the ciphertext back using the same key , the original plaintext is recovered. For each key , the encryption function and the decryption function are defined by:
where addition and subtraction by modulo are carried out characterwise.
Figure 7.2 shows an encryption of the message by the shift cipher with key . The resulting ciphertext is . Note that the particular shift cipher with key is also known as the Caesar cipher, since the Roman Emperor allegedly used this cipher during his wars to keep messages secret.
Footnote. Historic remark: Gaius Julius Caesar reports in his book De Bello Gallico that he sent an encrypted message to Q. Tullius Cicero (the brother of the famous speaker) during the Gallic Wars (58 until 50 B.C.). The system used was monoalphabetic and replaced Latin letters by Greek letters; however, it is not explicitly mentioned there if the cipher used indeed was the shift cipher with key . This information was given later by Suetonius.
This cipher is a very simple substitution cipher in which each letter is substituted by a certain letter of the alphabet.
Since the key space is very small, the shift cipher can easily be broken. It is already vulnerable by attacks in which the attacker knows the ciphertext only, simply by checking which of the possible keys reveals a meaningful plaintext, provided that the ciphertext is long enough to allow unique decryption.
The shift cipher is a monoalphabetic cryptosystem, since every plaintext letter is replaced by one and the same letter in the ciphertext. In contrast, a polyalphabetic cryptosystem can encrypt the same plaintext symbols by different ciphertext symbols, depending on their position in the text. Such a polyalphabetic cryptosystem that is based on the shift cipher, yet much harder to break, was proposed by the French diplomat Blaise de Vigenére (1523 until 1596). His system builds on previous work by the Italian mathematician Leon Battista Alberti (born in 1404), the German abbot Johannes Trithemius (born in 1492), and the Italian scientist Giovanni Porta (born in 1675). It works like the shift cipher, except that the letter that encrypts some plaintext letter varies with its position in the text.
Example 7.2 [Vigenére Cipher] This symmetric polyalphabetic cryptosystem uses a so-called Vigenére square, a matrix consisting of rows and columns, see Figure 7.3. Every row has the letters of the alphabet, shifted from row to row by one position. That is, the single rows can be seen as a shift cipher obtained by the keys . Which row of the Vigenére square is used for encryption of some plaintext symbol depends on its position in the text.
Messages are subdivided into blocks of a fixed length and are encrypted blockwise, i.e., . The block length is also called the period of the system. In what follows, the th symbol in a string is denoted by .
For each key , the encryption function and the decryption function , both mapping from to , are defined by:
where addition and subtraction by modulo are again carried out characterwise. That is, the key is written letter by letter above the symbols of the block to be encrypted. If the last plaintext block has less than symbols, one uses less key symbols accordingly. In order to encrypt the th plaintext symbol , which has the key symbol sitting on top, use the th row of the Vigenére square as in the shift cipher.
For example, choose the block length and the key . Figure 7.4 shows the encryption of the message , which consists of seven blocks, into the ciphertext by the Vigenére cipher using key . To the first plaintext letter, “H”, the key symbol “T” is assigned. The intersection of the “H” column with the “T” row of the Vigenére square yields “A” as the first letter of the ciphertext, see Figure 7.3.
There are many other classical cryptosystems, which will not be described in detail here. There are various ways to classify cryptosystems according to their properties or to the specific way they are designed. In Definition 7.1, the distinction between symmetric and asymmetric cryptosystems was explained. The two examples above (the shift cipher and the Vigenére cipher) demonstrated the distinction between monoalphabetic and polyalphabetic systems. Both are substitution ciphers, which may be contrasted with permutation ciphers (a.k.a. transposition ciphers) in which the plaintext letters are not substituted by certain ciphertext letters but go to another position in the text remaining otherwise unchanged.
Moreover, block ciphers such as the Vigenére system can be contrasted with stream ciphers, which produce a continuous stream of key symbols depending on the plaintext context to be encrypted. One can also distinguish between different types of block ciphers. An important type are the affine linear block ciphers, which are defined by affine linear encryption functions and decryption functions , both mapping from to . That is, they are of the following form:
Here, and are the keys used for encryption and decryption, respectively; is a matrix with entries from ; is the inverse matrix for ; , , and are vectors in , and all arithmetics is carried out modulo . Some mathematical explanations are in order (see also Definition 7.2 in Subsection 7.1.3): An matrix over the ring has a multiplicative inverse if and only if . The inverse matrix for is defined by , where is the determinant of , and is the adjunct matrix for . The determinant of is recursively defined: For and , ; for and each , , where denotes the entry of and the matrix results from by cancelling the th row and the th column. The determinant of a matrix and thus its inverse (if it exists) can be computed efficiently, see Problem 7-3.
For example, the Vigenére cipher is an affine linear cipher whose key contains the unity matrix as its first component. If in (7.2) is the zero vector, then it is a linear block cipher. A classical example is the Hill cipher, invented by Lester Hill in 1929. Here, the key space is the set of all matrices with entries in such that . This condition guarantees the invertibility of those matrices that are allowed as keys, since the inverse matrix is used for decryption of the messages encrypted by key . For each key , the Hill cipher is defined by the encryption function and the decryption function . Thus, it is the most general linear cipher. The permutation cipher also is linear, and hence is a special case of the Hill cipher.
Cryptanalysis aims at breaking existing cryptosystems and, in particular, at determining the decryption keys. In order to characterise the security or vulnerability of the cryptosystem considered, one distinguishes different types of attacks according to the information available for the attacker. For the shift cipher, ciphertext-only attacks were already mentioned. They are the weakest type of attack, and a cryptosystem that does not resist such attacks is not of much value.
Affine linear block ciphers such as the Vigenére and the Hill cipher are vulnerable to attacks in which the attacker knows the plaintext corresponding to some ciphertext obtained and is able to conclude the keys used. These attacks are called known-plaintext attacks. Affine linear block ciphers are even more vulnerable to chosen-plaintext attacks, in which the attacker can choose some plaintext and is then able to see which ciphertext corresponds to the plaintext chosen. Another type of attack is in particular relevant for asymmetric cryptosystems: In an encryption-key attack, the attacker merely knows the public key but does not know any ciphertext yet, and seeks to determine the private key from this information. The difference is that the attacker now has plenty of time to perform computations, whereas in the other types of attacks the ciphertext was already sent and much less time is available to decrypt it. That is why keys of much larger size are required in public-key cryptography to guarantee the security of the system used. Hence, asymmetric cryptosystems are much less efficient than symmetric cryptosystems in many practical applications.
For the attacks mentioned above, the method of frequency counts is often useful. This method exploits the redundancy of the natural language used. For example, in many natural languages, the letter “E” occurs statistically significant most frequently. On average, the “E” occurs in long, “typical” texts with a percentage of in English, of in French, and even of in German. In other languages, different letters may occur most frequently. For example, the “A” is the most frequent letter in long, “typical” Finnish texts, with a percentage of .
That the method of frequency counts is useful for attacks on monoalphabetic cryptosystems is obvious. For example, if in a ciphertext encrypting a long German text by the shift cipher, the letter occurring most frequently is “Y”, which is rather rare in German (as well as in many other languages), then it is most likely that “Y” encrypts “E”. Thus, the key used for encryption is “U” (). In addition to counting the frequency of single letters, one can also count the frequency with which certain pairs of letters (so-called digrams) and triples of letters (so-called trigrams) occur, and so on. This kind of attack also works for polyalphabetic systems, provided the period (i.e., the block length) is known.
Polyalphabetic cryptosystems with an unknown period, however, provide more security. For example, the Vigenére cipher resisted each attempt of breaking it for a long time. No earlier than in 1863, about 300 years after its discovery, the German cryptanalyst Friedrich Wilhelm Kasiski found a method of breaking the Vigenére cipher. He showed how to determine the period, which initially is unknown, from repetitions of the same substring in the ciphertext. Subsequently, the ciphertext can be decrypted by means of frequency counts. Singh writes that the British eccentric Charles Babbage, who was considered a genius of his time by many, presumably had discovered Kasiski's method even earlier, around 1854, although he didn't publish his work.
The pathbreaking work of Claude Shannon (1916 until 2001), the father of modern coding and information theory, is now considered a milestone in the history of cryptography. Shannon proved that there exist cryptosystems that guarantee perfect secrecy in a mathematically rigorous sense. More precisely, a cryptosystem guarantees perfect secrecy if and only if , the keys in are uniformly distributed, and for each plaintext and for each ciphertext there exists exactly one key with . That means that such a cryptosystem often is not useful for practical applications, since in order to guarantee perfect secrecy, every key must be at least as long as the message to be encrypted and can be used only once.
In order to understand some of the algorithms and problems to be presented later, some fundamental notions, definitions, and results from algebra and, in particular, from number theory, group theory, and graph theory are required. This concerns both the cryptosystems and zero-knowledge protocols in Chapter 7 and some of the problems to be considered in upcoming Chapter 8. The present subsection may as well be skipped for now and revisited later when the required notions and results come up. In this section, most of the proofs are omitted.
A group is defined by some nonempty set and a two-ary operation on that satisfy the following axioms:
– Closure: .
– Associativity: .
– Neutral element: .
– Inverse element: .
The element is called the neutral element of the group . The element is called the inverse element for . is said to be a monoid if satisfies associativity and closure under , even if has no neutral element or if not every element in has an inverse. A group (respectively, a monoid ) is said to be commutative (or abelian) if and only if for all . The number of elements of a finite group is said to be the order and is denoted by .
is said to be a subgroup of a group (denoted by ) if and only if and satisfies the group axioms.
A ring is a triple such that is an abelian group and is a monoid and the distributive laws are satisfied:
A ring is said to be commutative if and only if the monoid is commutative. The neutral element group is called the zero element (the zero, for short) of the ring . A neutral element of the monoid is called the one element (the one, for short) of the ring .
Let be a ring with one. An element of is said to be invertible (or a unity of ) if and only if it is invertible in the monoid .
A field is a commutative ring with one in which each nonzero element is invertible.
Let . The set is a finite group with respect to addition modulo , with neutral element . With respect to addition and multiplication modulo , is a commutative ring with one, see Problem 7-1. If is a prime number, then is a field with respect to addition and multiplication modulo .
Let denote the greatest common divisor of two integers and . For , define the set . With respect to multiplication modulo , is a finite group with neutral element .
If the operation of a group is clear from the context, we omit stating it explicitly. The group from Example 7.3 will play a particular role in Section7.3, where the RSA cryptosystem is introduced. The Euler function gives the order of this group, i.e., . The following properties of follow from the definition:
for all with , and
for all prime numbers .
Euler's Theorem below is a special case (namely, for the group ) of Lagrange's Theorem, which says that for each group element of a finite multiplicative group of order and with neutral element , . The special case of Euler's theorem, where is a prime number not dividing , is known as Fermat's Little Theorem.
In Section 8.4, algorithms for the graph isomorphism problem will be presented. This problem, which also is related to the zero-knowledge protocols to be introduced in Subsection 7.5.2, can be seen as a special case of certain group-theoretic problems. In particular, permutation groups are of interest here. Some examples for illustration will be presented later.
A permutation is a bijective mapping of a set onto itself. For each integer , let . The set of all permutations of is denoted by . For algorithmic purposes, permutations are given as pairs from .
If one defines the composition of permutations as an operation on , then becomes a group. For two permutations and in , their composition is defined to be that permutation in that results from first applying and then to the elements of , i.e., for each . The neutral element of the permutation group is the identical permutation, which is defined by for each . The subgroup of that contains as its only element is denoted by .
For any subset of , the permutation group generated by is defined as the smallest subgroup of containing . Subgroups of are represented by their generating sets, sometimes dubbed the generators of . In , the orbit of an element is defined as .
For any subset of , let denote the subgroup of that maps every element of onto itself. In particular, for and a subgroup of , the (pointwise) stabiliser of in is defined by
Observe that and .
Let and be permutation groups with . For , is said to be a right coset of in . Any two right cosets of in are either identical or disjoint. Thus, the permutation group is partitioned by the right cosets of in :
Every right coset of in has the cardinality . The set in (7.3) is called the complete right transversal of in .
The notion of pointwise stabilisers is especially important for the design of algorithms solving problems on permutation groups. The crucial structure exploited there is the so-called tower of stabilisers of a permutation group :
For each with , let be the complete right transversal of in . Then, is said to be a strong generator of , and we have . Every then has a unique factorisation with . The following basic algorithmic results about permutation groups will be useful later in Section 8.4.
1. For each , the orbit of in can be computed in polynomial time.
2. The tower of stabilisers can be computed in time polynomially in , i.e., for each with , the complete right transversals of in and thus a strong generator of can be determined efficiently.
The notions introduced in Definition 7.6 for permutation groups are now explained for concrete examples from graph theory. In particular, we consider the automorphism group and the set of isomorphisms between graphs. We start by introducing some useful graph-theoretical concepts.
Definition 7.8 (Graph isomorphism and graph automorphism) A graph consists of a finite set of vertices, , and a finite set of edges, , that connect certain vertices with each other. We assume that no multiple edges and no loops occur. In this chapter, we consider only undirected graphs, i.e., the edges are not oriented and can be seen as unordered vertex pairs. The disjoint union of two graphs and is defined as the graph with vertex set and edge set , where we assume that that the vertex sets and are made disjoint (by renaming if necessary).
Let and be two graphs with the same number of vertices. An isomorphism between and is an edge-preserving bijection of the vertex set of onto that of . Under the convention that , and are isomorphic (, for short) if and only if there exists a permutation such that for all vertices ,
An automorphism of is an edge-preserving bijection of the vertex set of onto itself. Every graph has the trivial automorphism . By we denote the set of all isomorphisms between and , and by we denote the set of all automorphisms of . Define the problems graph automorphism (, for short) and graph automorphism (, for short) by:
For algorithmic purposes, graphs are represented either by their vertex and edge lists or by an adjacency matrix, which has the entry at position if is an edge, and the entry otherwise. This graph representation is suitably encoded over the alphabet . In order to represent pairs of graphs, we use a standard bijective pairing function from onto that is polynomial-time computable and has polynomial-time computable inverses.
Example 7.4 (Graph isomorphism and graph automorphism) The graphs and shown in Figure 7.5 are isomorphic.
An isomorphism preserving adjacency of the vertices according to (7.4) is given, e.g., by , or in cycle notation by . There are three further isomorphisms between and , i.e., , see Exercise 7.1-4. However, neither nor is isomorphic to . This is immediately seen from the fact that the sequence of vertex degrees (the number of edges fanning out of each vertex) of and , respectively, differs from the sequence of vertex degrees of : For and , this sequence is , whereas it is for . A nontrivial automorphism of is given, e.g., by , or ; another one by , or . There are two more automorphisms of , i.e., , see Exercise 7.1-4.
The permutation groups , , and are subgroups of . The tower of stabilisers of consists of the subgroups , , and . In the automorphism group of , the vertices and have the orbit , the vertices and have the orbit , and vertex has the orbit .
and have the same number of elements if and only if and are isomorphic. To wit, if and are isomorphic, then follows from . Otherwise, if , then is empty but contains always the trivial automorphism . This implies (7.5) in Lemma 7.9 below, which we will need later in Section 8.4. For proving (7.6), suppose that and are connected; otherwise, we simply consider instead of and the co-graphs and , see Exercise 7.1-5. An automorphism of that switches the vertices of and , consists of an isomorphism in and an isomorphism in . Thus, , which implies (7.6) via (7.5).
If and are isomorphic graphs and if , then . Thus, is a right coset of in . Since any two right cosets are either identical or disjoint, can be partitioned into right cosets of according to (7.3):
where for all , . The set of permutations in thus is a complete right transversal of in . Denoting by the graph that results from applying the permutation to the vertices of , we have . Since there are exactly permutations in , it follows from (7.7) that
This proves the following corollary.
Then, we have
Proof. If and are isomorphic, then . Hence, by Corollary 7.10, we have
Analogously, one can show that . If and are isomorphic, then
It follows that . If and are nonisomorphic, then and are disjoint sets. Thus, .
7.1-1 Figure 7.6 shows two ciphertexts, and . It is known that both encrypt the same plaintext and that one was obtained using the shift cipher, the other one using the Vigenére cipher. Decrypt both ciphertexts.
Hint. After decryption you will notice that the plaintext obtained is a true statement for one of the two ciphertexts, whereas it is a false statement for the other ciphertext. Is perhaps the method of frequency counts useful here?
7.1-3 Prove the properties stated for Euler's function:
a. for all with .
b. for all prime numbers .
Using these properties, prove Proposition 7.3.
a. Determine all isomorphisms between and .
b. Determine all automorphisms of , , and .
c. For which isomorphisms between and is a right coset of in , i.e., for which is ? Determine the complete right transversals of , , and in .
d. Determine the orbit of all vertices of in and the orbit of all vertices of in .
e. Determine the tower of stabilisers of the subgroups and .
f. How many graphs with vertices are isomorphic to ?
c. is connected if is not connected.