Summary Cryptography: Definitions, Theorems, Remarks and Cryptosystems
10 views 0 purchase
Course
Cryptography (4017306ENR)
Institution
Vrije Universiteit Brussel (VUB)
Book
Introduction to Cryptography
This is the summary of the Cryptography lectures. This summary included information from both the slides and any additional notes to the slides.
Result: 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
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller lennyS. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.91. You're not tied to anything after your purchase.
