Cryptography: Definitions, Theorems, Remarks and
Cryptosystems
Lennert Saerens
June 2024
1 Basic concepts of cryptography
1.1 Cryptology
Definition 1.1 (Cryptography). Cryptography can be said to be a form of communication
concerned with the secure transmission (through encryption) of a secret message over an
insecure channel.
Definition 1.2 (Cryptanalysis). Cryptanalysis deals with attacks on encrypted intercepted
messages with the goal to recover the secret message.
Definition 1.3 (Cryptology). Cryptology is the umbrella term of both cryptography and
cryptanalysis.
1.2 Cryptosystems
Definition 1.4 (Cryptosystem). An encryption scheme or cryptosystem is a tuple (P, C, K, E, D)
with the following properties:
1. P is a set called the plaintext space. Its elements are called plaintexts.
2. C is a set called the ciphertext space. Its elements are called ciphertexts.
3. K is a set called the key space. Its elements are called keys.
4. E = {Ek : k ∈ K} is a family of functions Ek : P → C called encryption functions.
5. D = {Dk : k ∈ K} is a family of functions Dk : C → P called decryption functions.
6. ∀e ∈ K : ∃d ∈ K : ∀p ∈ P : Dd (Ee (p)) = p
Remark. The last point states that for every encryption function there is a decryption func-
tion with the property that decryption applied after encryption yields the original plaintext
message.
1
,1.3 Alphabets and words
Definition 1.5 (Alphabet). An alphabet is set Σ which is finite and nonempty (has to
contain at least one element). The length |Σ| is the amount of elements in Σ. Elements of Σ
are called symbols or letters.
Remark. Because we defined alphabets to be finite sets, their symbols can be identified with
a subset of the natural numbers.
Definition 1.6 (Word). A word or string w ⃗ over the alphabet Σ is a finite sequence of
symbols from Σ, including the empty sequence ϵ, called the empty string. The length of w
⃗
over Σ is the number of its components, denoted by |w|.⃗ |ϵ| = 0. The set of all words of
length n ∈ N over Σ is denoted by Σn . The set of all words over Σ is denoted by Σ∗ .
⃗ ∈ Σ∗ , then ⃗v w
Definition 1.7 (Concatenation). If ⃗v , w ⃗ = ⃗v ◦ w
⃗ is the concatenation of ⃗v
and w.⃗ It’s constructed by putting the sequence w⃗ after the sequence ⃗v . For ϵ it holds that
⃗v ◦ ϵ = ϵ ◦ ⃗v = ⃗v .
1.4 Permutations
Definition 1.8 (Permutation). Let X be a set. A permutation of X is a bijective map
f : X → X. The set of all permutations of X is denoted by S(X).
Definition 1.9 (Bit permutation). Let X = {0, 1}n be the set of all bitstrings of length n.
A bit permutation is a permutation of X in which just the positions of the bits are permuted.
Thus, we can conclude that there are n! bit permutations of bitstrings of length n.
Remark. There are a lot more permutations of {0, 1}n than there are bit permutations. As
stated previously there are n! bit permutations, but since there are 2n elements, there are
(2n )! permutations.
2 Symmetric cryptosystems
2.1 Block ciphers
Definition 2.1 (Block cipher). A cryptosystem is called a block cipher if its plaintext space
and it’s ciphertext space are the set Σn over the alphabet Σ. Or: P = C = Σn . The positive
integer n is called the block length.
Theorem 2.1. The encryption functions of a block cipher are permutations.
Proof. For each encryption function, there is a corresponding decryption function. Thus, the
encryption functions are injective. An injective map of the form Σn → Σn is bijective and
therefore a permutation.
Remark. As computing power increases, the need to easily increase security arises. This can
be done by increasing the key space. To increase the security of a block cipher, it is possible
to apply it a few times. E-D-E triple encryption is used frequently to accomplish this. This
results in a considerably larger key space because keys are three times as long. Using the
same key twice for encryption in E-D-E will only double the key space.
2
, Practical problem with block ciphers: They only encrypt n letters at a time, while the
messages we wish to send will be of arbitrary length. Choosing n as the length of the
message is extremely impractical. Splitting the message in blocks of length n and using some
mode of operation will be the solution.
1. Electronic codebook (ECB)
2. Cipher block chaining (CBC)
3. Cipher feedback (CFB)
4. Output feedback (OFB)
2.1.1 Electronic codebook (ECB)
The general idea of ECB is that an arbitrarily long plaintext message m is decomposed into
blocks mi of length n. If necessary the plaintext can be padded such that its length becomes
a multiple of n. Then each block mi of length n is encrypted individually using Ee . The
total ciphertext c then becomes the sequence of obtained ciphertexts ci . Decryption is then
done by applying the decryption function Dd with decryption key d, corresponding to e.
Figure 1: Diagrammatic representation of encryption and decryption in ECB (sizes are only
marked on the far right, but are the same throughout).
Advantages Disadvantages
Heavily parallelizable Equal plaintext blocks are encrypted into equal ciphertext blocks
Attacker can substitute ciphertext blocks that have been encrypted under the same key
Table 1: Advantages and disadvantages of ECB mode.
3
Cryptosystems
Lennert Saerens
June 2024
1 Basic concepts of cryptography
1.1 Cryptology
Definition 1.1 (Cryptography). Cryptography can be said to be a form of communication
concerned with the secure transmission (through encryption) of a secret message over an
insecure channel.
Definition 1.2 (Cryptanalysis). Cryptanalysis deals with attacks on encrypted intercepted
messages with the goal to recover the secret message.
Definition 1.3 (Cryptology). Cryptology is the umbrella term of both cryptography and
cryptanalysis.
1.2 Cryptosystems
Definition 1.4 (Cryptosystem). An encryption scheme or cryptosystem is a tuple (P, C, K, E, D)
with the following properties:
1. P is a set called the plaintext space. Its elements are called plaintexts.
2. C is a set called the ciphertext space. Its elements are called ciphertexts.
3. K is a set called the key space. Its elements are called keys.
4. E = {Ek : k ∈ K} is a family of functions Ek : P → C called encryption functions.
5. D = {Dk : k ∈ K} is a family of functions Dk : C → P called decryption functions.
6. ∀e ∈ K : ∃d ∈ K : ∀p ∈ P : Dd (Ee (p)) = p
Remark. The last point states that for every encryption function there is a decryption func-
tion with the property that decryption applied after encryption yields the original plaintext
message.
1
,1.3 Alphabets and words
Definition 1.5 (Alphabet). An alphabet is set Σ which is finite and nonempty (has to
contain at least one element). The length |Σ| is the amount of elements in Σ. Elements of Σ
are called symbols or letters.
Remark. Because we defined alphabets to be finite sets, their symbols can be identified with
a subset of the natural numbers.
Definition 1.6 (Word). A word or string w ⃗ over the alphabet Σ is a finite sequence of
symbols from Σ, including the empty sequence ϵ, called the empty string. The length of w
⃗
over Σ is the number of its components, denoted by |w|.⃗ |ϵ| = 0. The set of all words of
length n ∈ N over Σ is denoted by Σn . The set of all words over Σ is denoted by Σ∗ .
⃗ ∈ Σ∗ , then ⃗v w
Definition 1.7 (Concatenation). If ⃗v , w ⃗ = ⃗v ◦ w
⃗ is the concatenation of ⃗v
and w.⃗ It’s constructed by putting the sequence w⃗ after the sequence ⃗v . For ϵ it holds that
⃗v ◦ ϵ = ϵ ◦ ⃗v = ⃗v .
1.4 Permutations
Definition 1.8 (Permutation). Let X be a set. A permutation of X is a bijective map
f : X → X. The set of all permutations of X is denoted by S(X).
Definition 1.9 (Bit permutation). Let X = {0, 1}n be the set of all bitstrings of length n.
A bit permutation is a permutation of X in which just the positions of the bits are permuted.
Thus, we can conclude that there are n! bit permutations of bitstrings of length n.
Remark. There are a lot more permutations of {0, 1}n than there are bit permutations. As
stated previously there are n! bit permutations, but since there are 2n elements, there are
(2n )! permutations.
2 Symmetric cryptosystems
2.1 Block ciphers
Definition 2.1 (Block cipher). A cryptosystem is called a block cipher if its plaintext space
and it’s ciphertext space are the set Σn over the alphabet Σ. Or: P = C = Σn . The positive
integer n is called the block length.
Theorem 2.1. The encryption functions of a block cipher are permutations.
Proof. For each encryption function, there is a corresponding decryption function. Thus, the
encryption functions are injective. An injective map of the form Σn → Σn is bijective and
therefore a permutation.
Remark. As computing power increases, the need to easily increase security arises. This can
be done by increasing the key space. To increase the security of a block cipher, it is possible
to apply it a few times. E-D-E triple encryption is used frequently to accomplish this. This
results in a considerably larger key space because keys are three times as long. Using the
same key twice for encryption in E-D-E will only double the key space.
2
, Practical problem with block ciphers: They only encrypt n letters at a time, while the
messages we wish to send will be of arbitrary length. Choosing n as the length of the
message is extremely impractical. Splitting the message in blocks of length n and using some
mode of operation will be the solution.
1. Electronic codebook (ECB)
2. Cipher block chaining (CBC)
3. Cipher feedback (CFB)
4. Output feedback (OFB)
2.1.1 Electronic codebook (ECB)
The general idea of ECB is that an arbitrarily long plaintext message m is decomposed into
blocks mi of length n. If necessary the plaintext can be padded such that its length becomes
a multiple of n. Then each block mi of length n is encrypted individually using Ee . The
total ciphertext c then becomes the sequence of obtained ciphertexts ci . Decryption is then
done by applying the decryption function Dd with decryption key d, corresponding to e.
Figure 1: Diagrammatic representation of encryption and decryption in ECB (sizes are only
marked on the far right, but are the same throughout).
Advantages Disadvantages
Heavily parallelizable Equal plaintext blocks are encrypted into equal ciphertext blocks
Attacker can substitute ciphertext blocks that have been encrypted under the same key
Table 1: Advantages and disadvantages of ECB mode.
3
