Historical Ciphers §
Caesar Ciphers §
“Shift” with wraparound. A function from
Attack: Try all twenty-six possible keys
Reflection. , , etc.
Special case of affine cipher.
Encryption and decryption are identical.
Substitution Ciphers §
Each letter is substituted by another (distinct) letter. ciphers in total.
Attack: frequency analysis
Vigenere Cipher §
Security proportional to keyword length.
- Find the length of the keyword
- Kasiski Method: Look for repeated fragments. Occurrences separated by multiples of the key length.
- Guess the Length
- Every -th letter will be a caesar cipher
- random text:
- english text:
Modern Cryptography §
Goal: immune to code-breaking without knowing the key
Hard mathematical problems:
- DH: Given and , find (discrete logarithm)
- RSA: Given and , find (root extraction)
- modular arithmetic
- extended euclidean algorithm
- fermat’s little theorem
- public key: anyone can send encrypted messages to Alice
- private key: only Alice can decrypt the messages
Euclid’s Algorithm §
For all integers , there exist integers such that .
-th prime approx
number of primes lt
probability that a random number is prime approx
Modular arithmetic §
Equivalence relation (reflexive, transitive).
Chinese Remainder Theorem §
…there exists a unique integer such that for all , .
Fermat’s Little Theorem §
When is prime and :
- choose two large primes and
- choose such that
- is public; is private.
encryption: where is the message and
secure 2-way communication. one-to-one.
- choose a large prime and its primitive root
- , where
private keys: ,
public keys: ,
shared private key:
- (extended euclidean algorithm)
- single decrypted message:
- many encrypted messages: .
- MITM: eve replaces and with . eve knows the shared private key.
ephemeral key (else likely key can be found by calculating the gcd)
- find (extended euclidean algorithm)
Primitive Root Theorem: dots
set, binary op
- (optional, abelian) commutative:
- if is a finite group, every element of has finite order.
- if ,
Asymptotic Complexity §
Discrete Logarithm Problem for Arbitrary Groups §
Group , , order of is .
Brute force: compute . (exponential in the number of bits)
- Create two lists of size
- baby steps:
- giant steps:
- Find a match between the two lists:
- is a solution to
Pohlig-Hellman Theorem §
If we have an algorithm that takes steps to solve the DLP in a group for any element with where is prime. We can solve
Miller-Rabin Test §
Fundamental Theorem of Algebra: every polynomial of degree has exactly roots (possibly multiple and complex).
Bezout’s Theorem: suppose two polynomials and of degrees and respectively have no trivial factors. Then, has exactly points.
- : points at infinity
- : affine points
Note: is not a point in the projective space.