Formula sheet

Every formula across the unit, grouped by module. Every symbol is named — a formula with an unexplained variable is not revision material.

02Human factors

Password combinatorics

N = C^L

$N$: total number of possible passwords
$C$: size of the character set
$L$: password length in characters

Password strength and generation

Password entropy

H = \log_2 N = L \log_2 C

$H$: entropy in bits
$N$: total combinations, C^L
$L$: password length
$C$: character-set size

H, not N, is what the lecture and this site mean by "strength" - bits of uncertainty, not a raw count of passwords.

Password strength and generation

Passphrase entropy (dice method)

H = n \log_2 W

$H$: entropy in bits
$n$: number of words chosen
$W$: wordlist size, 7,776 for the EFF long list, since 6^5 = 7,776

The same formula as password entropy, with a word standing in for a character and the wordlist standing in for the character set.

Password strength and generation

03Access control

Octal permission digit

d = 4r + 2w + x

$r, w, x$: Each is 1 if that permission is granted, 0 if not.
$d$: The resulting octal digit, 0 to 7.

The same formula gives the leading special-bits digit, with r -> SUID (4), w -> SGID (2), x -> sticky (1).

Unix and Linux permissions

04Mathematics for cryptography

Divisibility

b \mid a \iff a = mb \text{ for some integer } m

$b \mid a$: "b divides a" — b is a divisor of a
$a, b, m$: integers, b nonzero

There is no remainder when a is divided by b.

Divisibility and the greatest common divisor

Linear combination property

b \mid g \text{ and } b \mid h \implies b \mid (mg + nh)

$g, h$: two integers b divides
$m, n$: any integers

Divisibility and the greatest common divisor

Division algorithm

a = qn + r, \quad 0 \le r < n, \quad q = \left\lfloor \frac{a}{n} \right\rfloor

$a$: the dividend, a non-negative integer
$n$: the divisor, a positive integer
$q$: the quotient, found by flooring a/n
$r$: the remainder, always in [0, n)

Divisibility and the greatest common divisor

Greatest common divisor

\gcd(a, b) = \max\{\, k : k \mid a \text{ and } k \mid b \,\}

$a, b$: the two integers
$k$: a common divisor of a and b

gcd(a, 0) = |a|, and gcd(0, 0) is defined to be 0.

Divisibility and the greatest common divisor

The mod operator

a \bmod n = r, \quad a = qn + r, \ \ 0 \le r < n, \ \ q = \left\lfloor \frac{a}{n} \right\rfloor

$a$: any integer, positive or negative
$n$: the modulus, a positive integer
$q$: the quotient, floor(a/n)
$r$: the remainder, always in [0, n)

For negative a, q rounds toward negative infinity, not toward zero — that is what keeps r non-negative.

Modular arithmetic and residue classes

Congruence modulo n

a \equiv b \pmod{n} \iff (a \bmod n) = (b \bmod n)

$a \equiv b \pmod{n}$: "a is congruent to b modulo n"
$a, b, n$: integers; n is the modulus

a ≡ 0 (mod n) if and only if n | a.

Modular arithmetic and residue classes

Modular arithmetic properties

[(a \bmod n) \circ (b \bmod n)] \bmod n = (a \circ b) \bmod n

$\circ$: any of +, -, x
$a, b$: any integers
$n$: the modulus

Reduce before combining or after — addition, subtraction and multiplication all give the same answer either way.

Modular arithmetic and residue classes

Residue class [r]

[r] = \{a : a \text{ is an integer}, \ a \equiv r \pmod{n}\}

$[r]$: the residue class of r modulo n
$a$: any integer congruent to r mod n

The smallest non-negative member of a class is the one normally used to name it.

Modular arithmetic and residue classes

The set Zn

\mathbb{Z}_n = \{0, 1, \ldots, n-1\}

$\mathbb{Z}_n$: the set of residues modulo n
$n$: the modulus

Modular arithmetic and residue classes

Bezout identity

ax + by = d = \gcd(a, b)

$a, b$: the two input integers
$d$: gcd(a, b)
$x, y$: the Bezout coefficients — the extended Euclidean algorithm finds both

x and y are not unique, but the algorithm always produces one valid pair.

The extended Euclidean algorithm and modular inverses

Modular inverse

a x \equiv 1 \pmod{n}

$a$: the integer being inverted
$n$: the modulus
$x$: the inverse, written a^{-1} mod n

A solution for x exists if and only if gcd(a, n) = 1.

The extended Euclidean algorithm and modular inverses

Fundamental theorem of arithmetic

