MATH3302 Cryptography summary
1. General concepts
• A cryptosystem is a 5-tuple of plaintexts, ciphertexts, keys, encryption functions and decryption
functions such that dK (eK (x)) = x.
• In private key cryptography the key must be exchanged over a secure channel.
• In public key cryptography one key is kept private (used for decryption or signature creation)
and one key is made public (used for encryption or signature verification).
• Various levels of attack: ciphertext only, known plaintext, chosen plaintext, chosen plaintext-
ciphertext.
• Various levels of security: unconditionally secure or computationally secure (provably secure).
pC (x) pC (y|x)
• Using Bayes’ Theorem we can compute pP (x|y) = . A cryptosystem has perfect
pC (y)
secrecy if pP (x|y) = pP (x) for all x ∈ P and y ∈ C.
• Shannon’s Theorem says that in a cryptosystem where |K| = |C| = |P|, then we have perfect
secrecy if and only if
(i) every key is used with equal probability and
(ii) for every x ∈ P and every y ∈ C, there is a unique K such that eK (x) = y.
2. Classical ciphers
• Monoalphabetic substitution ciphers: affine cipher, general mixed alphabet (cryptanalysis by
frequency analysis).
• Polyalphabetic substitution ciphers: Vigenere cipher (cryptanalysis by Kasiski’s test or Fried-
man’s test and then frequency analysis on sub-ciphertexts), Playfair cipher, Hill cipher, Vernam’s
one-time pad.
• Row transposition cipher uses a permutation to rearrange letters.
• ADFGVX cipher uses a substitution table followed by a transposition based on a keyword.
• In a stream cipher the key changes at each step based on the initial key and the preceding text.
Examples include the Autokey cipher and the LFSR-based stream cipher.
3. Modern cryptosystems
• Many modern ciphers combine one or more substitution operations and one or more permutation
operations.
• A Feistel cipher takes a plaintext of length 2n, divides it into two parts (L0 and R0 ), applies r
rounds of processing where Li = Ri−1 and Ri = Li−1 ⊕ f (Ri−1 , Ki ), and outputs the ciphertext
Rr Lr .
• DES is a Feistel cipher. DES takes a plaintext of length 64, applies an initial permutation, then
applies 16 rounds of a Feistel algorithm, and then applies the inverse permutation to obtain the
ciphertext. The Feistel algorithm uses a function f which takes a bitstring of length 32, expands
it to a bitsting of length 48, combines that with a second bitstring of length 48, uses S-boxes to
create a string of length 32 and then applies a permutation to this string to obtain the output of
length 32. The key schedule for DES involves permuting the initial key, performing some shifts
on the result and then applying another permutation to obtain each subkey.
• IDEA is based on three mathematical operations: ⊕, (addition modulo 2m ) and (mutipli-
cation modulo 2m + 1). IDEA takes a plaintext of length 64, writes it in four blocks of length
16, applies 8 rounds of 14 mathematical operations, and one output round of 4 mathematical
operations. IDEA could not be used for AES since IDEA requires 2m + 1 to be prime which is
true for m = 16 but not for m = 32.
• Basic AES takes a plaintext of length 128 and a key of length 128, adds an initial key, performs 9
rounds of the four steps: Substitute Bytes, Shift Rows, Mix Columns, Add Round Key, performs
one round of Substitute Bytes, Shift Rows, Add Round Key, and then outputs the ciphertext
of length 128. The bytes (bitstring of length 8, or polynomial of degree at most 7, or 2-digit
hex number) are added and multiplied in the field GF(256) where multiplication is carried out
modulo x8 + x4 + x3 + x + 1.
4. RSA
• To set up RSA: generate two large distinct primes p and q, compute n = pq and φ(n) =
(p − 1)(q − 1), choose b such that gcd(b, φ(n)) = 1, and compute a = b−1 modulo φ(n). The
public key (n, b) is published and the private key is (a, p, q).
• The encryption of M is C = M b mod n. The decryption of C is M = C a mod n. The Chinese
Remainder Theorem can be used to speed up the decryption process.
5. ElGamal
• To set up ElGamal: generate a large prime p (such that φ(p) has a large prime factor), choose a
generator α of Z∗P , choose a value a ∈ {2, 3, . . . , p − 2} and compute β = αa (mod p). The public
key (p, α, β) is published and the private key is (a).
• To encrypt a message, the sender must choose a value d ∈ {2, 3, . . . , p − 2}. Then the encryption
of M is C = (c1 , c2 ) where c1 = αd (mod p) and c2 = β d · M (mod p). The decryption of
C = (c1 , c2 ) is M = ((c1 )a )−1 · c2 (mod p). The fact that xp−1 = 1 (mod p) if gcd(x, p) = 1 can
be used to speed up the computation of ((c1 )a )−1 .
