Skip to main content
main-content
Top

About this book

In this introductory textbook the author explains the key topics in cryptography. He takes a modern approach, where defining what is meant by "secure" is as important as creating something that achieves that goal, and security definitions are central to the discussion throughout.
The author balances a largely non-rigorous style — many proofs are sketched only — with appropriate formality and depth. For example, he uses the terminology of groups and finite fields so that the reader can understand both the latest academic research and "real-world" documents such as application programming interface descriptions and cryptographic standards. The text employs colour to distinguish between public and private information, and all chapters include summaries and suggestions for further reading.
This is a suitable textbook for advanced undergraduate and graduate students in computer science, mathematics and engineering, and for self-study by professionals in information security. While the appendix summarizes most of the basic algebra and notation required, it is assumed that the reader has a basic knowledge of discrete mathematics, probability, and elementary calculus.

Table of Contents

Mathematical Background

Frontmatter

Chapter 1. Modular Arithmetic, Groups, Finite Fields and Probability

Abstract
Much of this book will be spent looking at the applications of modular arithmetic, since it is fundamental to modern cryptography and public key cryptosystems in particular. Hence, in this chapter we introduce the basic concepts and techniques we shall require.
Nigel P. Smart

Chapter 2. Primality Testing and Factoring

Abstract
Luckily we shall see that testing a number for primality can be done very fast using very simplecode, but with an algorithm that has a probability of error. By repeating this algorithm we can reduce the error probability to any value that we require.
Nigel P. Smart

Chapter 3. Discrete Logarithms

Abstract
In Chapter 2 we examined the hard problem of FACTOR. This gave us some (hopefully) one-way functions, namely the RSA function, the squaring function modulo a composite and the function which multiplies two large numbers together.
Nigel P. Smart

Chapter 4. Elliptic Curves

Abstract
This chapter is devoted to introducing elliptic curves. Some of the more modern public key systems make use of elliptic curves since they can offer improved efficiency and bandwidth. Since much of this book can be read with just the understanding that an elliptic curve provides another finite abelian group in which one can pose a discrete logarithm problem, you may decide to skip this chapter on an initial reading.
Nigel P. Smart

Chapter 5. Lattices

Abstract
In this chapter we present the concept of a lattice. Traditionally in cryptography lattices have been used in cryptanalysis to break systems, and we shall see applications of this in Chapter 15. However, recently they have also been used to construct cryptographic systems with special properties, as we shall see in Chapter 17.
Nigel P. Smart

Chapter 6. Implementation Issues

Abstract
In this chapter we examine how one actually implements cryptographic operations. We shall mainly be concerned with public key operations since those are the most complex to implement. For example, when we introduce RSA or DSA later we will have to perform a modular exponentiation with respect to a modulus of a thousand or more bits. This means we need to understand the implementation issues involved with both modular arithmetic and exponentiation algorithms.
Nigel P. Smart

Historical Ciphers

Frontmatter

Chapter 7. Historical Ciphers

Abstract
An encryption algorithm, or cipher, is a means of transforming plaintext into ciphertext under the control of a secret key. This process is called encryption or encipherment.
Nigel P. Smart

Chapter 8. The Enigma Machine

Abstract
With the advent of the 1920s people saw the need for a mechanical encryption device. Taking a substitution cipher and then rotating it was identified as an ideal solution. This idea had actually been used previously in a number of manual ciphers, but mechanization was able to make it far more efficient. The rotors could be implemented using wires and then encryption could be done mechanically using an electrical circuit.
Nigel P. Smart

Chapter 9. Information-Theoretic Security

Abstract
Information theory is one of the foundations of computer science. In this chapter we will examine its relationship to cryptography. But we shall not assume any prior familiarity with information theory.
Nigel P. Smart

Chapter 10. Historical Stream Ciphers

Abstract
It is desirable that both the encryption and decryption functions be public knowledge and so the secrecy of the message, given the ciphertext, depends totally on the secrecy of the secret key k. Although this well-established principle, called Kerckhoffs’ principle, has been known since the mid-1800s some companies still ignore it and choose to deploy secret proprietary encryption schemes which usually turn out to be insecure as soon as someone leaks the details of the algorithms.
Nigel P. Smart

Modern Cryptography Basics

Frontmatter

Chapter 11. Defining Security

Abstract
The first challenge modern cryptography addresses is to actually arrive at a concrete mathematical definition of what it means for a particular cryptographic mechanism to be secure. Whilst we may have a conceptual notion that encryption should be secure as long as the key is not revealed, it is not straightforward to define this precisely. We will also see that modern cryptography is about more than just encryption.
Nigel P. Smart

Chapter 12. Modern Stream Ciphers

Abstract
We can interpret a pseudo-random function as a stream cipher. Let {F k } K be a PRF family with codomain C of bitstrings of length l. The PRF family immediately defines a stream cipher for messages of length l bits. We encrypt a message by setting
Nigel P. Smart

