CS588: Cryptography, Spring 2005

Notes: Tuesday 1 February 2005
Assignments Due
 Thursday, 3 February: Problem Set 1
Notes
How many women should we expect the Iraqi national assembly to have?
(define numberofparties 111) (define numberofassemblymembers 275) (define (max a b) (if (> a b) a b)) (define (factorial n) (if (= n 0) 1 (* n (factorial ( n 1))))) (define (choose n k) (/ (factorial n) (* (factorial k) (factorial ( n k))))) (define (binomialprobability n k p) (* (choose n k) (expt p k) (expt ( 1 p) ( n k)))) (define (expectedparties seats) (exact>inexact (* numberofparties (binomialprobability numberofassemblymembers seats (/ 1 numberofparties))))) (define (expectedpartycount n) (if (< n 0) 0 (+ (expectedparties n) (expectedpartycount ( n 1))))) (define (expectedwomen n) (if (< n 0) 0 (+ (* (floor (/ n 3)) (expectedparties n)) (expectedwomen ( n 1)))))
Enigma Schematic
How big is the keyspace for the Enigma machine?
What is an involution?
Why must the reflector be an involution?
Rejewski's Theorem: The composition of two permutations that are involutions consists of pairs of cycles of the same length.
Links
 Cryptanalysis of Enigma, Jason Friedman's lecture notes on a lecture by Alex Biryukov.
 Storm Over UBoat Film, BBC News, June 2000.
 Bletchley Park
 Dave's Bletchley Park Pictures
Propose to an Englishman any principle, or any instrument, however admirable, and you will observe that the whole effort of the English mind is directed to find a difficulty, a defect, or an impossiblity in it. If you speak to him of a machine for peeling a potato, he will pronounce it impossible: if you peel a potato with it before his eyes, he will declare it useless, because it will not slice a pineapple.
Charles Babbage, breaker of Vigenere cipher, after losing funding for his Difference Engine project, 1823.
University of Virginia Department of Computer Science CS 588: Cryptology  Principles and Applications 
cs588–staff@cs.virginia.edu 