CMU cryptography lecture 1 notes

Lecture1 - Introduction

Teaching Assistant: Xinyi Hu

In the first week, we talked about cryptography’s first goal, the three algorithms of a secret key encryption, 3 classical ciphers and how to break them. The detailed class notes are as follows.

Cryptography’s first goal is to keep secret communication.

A secret key encryption(SKE) consists of 3 algorithms:

  • Gen - generation algorithm
  • Enc - encryption algorithm
  • Dec - decryption algorithm

Some classical ciphers

  • Caesar Cipher - shift by 3
  • Substitution Cipher - can be broken by frequency analysis
  • Vigenere cipher - can be broken by frequency analysis

Homework:

  • Read http://norvig.com/mayzner.html
  • Exercises to think about:
    • You are given a ciphertext encrypted under Caesar cipher: “ibbiks eqbp nctt nwzkm ia awwv ia bpm acv zqama”. Recover the key and the plaintext.
    • Review the slides for this class as well as the next class
    • Read about digital signature, public key encryption and private key encryption. See their applications. See how they are different.
    • Read about modular exponentiation if you can (and if you are done with the first 3 exercises)

Extra materials for this course:

Questions:

Q1: Does the ‘spacebar’ count when encrypting?

A1: Frequency analysis.

Q2: In Vigenere cipher, if we generate a random string equal the ciphertext length, how to attack this one?

A2: Guess the length of Vigenere cipher, then use frequency analysis.

Q3: As you mention before, we can break the Caeser cipher by finding the frequency. If we encrypt the plaintext by using the same keys again and again, it will be almost impossible to analyze the frequency. if you shift by 2 say 3 times, its same as shifting once by 6.

A3: No, even if you encrypt again and again using the same key, frequency analysis should still work
encrypting with the same key many times is no different than encryption with another key once

Q4: how does the “attack” shift “cuycdp”

A4: Using the alphabet, A matchs 1, B matchs 2, …, Z matchs 26. (or A matchs 0, B matchs 1, …, Z matchs 25, they are the same). Key is BAEBAE. Add ATTACK and BAEBAE separately, you can get CUYCDP.

Q5: why t mapped to r ,h mapped to,is it fixed

A5: It’s already defined.

Q6: In Vigenere cipher, if the length of random string is not equal to message, there are some extra letters left. How can we deal with them?

A6: Repeat to make it equal to message length

Q7: i search the vigenere cipher on the Internet, the ciphertext of “ATTACK” is “BTXBCO” instead of “CUYCDP”, according to a table, why?

A7: You can select key you like in vigenere cipher. The ciphertext depends upon the key as well.