Chapter 13. Block Ciphers and Modes of Operation

Abstract
The basic description of a block cipher is shown in Figure 13.1. Block ciphers operate on blocks of plaintext one at a time to produce blocks of ciphertext. The block of plaintext and the block of ciphertext are assumed to be of the same size, e.g. a block of n bits. Every string of n bits in the domain should map to a string of n bits in the codomain, and every string of n bits in the codomain should result from the application of the function to a string in the domain. This means that for a fixed key a block cipher is bijective and hence is a permutation.
Nigel P. Smart

Chapter 14. Hash Functions, Message Authentication Codes and Key Derivation Functions

Abstract
A cryptographic hash function H is a function which takes arbitrary length bit strings as input and produces a fixed-length bit string as output; the output is often called a digest, hashcode or hash value. Hash functions are used a lot in computer science, but the crucial difference between a standard hash function and a cryptographic hash function is that a cryptographic hash function should at least have the property of being one-way.
Nigel P. Smart

Chapter 15. The “Naive” RSA Algorithm

Abstract
The RSA algorithm was the world’s first public key encryption algorithm, and it has stood the test of time remarkably well. The RSA algorithm is based on the difficulty of the RSA problem considered in Chapter 2, and hence it is based on the difficulty of finding the prime factors of large integers. However, we have seen that it may be possible to solve the RSA problem without factoring, hence the RSA algorithm is not based completely on the difficulty of factoring.
Nigel P. Smart

Chapter 16. Public Key Encryption and Signature Algorithms

Abstract
In this section we present three basic passively secure encryption schemes, namely the Goldwasser–Micali encryption scheme, the ElGamal encryption scheme, and the Paillier encryption scheme.
Nigel P. Smart

Chapter 17. Cryptography Based on Really Hard Problems

Abstract
Up until now we have looked at basing cryptography on problems which are believed to be hard, e.g. that AES is a PRF, that factoring a product of large primes is hard, that finding discrete logarithms is hard. But there is no underlying reason why these problems should be hard. Computer Science gives us a whole theory of categorizing hard problems, called complexity theory. Yet none of our hard problems appear to be what a complexity theorist would call hard. Indeed, in comparison to what complexity theorists discuss, factoring and discrete logarithms are comparatively easy.
Nigel P. Smart

Chapter 18. Certificates, Key Transport and Key Agreement

Abstract
We can now perform encryption and authentication using either public key techniques or symmetric key techniques. However, we have not addressed how parties actually obtain the public key of an entity, or obtain a shared symmetric key. When using hybrid ciphers in Section 16.3 we showed how a symmetric key could be transported to another party, and then that symmetric key used to encrypt a single message. However, we did not address what happens if we want to use the symmetric key many times, or use it for authentication etc. Nor did we address how the sender would know that the public key of the receiver he was using was genuine.
Nigel P. Smart

Advanced Protocols

Frontmatter

Chapter 19. Secret Sharing Schemes

Abstract
Suppose you have a secret s which you wish to share amongst a set P of n parties. You would like certain subsets of the n parties to recover the secret but not others. The classic scenario might be that s is a nuclear launch code and you have four people, the president, the vice-president, the secretary of state and a general in a missile silo.
Nigel P. Smart

Chapter 20. Commitments and Oblivious Transfer

Abstract
In this chapter we shall examine a number of more advanced cryptographic protocols which enable higher-level services to be created. We shall particularly focus on protocols for
  • commitment schemes,
  • oblivious transfer.
Nigel P. Smart

Chapter 21. Zero-Knowledge Proofs

Abstract
Suppose Alice has a password and wants to log in to a website run by Bob, but she does not quite trust the computer Bob is using to verify the password. If she just sends the password to Bob then Bob’s computer will learn the whole password. To get around this problem one often sees websites that ask for the first, fourth and tenth letter of a password one time, and then maybe the first, second and fifth the second time and so on. In this way Bob’s computer only learns three letters at a time. So the password can be checked but in each iteration of checking only three letters are leaked. It clearly would be better if Bob could verify that Alice has the password in such a way that Alice never has to reveal any of the password to Bob. This is the problem this chapter will try to solve.
Nigel P. Smart

Chapter 22. Secure Multi-party Computation

Abstract
Secure multi-party computation is an area of cryptography which deals with two or more parties computing a function on their private inputs. They wish to do so in a way that means that their private inputs still remain private. Of course depending on the function being computed, some information about the inputs may leak. The classical example is the so-called millionaires problem; suppose a bunch of millionaires have a lunch time meeting at an expensive restaurant and decide that the richest of them will pay the bill. However, they do not want to reveal their actual wealth to each other. This is an example of a secure multi-party computation.
Nigel P. Smart
Additional information