# COM-401: Cryptography and Security

"A man provided with paper, pencil, and rubber, and subject to strict discipline, is in effect a universal machine." - Alan Turing

This compendium is made for the course COM-401 Cryptography and Security at École Polyteqnique Fédérale de Lausanne (EPFL) and is a summary of the lectures and lecture notes. Is is not the complete curriculum, but rather a list of reading material.

# Ancient Cryptography

## Terminology

Confidentiality | Only receiver shall receive message |

Authentication | Only sender can send the message |

Integrity | Message shall not change |

## Cryptography Prehistory

### Transposition

Transposition moves the characters around, but all the characters are still in place.

**Scylates** is a cylider with a belt wrapped around. Only cylinder of same circumference can decrypt message.

### Simple substitution

Substitute each letter in the alphabet by another letter. **Ceasar cipher** that is a shift in the alphabet by two positions.

Simple substitution can easily be broken by statistical analysis, i.e. frequency analysis, digrams, trigrams, etc..

### Vignère cipher

Is configured by a key. Algorithm can be known. *Add more info*

Can be broken by guessing key lenght and doing statistical analysis on each column.

**Kasinsky**: Frequent patterns is not random. Can guess key lenght out of this.

**Index of coincidence**: Can guess key lenght and test with index of coincidence. This will reveal key length since natural languace does not have the same IoC as random text.

## Pre-Modern Industrial Cryptography

### Enigma

### Kerckhoffs principle

Do not make security dependent on the secrecy of its design. Instead, use an easy to select secret key.

## Cryptography and Information Theory

### Vernam cipher:

$ (x_1, ... , x_n) \oplus (y_1, ... , y_n) = (x_1 \oplus y_1, ... , x_n \oplus y_n) $ $ a \oplus b = (a + b)\bmod 2 $ for$a, b \in {0, 1} $

Do not encrypt two times with same key!

# Diffie-Hellman Cryptography

## Artihmetics and Zn

- For all
$a \in \mathbb{Z}$ and$n \gt 0$ , there exists a unique way to write$ a = qn + r$ with$q;r \in \mathbb{Z}$ and$ 0 \leq r \le n$ . $ a \boxplus b = (a + b) mod n$ and$ a \boxtimes b = (a \cdot b) mod n$

## Groups: Theory, Algorithms and Diffie-Hellman Key Exchange

### Group definition

A group is a set with a dyadic operation + such that:

- The set is closed under the operation: for all
$a$ and$b$ in$G$ , we have$a + b \in G$ - The operation is assiciative: for all
$a;b;c \in G$ , we have$(a + b) + c = a + (b + c)$ - There exists a neutral element 0: for all
$a \in G$ , we have$a + 0 = 0 + a = a$ - Every set element has an inverse: for all
$a \in G$ , there exits an eleent in$G$ denoted by$-a$ such that$ a + (-a) = (-a) + a = 0$

The group is said Abelian if the operation is further commutative: for all

We have both addition groups and multiplication groups. An element added (multpilied with itsef is denoted

A mapping from one group to another is called homomorphisms, and isomorphisms if they are further bijective.

### The Diffie-Hellman Key Exchange

- The existense of subgroups, in general, create security problems and should be avoided, by taking groups of prime order.
- The existence of the trivial subgroup
$\{1\}$ cannot be avoided and a specific countermeasure must be taken in te protocol. - The value
$\mathbb{K} = g^{xy}$ may have some bad distribution and it canoot be used directly as a symmetric key.

We use a goup whose order

The key exchange follows:

**Alice**: pick$x \in \mathbb{Z}^*_q, X \gets g^x$ **Bob**: if$X \notin \langle g \rangle - \{1\}$ , abort**Bob**: pick$y \in \mathbb{Z}^*_q, Y \gets g^y$ **Alice**: if$Y \notin \langle g \rangle - \{1\}$ , abort**Both**:$K \gets KDF(Y^X)$

There is still a problem with the active man-in-the-middle attack. The adversary Eve can pretend to be the other part in this key exchange and can therefor perform an active attack.

The hardness of the computatilnal Diffie-Hellman problem implies the hardness of the discrete logarithm problem in the same group.

### The ElGamal Public-Key Cryptosystem

Three algorithms

- A key generation algorithm, produsing a key pair
$(K_p; K_s)$ . - An encryption algorithm, using the public key
- A decryption algorithm, using the secret key.

We could use Bob's key

# RSA Cryptography

## Euler and other Chinese

## Orders in a group

## Primality testing

## RSA Basics

- Public key consist of modulus
$n = pq$ and some exponent$e$ such that$gcd(e, \varphi (n)) = 1$ . Note that$\varphi (n) = (q - 1)(p - 1)$ - Secret key is the inverse
$d$ of$e$ modulo$\varphi (n)$ .$ d = e^{-1} \mod \varphi(n) $ **Encrypt**:$y = x^e \mod n$ **Decrypt**:$x = y^d \mod n$

## Quadratic Residuosity

In a field, the equation

For

Given a prime

# Elliptic Curve Cryptography

## Galois fields

All finite fields have cardinality

In cryptography we are interested in prime fields with cardinality of a large prime number

Characteristics of a binary field:

$-a = a$ $(a + b)^2 = a^2 + b^2$ $\sqrt{a} = a^{2^{k - 1}}$ $Tr(a) = a + a^2 + ... + a^{2^{k - 1}}$ $Tr(a^2) = Tr(a)$

In

## Elliptic curves

Over a field **R** an elliptic curve with parameters *point of infinity*

Slope between two points

## Elliptic curves over a prime field

Characteristics:

- for
$P = (x_P, y_P)$ , we let$−P = (x_P,−y_P)$ and$−O = O$ - for
$P = (x_P, y_P)$ and$Q = (x_Q, y_Q)$ , if$Q = −P$ we let$P+Q = O$ - ...

# Symmetric encryption

Symmetric encryption uses the same key for encryption and decryption. Main focus on two types, block ciphers and stream ciphers.

## Block ciphers

### DES

- Encrypts blocks of 64 bits with a key of 56 effective bits (last 8 are checksum).
- The 56-bit key is expanded into 16 48-bit subkeys.
- The encryption goes through 16 rounds, each uses a subkey as the round key.
- Follows the Feistel scheme

Can do double or triple encryption. Triple is defined as

### AES

Encrypts blocks of 128 bits using keys of 128, 192 or 256 bits with 10, 12 or 14 rounds respectively. Each 16 bytes (128 bits) represent an element in

- AddRoundKey
- SubBytes
- ShiftRows
- MixColumns

See more on AES here

### Modes of operation

**ECB**: Electronic Codebook**CBC**: Cipher Block Chaining**OFB**: Ouput Feedback**CFB**: Cipher Feedback**CTR**: Counter**TCB**: Tweaked-codebook**XTS**: For harddisks etc.

## Stream ciphers

Encrypt streams of data on-the-fly.

### RC4

RC4 geneates a key-stream of bytes from a secret key (a nonce) which is a sequence of bytes of total lenght between 40 and 256 bits. It is based on operations in the

Known weaknesses slike correlation between some key byte and some output bytes. Passive key recovery attacks in WEP. Cipher text only attacks in TLS when same plaintext is encrypted many times.

### A5/1

Used in GSM communication. 64-bit secret key and 22-bit nonce. Key-recovery know plaintext attacks and active attacks on GSM.

## Bruteforce Inversion Algorithms

Random guessing game etc.