MATH2020 (Lec 10) - Cryptography

Cryptography

What is cryptography

• practice and study of techniques for securing communication and data in the presence of adversaried
• 2 types of cryptosystems
  • Private-key cryptography (symmetric cryptography)
  • Public-key cryptography (asymmetric cryptography)

Private-key encryption scheme

• A triplet of algorithms (Gen, Enc, Dec), a message space M, and a key space K
• Gen: Alice and Bob first need to meet in advance to generate and agree on a secret key k ← K.
• Enc: Alice has a private message m ∈ M for Bob, she sends c = Enck (m) over the insecure channel.
• Dec: Once Bob receives the cipher-text c, he decrypts it by running m = Deck(c) to read the original message.

Caesar Cipher

• private-key encryption scheme used by Julius Caesar to communicate with his generals, achieved by shifting each alphabet by some fixed amount (the key)
• message space $M=\{A,B,...,Z\}\ast$ and key space $K=\{0,1,...,25\}$:
• Gen outputs a uniformly random key k from $K=\{0,1,...,25\}$.
• Encryption shifts the alphabet of each letter in the plain-text by k: $En{c}_k(m_1{m}_2...m_n)=c_1{c}_2...c_n,where{c}_i=m_i+k\mathrm{mod}26$
• Decryption shifts each letter back: $De{c}_k(c_1{c}_2...c_n)=m_1{m}_2...m_n,where{m}_i=c_i+k\mathrm{mod}26$

One-time pad scheme

• the key is as long as the message