CMU cryptography mentor session 1 notes

Mentor Session 1 - Introduction

Teaching Assistant: Xinyi Hu

In the first mentor session, we reviewed three classical ciphers, learnt affline cipher, and its enigma example. The detailed class notes are as follows.

Classical ciphers

  • Caesar cipher
  • Substitution cipher
  • Vignere cipher

In this session

  1. Affine cipher

Broken by frequency analysis.

  1. Enigma example
  1. Puzzles

Use the cipher table to decrypt the ciphertext:

WLZD HMLAAFJ IPG OIN OANLHVAN

Answer: jack sparrow hid the treasure.

Mathematical Interpretation:

  1. Optional: secret sharing example

Multiple people coming together to reconstruct a secret. Example: In a (t,n) secret sharing scheme, there are ‘n’ users each with a piece of the puzzle. The secret is successfully reconstructed only if at least ‘t’ users come together.

Questions:

Q1: Is there any possibility that two characters are converted to the same number?

A1:

As a matter of fact, $x_1 - x_2$ mod 26 could not be 0, if so, $x_1$ and $x_2$ must be the same letter.

Therefore, as long as $a$ is not the factor of 26, this cipher is injective.

Q2: Why the affine cipher is bijection?

A2:

Firstly, injection:

Thus, as long as $a$ is not the factor of 26, this cipher is injective.

Secondly, subjection:

Thus, as long as $a$ is not 0 and $a^{-1}$ is not the factor of 26, this cipher is surjective.