Introduction to Cryptography @ Coursera

A cheat sheet

This cheatsheet wants to provide an overview of the concepts and the used formulas and definitions of the »Introduction to Cryptography« online course at coursera.

Week 1

Notes on Notation

Note that both $\leftarrow$ and $:=$ are used as assignments. However, $\leftarrow$ denotes assignments where subsequent execution of the right side might not yield the same result, meaning it is possibly randomized. $:=$ is used for deterministic assignments. $=$ is used for mathematical equality.

Overview of Modular Arithmetic

• $x = x' \mod N$ if and only if $N$ divides by $x-x'$.
• $\left[x \mod N\right]$ denotes the remainder when $x$ is divided by $N$ (the unique value $x' \in \{0,…,N-1\}$ such that $x = x' \mod N$).

Introduction

Private-key Encryption

For a message space $M$ the private key encryption scheme is defined by a number of algorithms:

• Gen: the key generation algorithm yielding $k$
• Enc: the encryption algorithm taking key $k$, message $m \in M$ as input. Outputs ciphertext $c$: $c \leftarrow \text{Enc}_k(m)$
• Dec: the decryption algorithm takes key $k$, ciphertext $c$ as input, yielding either $m$ or an error: $m := \text{Dec}_k(c)$

Any encryption scheme is required to satisfy the following correctness requirement: $\forall m \in M$, $k$ given by $\text{Gen}: \;\;\; \text{Dec}_k(\text{Enc}_k(m)) = m$

Example: The Shift Cipher

Considering the encryption of english text (only lower case characters). a is associated with $0$, b with $1$ and so on. $k \in \{1,2,…,25\}$. To encrypt using the key $k$, shift every letter of the plaintext message by $k$ positions (with wraparound). Decryption is just the reverse operation.

More formally, the scheme can be defined as:

• $M = \{$ strings over lowercase English alphabet $\}$
• $\text{Gen}$: choose uniformly $k\in\{0,…,25\}$
• $\text{Enc}_k(m_1, …, m_t)$: output $c_1,…,c_t$ where $c_i := \left[ m_i + k \mod 26 \right]$
• $\text{Dec}_k(c_1,…,c_t)$: output $m_1, …, m_t$ where $m_i := \left[c_i - k \mod 26\right]$

Note that the scheme is not safe as an attacker can simply try all possible keys. This assumes however, that the attacker does know which scheme was used in the first place.

Definition: Kerckhoff's Principle

The encryption scheme itself is not secret. The only secret is the key which must be chosen at random and kept secret. This principle is subject to controversion. Arguments in favor of this principle however include that it is easier to change the key than to change the algorithm, that it is easier to keep the key secret than the algorithm for two participators. Additionally it is easier to deploy and its open approach leads to public validation if the algorithm is known.

Definition: Sufficient Key Space Principle

A too small key space for an encryption scheme is vulnerable to exhaustive-search attacks. However, large key spaces do not guarantee security.

Example: The Vigenère Cipher

The key is now a string, not just a character. To encrypt a message the characters are shifted by the respective character of the key, which is repeated in a wrap around manner for messages longer than the key. Decryption is again just the reverse operation.

The key space for this scheme with a key size of $14$ is $26^{14} \approx 2^66$ which renders brute-force search attacks useless. The scheme however is not secure as it can be attacked differently.

Suppose a key of length 14. Then every 14th character in the ciphertext was shifted the same amount. Together with plain text letter frequencies the following algorithm can be applied:

• Look at every 14th character, starting with the first
• Let $\alpha$ be the most common character appearing in this portion of the ciphertext
• Most likely, this character corresponds to the most common plaintext character $e$. Guess the first character of the key is $\alpha - e$
• Repeat for remaining positions

There are better (but more complicated) attacks available for this scheme, however this attack will work for long enough Vigenère ciphers.

Breaking the Vigenère Cipher

Variant Vigenère Cipher

An alternative variant of the cipher views the message as ASCII plaintext and the ciphertext as hex. This way it supports arbitrary letters (punctuation and capitals). Instead of modulo we can use XOR.

The key is a string of bytes. The plaintext is a string of ASCII chars. To encrypt, XOR each character in the plaintext with the next character of the key, which is wrapped around as needed. Decryption again just is the reverse process.

Example

• Plaintext: Hello! (hex: 0x48 65 6C 6C 6F 21)
• Key: 0xA1 2F
• Encrypt by using XOR with 0xA1 2F A1 2F A1 2F
• Take as an example: 0x48 $\oplus$ 0xA1
  This can be expressed as: 0100 1000 $\oplus$ 1010 0001 = 1110 1001 = 0xE9
• The ciphertext then is: 0xE9 4A CD 43 CE 0E

Attacking the Variant Cipher

Basically we need two steps:

• Determine the key length
• Determine each byte of the key

Determining the Key Length

Let $p_i$ (for $0 \leq i \leq 255$) be the frequency of byte $i$ in plaintext (English text)

• i.e., $p_i = 0$ for $i < 32$ or $i > 127$ (non printable chars)
• i.e., $p_{97} = $ frequency of a

If the key length is $N$ then every $N$th character of the plaintext is encrypted using the same shift. If we take every $N$th character and calculate frequencies, we should get the $p_i$'s in permuted order. If we take every $M$th character ($M$ not a multiple of $N$) and calculate frequencies, we should get something close to uniform. In this case $M$ can be dismissed as the key length because it is not a permutation of the frequencies of english text.

To distinguish these two, compute $\sum q_i^2$ for some candidate distribution $q_0, …, q_{255}$. If it is close to uniform it is roughly $\frac{1}{256}$. If it is a permutation of $p_i$, then $\sum q_i^2 \approx \sum p_i^2$ and it will be much larger than $\frac{1}{256}$.

In order to find the key length we compute $\sum q_i^2$ and choose the maximum value for a candidate length.