This is a study note of “Understanding Cryptography” ch01. It covers:

- The general rules of cryptography
- Key lengths for short-, medium- and long-term security
- The difference between different types of attacks against ciphers
- A few historical ciphers
- Modular arithmetic
- Why one should only use well-established encryption algorithms

## 1 Introudction

**Cryptology** splits into two main branches: **Cryptography** for building cryptosystem and **Cryptanalysis** for braking cryptosystem. Cryptography has three branches: **symmetric algorithms**, **asymmetric algorihms** and **cryptographic protocols**. The cryptographic protocols are applications built upon the primitives provided by symmetric and asymmetric algorithms.

## 2 Symmetric Cryptography

Symmetric cryptographic schemes are also referred to as **symmetric-key**, **secret-key**, and **single-key** schemes or algorithms.

The only way to find out whether an encryption method is strong, i.e., cannot be broken by a determined attacker, is to make it public and have it analyzed by other cryptographers.

Good ciphers should hide the statistical properties of the encrypted plaintext. The ciphertext symbols should appear to be random. Also, a large key space alone is not sufficient for a strong encryption function.

## 3 Cryptanalysis

Cryptanalysis has three branches: classic cryptanalysis, implementation attacks and social enginnering. Classic cryptanalysis has mathematical analysis and brute-force attacks. Implementation attacks include buffer overflow attacks and side-channel analysis that often targets hardware.

**Kerckhoffs’ Principle**: A cryptosystem should be secure even if the attacker (Oscar) knows all details about the system, with the exception of the secret key. In particular, the system should be secure when the attacker knows the encryption and decryption algorithms.

**Security by Obscurity** is a bad idea. An example is the Content Scrambling System (CSS) for DVD content protection, which was broken easily once it was reverseengineered.

## 4 Modular Arithmetic

**Caesar cipher** is a modular addition with a fixed value. **Affine cipher** uses multiplication and modular additions.

### 4.1 Modulo Operation

Modulo operation definition: Let `a`

, `r`

,`m`

∈ `Z`

(where `Z`

is a set of all integers) and `m > 0`

. We write `a ≡ r mod m`

if `m`

divides `a - r`

. `m`

is called the **modulus** and `r`

is called the **remainder**.

There are infinitely many valid remainders for any `m`

and `r`

. For example: `12 ≡ 3 mod 9`

,`12 ≡ 21 mod 9`

, `12 ≡ −6 mod 9`

. Because `9`

divides `(12 - 3)`

, `12 - 21`

and `12 - (-6)`

. They are call an **equivalence class**. There are a total nine eqivalence classes for the modulus `9`

.

By agreement, we usually choose `r`

such that `0 <= r < m`

.

### 4.2 Ring

An integer ring `Zm`

consists of:

- The set
`Zm = {0,1,2, . . . ,m−1}`

- Two operations
`+`

and`·`

for all`a,b ∈ Zm`

such that:`a+b ≡ c mod m , (c ∈ Zm)`

`a·b ≡ d mod m , (d ∈ Zm)`

A ring is **closed** and has the following properties:

- Addition and multiplication are
**associative** - The
**distributive law**holds:`a·(b + c) = (a·b) + (a·c)`

. - There is the neutral element
`0`

with respect to addition, i.e., for every element`a ∈ Zm`

it holds that`a+0 ≡ a mod m`

. - For any element
`a`

in the ring, there is always the negative element`−a`

such that`a+(−a) ≡ 0 mod m`

, i.e., the additive inverse always exists. - There is the neutral element
`1`

with respect to multiplication, i.e., for every element`a ∈ Zm`

it holds that`a·1 ≡ a mod m`

. - The multiplicative inverse exists only for some, but not for all, elements. Let
`a ∈ Z`

, the inverse`a^(−1)`

is defined such that`a · a^(−1) ≡1 mod m`

. If an inverse exists for`a`

, we can divide by this element since`b/a ≡ b·a^(−1) mod m`

. - It takes some effort to find the inverse but it is easy to tell whether an inverse exists or not. An element
`a ∈ Z`

has a multiplicative inverse if and only if`gcd(a,m) = 1`

,

In summary, roughly speaking, we can say that the ring `Zm`

is the set of integers `{0,1,2, . . . ,m−1}`

in which we can add, subtract,
multiply, and sometimes divide.

### 4.3 Two Ciphers

Shift Cipher has a key space of `26`

:

- Let
`x,y,k ∈ Z26`

- Encryption:
`ek(x) ≡ x+k mod 26`

- Decryption:
`dk(y) ≡ y−k mod 26`

Affine Cipher has a key space of `12 * 26 = 312`

:

- Let
`x,y,a,b ∈ Z26`

- Encryption:
`ek(x)= y ≡ a·x + b mod 26`

- Decryption:
`dk(y) ≡ a^(-1)·(y−b) mod 26`

The key: `k = (a,b)`

has the restriction: `gcd(a,26) = 1`

. Thus `a`

must be in the set `{1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25}`

to make `gcd(a, 26) = 1`

.