Dit is de samenvatting van de hoorcolleges Cryptografie. In deze samenvatting werd informatie uit zowel de slides, als eventuele extra notities bij de slides opgenomen.
Resultaat: 18/20
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
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur lennyS. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €5,48. Vous n'êtes lié à rien après votre achat.
