Introuction to Cryptography

The cores of cryptography are:

• Secret key establishment
• Secure communication

Beyond the basic:

• Digital signature
• Anonymous communication
• Anonymous digital cash: OK to spend once, identify uncovered for double spending.
• Secure multi-party computation without trusted auth.
• Zero knowledge

History of Cryptography

Code Breakers by David Kahn.

Histroical ciphers:

• Substitution cipher
• Caesar Cipher, a substitiion cipher with shift by 3.
• Vigenar Cipher.

Substitution Cipher

The key space in substitution cipher is $26!$, roughly $2^{88}$.

We can use the frequency of English letters to map to the occurance of cipher texts:

• e: 12.7%
• t: 9.1%
• a: 8.1%

Then we can use frequency of pair of letters, aka digrams, then trigram etc.

Vigener cipher

Repeat the key, c = (k + m) % 26.

Suppose we know the length of the key, l, we can break down the ciphertext to block with the lenght l, the most common letter MUST be the encrypted e! So we can recover the first letter of key, we can repeat this process to recover the key.

We can use error-n-trail to test different key lenght until the message makes sense.