Cryptography 1

Keywords: Crypto Class Coursera Cryptogrophy

Video Lectures

Week 1 : Introduction

Overview

Crypto is everywhere. This course will cover symmetric encryption.

A cipher consists of E and D - the encryption and decryption algorithm. They should be know algorithms, not proprietary.

What is Crypto

Uses:

• Digital signatures
• Mix net - allows anonymous communications
• Digital currency
• Elections
• Private auctions
• Secure multi-party computation
• Privately outsourcing computation
• Zero knowledge: can show proof of having some piece of information without revealing the information

Theorm: Anything that can be done with a trusted authority can also be done without a trusted authority.

Crypto Analysis

1. Precisely specify threat model
2. Propose a construction
3. Prove that breaking construction under threat model will solve an underlying hard problem

History of Crypto

Symmetric ciphers: use the same key for encryption and decryption.

Historic Ciphers

Substitution cipher

Simplest form is the Caesar Cipher which only uses a shift. A substitution cipher uses a random mapping of letters as it's key. The key space is about 2⁸⁸ which is sufficiently large, but the cipher is subject to frequency analysis. It is subject to a cipher-text only attack.

Vigener Cipher

Key is some sequence of letters. Key is repeated until it is the same length as the plain text. Each position is then summed and mod26. If we know the length of the key, we can still use a frequency analysis. If the key length is not known, the same attack can be run for an assumed key size (starting at 1) and incremented. If the key size is wrong, the frequency distribution will be even, when the key size is correct, the frequency distribution will be correct. Again, cipher-text only attack (though a larger sample is needed).

Rotor Machines

Uses substitution ciphers encoded on spinning disks. Changes the cipher based on the last letter used. Still subject to frequency based, cipher-text only attacks. The Enigma machine was the most advanced rotor machine.

DES (1974)

Key space was 2⁵⁶ and the block size was 64.

Today

AES (2001), Salsa20(2008) and others.

Discrete Probability 1

Review of notations and concepts in discrete mathematics and probability. Nothing here that I don't remember.

Discrete Probability 2

More review. Independence of events. XOR.

Given Y with a random distribution over {0,1}ⁿ (though not necessarily uniform) and X with an independent, uniform distribution over {0,1}ⁿ then Z := Y ⊕ X is uniform over {0,1}ⁿ. There is a very cool proof of this.