a = p_1^{a_1} \times p_2^{a_2} \times \ldots \times p_t^{a_t}

$a$: any integer greater than 1
$p_1 < p_2 < \ldots < p_t$: the distinct prime factors of a, in increasing order
$a_i$: the positive integer power of p_i in the factorisation

This factorisation is unique: there is exactly one way to write a as a product of prime powers.

Primes, Fermat, Euler and fast modular exponentiation

Fermat's little theorem

a^{p-1} \equiv 1 \pmod{p}

$p$: a prime number
$a$: any integer not divisible by p

A special case of Euler's theorem below, with n = p and phi(p) = p - 1.

Primes, Fermat, Euler and fast modular exponentiation

Euler's totient function

\varphi(n) = |\{\, k : 1 \le k < n, \ \gcd(k, n) = 1 \,\}|

$\varphi(n)$: the count of positive integers below n that are coprime to n
$n$: any positive integer

phi(p) = p - 1 for prime p, since every integer from 1 to p-1 is coprime to p.

Primes, Fermat, Euler and fast modular exponentiation

Totient of a product of two primes

\varphi(pq) = \varphi(p) \times \varphi(q) = (p - 1)(q - 1)

$p, q$: two distinct prime numbers
$n = pq$: their product

This is the identity RSA key generation runs directly: n = pq, phi(n) = (p-1)(q-1).

Primes, Fermat, Euler and fast modular exponentiation

Euler's theorem

a^{\varphi(n)} \equiv 1 \pmod{n}

$a, n$: any two relatively prime integers, n positive
$\varphi(n)$: the Euler totient of n

Alternative form: a^{phi(n)+1} = a (mod n). Setting n = p prime recovers Fermat's little theorem.

Primes, Fermat, Euler and fast modular exponentiation

Order of an element

\mathrm{ord}_p(a) = \min\{\, n > 0 : a^n \equiv 1 \pmod{p} \,\}

$\mathrm{ord}_p(a)$: the order of a modulo p
$p$: a prime modulus
$a$: an integer not divisible by p

The order always divides phi(p) = p - 1.

Discrete logarithms and primitive roots

Primitive root condition

\mathrm{ord}_p(g) = \varphi(p) = p - 1

$g$: a primitive root of p
$p$: a prime

A primitive root's powers g^1, g^2, ..., g^{p-1} run through every nonzero residue mod p exactly once before repeating.

Discrete logarithms and primitive roots

Discrete logarithm problem (DLP)

y = g^x \bmod p

$p$: a prime
$g$: a primitive root of p
$x$: the discrete logarithm of y to base g: the unknown the problem asks for
$y$: the given result of the exponentiation

Computing y from g, x, p is fast (square-and-multiply); recovering x from g, y, p has no known fast general method.

Discrete logarithms and primitive roots

Group axioms

\forall a, b \in G: \ a + b \in G; \quad \exists\, 0 \in G: \ a + 0 = a; \quad \exists\, -a \in G: \ a + (-a) = 0

$G$: the set, with a binary operation written + here
$0$: the identity element
$-a$: the inverse of a

Closure, associativity, identity, inverse. Add commutativity (a+b=b+a) and the group is abelian.

Groups, rings and fields

Ring axioms

(R, +) \text{ abelian}; \quad a \cdot (b + c) = a \cdot b + a \cdot c; \quad (a+b) \cdot c = a \cdot c + b \cdot c

$R$: the set, with addition and multiplication
$(R, +) \text{ abelian}$: R is an abelian group under addition

Multiplication must be closed and associative, and distribute over addition. Neither a multiplicative identity nor multiplicative commutativity is required.

Groups, rings and fields

Commutative ring

a \cdot b = b \cdot a \quad \forall a, b \in R

$R$: a ring

A ring where multiplication is also commutative.

Groups, rings and fields

Field axioms

\forall a \neq 0 \in F, \ \exists\, a^{-1} \in F: \ a \cdot a^{-1} = 1

$F$: a commutative ring with a multiplicative identity 1
$a^{-1}$: the multiplicative inverse of a

A field is a commutative ring where every nonzero element has a multiplicative inverse. Z is not a field; Q is.

Groups, rings and fields

Prime field GF(p)

\mathrm{GF}(p) = \{0, 1, \ldots, p-1\}, \quad \text{addition and multiplication mod } p

$p$: a prime number

Also written F_p. Characteristic p is the smallest number of copies of any element that sum to 0.

Finite fields, GF(p) and GF(2^n)

Extension field GF(p^n)

\mathrm{GF}(p^n), \quad n > 1

