02.1 OTP, Perfect Secrecy, Public Key

Why cryptography ?

• Privacy and Authenticity

Pre-Internet :

• Diplomats/generals
• Signing a letter → authenticity Internet :
• Keeping our communication/activity private

Caesar’s Cipher

We shift the letter by the key $k$, modulo the length of the alphabet

Caesar's cipher

we take the english alphabet and shift it by one letter $k=1$ $\text{ABC}\to \text{BCD}$

Monoalphabetic Cipher

We take an arbitrary permutation of the alphabet (The key $k$ is the permutation)

Polyalphabetic Cipher

Uses multiple substitution tables

Vigernère Cipher

Has multiple keys, uses caesar’s cipher $\text{ABCD}\to \text{CEDF},k=\{2,3,1\}$

Security

The security of those algorithms is determined by the key, not the algorithm. → If that was the case, then when the algorithm gets leaked you’re toast

Ideally, a cryptographic system should be secure against attacks on the plaintext At the very least it should be secure on ciphertext only attacks

OTP

The plaintext, the key and the cryptogram are $n$-length binary The key $k$ is produced by selecting each bit independently with uniform distribution

Encryption : $c=t\oplus k$ Decryption : $t=c\oplus k$

Perfect Secrecy

Definition

A cryptosystem has perfect secrecy if the plaintext and the cryptogram are statistically independent

Example

Perfect Secrecy of the OTP We have $c=t\oplus k$

$$p_{C|T}(c\mid t)=p_{K\mid T}(c\ominus t\mid t)=p_K(c\ominus t)=\frac{1}{2^n}$$

Hence they are independent

Theorem

If we have perfect secrecy, then

$$H(T)\le H(K)$$

Diffie and Hellman

A way to distribute keys over a public channel

We fix a large prime number $p$. (we will do $\text{mod }p$) We pick a generator $g$, which we will use to generate numbers $g^i$

We pick a secret number $a$, which gives $A=g^a$ The person we wish to share our key to picks $b$, $B=g^b$ We can share those keys publicly

To get the shared key $k$, we can get it by raising the other’s public key to our secret number :

$$\begin{array}{l}k=B^a=g^{ba}\\ k=A^b=g^{ab}\end{array}$$

One-Way Functions

Discrete exponentiation (DH) is an example of a one-way function ⇒ a function of a fast algorithm, but where reversing is slow

Trapdoor One-Way Functions

A trapdoor one-way function is a function with a trapdoor information, where if we know this information, then the reverse function is trivial.

This could be used for public-key cryptography, to decode images

ElGamal’s Trapdoor One-Way

We pick $g,p$ as in DH.
We then randomly pick $x,y$, which are both kept secret.

We have the function $f(g^y)=(g^x,g^{yx}t)$, with $t$ the plaintext. We compute the inverse of $g^{xy}$ By multiplying the inverse $\frac{1}{g^{xy}}$ to the result of the function, we find the plaintext $t$

Here, we send $g^x$. We get sent back $(g^y,g^{xy}t)$ We can then find $g^{xy}$, and therefore $\frac{1}{g^{xy}}$ and therefore $t$

Quote

“We share a secret number, we’re happy , we’re hahaha”

• Gastpar