Lecutre 1: Introduction

Crypto Use Cases:

• Single use key
• Multi use key

Things to remember, Cryptography is:

• A tremendous tool
• The basis for many security machanisms

Cryptography is not:

• The solution to all security problems
• Reliable unless implemented and used properly
• Something you should try to invent yourself (many exmaples of broken ad-hoc designs)

Crypto Core

1. Secret key establishment
2. Secure communication

A rigorous science. The three steps in cryptography:

1. Precisely specify threat model
2. Propose a construction
3. Prove that breaking constrcution under threat mode will solve an underlying hard problem

History: "The code breakers" David Kahn

Few Historic Exmaples (all badly broken)

1. Substitution cipher
   1. Use frequency of English Letters: "e", "t", "a"
   2. Use frequency of pairs of letters (digrams): "he", "an", "in", "th"
2. Vigener cipher
3. Rotor Machines
   • the Hebern machine - single rotor
   • the Enigma - 3~5 rotors
4. Data Encryption Standard
   • DES: #key = 2^56, block size = 64 bits
   • Today: AES(2001), Salsa20(2008), ...

Discrete Probability

https://en.wikibooks.org/wiki/High_School_Mathematics_Extensions/Discrete_Probability

U: finite set, (Def)probability distribution P over U as a function P

Events: for a set $A \subseteq U: Pr[A] = \sum_{x \in A}^{P(x)} \in [0, 1]$, the set A is called event.

The union bound: for events A1 and A2, Pr[A1 union A2] <= Pr[A1] + Pr[A2]

Random variables

The uniform random variable

Randomized algorithms

Independence

XOR, Thm: Y a rand. var. over U, X and indep. uniform var. on U; then Z := Y XOR X is uniform var. on U.

The birthday paradox: $when n = 1.2 * |U|^{1/2} then Pr[\exists i != j: r_i = i_j] >= 1/2$