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 §
\gcd(a, b) \cdot \lcm(a, b) = ab
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).