$p$: a prime (2 for every field on this page)
$n$: the extension degree

Built from GF(p) by adjoining the roots of a degree-n irreducible polynomial over GF(p).

Finite fields, GF(p) and GF(2^n)

GF(2^3) irreducible polynomial

p(x) = x^3 + x + 1

$p(x)$: the modulus every multiplication in GF(2^3) reduces by

Cannot be factored into lower-degree polynomials with coefficients in GF(2), which is what makes it irreducible over GF(2).

Finite fields, GF(p) and GF(2^n)

AES irreducible polynomial

m(x) = x^8 + x^4 + x^3 + x + 1

$m(x)$: the modulus every GF(2^8) multiplication in AES reduces by

In binary: 100011011, or 0x11B.

Finite fields, GF(p) and GF(2^n)

05Symmetric cryptography

Encryption and decryption

\text{Enc}_{k_e}(p) = c, \qquad \text{Dec}_{k_d}(c) = p

$p$: plaintext, drawn from an alphabet R
$c$: ciphertext, drawn from an alphabet S that need not match R, in size or content
$k_e$: the encryption key
$k_d$: the decryption key

In symmetric cryptography k_e = k_d, or k_d is trivially derivable from k_e. In asymmetric cryptography neither holds.

Cryptography basics and Kerckhoffs's principle

Caesar cipher

C_i = (P_i + n) \bmod 26, \qquad P_i = (C_i - n) \bmod 26

$P_i, C_i$: the numeric value (A=0 .. Z=25) of the i-th plaintext and ciphertext letter
$n$: the shift, a fixed integer from 0 to 25

Every letter uses the same shift n: one fixed rule for the whole message, which is exactly what frequency analysis exploits.

Substitution, transposition and frequency analysis

Caesar cipher keyspace

|K| = 26

$|K|$: the number of distinct keys

A 26-letter alphabet gives 26 possible shifts, of which the shift of 0 does nothing to the plaintext, so 25 keys actually change the message.

Substitution, transposition and frequency analysis

Vigenère encryption and decryption

C_i = (P_i + K_{i \bmod L}) \bmod 26, \qquad P_i = (C_i - K_{i \bmod L} + 26) \bmod 26

$P_i, C_i$: the numeric value of the i-th plaintext and ciphertext letter
$K_j$: the numeric value of the j-th letter of the key
$L$: the length of the key

i mod L cycles the key to match however long the plaintext is; +26 before the mod in decryption keeps the result non-negative.

The Vigenère cipher and the Kasiski examination

Vigenère keyspace

|K| = 26^{L}

$|K|$: the number of distinct keys of length L
$L$: the key length in letters

Grows exponentially with key length: a 3-letter key already gives 26^3 = 17,576 possible keys, far more than Caesar's 26, but still small enough that a short key is worth attacking directly, which is exactly what the Kasiski examination does.

The Vigenère cipher and the Kasiski examination

One-time pad encryption and decryption

c = p \oplus k, \qquad p = c \oplus k

$p$: plaintext bits
$c$: ciphertext bits
$k$: the one-time key (the pad), the same length as p

XOR is its own inverse, so encryption and decryption are the same operation.

Stream ciphers and the one-time pad

Many-time pad key-reuse relationship

P = C_1 \oplus C_2 = P_1 \oplus P_2

$C_1, C_2$: two ciphertexts produced under the same reused key K
$P_1, P_2$: the plaintexts behind them
$P$: C_1 XOR C_2, independent of the key entirely

The key cancels out completely, because K XOR K is all zeros.

Stream ciphers and the one-time pad

DES S-box addressing

\text{row} = 2b_0 + b_5, \qquad \text{col} = 8b_1 + 4b_2 + 2b_3 + b_4

$b_0, b_5$: the outer two bits of the 6-bit S-box input — together they give a row from 0 to 3
$b_1 b_2 b_3 b_4$: the inner four bits, read as a 4-bit number — a column from 0 to 15

DES has eight S-boxes addressed this way. S[0] is worked in full below.

Block ciphers, S-boxes, P-boxes and Feistel

Feistel round

L_{n+1} = R_n, \qquad R_{n+1} = L_n \oplus F(R_n, K_n)

$L_n, R_n$: the left and right halves entering round n
$F$: the round function, keyed by the round subkey
$K_n$: the subkey used in round n
$\oplus$: bitwise XOR

Block ciphers, S-boxes, P-boxes and Feistel

DES keyspace

|K| = 2^{56} \approx 7.2 \times 10^{16}

$K$: the set of all possible DES keys
$56$: the DES key length in bits

