Table of Contents

• Symmetric Cryptography
• Cryptanalysis
• Why do we need Cryptanalysis
• Attacking Cryptosystems
• Brute-force attack
• Substitution Cipher
• Brute-force
• Frequency Analysis
• Modular Arithmetic
• Add stuff
• Properties of Modular Arithmetic
• Algebraic View

---

Symmetric Cryptography

• Also known as private-key, single-key, secret-key cryptography

Problem: If Alice and Bob would like to communicate via an unsecure channel, then a third party, should not be able to understand the communications

Encrypted and decrypted with respective functions

• $x$ is the plaintext

• $y$ is the ciphertext

• $K$ is the key

• Set of all keys ${K_1,K_2, ... , K_n}$

• Encryption equation -> $y = e_K(x)$

• Decryption equation -> $x = d_K(y)$

Note that encryption and decryption are inverse operations if the same key $K$ is used on both sides and must be transmitted via a secure channel between Alice and Bob. System is secure iff attacker doesn't learn the key $K$.

$d_K(y) = d_K(e_K(x)) = x$

Note: Problem of secure communication reduced to secure transmission and storage of key $K$

Cryptanalysis

Why do we need Cryptanalysis

• No unconditional mathematical proof of security for any practical cipher

Kerckhoff's Principle

A cryptosystem should be secure even if the attacker knows all details about the system, with the exception of the secret key.

Attacking Cryptosystems

• Classical Attacks
  • Mathematical Analysis
  • Brute-force Attack
• Implementation Attack -> Extract key through reverse engineering or power measurement
• Social Engineering -> Trick user into giving up password

Brute-force attack

• Requires at least 1 plaintext-ciphertext pair $(x_0,y_0)$
• Check all possible keys until condition is fulfilled

$d_K(y_0) =^? x_0$

Substitution Cipher

• Encrypt letters rather than bits
  • Replace each plaintext letter by another letter

Brute-force

• Try all possible permutations until an intelligent plaintext appears

• Possible keys -> $26 \times 25 \times ... \times 2 \times 1 = 26! \approx 2^88$

Frequency Analysis

Frequency of letters can give away/break sub-ciphers

Example

---

Modular Arithmetic

Cryptosystems based on sets of numbers

1. Discrete -> Sets with integers are partially useful
   • i.e. no floating point numbers, integers only
2. Finite -> If we only compute with a finitely many numbers

Definition Let $a,r,m$ be integers and $m > 0$. We write

if $(a - r)$ is divisible by $m$

• $m$ is called the modulus
• $r$ is called the remainder

Add stuff

Properties of Modular Arithmetic

Algebraic View