Introduction

Cryptography
Introduction

Luu Quang Minh

Vietnamese-German University (VGU)

March 2025

1 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Overview

Some myths about cryptography

What is cryptography?
Brief history
Encryption: definition and properties
Symmetric and asymmetric schemes
Historical ciphers: Caesar and Vigenère

2 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Some Myths about Cryptography

Cryptography is only about encryption methods.

Encryption is strong if the ciphertext is not readable.
Encryption also protects against the modification of data.
Every cipher can be broken with large resources.
Passwords are used as secret keys.
Most data is now encrypted using asymmetric schemes, e.g., RSA.
The current public-key algorithms can be used safely until large
quantum computers become available.

What do you think?

3 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

What is Cryptography?

Classical cryptography: converting messages into an incomprehensible

form. Classical cryptography is mainly dealing with encryption methods.

Modern cryptography: applying mathematical techniques to achieve

security objectives (confidentiality, integrity and availability) in the
presence of adversaries.

Modern cryptography goes beyond encryption methods and includes a

variety of cryptographic primitives, algorithms, schemes and protocols.

4 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Cryptology

Cryptology has two main branches:

Cryptography is the collection of mathematical techniques
(primitives, algorithms, schemes, protocols) related to information
security.
Cryptanalysis is the science of analysing cryptographic algorithms,
revealing their weaknesses, launching attacks and potentially
breaking them.

However, Cryptography and Cryptology are often considered to be

synonymous. Modern cryptography not only defines algorithms and
schemes, but also studies their security in the presence of adversaries and
often provides security proofs.

5 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

History

Classic cryptography is an ancient art which has been used since ancient
times.
Egyptians, Greeks and Romans used monoalphabetic substitution
and transposition ciphers.
Successful cryptanalysis with frequency analysis in medieval times.
Systematic mathematical description of polyalphabetic ciphers and
their cryptanalysis in the 19th century.

6 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

History II

Development of the Vernam One-Time-Pad and the use of statistical

techniques in the beginning of the 20th century.
Cipher machines (e.g., Enigma) and advances in cipher breaking
during World War II.
Shannon (1949) provides a theoretical basis of cryptography
(Communication Theory of Secrecy Systems).

7 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

History III

Modern cryptography started in the 1970s with the first commercially

available secure cipher and the development of public-key mechanisms.
Since the 1970s availability of modern symmetric ciphers, in
particular DES (Data Encryption Standard). Development of
asymmetric cryptography (Diffie-Hellman, RSA etc.).
Since the 1990s widespread use of cryptography in computer
systems and networks. Large computing resources become available.
Advances in cryptanalysis.
Successful attacks and broken schemes (e.g., DES, GSM A5, WLAN
WEP, RC4, RFID Crypto1, MD5, SHA-1, . . . ).

8 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

History IV

Since the 1990s precise definitions and formal proofs of security.

Development and adoption of new ciphers and mechanisms, e.g.,
AES, SHA-3, Elliptic Curve Cryptography (ECC). Cryptography
becomes feasible even for devices with very restricted resources (e.g.
RFID transponder). New types of attacks, e.g., using side channel
analysis.
Quantum algorithms can break asymmetric schemes (RSA,
Diffie-Hellman, ECC). However, sufficiently large and stable
quantum computers are not yet available.
Development of Post-quantum Cryptography (PQC). New
public-key ciphers are standardised (ML-KEM, ML-DSA, SLH-DSA).

9 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Encryption
An encryption scheme or cryptosystem consists of algorithms which
produce keys and transform plaintext into ciphertext and conversely.

random
k k

m E c D m

Encryption and decryption algorithms.

The encryption algorithm is either deterministic or probabilistic
(randomized), i.e., the ciphertext can also depend on random input data.
In the case of probabilistic schemes, different encryptions of the same
plaintext give different ciphertexts.
10 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Definition of Encryption

Definition
An encryption scheme or cryptosystem consists of
A plaintext space M, the set of plaintext or clear-text messages,
A ciphertext space C, the set of ciphertext messages,
A key space K, the set of keys,
A randomized key generation algorithm Gen(1n ) that takes the security
parameter n as input and returns a key k ∈ K,
An encryption algorithm E = {Ek | k ∈ K}, which is possibly randomised.
A deterministic decryption algorithm D = {Dk | k ∈ K}. An error symbol
⊥ is returned if the ciphertext is invalid.

11 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Definition of Encryption II

We require that all algorithms (key generation, encryption, decryption)

have polynomial running time with respect to their input size.

The scheme provides correct decryption, if for each key k ∈ K and all
plaintexts m ∈ M, one has


Dk Ek (m) = m.

12 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Symmetric and Asymmetric Encryption Schemes

A scheme is said to be symmetric-key if encryption and decryption use
the same secret key k. In contrast, public-key (asymmetric-key)
encryption schemes use key pairs k = (pk, sk), where pk is public and sk
is private; encryption uses pk and decryption sk.

Public-key encryption can also be randomized. We will discuss

symmetric-key schemes first and deal with public-key schemes later.

pk sk

m E c D m

Asymmetric encryption and decryption.

13 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Historical Ciphers

Ciphers have been used since ancient times. Historical ciphers use letters,
i.e., the plaintext and ciphertext space consists of strings of letters A to
Z:
M = C = Σ∗ , where Σ = {A, B, . . . , Z }.
The ∗ denotes strings of arbitrary length. Basically, such a cipher
transforms plaintext words and sentences into ciphertext, and vice versa.
Special characters are omitted or transcribed.

Of course, modern ciphers instead use the binary alphabet {0, 1}.

14 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Caesar’s Cipher

Caesar encrypted by shifting letters three places forward: A is replaced