DES and 3DES

Average-case brute-force time

T = \frac{2^{55}}{R}

$T$: expected time to find the key, in seconds
$2^{55}$: half the keyspace — the average number of keys tried before a hit
$R$: attack rate, in keys tried per second

Worst case tries the full 2^56; on average a hit comes after trying half the keyspace.

DES and 3DES

3DES effective key sizes

56 \times 2 = 112, \qquad 56 \times 3 = 168

$56$: one DES key length
$2, 3$: the number of independent DES keys, for two-key and three-key 3DES

The unit teaches these as the effective strengths. See the discrepancy noted below for what NIST rates instead.

DES and 3DES

AES round count by key size

N_r = \begin{cases} 10 & N_k = 4 \\ 12 & N_k = 6 \\ 14 & N_k = 8 \end{cases}

$N_k$: key length in 32-bit words — 4, 6 or 8 for AES-128, AES-192, AES-256
$N_r$: number of rounds for that key size

AES

Key expansion size

w = N_b (N_r + 1)

$N_b$: block size in 32-bit words — fixed at 4 for every AES key size, since the block is always 128 bits
$N_r$: number of rounds for the chosen key size
$w$: total 32-bit words produced by key expansion, one round key of N_b words per round plus one extra for the initial AddRoundKey

The lecture works the AES-128 case only: w = 4(10+1) = 44 words, 176 bytes. The same formula gives 52 words for AES-192 and 60 for AES-256.

AES

AES finite field

m(x) = x^8 + x^4 + x^3 + x + 1

$m(x)$: the irreducible polynomial AES reduces modulo, defining GF(2^8)

Every AES byte operation — SubBytes and MixColumns — is arithmetic in this field.

AES

ECB

C_i = E_k(P_i)

$P_i$: plaintext block i
$C_i$: ciphertext block i
$E_k$: the block cipher's encryption function under key k

No chain-in at all. Every block is encrypted exactly as if it were the only block in the message.

Modes of operation

CBC encrypt

C_i = E_k(P_i \oplus C_{i-1})

$P_i, C_i$: plaintext and ciphertext block i
$C_{i-1}$: the previous ciphertext block, or the IV when i = 0
$E_k$: the block cipher's encryption function under key k

The first block has no previous ciphertext, so C_{-1} is replaced by the IV.

Modes of operation

CBC decrypt

P_i = D_k(C_i) \oplus C_{i-1}

$D_k$: the block cipher's decryption function under key k
$C_i, C_{i-1}$: the current and previous ciphertext blocks

Every block of ciphertext is already available before decryption starts, unlike encryption, which must run in order.

Modes of operation

CTR keystream

C_i = P_i \oplus E_k(\text{nonce} \Vert i)

$i$: the per-block counter value, incremented once per block
$\text{nonce}$: a value combined with the counter, never reused under the same key
$E_k(\text{nonce}\Vert i)$: the keystream block for position i

Every block's keystream depends only on the nonce and its own counter value, never on another block's ciphertext. This is what lets CTR parallelise.

Modes of operation

06Asymmetric cryptography

One-way function

Y = f(X) \implies \text{easy}, \qquad X = f^{-1}(Y) \implies \text{infeasible}

$X$: the input, from the function's domain
$Y$: the output, from the function's range
$f$: the one-way function itself

Every output has a unique inverse; computing it just is not feasible without extra information.

Public-key cryptography and trapdoor functions

Trapdoor one-way function

Y = f_k(X) \implies \text{easy}, \qquad X = f_k^{-1}(Y) \implies \text{easy if } k \text{ known, infeasible if } k \text{ unknown}

$X, Y$: input and output, as above
$k$: the trapdoor — a piece of extra information
$f_k$: the function, parameterised by the trapdoor

Every public-key cryptosystem in this module is one instance of this idea.

Public-key cryptography and trapdoor functions

Discrete Logarithm Problem (DLP)

y = g^{x} \bmod p

$p$: a prime number
$g$: a primitive root of p
$x$: the value to find — the discrete logarithm of y
$y$: the given result of raising g to the power x

Finding x given p, g and y is believed infeasible for a large enough p.

Public-key cryptography and trapdoor functions

RSA problem

c = m^{e} \bmod n

$n$: the modulus
$e$: the public exponent
$m$: the value to find — the e-th root of c
$c$: the given result of raising m to the power e

Finding m given c, e and n is believed infeasible for certain n.

Public-key cryptography and trapdoor functions

RSA key generation

