Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag
Chapter 1
Introduction to Cryptography and Data Security
This section will introduce the most important terms of modern cryptology and will
teach an important lesson about proprietary vs. openly known algorithms. We will
also introduce modular arithmetic which is also of major importance in public-key
cryptography.
In this chapter you will learn:
The general rules of cryptography
Key lengths for short-, medium- and long-term security
The difference between different types of attacks against ciphers
A few historical ciphers, and on the way we will learn about modular arithmetic,
which is of major importance for modern cryptography as well
Why one should only use well-established encryption algorithms
1
Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag
2 Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag
1.1 Overview of Cryptology (and This Book)
If we hear the word cryptography our first associations might be e-mail encryption,
secure website access, smart cards for banking applications or code breaking during
World War II, such as the famous attack against the German Enigma encryption
machine (Fig. 1.1).
Fig. 1.1 The German Enigma encryption machine (reproduced with permission from the
Deutsches Museum, Munich)
Cryptography seems closely linked to modern electronic communication. How-
ever, cryptography is a rather old business, with early examples dating back to about
2000 B.C., when non-standard “secret” hieroglyphics were used in ancient Egypt.
Since Egyptian days cryptography has been used in one form or the other in many,
if not most, cultures that developed written language. For instance, there are doc-
umented cases of secret writing in ancient Greece, namely the scytale of Sparta
(Fig. 1.2), or the famous Caesar cipher in ancient Rome, about which we will learn
later in this chapter. This book, however, strongly focuses on modern cryptographic
T HESC Y T A L
EIS A T R A N
SP OSI T IO
NCIP HER
Fig. 1.2 Scytale of Sparta
methods and also teaches many data security issues and their relationship with cryp-
tography.
Let’s now have a look at the field of cryptography (Fig. 1.3). The first thing
Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag
Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag 3
Fig. 1.3 Overview of the field of cryptology
that we notice is that the most general term is cryptology and not cryptography.
Cryptology splits into two main branches:
Cryptography is the science of secret writing with the goal of hiding the mean-
ing of a message.
Cryptanalysis is the science and sometimes art of breaking cryptosystems. You
might think that code breaking is for the intelligence community or perhaps or-
ganized crime, and should not be included in a serious classification of a scien-
tific discipline. However, most cryptanalysis is done by respectable researchers
in academia nowadays. Cryptanalysis is of central importance for modern cryp-
tosystems: without people who try to break our crypto methods, we will never
know whether they are really secure or not. See Sect. 1.3 for more discussion
about this issue.
Because cryptanalysis is the only way to assure that a cryptosystem is secure,
it is an integral part of cryptology. Nevertheless, the focus of this book is on
cryptography: We introduce most important practical crypto algorithms in detail.
These are all crypto algorithms that have withstood cryptanalysis for a long time, in
most cases for several decades. In the case of cryptanalysis we will mainly restrict
ourselves to providing state-of-the-art results with respect to breaking the crypto al-
gorithms that are introduced, e.g., the factoring record for breaking the RSA scheme.
Let’s now go back to Fig. 1.3. Cryptographyitself splits into three main branches:
Symmetric Algorithms are what many people assume cryptography is about:
two parties have an encryption and decryption method for which they share a
secret key. All cryptography from ancient times until 1976 was exclusively based
on symmetric methods. Symmetric ciphers are still in widespread use, especially
for data encryption and integrity check of messages.
Asymmetric (or Public-Key) Algorithms In 1976 an entirely different type of
cipher was introduced by Whitfield Diffie, Martin Hellman and Ralph Merkle. In
public-key cryptography, a user possesses a secret key as in symmetric cryptog-
raphy but also a public key. Asymmetric algorithms can be used for applications
such as digital signatures and key establishment, and also for classical data en-
cryption.
Cryptographic Protocols Roughly speaking, crypto protocols deal with the ap-
plication of cryptographic algorithms. Symmetric and asymmetric algorithms
Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag
4 Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag
can be viewed as building blocks with which applications such as secure Inter-
net communication can be realized. The Transport Layer Security (TLS) scheme,
which is used in every Web browser, is an example of a cryptographic protocol.
Strictly speaking, hash functions, which will be introduced in Chap. 11, form
a third class of algorithms but at the same time they share some properties with
symmetric ciphers.
In the majority of cryptographic applications in practical systems, symmetric and
asymmetric algorithms (and often also hash functions) are all used together. This is
sometimes referred to as hybrid schemes. The reason for using both families of
algorithms is that each has specific strengths and weaknesses.
The main focus of this book is on symmetric and asymmetric algorithms, as
well as hash functions. However, we will also introduce basic security protocols. In
particular, we will introduce several key establishment protocols and what can be
achieved with crypto protocols: confidentiality of data, integrity of data, authentica-
tion of data, user identification, etc.
1.2 Symmetric Cryptography
This section deals with the concepts of symmetric ciphers and it introduces the
historic substitution cipher. Using the substitution cipher as an example, we will
learn the difference between brute-force and analytical attacks.
1.2.1 Basics
Symmetric cryptographic schemes are also referred to as symmetric-key, secret-key,
and single-key schemes or algorithms. Symmetric cryptography is best introduced
with an easy to understand problem: There are two users, Alice and Bob, who want
to communicate over an insecure channel (Fig. 1.4). The term channel might sound
a bit abstract but it is just a general term for the communication link: This can be the
Internet, a stretch of air in the case of mobile phones or wireless LAN communica-
tion, or any other communication media you can think of. The actual problem starts
with the bad guy, Oscar
1
, who has access to the channel, for instance, by hacking
into an Internet router or by listening to the radio signals of a Wi-Fi communica-
tion. This type of unauthorized listening is called eavesdropping. Obviously, there
are many situations in which Alice and Bob would prefer to communicate without
Oscar listening. For instance, if Alice and Bob represent two offices of a car man-
ufacturer, and they are transmitting documents containing the business strategy for
the introduction of new car models in the next few years, these documents should
1
The name Oscar was chosen to remind us of the word opponent.
Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag
Understanding Cryptography by C. Paar and J. Pelzl, Copyright Springer-Verlag 5
not get into the hands of their competitors, or of foreign intelligence agencies for
that matter.
Fig. 1.4 Communication over an insecure channel
In this situation, symmetric cryptography offers a powerful solution: Alice en-
crypts her message x using a symmetric algorithm, yielding the ciphertext y. Bob
receives the ciphertext and decrypts the message. Decryption is, thus, the inverse
process of encryption (Fig. 1.5). What is the advantage? If we have a strong encryp-
tion algorithm, the ciphertext will look like random bits to Oscar and will contain
no information whatsoever that is useful to him.
Fig. 1.5 Symmetric-key cryptosystem
The variables x, y and k in Fig. 1.5 are important in cryptography and have special
names:
x is called plaintext or cleartext,
y is called ciphertext,
k is called the key,
the set of all possible keys is called the key space.
The system needs a secure channel for distribution of the key between Alice
and Bob. The secure channel shown in Fig. 1.5 can, for instance, be a human who
is transporting the key in a wallet between Alice and Bob. This is, of course, a
somewhat cumbersome method. An example where this method works nicely is
the pre-shared keys used in Wi-Fi Protected Access (WPA) encryption in wireless