**Reading**: *text*, §10^{*}

**Assignments**: Homework 2, due Oct. 21; Lab 2, due Oct. 21

- Greetings and felicitations!
- Puzzle of the Day
- Cryptography
- Codes vs. ciphers
- Attacks: ciphertext only, known plaintext, chosen plaintext
- Types: substitution, transposition

- Symmetric Cryptography
- Monoalphabetic (simple substitution):
*f*(*a*) =*a*+*k*mod*n* - Example: Caesar with
*k*= 3,`RENAISSANCE`→`UHQDLVVDQFH` - Polyalphabetic: Vigenère,
*f*(_{i}*a*) =*a*+*k*_{i} - Cryptanalysis: first do index of coincidence to see if it is monoalphabetic or polyalphabetic, then Kasiski method.
- Problem: eliminate periodicity of key

- Monoalphabetic (simple substitution):
- Long key generation
- Autokey cipher: key is plaintext followed by plaintext or ciphertext
- Running-key cipher:key is simply textl wedge is that (plaintext, key) letter pairs are not random (
`T`/`T`,`H`/`H`,`E`/`E`,`T`/`S`,`R`/`E`,`A`/`O`,`S`/`N`, etc.) - Perfect secrecy: when the probability of computing the plaintext message is the same whether or not you have the ciphertext; only cipher with perfect secrecy: one-time pads;
*C*=`AZPR`; is that`DOIT`or`DONT`?

- Product ciphers: DES, AES
- Public-Key Cryptography
- Basic idea: 2 keys, one private, one public
- Cryptosystem must satisfy:
- Given public key, computationally infeasible to get private key;
- Cipher withstands chosen plaintext attack;
- Encryption, decryption computationally feasible (
*note*: commutativity not required)

- Benefits: can give confidentiality or authentication or both

- Use of public key cryptosystem
- Normally used as key interchange system to exchange secret keys (cheap)
- Then use secret key system (too expensive to use public key cryptosystem for this)

- RSA
- Provides both authenticity and confidentiality
- Go through algorithm:

Idea:*C*=*M*mod^{e}*n*,*M*=*C*mod^{d}*n*, with*ed*mod*φ*(*n*) = 1

Public key is (*e*,*n*); private key is*d*. Choose*n*=*pq*; then*φ*(*n*) = (*p*−1)(*q*−1). - Example:
*p*= 5,*q*= 7; then*n*= 35,*φ*(*n*) = (5−1)(7−1) = 24. Pick*d*= 11. Then*ed*mod*φ*(*n*) = 1,

so*e*= 11

To encipher 2,*C*=*M*mod^{e}*n*= 2^{11}mod 35 = 2048 mod 35 = 18, and*M*=*C*mod^{d}*n*= 18^{11}mod 35 = 2. - Example:
*p*= 53,*q*= 61; then*n*= 3233,*φ*(*n*) = (53−1)(61−1) = 3120. Pick*d*= 791. Then*e*= 71

To encipher*M*=`RENAISSANCE`, use the mapping`A`= 00,`B`= 01, …,`Z`= 25,`␢`= 26.

Then:*M*=`RE NA IS SA NC E␢`= 1704 1300 0818 1800 1302 0426

So:*C*= 1704^{71}mod 3233 = 3106; … = 3106 0100 0931 2691 1984 2927

You can also obtain a PDF version of this. | Version of October 21, 2016 at 11:23AM |