with D, B with E , and so on. At the end of the alphabet, X is replaced
with A, Y with B and Z with C . For decryption, the ciphertext is shifted
three places backward.

For example, TOY is encrypted into WRB.

Representing the letters by the residue classes 0, 1, . . . , 25 modulo 26,

encryption corresponds to adding 3 modulo 26. For decryption, one has
to subtract 3 modulo 26. Caesar’s cipher (encryption and decryption) is
affine, i.e. is the composition of a linear map and a constant translation.

In the above example, the plaintext (19, 14, 24) is encrypted into the
ciphertext (22, 17, 1). What is the corresponding linear map and what
the constant translation? What about the key of this cipher?

15 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Monoalphabetic Substitution Ciphers

Monoalphabetic substitution ciphers replace one letter of the alphabet
with another one. The key is a permutation of the letters. Note that
general permutations are not affine.

Example:

A B C D E F G H I J K L M
Q W E R T Z U I O P A S D

N O P Q R S T U V W X Y Z
F G H J K L Y X C V B N M

For example, ROM is mapped to KGD.

There are 26! ≈ 288 different keys. Is the cipher secure?

16 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Frequency Analysis
Substitution ciphers can be attacked with a frequency analysis. One
exploits the fact that letters are not uniquely distributed in natural
languages.

Frequency of letters in English texts:

E T A ... Z
12.7% 9.06% 8.17% ... 0.07%

For longer English texts, the most frequent ciphertext letter corresponds
to the plaintext letter E , the second most frequent letter is T etc. Note
that some correct plaintext letters are often sufficient to guess the
complete text.

This method can be refined by looking at pairs or triples of letters. For

example, combinations such as IN, OF , AND are frequent in English
texts.
17 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Attacks against Monoalphabetic Ciphers

The frequency analysis is a ciphertext-only attack and works well if the

ciphertext is long and the plaintext comes from a known language.

A more powerful attacker has access to plaintext-ciphertext pairs

(known-plaintext attack). He can then set up a dictionary (codebook)
of plaintext and associated ciphertext letters. The dictionary can then be
used to decrypt new ciphertexts.

18 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Polyalphabetic Substitution Ciphers

Polyalphabetic ciphers are based on substitution, but the substitution

depends on the position of the plaintext or ciphertext character. A
polyalphabetic cipher has length n if the substitution key repeats every n
characters.

The best-known example is the Vigenère cipher, which shifts the

plaintext by the number of positions given by the key. The Vigenère
cipher is affine.

Example: Suppose the key-length is 2 and the key is k = DY , which

corresponds to (3, 24), then the plaintext m = ALFA = (0, 11, 5, 0) is
encrypted into c = DJIY = (3, 9, 8, 24).

(0, 11, 5, 0) + (3, 24, 3, 24) = (3, 9, 8, 24) (mod 26)

19 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Vigenère Cipher

The Vigenère cipher of length n is a classical example of a polyalphabetic

substitution cipher. We have

M = C = Σ∗ and K = Σn , where Σ = {A, B, . . . , Z }.

For encryption and decryption, the message and the ciphertext is split
into blocks of length n; the last block can be shorter. Encryption adds
the key to each plaintext block, decryption subtracts the key.

c = Ek (m) = Ek (m1 ∥m2 ∥ · · · ) = (m1 + k ∥ m2 + k ∥ · · · ) (mod 26)

m = Dk (c) = Dk (c1 ∥c2 ∥ · · · ) = (c1 − k ∥ c2 − k ∥ · · · ) (mod 26)

20 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Attacking the Vigenère Cipher

A special weakness of the Vigenère cipher is the simple linear relation

between plaintext, ciphertext and key. If a plaintext m and the
corresponding ciphertext c is known, the key can be easily computed:

c − m = (c1 ∥c2 ∥ · · · ) − (m1 ∥m2 ∥ · · · ) = (k∥k∥ · · · ) (mod 26)

This is a known-plaintext attack.

21 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Vigenère Cipher: Exercises

1 Let k = FZC be the key of a Vigenère cipher. Encrypt m = GKLM

and decrypt c = MZNQN.

2 Let m = ZHUK be a plaintext and c = BGFM a ciphertext of a

Vigenère cipher of length 3. Find the key.

3 In the above example of a Vigenère cipher of length 3, can you write

down any four-letter plaintext and ciphertext? Why or why not?
Give examples of infeasible plaintext-ciphertext combinations.

22 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Security of Polyalphabetic Substitution Ciphers

Since the Vigenère cipher is affine, known plaintext attacks are easy.
General polyalphabetic ciphers can be attacked by a frequency analysis, in
a similar way as monoalphabetic ciphers. Suppose the length n is known.
Then the ciphertext is grouped into n classes, where the positions
1, n + 1, 2n + 1, . . . form the first class, the positions 2, n + 2, 2n + 2 the
second class, etc. Since the ciphertext in each class was encrypted with a
monoalphabetic cipher, it can be attacked by a frequency analysis.

If some plaintext and the corresponding ciphertext is known, a dictionary

can be set up as for monoalphabetic ciphers, but for each class of
positions separately.

23 / 25
 Overview
History
Introduction
Encryption
Historical Ciphers

Key-length of Polyalphabetic Substitution Ciphers

How can an attacker find the length of the key of a polyalphabetic cipher?

Kasiski’s method can be used. One looks for strings of characters that
occur repeatedly in the ciphertext. The distances between these strings
are likely to be multiples of the key length (why?). Then take the
greatest common divisor of all distances. We skip the details.

24 / 25
 Thank You
Questions?

Luu Quang Minh

Vietnamese-German University (VGU)
March 2025