Brief introduction to cryptography
with
interactive RSA demo

Substitution ciphers

Caesar cipher

• Very old and very simple
• Shift letters in an alphabet
• Examples with key = 3:

  Plaintext:	ABCDEFGHIJKLMNOPQRSTUVWXYZ
  Ciphertext:	DEFGHIJKLMNOPQRSTUVWXYZABC

  Plaintext:	the quick brown fox jumps over the lazy dog
  Ciphertext:	QEB NRFZH YOLTK CLU GRJMP LSBO QEB IXWV ALD

• Vulnerable to frequency analysis attacks

Frequency analysis

Substitution ciphers (2)

Vigenère cipher

• First mention in the 16th century
• Combine several Caesar ciphers in sequence
  with different shift values

• Plaintext:	ATTACKATDAWN
  Key:	LEMONLEMONLE
  Ciphertext:	LXFOPVEFRNHR

• Still vulnerable to frequency analysis attacks:
  find out the key length

Kerkhoffs' Principle

“A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.”

• Previously shared secret
• Common knowledge: date, etc.
• Codebooks

Asymmetric cryptography!

• Two keys: one is public, one is secret
• the public one for encryption, the secret one for decryption
• One-way function
• Slower than symmetric ciphers
• Usually used to transmit the key of a symmetric cipher
  Hybrid cryptosystem
• 1976: Diffie-Hellman key exchange
• 1977: Ron Rivest, Adi Shamir and Leonard Adleman: RSA
• 1984: ElGamal encryption system

RSA key generation

1. Choose two distinct prime numbers $p$ and $q$
2. Compute $n = pq$
3. Compute $\varphi(n) = \varphi(p)\varphi(q) = (p − 1)(q − 1)$
4. Choose an integer $e$ such that
   $1 < e < \varphi(n)$ and $gcd(e, \varphi(n)) = 1$
5. Compute $d$ as the multiplicative inverse of $e$

   $d$	$≡ e^{−1}$	$\pmod{\varphi(n)}$
   $e d$	$≡ 1$	$\pmod{\varphi(n)}$

RSA trick

• Set message $\,m\,$ such that $\,0 \leq m \lt n$
• Encryption: $\,c = m^e \mod{n}$
• Decryption: $\,m = c^d \mod{n}$

• $m$	$= (m^e)^d$	$\mod{n}$
  	$= m^{ed}$	$\mod{n}$
  	$= m^{1\mod{\varphi(n)}}$	$\mod{n}$
  $m$	$= m$

RSA key generation demo

1. Choose two distinct prime numbers
   $p =$ and $q =$
2. $n = pq =$ $\cdot$ $=$
3. $\varphi(n) = \varphi(p) \cdot \varphi(q) = (p − 1)(q − 1)$
   $\varphi(n) = $ $\cdot$ $=$
4. Choose an integer $e =$ , such that
   

   $1 < e < \varphi(n)$	and	$gcd(e, \varphi(n)) = 1$
   $1 <$ $<$	and	$gcd($ $,$ $) =$ $\,\neq 1$

5. Determine $d$ as $d ≡ e^{−1} (mod\ \varphi(n)) = $

   Public key:	$(n, e) = ($$,\ $$)$
   Private key:	$(n, d) = ($$,\ $$)$

RSA signing

• Sender:
  1. Compute the hash $\,h = \text{hash}(m)$
  2. Compute signature $\,s = h^d \mod{n}$
  3. Send the signature $s$ together with the (possibly) encrypted message to the recipient
• Recipient:
  1. Compute the hash $\,h = \text{hash}(m)$
     (using the same hash function)
  2. Reconstruct the hash from the signature $\,h' = s^e \mod{n}$
  3. Verify that $\,h = h'$