Lecture notes for Algorithm Design

Lecture Notes for Algorithm Design

Introduction to Cryptography, 9 December 1999

These are provisional lecture notes, expect changes.

cryptography - from the greek, secret writing
1. cryptanalysis, cryptology
cipher - a cryptographic system
1. encrypted text = encryption function(plain text, encryption key)
2. decrypted text = decryption function(encrypted text, decryption key)
3. cipher properties
  1. for a proper (encryption key, decryption key) pair,
    plain text = decryption(encryption(plain text, encryption key), decryption key)
  2. for any improper (encryption key, decryption key) pair,
    plain text != decryption(encryption(plain text, encryption key), decryption key)
  3. any other method of going from encrypted to decrypted text is intractable.
three main types of cryptographic systems: concealment, transposition, and substitution ciphers.
concealment (null, open-letter) ciphers - plain text hidden in plain sight
1. puncture ciphers, first letter ciphers
2. steganography, digital water marks
transposition (permutation) ciphers - textual re-arrangements
1. knight's tour permutations
2. matrix ciphers
substitution ciphers - substituting one thing for another
1. alphabet, letters
2. caesar ciphers - constant shifted alphabet
  1. for example
    
    plain text A B C D E F G H I J K L M N O P Q R S T U V W X Y Z *
    
    cipher text Y Z * A B C D E F G H I J K L M N O P Q R S T U V W X
    
    plain text E A T * A T * J O E S
    
    cipher text B Y Q X Y Q X G L B P
  2. there's no key, the encryption and decryption functions themselves are secret - restricted-use cipher
3. vigenere ciphers - several shifted alphabets; alphabet matrix
  1. the key selects the shifted alphabets
    
    plain text A B C D E F G H I J K L M N O P Q R S T U V W X Y Z *
    
    shifted R K L M N O P Q R S T U V W X Y Z * A B C D E F G H I J
    
    shifted V G H I J K L M N O P Q R S T U V W X Y Z * A B C D E F
    
    shifted C Y Z * A B C D E F G H I J K L M N O P Q R S T U V W X
  2. encryption uses several shifted alphabets as selected by the letters in the key.
    
    key R V C R V C R V C R V
    
    plain text E A T * A T * J O E S
    
    cipher text O G Q J G Q J P L O Y
4. permutation ciphers
  1. permute, rather than , the alphabet.
  2. the key is the permutation
5. vernam (one-time pad) ciphers
  1. generate a random pad as long as the message
  2. to encrypt, xor the pad and the message together
  3. to decrypt, xor the pad and the encrypted text
  4. the pad can only be used once
breaking the codes
1. caesar ciphers
  1. know the algorithm
  2. statistical attack on the encoded text
2. shifted alphabet ciphers
  1. brute force is easiest
  2. statistical attacks also work
3. vigenere ciphers
  1. brute force is difficult because of the key length
  2. statistical attacks are more difficult but still possible
4. permutation ciphers
  1. brute force is hard - 27! is around 10²⁸, and there are around 31 x 10¹⁵ nsecs per year
  2. statistical attacks are easy
5. vernam ciphers
  1. the only provably unbreakable cipher in existence - claude shannon in the late 1940s.
  2. but the pad must be truly random and it can only be used once.
  3. brute force will produce every possible message
  4. the pad's randomness makes statistical analysis meaningless.

modern cryptography

asymmetric (or public key) vs. symmetric (or private key) systems
cryptographic uses
1. secrecy - encryption and decryption
2. authentication - digital signatures
3. verification - cryptographic hashes
intractability - the basis for cryptography
1. one-way functions - easy to compute y = f(x); hard to find x given y
  1. example - multiplication by primes

diffe-hillman key exchange

the boot-strap problem
1. alice and bob need to share a secret key to communicate securely
2. alice and bob need secure communication to share a secret key

the diffe-hillman key exchange solves the boot-strap problem by allowing secret key exchanges using unsecure communication

the protocol
1. alice and bob agree on a large - 200 digit - integer p and an integer g between p and 2
2. alice and bob pick each pick secret integers A and B at random to be less than p
3. alice computes a = g^A mod p and sends it to bob
  bob computes b = g^B mod p and sends it to alice
4. g^A mod p is the modular exponent of g, A, and p
5. alice computes x = b^A mod p
  bob computes y = a^B mod p
6. done

alice knows x and bob knows y - so what?

a fun fact: xy mod p = (x mod p)(y mod p)

let's look at what alice's value x:

x	=	b^A mod p
	=	(g^B mod p)^A mod p
	=	(g^B mod p)(g^B mod p)^{A - 1} mod p
	=	g^B(g^B mod p)^{A - 1} mod p
	=	and so on, and so on
	=	g^{(A - 1)B}(g^B mod p) mod p
	=	g^{(A - 1)B}g^B mod p
	=	g^AB mod p

bob can do the same thing with y and get y = g^BA mod p
that means x = y and bob and alice know something in common

can an eavesdropper know x or y?
1. an eavesdropper can learn p, g, a, and b
2. an eavesdropper knows that a = g^A mod p
3. the eavesdropper needs to know A to find x
4. the discrete logarithm computes A from p, g, and a
```
A <- 0
x <- 1
do a != x mode p and A != p
  A <- A + 1
  x <- x*g
od
```
5. this is an exhaustive search which will take, on average, p/2 iterations to terminate
6. inverting modular exponentiation is intractable, and it's a one-way function

This page last modified on 16 December 1999.

key	R	V	C	R	V	C	R	V	C	R	V
plain text	E	A	T	*	A	T	*	J	O	E	S
cipher text	O	G	Q	J	G	Q	J	P	L	O	Y