Lecture notes for Algorithm Design

Lecture Notes for Algorithm Design

Introduction to Cryptography, 3 May 2000

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 shift, 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.
6. digital encryption standard (des) - a us (nbs) standard
  1. n-bit, 56 <= n <= 1000, secret key system
  2. data are run through 16 stages, each stage swaps halves of the data and xors half the data with the results of a function applied to part of the key and the other half of the data
  3. 56-bit des broken in 57 hours by a $250,000 machine in 1998

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
underpinnings
1. information theory - provably secure crypto systems; rare
2. intractability - believed secure crypto systems; much more common
  1. one-way functions - easy to compute y = f(x); hard to find x given y
  2. trapdoor functions - one-way functions with a secret, easy to compute inverse function

example - diffie-hellman 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 diffie-hellman 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 25 June 2000.

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