Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

1. Introduction

Abstract
Cryptology, the study of cryptosystems, can be divided into two disciplines. Cryptography concerns itself with the design of cryptosystems, while cryptanalysis studies the breaking of cryptosystems. At this moment we will not give a formal definition of a cryptosystem. That will come later in this chapter. We assume that the reader has the right intuitive idea of what a cryptosystem is.
Henk C. A. van Tilborg

2. Classical Systems

Abstract
In this chapter we shall discuss a number of classical systems. For further reading we refer the interested reader to [Bek82], [Den82], [Kah67], [Kon81] or [Mey82]. One of the oldest cryptosystems is due to Julius Caesar. It shifts each letter in the text cyclicly over k places in the alphabet. In our terminology the Caesar cipher is defined by:
$$ {E_k}\left( i \right) = \left( {i + k} \right)\underline {\bmod } {\text{ }}q,0 \leqslant i < q $$
(2.1)
$$ E = \left\{ {{E_k}|0 \leqslant k < q} \right\} $$
(2.2)
, where i mod n denotes the unique integer j, satisfying j = i mod n and 0 ≤ j < n. In this case the keyspace K is the set {0,1,…,q-1} and D k = E q-k . For most practical alphabet sizes the cryp-tanalist can break this system easily by trying all q possible keys. This is called exhaustive key search. For instance, when q = 26 and we use {a,b,..., z} as alphabet, one only has to check 26 possibilities. In Table 2.1 one can find the cryptanalysis of the ciphertext IYBABZ.
Henk C. A. van Tilborg

3. Shift Register Sequences

Abstract
During and after World War II the use of logical circuits made completely electronic cryptosystems possible. These turned out to be very practical in the sense of being easy to implement and very fast. The analysis of their security is not so easy! Working with logical circuits often leads to the alphabet {,1}. There are only two permutations of the symbols 0 and 1. One interchanges the two symbols. This can also be described by adding 1 (modulo 2) to the two elements. The other leaves the two invariant, which is the same as adding 0 (modulo 2) to these two elements. Since the Vernam cipher is unconditionally secure but not very practical, it is only natural that people came up with the following scheme.
Henk C. A. van Tilborg

4. Shannon Theory

Abstract
In Chapter II we have seen that the cryptanalysis of a cryptosystem often depends on the structure that is present in most texts. For instance in Table 2.1 we could find the key 19, because BRUTUS was the only word in the table that made sense. This structure in the plaintext remains present in the ciphertext (it is hoped in a hidden form). If the extra information arising from this structure exceeds our uncertainty about the key, one may be able to determine the ciphertext!
Henk C. A. van Tilborg

5. Huffman Codes

Abstract
It is clear from the previous chapter (in particular from (4.5) and (4.6)) that the security of a cryptosystem can be increased by reducing the redundancy in the plaintext. In Example 4.1 such a reduction has been demonstrated. In this chapter we shall describe a general method for what is called data compression or source coding. Let a (plaintext) source S output independently chosen symbols from the set {m1,m2, …, mn}, with respective probabilities p1, p2, …, pn. A symbol mi, 1 ≤ in, will be encoded into a binary string ci of length li.The set {c1,c2, …, cn} is called a code C for the source S. The idea of data compression is to use such a code that the expected value of the length of the encoded plaintext is minimal. Since the output symbols are independent we have to minimize the expected length per symbol
$$ L = \sum\limits_i -1^n p_il_i$$
(5.1)
over all possible codes C for the source S. There is however an additional constraint. One has to be able to retrieve the individual messages from the concatenation of the succesive codewords. Not every code has this property. Indeed let C = {0,01, 10}. The sequence 010 can be made in two ways: 0 followed by 10 and 01 followed by 0. This ambiguity has to be avoided.
Henk C. A. van Tilborg

6. DES

