Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data
Security
Applied Cryptography
A01: Introduction and History
Ina Schiering
Ostfalia Hochschule für angewandte Wissenschaften
Ina Schiering, Applied Cryptography 1 / 25
Literature
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography This course is mainly based on the following book:
and Data
Security Paar, Christof, and Jan Pelzl. Understanding cryptography: a
Overview of Cryptology
Symmetric
Cryptography
textbook for students and practitioners. Springer Science &
Simple Symmetric
Encryption: The
Business Media, 2009.
Substitution Cipher
Cryptoanalysis
The german version of the book is available as ebook via VPN:
Modular Arithmetic and
More Historical Ciphers [Link]
978-3-642-04101-3
Additional resources will be given during the course.
Ina Schiering, Applied Cryptography 2 / 25
Summary
Applied
Cryptography
This course will follow mainly the description of “Curriculum 1
Ina Schiering (applications of cryptography)”.
Introduction to
• 1. Introduction and History
Cryptography
and Data
• 2. Stream Ciphers
Security
Overview of Cryptology
• 4. AES
Symmetric
Cryptography • 5.1 Block Ciphers: Modes of Operation
Simple Symmetric
Encryption: The
Substitution Cipher
• 6 Public-Key Cryptography
Cryptoanalysis
Modular Arithmetic and • 7 RSA
More Historical Ciphers
• 8 Diffie-Hellman (Discrete Logarithm Problem)
• 9 Elliptic Curve Cryptosystems
• 10.1 - 10.2 Digital Signatures
• 11.1 - 11.3 Hash Functions
• 12 Message Authentication Codes (MAC)
• 13 Key Establishment
Ina Schiering, Applied Cryptography 3 / 25
Examples for Cryptology and Cryptography
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data
Security
Overview of Cryptology
Symmetric
Cryptography What are examples of Cryptology and Cryptography and
Simple Symmetric
Encryption: The
Substitution Cipher
applications?
Cryptoanalysis
Modular Arithmetic and
More Historical Ciphers
Ina Schiering, Applied Cryptography 4 / 25
Examples for Cryptology and Cryptography
Applied
Cryptography
Ina Schiering
Introduction to • History: Enigma (World War II), scytale (in ancient Greece)
Cryptography
and Data • Today: email encryption (PGP, DANE), HTTPS, hashing to
Security
Overview of Cryptology ensure the integrity of data or prove the identity of the author
Symmetric
Cryptography
Simple Symmetric
• Additional means are: e.g. Steganography to hide content
Encryption: The
Substitution Cipher instead of encrypting it.
Cryptoanalysis
Modular Arithmetic and
More Historical Ciphers
• Advances applications: e.g. Attribute Based Credentials
(ABC)
• Risks: “PRISM”, organized crime, compliance, quantum
computing
Ina Schiering, Applied Cryptography 5 / 25
Overview
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography Cryptology
and Data
Security
Overview of Cryptology
Symmetric
Cryptography
Cryptography Cryptoanalysis
Simple Symmetric
Encryption: The
Substitution Cipher
Cryptoanalysis
Symmetric Asymmetric Cryptographic
Modular Arithmetic and Ciphers Ciphers Protocols
More Historical Ciphers
Block Ciphers Stream Ciphers
Ina Schiering, Applied Cryptography 6 / 25
Definitions - Cryptology
Applied
Cryptography
Ina Schiering
Cryptology
Introduction to
Cryptography Cryptography Cryptoanalysis
and Data
Symmetric Asymmetric Cryptographic
Security
Ciphers Ciphers Protocols
Overview of Cryptology
Symmetric Block Ciphers Stream Ciphers
Cryptography
Simple Symmetric
Encryption: The
Substitution Cipher
• Cryptology science concerned with data communication and
Cryptoanalysis
Modular Arithmetic and
storage in secure and usually secret form
More Historical Ciphers
• Cryptography science of secret writing with the goal of
hiding the the meaning of a message
• Cryptoanalysis science of breaking cryptosystems
Ina Schiering, Applied Cryptography 7 / 25
Definitions - Cryptology
Applied
Cryptography
Cryptology
Ina Schiering
Cryptography Cryptoanalysis
Introduction to
Cryptography Symmetric Asymmetric Cryptographic
and Data Ciphers Ciphers Protocols
Security
Overview of Cryptology Block Ciphers Stream Ciphers
Symmetric
Cryptography
Simple Symmetric
• Symmetric Cipher two parties have an encryption and
Encryption: The
Substitution Cipher decryption method for which they share a secret key
Cryptoanalysis
Modular Arithmetic and
More Historical Ciphers
• Asymmetric (or Public-Key) Cipher the user possesses
public key for encryption and a private key for decryption
• Cryptographic Protocols are based on symmetric and
asymmetric algorithms as building blocks. Examples are TLS,
etc.
Ina Schiering, Applied Cryptography 8 / 25
Communication over an insecure channel
Applied
Cryptography
Ina Schiering
Oscar
(bad)
Introduction to
Cryptography x
and Data
Security
Overview of Cryptology Alice x insecure x Bob
Symmetric (good) channel (good)
Cryptography
Simple Symmetric
Encryption: The
Substitution Cipher
Cryptoanalysis
• Alice and Bob want to communicate over an insecure channel
Modular Arithmetic and
More Historical Ciphers • The insecure channel is a communication link, e.g. the
Internet, mobile phone call, Wi-Fi communication.
• Oscar has access to this channel and is an unauthorized
listener or eavesdropper, attacker.
Ina Schiering, Applied Cryptography 9 / 25
Symmetric-Key Cryptosystem
Applied
Cryptography
Oscar
Ina Schiering
(bad)
Introduction to y
Cryptography
and Data
Security Alice x encryption y insecure y decryption x Bob
Overview of Cryptology (good) e() channel d () (good)
Symmetric
Cryptography
Simple Symmetric k k
Encryption: The
Substitution Cipher
Cryptoanalysis
secure channel
Modular Arithmetic and
More Historical Ciphers
• x is called plaintext or cleartext
• y is called ciphertext
• k is called the key
• the set of all possible keys is called key space
Ina Schiering, Applied Cryptography 10 / 25
Symmetric-Key Cryptosystem
Oscar
Applied (bad)
Cryptography
y
Ina Schiering
Alice x encryption y insecure y decryption x Bob
Introduction to (good) e() channel d () (good)
Cryptography
and Data k k
Security
Overview of Cryptology
secure channel
Symmetric
Cryptography
Simple Symmetric
Encryption: The
• Alice and Bob exchange via a secure channel a common
Substitution Cipher
Cryptoanalysis
secret key.
Modular Arithmetic and
More Historical Ciphers • Alice encrypts the message x using a symmetric encryption
algorithm y = ek (x )
• Bob decrypts the ciphertext y using the inverse process of
encryption x = dk (y ).
• Oscar only perceives the ciphertext y . If the encryption
algorithm is strong and the protocol used is appropriate, the
ciphertext will look like random bits.
Ina Schiering, Applied Cryptography 11 / 25
Symmetric-Key Cryptosystem - Remarks
Applied
Cryptography
• The encryption and decryption algorithms are public.
Ina Schiering
• The secret consists only of the key.
Introduction to
Cryptography • The problem of transmitting a message securely is reduced to
and Data
Security the problem of transmitting and storing a key securely.
Overview of Cryptology
Symmetric
Cryptography
• A secret algorithm is an untested algorithm
Simple Symmetric
Encryption: The (Security by obscurity)!
Substitution Cipher
Cryptoanalysis
Modular Arithmetic and
• Methods for establishing keys over insecure channels will be
More Historical Ciphers
introduced later.
• The scenario above only addresses confidentiality. Other
scenarios for an opponent (Oscar) are to make unnoticed
changes to the message (integrity ).
• Cryptography can be also used to ensure the identity of the
sender of a message (authentication).
Ina Schiering, Applied Cryptography 12 / 25
Substitution Cypher
Applied
Cryptography
Ina Schiering • The idea of the substitution cipher is to define a bijective
Introduction to substitution function f : Σ → Σ on the alphabet Σ and to
Cryptography
and Data
substitute the letters of the plaintext according to that function
Security
Overview of Cryptology
A → k
Symmetric
Cryptography B → d
Simple Symmetric
Encryption: The
Substitution Cipher
C → w
Cryptoanalysis
Modular Arithmetic and
...
More Historical Ciphers
• The key k is the substitution function.
• The substituion cipher is not secure!
• Example:
iq ifcc vqqr fb rdq vfllcq na rdq cfjwhwz hr bnnb
hcc hwwhbsqvqbre hwq vhlq
Ina Schiering, Applied Cryptography 13 / 25
Brute-Force Attack or Exhaustive Search
Applied
Cryptography
Ina Schiering
Introduction to The idea of a brute-force attack is that the attacker has a
Cryptography
and Data
ciphertext and a piece of the plaintext (e.g. header of files) and
Security
Overview of Cryptology
decrypts the first part of the ciphertext with all possible keys.
Symmetric
Cryptography • Let (x , y ) be a pair of plaintext and corresponding ciphertext.
Simple Symmetric
Encryption: The
Substitution Cipher
Let K = k1 , . . . , kn be the key space of all possible keys ki . Let
Cryptoanalysis
Modular Arithmetic and
dki () be the decryption function.
More Historical Ciphers
• A brute-force attack now checks for every ki ∈ K if
dki (y ) = x
Ina Schiering, Applied Cryptography 14 / 25
Brute-Force Attack or Exhaustive Search
Applied
Cryptography
Ina Schiering
Introduction to • Because of false positives it might be needed to test all keys
Cryptography
and Data in the key space K .
Security
Overview of Cryptology • If testing all keys takes too much time (with appropriate
Symmetric
Cryptography
Simple Symmetric
budget), the cipher is computationally secure against a
Encryption: The
Substitution Cipher brute-force attack
Cryptoanalysis
Modular Arithmetic and
More Historical Ciphers
• The key space of the substitution cipher for the alphabet
Σ = {A, . . . , Z } is
26 · 25 · . . . · 3 · 2 · 1 = 26! ≈ 288
Ina Schiering, Applied Cryptography 15 / 25
Letter Frequency Analysis
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data
Security
Overview of Cryptology
Symmetric
Cryptography
Simple Symmetric Quelle: Wikipedia
Encryption: The
Substitution Cipher
Cryptoanalysis
• Plaintext symbols are always mapped to the same ciphertext
Modular Arithmetic and
More Historical Ciphers symbol by the substitution cipher.
• The statistical properties of the plaintext are preserved in the
ciphertext.
• The method can be generalized by considering pairs, triples,
or n-grams in general.
• If word separators are preserved, short words as THE,
AND, OF, ... can be used as additional information.
Ina Schiering, Applied Cryptography 16 / 25
Lessons Learned
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data
Security
Overview of Cryptology • Good ciphers hide statistical properties of the plaintext.
Symmetric
Cryptography
Simple Symmetric
• The ciphertext symbols should appear to be random.
Encryption: The
Substitution Cipher
Cryptoanalysis
• A large key space is an important but not sufficient
Modular Arithmetic and
More Historical Ciphers
requirement for a strong encryption function.
Ina Schiering, Applied Cryptography 17 / 25
Cryptoanalysis
Applied
Cryptography
Cryptoanalysis
Ina Schiering
Introduction to Classical Implementation Social
Cryptography Cryptoanalysis Attacks Engineering
and Data
Security Mathmatical Brute-Force
Overview of Cryptology Analysis Attacks
Symmetric
Cryptography
Simple Symmetric
Encryption: The
• Classical Cryptoanalysis: The science of recovering the
Substitution Cipher
Cryptoanalysis
plaintext x from the ciphertext y .
Modular Arithmetic and
More Historical Ciphers • Implementation Attacks: Attacker needs physical access to
the system or secure channel to perform a side-channel
analysis, e.g. by measuring power consumption.
• Social Engineering: Beside technical measurements training
and awareness of people is equally important.
Ina Schiering, Applied Cryptography 18 / 25
Kerckhoffs’ Principle
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data
Security
Overview of Cryptology
A cryptosystem should be secure even if the attacker knows all
Symmetric
Cryptography
Simple Symmetric
details about the system with the exception of the secret key. In
Encryption: The
Substitution Cipher particular, the system should be secure when the attacker knows
Cryptoanalysis
Modular Arithmetic and the encryption and decryption algorithms.
More Historical Ciphers
Ina Schiering, Applied Cryptography 19 / 25
Key Length
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data
Security
Overview of Cryptology
Symmetric
Cryptography
For a recommendation concerning appropriate key length the
Simple Symmetric
Encryption: The
following source summarizes actual recommendations:
Substitution Cipher
Cryptoanalysis
[Link]
Modular Arithmetic and
More Historical Ciphers
Ina Schiering, Applied Cryptography 20 / 25
Modular arithmetic
Applied
Cryptography
Ina Schiering Let a, r , m ∈ Z and m > 0. We write
Introduction to
Cryptography a≡r mod m
and Data
Security
Overview of Cryptology
Symmetric
if m divides a − r .
Cryptography
Simple Symmetric
Encryption: The
• m is called the modulus and r is called the remainder.
Substitution Cipher
Cryptoanalysis • The set {r |a ≡ r mod m} is an equivalence class for all
Modular Arithmetic and
More Historical Ciphers a, m ∈ Z, m > 0.
• For mathematical operations it is possible to choose
appropriate elements of the equivalence class.
• The set Zm = {0, 1, . . . , m − 1} with the operations +, × (
mod m) form a ring.
Ina Schiering, Applied Cryptography 21 / 25
Mathematical background
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
For the lecture the following mathematical background is needed:
and Data
Security
• m is called the modulus and r is called the remainder.
Overview of Cryptology
Symmetric • The set {r |a ≡ r mod m} is an equivalence class for all
Cryptography
Simple Symmetric
Encryption: The
a, m ∈ Z, m > 0.
Substitution Cipher
Cryptoanalysis • For mathematical operations it is possible to choose
Modular Arithmetic and
More Historical Ciphers
appropriate elements of the equivalence class.
• The set Zm = {0, 1, . . . , m − 1} with the operations +, × (
mod m) form a ring.
Ina Schiering, Applied Cryptography 22 / 25
Ring
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data
Security A set R with to binary functions +, × on R is a ring if and only if
Overview of Cryptology
Symmetric
Cryptography
• (R , 0, +) is a commutative group with the neutral element 0.
Simple Symmetric
Encryption: The • (R , 1, ×) is a monoid (associative, neutral element) with the
Substitution Cipher
Cryptoanalysis
neutral element 1.
Modular Arithmetic and
More Historical Ciphers
• The distributive law holds for R, +, ×
Ina Schiering, Applied Cryptography 23 / 25
Caesar Cipher or Shift Cipher
Applied
Cryptography
Ina Schiering
Introduction to
Cryptography
and Data The Shift cipher is a special case of the substitution cipher. The
Security
Overview of Cryptology substitution function is a shift on the alphabet for k positions.
Symmetric
Cryptography
Simple Symmetric
• Let x , y , k ∈ Z26 .
Encryption: The
Substitution Cipher
Cryptoanalysis
• Encryption: ek (x ) ≡ x + k mod 26.
Modular Arithmetic and
More Historical Ciphers • Decryption: dk (y ) ≡ y − k mod 26.
The size of the key space is only 26.
Ina Schiering, Applied Cryptography 24 / 25
Affine Cipher
Applied
Cryptography
Ina Schiering
The Affine cipher is a an improvement of the shift cipher by
Introduction to
Cryptography generalizing the encryption and decryption functions (+, −). The
and Data
Security key k = (a, b) consists of two parts. The plaintext symbols are
Overview of Cryptology
Symmetric
multiplied by a followed by addition with b.
Cryptography
Simple Symmetric
Encryption: The
• Let x , y , a, b ∈ Z26 . k = (a, b) with gcd(a, 26) = 1.
Substitution Cipher
Cryptoanalysis • Encryption: ek (x ) = y ≡ a · x + b mod 26.
Modular Arithmetic and
More Historical Ciphers
• Decryption: dk (y ) = x ≡ a−1 · (y − b) mod 26.
Why is the restriction for the key k = (a, b) with gcd(a, 26) = 1
needed?
What is the size of the key space?
Ina Schiering, Applied Cryptography 25 / 25