Lecture 8 Notes;  April 16, 1997; Notetaker: Elizabeth Jurrus

DES - Data Encryption Standard (unbroken)

	- main function: secrecy.  Not used for classified data
	- takes in 64 bits, outputs 64 bits, key is 56 bits (ignore parity bit)
	- encipher and decipher blocks of data
	- deciphering is the reverse processes of the enciphering processes

IDEA cipher - fixes weaknesses in DES
Lucifer Cipher - key changed from 128 to 64 bits.  Good cipher
Product cipher - uses transposition and substitution at the bit level.  Is also a round 
cipher (iterates 16 times, 16 different keys).

DES - 3 parts
1) Initial Permutation (IP) (see page 17 of the Data Encryption Standard Handout)
	 - Used to generate 16 sets of keys („round keys¾) used to encipher

2) Complex key-dependent computation (see page 8 of the Data Encryption Standard 
Handout )
	- defined in terms of function f (the cipher function) and KS (the key 
schedule)
	- strength lies in how hard it is to invert f.
	  (see page 11 of the Data Encryption Standard Handout)
	
3) Inverse Initial Permutation (IP-1)

Things people noticed:

1)  Complementation Problem (Diffie & Hellman):
	DESk(M) = C	DESe(M¼) = C¼

2) Certain keys contain their own inverses
	DES0(M) = C	DES0(C) = M

3) Double Encipherment does not help.
	if   (DESk2 (DESk1(M) ) = C  then
		DESk3(M) = C

	How good is key length?

4) Differential Cryptanalysis
	focus on plaintext and ciphertext pairs

	C1 xor C2 = b
	M1 xor M2 = b¼

DES modes:
1) ECD - straight DES.  On it¼s way to being broken.
2) CBC - Cipher Block Chain
3) Triple DES - uses only 3 keys
4) EDE mode - uses 2 keys to add more complexity
	(DESk1 (DES-1k2 (DESk1 (M)))

Public Key Cryptography (Diffie and Hellman):
- Created key exchange protocol
- How do you distribute keys?
- use 2 keys: 1) public - available to all ( E )
                     2) private - you are the only one who knows it (D)


RSA - an exponentiation cipher
	C, M elem [0, n - 1]

	Me mod n = C
	Cd mod n = M

in order for this to work:
1) (Me mod n)d mod n = M or
2) Med mod n = M
must hold

ed mod g(n) = 1
Med mod n = M1+kg(n) mod n 
	( ed mod g(n) = 1 <=> ed = 1 + k g(n) )
                = M (Mg(n))k mod n
                = M (Mg(n) mod n) k mod n
                = M ( 1 ) mod n

pick two large primes, p & q
	p * q = n

pick e so that this holds:
	ed mod g(n) = 1
	where 
	g(n) = (p - 1)(q - 1)

d is a private key and the pair of e & n are public

take message, M
	Me mod n = C
	ed mod n = M (to decipher)

example:
	p = 5, q = 7, => n = 35, g(n) = 24
	e = 11
	11d mod 24 = 1, so d = 1

M = hello ( message must not exceed 25 )

so,            h  e  l  l  o 
maps to   07 04 11 11 14	

use 2811 mod 37 = 7 to decipher

Note:  g(n) -> since e and n are unknown, it is easy to break the cipher.  However, n cannot be 
factored and you can¼t break the cipher.