Abstract
In 1974 the National Bureau of Standards (NBS) solicited the American industry to develop a cryptosystem that could be used as a standard in unclassified U.S. Government applications. IBM developed a system called LUCIFER. After being modified and simplified, this system became the Data Encryption Standard (DES) in 1977. It has been implemented on a chip, which makes it very suitable for use in large communication systems. The encryption and decryption algorithms of DES have been made public. This has never been done before, although in each textbook one can find the remark that the security of a cryptosystem should not depend on the secrecy of the system. Later we shall give a complete description of DES. DES is a block cipher operating on 64 bits simultaneously (see Figure 6.1). Although the keysize is 64, the effective keysize is 56 bits. The remaining 8 bits are parity checks. The input M and key K result in a ciphertext C, which we shall denote by DES(M,K). For the decryption the same DES chip with the same key can be used, as we shall see later.
Henk C. A. van Tilborg

7. Public Key Cryptography

Abstract
In modern day communication systems the conventional cryptosystems turned out to have two disturbing disadvantages.
Henk C. A. van Tilborg

8. The Discrete Logarithm Problem

Abstract
In [Dif76] Diffie and Hellman propose a public key distribution system which is based on the apparent difficulty of computing logarithms over the finite field GF (p), p prime. The reader, who is not familiar with the theory of finite fields is referred to Appendix B. Let α be a primitive element of GF(p). So each nonzero element c in GF (p) can be written as
$$ c = {\alpha ^m} $$
(8.1)
where m is unique modulo p - 1. If m is given, c can be computed from (8.1) with 2 • [log2P] multiplications [Knu69, pp.398–422]. One can realize this by repeated squaring or multiplying by α. The binary representation of m gives the order of these operations. For instance the binary representation 10101011 corresponds in the following way with the computation of α17110 10 10 1 1
$$ {\alpha ^{171}} = {({({({({({({(\alpha )^2})^2}\alpha )^2})^2}\alpha )^2})^2}\alpha )^2}\alpha $$
Henk C. A. van Tilborg

9. RSA

Abstract
In 1978 R.L. Rivest, A. Shamir and L. Adleman [Riv78] proposed a public key cryptosystem that has become known as the RSA system, although one sometimes also sees the name “the MIT system”. It depends on Euler’s Theorem (see Definition A. 13 and Theorem A.16).
Henk C. A. van Tilborg

10. The Mceliece System

Abstract
In this chapter it is assumed that the reader is familiar with algebraic coding theory. A reader without this background can freely skip this chapter and continue with Chapter 11. From [Mac77] we recall the following facts about Goppa codes.
With each irreducible polynomial of degree tover GF(2 m ) corresponds a binary, irreducible Goppa code of length n = 2m, dimension k ≥ n - tm and minimum distance d ≥ 2t + 1. A fast decoding algorithm with running time nt, exists [Pat75]. There are about 2 mt /t (see Corollary B.23) irreducible polynomials of degree t over GF(2 m ). So a random polynomial of degree t over GF(2 m ) will be irreducible with probability 1/t. Since there is a fast algorithm for testing irreducibility (see [Ber68, Ch.6] or [Rab80]), one can find an irreducible polynomial of degree t over GF(2 m ), just like in Algorithm 9.5, by repeated guessing and testing.
Henk C. A. van Tilborg

11. The Knapsack System

Abstract
In [Mer78] Merkle and Hellman propose a public key cryptosystem that is based on the difficulty of solving the knapsack problem. Later other knapsack related cryptosystems have been suggested. See, for instance [ChR85].
Henk C. A. van Tilborg

12. Threshold Schemes

Abstract
In this chapter we shall not introduce a new cryptosystem, but we shall discuss a related topic. We start with an example [Liu68].
Henk C. A. van Tilborg

13. Other Directions

Abstract
The best way to get an impression of the developments in cryptology that are not discussed in this textbook, is to look at the proceedings of the conferences held on cryptology. There are two yearly conferences on cryptology. Since 1981 one takes place in Santa Barbara and is called Crypto ’81, Crypto ’82, etc. The other one has been held in various cities in Europe since 1982 and is called Eurocrypt 82, etc. The IEEE Symposia on Information Theory that are held every one and a half year also always have several sessions on cryptology. Many articles on cryptology have appeared in the IEEE Transactions on Information Theory and are also to be expected in the forthcoming new Journal on Cryptology. Cryptologia is a quarterly journal on cryptology since 1978. It contains many interesting articles of a historical nature, but also new results do appear in it.
Henk C. A. van Tilborg

Backmatter

Weitere Informationen