n = pq, \qquad \varphi(n) = (p-1)(q-1), \qquad \gcd(e, \varphi(n)) = 1, \qquad d \equiv e^{-1} \pmod{\varphi(n)}

$p, q$: two distinct primes, chosen and then discarded
$n$: the modulus, published as part of both keys
$\varphi(n)$: Euler's totient of n — kept secret, discarded after key generation
$e$: the public exponent, 1 < e < \varphi(n)
$d$: the private exponent, the modular inverse of e mod \varphi(n)

Public key PU = {e, n}. Private key PR = {d, n}.

RSA

Euler's totient of a semiprime

\varphi(n) = (p-1)(q-1) \quad \text{when } n = pq,\ p \neq q \text{ both prime}

$n$: the RSA modulus, a product of two distinct primes
$p, q$: the two prime factors of n

The shortcut used throughout RSA key generation — see 04-04 for the general definition of phi.

RSA

RSA encryption

C = M^{e} \bmod n

$M$: the plaintext, an integer with 0 \le M < n
$e, n$: the public key
$C$: the ciphertext

RSA

RSA decryption

M = C^{d} \bmod n

$C$: the ciphertext
$d, n$: the private key
$M$: the recovered plaintext

RSA

RSA malleability

c' \equiv c \cdot r^{e} \pmod{n}, \qquad (c')^{d} \equiv m \cdot r \pmod{n}

$c$: the intercepted ciphertext, c = m^e mod n
$r$: any value the attacker chooses
$e, n$: the victim's public key
$c'$: the modified ciphertext the attacker submits for decryption
$d$: the victim's private exponent, never seen by the attacker
$m$: the original plaintext, still unknown to the attacker at this point

The attacker never learns d and never sees m directly, but recovers m from the decrypted (c')^d by dividing out r.

RSA security, attacks, padding and hybrid encryption

Diffie-Hellman shared secret

K = Y^{a} \bmod p = X^{b} \bmod p = g^{ab} \bmod p

$p$: a public prime modulus
$g$: a public primitive root (generator) of p
$a, b$: Alice's and Bob's private exponents, never sent
$X, Y$: the public values X = g^a mod p and Y = g^b mod p, exchanged in the open
$K$: the shared secret both sides compute independently

K = g^(ab) mod p either way the exponents are applied, which is why the two sides agree without ever sending a or b.

Diffie-Hellman key exchange

Elliptic curve over a prime field

E_p(a,b): \quad y^{2} \equiv x^{3} + ax + b \pmod{p}

$p$: a prime defining the field the curve is drawn over
$a, b$: the curve's two coefficients
$x, y$: coordinates of a point on the curve, both reduced mod p

Over the reals (no modulus) this is the same equation and gives the familiar smooth curve used for the geometric picture of point addition.

Elliptic curve cryptography

Elliptic curve over a binary field

y^{2} + xy = x^{3} + ax^{2} + b \quad \text{over } GF(2^{m})

$GF(2^m)$: the binary field the curve is defined over, see finite fields for the general construction
$a, b$: the curve's coefficients, themselves elements of GF(2^m)
$x, y$: coordinates, also elements of GF(2^m)

A different equation from the prime-field case, not the same one with a different modulus. Addition and subtraction in GF(2^m) both reduce to XOR.

Elliptic curve cryptography

Elliptic curve discrete logarithm problem

Q = kP

$P$: a known point on the curve, often the agreed base point G
$k$: the value to find: a scalar less than the order of P
$Q$: the given result of adding P to itself k times

Finding k given only P and Q is believed harder, bit for bit, than the classical discrete logarithm problem, which is why ECC keys are shorter than RSA or Diffie-Hellman keys for the same security level.

Elliptic curve cryptography

ECDH shared secret

K = n_A \cdot P_B = n_A \cdot (n_B \cdot G) = n_B \cdot (n_A \cdot G) = n_B \cdot P_A

$G$: the public base point, with public order n
$n_A, n_B$: Alice's and Bob's private scalars
$P_A, P_B$: the public points P_A = n_A G and P_B = n_B G
$K$: the shared point both sides compute independently

The same commutativity trick as classical Diffie-Hellman, with scalar point multiplication standing in for modular exponentiation.

Elliptic curve cryptography

Grover's algorithm: effective symmetric key strength

b_{\text{eff}} = \frac{b}{2}

$b$: the nominal length of a symmetric key, in bits
$b_{\text{eff}}$: the effective security level against a quantum adversary running Grover's algorithm

A 256-bit key offers security comparable to a 128-bit key against a quantum adversary, per the lecture. Doubling key sizes is the stated mitigation.

Post-quantum cryptography