Online Cryptography Course Dan Boneh Introduction History Dan Boneh
History David Kahn, “The code breakers” (1996) Dan Boneh
Symmetric Ciphers Dan Boneh
Few Historic Examples (all badly broken) 1. Substitution cipher k := Dan Boneh
Caesar Cipher (no key) Dan Boneh
What is the size of key space in the substitution cipher assuming 26 letters? Dan Boneh
How to break a substitution cipher? What is the most common letter in English text? “X” “L” “E” “H” Dan Boneh
How to break a substitution cipher? (1) Use frequency of English letters (2) Use frequency of pairs of letters (digrams) Dan Boneh
An Example UKBYBIPOUZBCUFEEBORUKBYBHOBBRFESPVKBWFOFERVNBCVBZPRUBOFERVNBCVBPCYYFVUFO FEIKNWFRFIKJNUPWRFIPOUNVNIPUBRNCUKBEFWWFDNCHXCYBOHOPYXPUBNCUBOYNRVNIWN CPOJIOFHOPZRVFZIXUBORJRUBZRBCHNCBBONCHRJZSFWNVRJRUBZRPCYZPUKBZPUNVPWPCYVF ZIXUPUNFCPWRVNBCVBRPYYNUNFCPWWJUKBYBIPOUZBCUIPOUNVNIPUBRNCHOPYXPUBNCUB OYNRVNIWNCPOJIOFHOPZRNCRVNBCUNENVVFZIXUNCHPCYVFZIXUPUNFCPWZPUKBZPUNVR B 36 E NC 11 IN UKB 6 THE N 34 PU 10 AT RVN 6 U 33 T UB 10 FZI 4 P 32 A UN 9 trigrams C 26 digrams Dan Boneh
2. Vigener cipher (16’th century, Rome) k = C R Y P T O C R Y P T O C R Y P T (+ mod 26) m = W H A T A N I C E D A Y T O D A Y c = Z Z Z J U C L U D T U N W G C Q S suppose most common = “H” first letter of key = “H” – “E” = “C” Dan Boneh
3. Rotor Machines (1870-1943) Early example: the Hebern machine (single rotor) A K E N B S K E C T S K . . T S . . . T X R . . Y N R . Z key E N R Dan Boneh
Rotor Machines (cont.) Most famous: the Enigma (3-5 rotors) 4 # keys = 26 = 2 18 (actually 2 due to plugboard) 36 Dan Boneh
4. Data Encryption Standard (1974) 56 DES: # keys = 2 , block size = 64 bits Today: AES (2001), Salsa20 (2008) (and many others) Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh See also: http://en.wikibooks.org/High_School_Mathematics_Extensions/Discrete_Probability Introduction Discrete Probability (crash course, cont.) Dan Boneh
n U: finite set (e.g. U = {0,1} ) Def: Probability distribution P over U is a function P: U ⟶ [0,1] such that Σ P(x) = 1 x∈U Examples: 1. Uniform distribution: for all x∈U: P(x) = 1/|U| 2. Point distribution at x : P(x ) = 1, ∀x≠x : P(x) = 0 0 0 0 Distribution vector: ( P(000), P(001), P(010), … , P(111) ) Dan Boneh
Events • For a set A ⊆ U: Pr[A] = Σ P(x) ∈ [0,1] x∈A note: Pr[U]=1 • The set A is called an event Example: U = {0,1} 8 • A = { all x in Usuch that lsb (x)=11 } ⊆ U 2 8 for the uniform distribution on {0,1} : Pr[A] = 1/4 Dan Boneh
The union bound • For events A and A 2 1 Pr[ A ∪ A ] ≤ Pr[A ] + Pr[A ] 2 1 2 1 A 1 A 2 Example: A = { all x in {0,1} s.t lsb (x)=11 } ; A = { all x in {0,1} s.t. msb (x)=11 } n n 1 2 2 2 Pr[ lsb (x)=11 or msb (x)=11 ] = Pr[A ∪A ] ≤ ¼+¼ = ½ 2 2 1 2 Dan Boneh
Random Variables Def: a random variable X is a function X:U⟶V n Example: X: {0,1} ⟶ {0,1} ; X(y) = lsb(y) ∈{0,1} U V For the uniform distribution on U: lsb=0 0 Pr[ X=0 ] = 1/2 , Pr[ X=1 ] = 1/2 lsb=1 1 More generally: rand. var. X induces a distribution on V: Pr[ X=v ] := Pr[ X (v) ] -1 Dan Boneh
The uniform random variable Let U be some set, e.g. U = {0,1} n R We write r ⟵ U to denote a uniform random variable over U for all a∈U: Pr[ r = a ] = 1/|U| ( formally, r is the identity function: r(x)=x for all x∈U ) Dan Boneh
Let r be a uniform random variable on {0,1} 2 Define the random variable X = r + r 2 1 Then Pr[X=2] = ¼ Hint: Pr[X=2] = Pr[ r=11 ] Dan Boneh
Randomized algorithms inputs outputs • Deterministic algorithm: y ⟵ A(m) m • Randomized algorithm A(m) R n y ⟵ A( m ; r ) where r ⟵ {0,1} output is a random variable R y ⟵ A( m ) m A(m) R Example: A(m ; k) = E(k, m) , y ⟵ A( m ) Dan Boneh
End of Segment Dan Boneh
Online Cryptography Course Dan Boneh See also: http://en.wikibooks.org/High_School_Mathematics_Extensions/Discrete_Probability Introduction Discrete Probability (crash course, cont.) Dan Boneh
Recap n U: finite set (e.g. U = {0,1} ) Prob. distr. P over U is a function P: U ⟶ [0,1] s.t. Σ P(x) = 1 x∈U A ⊆ U is called an event and Pr[A] = Σ P(x) ∈ [0,1] x∈A A random variable is a function X:U⟶V . X takes values in V and defines a distribution on V Dan Boneh
Independence Def: events A and B are independent if Pr[ A and B ] = Pr*A+ ∙ Pr[B] random variables X,Y taking values in V are independent if ∀a,b∈V: Pr[ X=a and Y=b] = Pr[X=a] ∙ Pr[Y=b] 2 R Example: U = {0,1} = {00, 01, 10, 11} and r ⟵ U Define r.v. X and Y as: X = lsb(r) , Y = msb(r) Pr[ X=0 and Y=0 ] = Pr[ r=00 ] = ¼ = Pr[X=0] ∙ Pr[Y=0] Dan Boneh
Review: XOR n XOR of two strings in {0,1} is their bit-wise addition mod 2 0 1 1 0 1 1 1 ⊕ 1 0 1 1 0 1 0 Dan Boneh
An important property of XOR n n Thm: Y a rand. var. over {0,1} , X an indep. uniform var. on {0,1} n Then Z := Y⨁X is uniform var. on {0,1} Proof: (for n=1) Pr[ Z=0 ] = Dan Boneh
The birthday paradox Let r , …, r ∈ U be indep. identically distributed random vars. n 1 Thm: when n= 1.2 × |U| 1/2 then Pr[ ∃i≠j: r = r ] ≥ ½ i j notation: |U| is the size of U Example: Let U = {0,1} 128 64 After sampling about 2 random messages from U, some two sampled messages will likely be the same Dan Boneh
|U|=10 6 collision probability # samples n Dan Boneh
End of Segment Dan Boneh
Search
Read the Text Version
- 1 - 31
Pages: