Skip to content

Cryptography Cheatsheet

AKA I've only got a day until my exam what do I really need to know?

Note: Difficult (todo if time)

  • AES key schedule
  • Galois field

Classic Ciphers

  • Before sending date, compress, then encrypt, then add error detection
  • Either substitution (swapping letters for other letters) or transposition (moving letters around)
  • Combination of both is good for encryption (want to maximise confusion and diffusion), ideally use product ciphers to do both (transposition and substitution)
  • Can use techniques such as frequency analysis, index of coincidence and the Kasisky Test to figure out classic ciphers
  • Steganography is the practice of hiding a message in plain sight
    • Alter the image or use a null cipher or use something like microdots embedded in the image

Ciphers

  • Caesar: shift of \(N\) letters of the alphabet for all.
  • Vignere: multiple alphabets with different shifts and a keyword
  • Enigma: combination of confusion and diffusion
  • Scytale: wrap around a dowel of the same diameter, then write across the ribbon
  • Railfence: \(N\) rails, write in a zig-zag, then read off row-by-row
  • Columnar: Use a keyword, write the message in \(N\) columns same as length of keyword, then sort the keyword alphabetically

Tests

  • Kasisky: Decrypt ciphertest with some key of length \(N\), then search for identical segments length \(N\). Key length is GCD of the distances between the segments.
  • Index of Coincidence: Probability of two random letters from the text being identical. \(IC = \sum_{i=a}^z P_i^2\). Will be similar to English if monoalphabetic or transposition, so will differ for Vignere or other text not decrypted properly
  • Message Length: can sometimes deduce that the key length divides the total length of the message
  • Fitness Metrics: Can look at \(n\)-grams from the text and compare to \(n\)-gram frequency for English text

Cracking the Key

  • Can brute force up to about 10 key length then gets difficult
  • Can use fitness metrics to order results
  • Hill Climbing: generate random starting keyword, then measure fitness of resulting text. Generate child keys, then measure their fitness. Choose higher fitness child keys as new seed keys

Terminology

  • Private key, or symmetric cryptography: shared key between parties. Typically used for session keys after setup with asymmetric.
    • E.g., DES, 3DES, Twofish, Rijndael
  • Public key, or asymmetric: use two different keys, one private, one public
    • Relies on trapdoor functions
    • For sending data between parties where we cannot safely send a symmetric key
    • E.g., RSA, ED25519
  • One way function: \(f(x)\) trivial, given \(f,x\). Evaluation of \(f^{-1}\) should not be trivial.
  • Trapdoor One Way Function: \(f^{-1}\) hard to get unless we have function \(g\) which we define at the same time as \(f\).

Shannon and Kirchoff

  • Entropy: \(H(X) = \sum_i p_i \log_2(1/p_i)\). Similar messages have lower entropy
  • Compression: theoretical min number of bits to store the data. This is \(B(X) = nH(X)\), where \(n\) is length of data
  • Shannon Perfect secrecy: For all messages in the message space of the same length, the probability of each ciphertext appearing should be the same
  • Computational perfect secrecy: similar idea but theoretically different just needs a lot of computing power
  • Cipher must not depend on the secrecy of the mechanism. Inner workings should be publicly available
  • Permutation causes confusion
  • Transposition causes diffusion
  • Want to have a cipher cause an avalanche effect, altering lots of bits in resultant text if we change the cipher.

Attack Types

  • Known-plaintext: access to both the plaintext and the ciphertext for a specific cipher and can then gain marginally better performance solving the cipher compared to brute force or general sieve
  • Chosen-plaintext: Can choose our own plaintext messages and get the ciphertext for them.
  • Ciphertext-only: Nothing other than the ciphertext. Anything vulnerable to this is completely insecure
  • Side channel and quantum
  • Ideally, a cipher should be resilient to these
  • Unsalted text can be broken by exhaustively storing it and using things such as rainbow tables

Symmetric Ciphers

  • Either stream or block. Stream is one bit or byte at a time, block is a block of bits or bytes with a fixed size
  • E.g., AES is 128, or 192 bits in a block, and XOR is a stream cipher
  • Stream ciphers use some bitstream generation algorithm to get a bitstream to XOR with the data
  • Once key compromised, then can decrypt all data used. Rekey often
  • Cipher defined over \((K,M,C)\) as algorithms \((E,D)\), where encryption followed by decryption with the same key yields the same plaintext
  • Pseudorandom functions map some key in \(K\) and message in \(X\) to an output \(Y\)
  • Pseudorandom permutations are a subset where \(X=Y\) and thus \(PRP: X \times K \to X\).
  • PRPs must be invertible, PRFs don't have to be
  • Security of PRPs is defined in terms of efficient algorithms:
    • \(Adv[A,e] = |Exp_A[E(k,m_1)]-Exp_A[E(k,m_2)]|\)
  • Ideal block cipher would have truly random permutation of each of the bits in the block (e.g., \(01001010 \to 00100101\) or anything else in \(\{0,1\}^8\))
  • This would mean storing huge amounts of mapping data

