Cryptography 1

In this post I'll be recaping the coursera course on Crpytography 1.

Week1: Stream ciphers


cryptography is a rigorous science:

discrete prob

vid 1:

independence: event A and event B are independent if P[A and B] = P[A] * P[B]

'XOR': either or but not both x y xor 0 0 0 0 1 1 1 0 1 1 1 0

Theorem: Y a random variable over {0,1}^n X an independent uniform variable on {0,1}^n Z := Y xor X is a uniform variable

XOR has the property: that we can make a rand variable uniform prob by XORing with a uniform independent variable.

birthday paradox: probability that a collision will be found given r1..rn in U. independent identically distributed variables when you take n samples prob that two are equal is 1/2 n = 1.2 |U|^1/2 then P[ri = rj] >= 1/2

stream cipher 1

vid 1: symmetric cipher is defined over a triple (K, M, C) (keys, message, ciphertext) a pair of efficient algorithms (E, D) encryption and decryption

D(K, E(E, m)) = m => decryption needs to be inverse of encryption E is often a randomized algo (generate random bits) but D is deterministic

OTP One time pad OTP: first secure cipher M = C = K = {0,1}^n C := E(K,m) = K xor m (ciphertext is xor of key and message) the key needs to be as long as the message so its not very practical

why is OTP secure? Information Theory - Claude Shannon ciphertext should reveal no 'info' about plaintext (ciphertext and plaintext)

a cipher (E,D) over (K,M,C) has perfect secrecy if given m0 and m1 in M and c in C P[ E(k,m0) = c ] = P[ E(k,m1) = c ] prob of the two ciphertext being equal given ciphertext cant tell if msg is m0 or m1 or given ciphertext i cant tell what the original msg was an advisary learns nothing about plaintext from ciphertext NO ciphertext attack is possible

given ciphertext it is not possible to tell plaintext because the probility for all possible plaintext is the same (xor makes this easy to see)

perfect secrecy is an ideal goal, becuase is says that |K| >= |M|, length of the keys must be equal or more than messages again for OTP the keys and message are the same length, each message has one key


We define a statistical test for the generator G of the random distribution.

We then define an advantage as how likely the generator will output 1 compared to truly random generator. Adv (PRG) : [A, G] : Pr[ A(G(k)) = 1 ] - Pr[ A(r) ]

Unpredictable An unpredictable PRG is a secure PRG. If the 'next-bit' predictor cannot distinguish G from random then no statistical test can.

Computationally indistinguishable: notation to compare two distributions | Pr[ A(P1((x))) = 1 ] - Pr[ A(P2((x))) = 1 ] | < negligible

Semantic Security

The attacker should learn no information about the plaintext.

Semantic Security for one time key:

Experiment 1(Exp1) and Experiment 2(Exp2)
b= 0,1
[Challenger]    <- m0 or m1     [Adversary]
                E(k, mb) ->        v
                                guess m0 or m1
W(b) = event that Exp(b) = 1
Advantage(SS) = | Pr[ W(0) ] - Pr[ W(1) ] |

Week 2: Block Ciphers

Week 3: Message Integrity

Week 4: Authenticated Encryption

Week 5: Key Exchange

Week 6: Public-Key Encryption