DES

  • 1971, IBM invented
  • Adopted 1976
  • Key length 56 bits, block length of 64 bits
  • Broken 1997
  • Replaced with AES 2000
  • Uses feistel structure
    • Split plaintext into LHS and RHS
    • XOR LHS with some \(F\) applied to RHS
    • Then switch result from XOR to the RHS and use previous RHS as LHS
    • At end do XOR and \(F\) but don't swap
    • Can choose many different parameters
  • DES uses 16 rounds Feistel with block size 64, key length 56
  • \(F\) takes 32 bits, expands to 48 bits, combined with round key of 48 and XORed, then reduced back to 32 bits
  • All these operations invertible
  • Has some weak keys
  • Can also be brute forced as key space is small
  • Replaced with double-DES but susceptible to a meet-in-the-middle attack
  • Ultimately, 3DES works with two keys, and two keys as EDE means that we can use legacy systems with new hardware for 3DES, using the same key \(k1=k2\) for DES hardware

AES

  • New standard started consulting in 1997
  • 128- 192- and 256-bit key sized
  • Substitution-permutation based network, not Feistel
  • Each 128 bits into 16 bytes, stored in 4x4 matrix
  • This is the state
  • Consider the bytes as a Galois field
  • Flow:
    • Add round key (simple XOR)
    • Then loop on this:
    • byte substitute using LUT based on GF
    • Shift row (left shift by 0,1,2,3,4)
    • Mix column (left multiply by specific values)
    • Add round key (again simple XOR)
    • Then loop unless last round
    • If last round do byte substitution, shift row, then add round key
  • Key schedule for deriving round keys, quite complicated

Block Cipher Modes

  • If using cipher with same key would yield the same result
  • Need to consider padding, and how to break plaintext into blocks
  • Want to ensure that encryption of the same block yields different ciphertext, e.g., same 128 bits would not give same ciphertext
  • This is where modes come in handy
  • Naïve implementation is ECB, storing \(C_i = E_K(P_i)\).
  • Using a mode will allow us to fix this problem
  • CBC: takes initial vector then encrypts with previous ciphertext XORed with the current block
    • Can't run in parallel
    • Transmission errors compound
    • Need to rekey to prevent chosen plaintext every \(2^{12}\) blocks
  • CTR: initialize a counter to some IV then increment by 1 each block. XOR the encrypted CTR with the plaintext to get the ciphertext
    • Can parallelize
    • But is more prone to CPA and IV needs to be communicated
  • CFB: Use output of the previous block and encrypt with the key and this previous block, then XOR with the next plaintext block
  • OFB: Similar to CFB but only send some bits from the output

Number Theory

  • Mainly focused around modular arithmetic
  • Mod congruence is where we wrap round at the modulus
  • Addition, multiplication do as normal then take mod congruence
  • Modular inversion or multiplicative inverse is where we have \(xy=1 (\mod n)\) for a chosen \(x\) with \(y\) as the inverse
  • We denote \(y\) as \(x^{-1}\)
  • Division is a multiplication of the multiplicative inverse, or modular inversion of 1/denominator
  • So \(2/3\) in \(\mathbb{Z}_7\) would be \(2 \times \frac{1}{3}\), and multiplicative inverse of \(\frac{1}{3}\) which is \(3y=1\), so choose 5.
  • Then have \(2 * 5 = 10 = 3\)
  • Not all elements have an inverse
  • This is only if \(\gcd(x,N)= 1\)
  • Euclid algorithm \(\gcd(r_0, r_1) = \gcd(r_0 - r_1, r_1)\)
  • This is the classical algorithm
  • We can apply it to modular arithmetic: \(\gcd(r_0, r_1) = \gcd(r_1, r_0 \mod r_1)\)
  • Inverses can be calculated with extended Euclid
  • First check \(\gcd(x,N) = 1\), then find \(a,b | ax + bN = 1\)
  • \(a\) is then the inverse of \(x\) in \(\mathbb{Z}_n\).
  • Extended Euclid can be done by expressing \(\gcd(x,y)\) as \(x = y(k) + n\), where \(k\) is some integer we don't really care about, and \(n\) is the remainder.
  • In the LHS, for \(\gcd(8,11) = 1\), we have \(11 = 8(1) + 3\)
  • On the RHS, we then rearrange for \(3\)
  • Do this down the chain, then rearrange and back substitute
  • Division can be rearranged as the quotient and then 1/denominator

Modular Inversion

  • So far have seen this naïvely
  • This is where we get \(xy=1\) for a chosen \(x\) with \(y\) inverse
  • Can use Fermat's little theorem instead
  • Only if modulus is prime \(p\)
  • \(\forall x \in (\mathbb{Z}_p)^*: x^{p-1} = 1 (\mod p)\)
  • \((\mathbb{Z}_N)^*\) is the set of invertible elements
  • So for \(p=5\), we know that \(x^{5-1} = 1\), and is thus invertible
  • So \(3^4 = 81 = 1\) in \(\mathbb{Z}_5\)
  • Modular inverse can be found by taking \(xx^{p-2} = 1 = x^{-1} = x^{p-2}\) in \(\mathbb{Z}_p\)
  • Less efficient than Euclid

Roots

  • If \(p\) prime, \(c \in \mathbb{Z}_p\), then \(x \in \mathbb{Z}_p\) such that \(x^e=c\). \(x\) is then an \(e\)th root of \(c\)
  • If \(\gcd(e,p-1) = 1\), then \(d\) is the inverse of \(e\) in \(\mathbb{Z}_{p-1}\) (\(d=e^{-1}\) in \(\mathbb{Z}_{p-1}\))
  • Two cases with different solutions \(\gcd(e,p-1) = 1\) and \(\ne 1\)
  • If \(\ne 1\), then have to use quadratic residue
  • QR is an element \(x\) in \(\mathbb{Z}_p\) if it has a square root in \(\mathbb{Z}_p\)
  • Euler's Theorem: let \(p\) an odd prime, if \(x\) in \((\mathbb{Z}_p)^*\) is QR, then \(x^{(p-1)/2} = 1\) in \(\mathbb{Z}_p\)
  • To get QR, take every element and raise to the power \((p-1)/2\)
  • If this equals 1, then element is QR
  • Square root modular odd prime
    • Either \(p=3 (\mod 4)\)
    • or \(p = 1 (\mod 4)\)
  • First allows us to use theorem if \(c \in (\mathbb{Z}_p)^*\) is QR, then \(\sqrt{c} = c^{\frac{p+1}{4}}\) in \(\mathbb{Z}_p\)
  • E.g. \(\sqrt{6}\) in \(\mathbb{Z}_{43}\) would be \(p = 43 = 3 \mod 4\), which gives \(\sqrt{6} = 6^{\frac{43+1}{4}} = 6^{11} = 36\)

Groups

  • Hold 4 properties over a binary operation \(*\) on \(G\)
  • These 4 properties are closure, associativity, identity and invertability
  • Order is size or number of elements in the group
  • Denote groups as set of numbers, and the binary operation
  • E.g., \((\mathbb{Z}_{12}, +)\)
  • Abelian groups are where commutativity holds
  • Totient function \(\phi\) is Euler function
  • This is \(\phi(N) = | (\mathbb{Z}_N)^*|\), with two cases:
    • For \(N = p\) where \(p\) prime, \(\phi(N) = N-1\)
    • For \(N = pq\), where \(p,q\) prime, \(\phi(N) = (p-1)(q-1)\)
  • This function used as a generalization of Fermat's little theorem:
    • Fermat: \(\forall x \in (\mathbb{Z}_p)^*: x^{p-1} = 1\) in \(\mathbb{Z}_p\)
    • Euler: \(\forall x \in (\mathbb{Z}_N)^*: x^{\phi(N)} \mod N = 1\)
  • This is used for RSA

Intractable Problems

  • Discrete log: given \(y=2^x\), try and compute \(x = D\log_2(y)\):
    • Generalise to \(y \mapsto g^x\)
    • Can compute \(y\) given \(g,x\)
    • Given \(g,y\), can't easily compute \(x\)
    • Fastest is \(e^{O(\sqrt[3]{N})}\), general number field sieve
  • Factoring problem: factoring large numbers:
    • Best currently general number field sieve
    • Forms basis for RSA

Asymmetric

  • Key pair with private and public part

Trapdoor Functions

  • Makes use of trapdoor functions \(f,f^{-1}\), where we are given \(f^{-1}\) as the private key, but hard to get otherwise
  • Technically a triple of \((G,F,F^{-1})\), comprising:
    • \(G\) keygen
    • \(F\) encryption function with public key
    • \(F^{-1}\) decryption function with private key
  • Secure if \(F\) is one way
  • Must assume that the adversary can see \(C\), the public key and \(F\)
  • Don't use by applying directly to plaintext

RSA

  • Choose random \(p,q\), then set \(N = pq\)
  • Choose \(e,d\) such that \(ed = 1 \mod \phi(N)\)
  • Public key is \(N,e\)
  • Private key is \((p,q,d)\)
  • To encrypt, take \(x^e\), to decrypt take \(y^d\)

Comments