Cryptography

Course Material Spring 2006

News
• Any rumours you may have heard about the Cryptography Exam being postponed or cancelled should be ignored. The exam will take place as scheduled.
• Marked coursework 6 is available for collection from the School Office.
• Next scheduled office hour: Thursday 4th May, 1-3pm. Or email for an appointment or help (but I may not be able to give instant replies!).
• There is an error in the solution to 4(d) in assignment 5. We have g^k=56, not 44, so h^k=5 and the inverse of 5 mod 59 is 12, so the answer is 45.12 mod 59, i.e. 9. This does not affect any of your marks, as it depends on my choice of the random number k (=21), and your choice will almost certainly be different.
• Return of coursework

Marked Coursework 5 and 6 can be collected from the Maths Office (room 101).

• New book: "Complexity and cryptography" by Talbot and Welsh. Cambridge University Press. Might be suitable as a textbook for the course.

Course descriptions and course information
Disclaimer and acknowledgement

This web-page and the notes etc. for the course closely follow Peter Cameron's originals which he has very kindly allowed me to use. His pages may still be accessible here.

Notes

• Notes 1: Introduction
• Notes 2: Substitution ciphers
• Notes 3: Stream ciphers
• Notes 4: Stream ciphers, continued
• Notes 5: Stream ciphers, concluded
• Notes 6: Public-key cryptography
• Notes 7: Public-key cryptography: RSA
• Notes 8: Public-key cryptography: Primes and factorisation
• Notes 9: Public-key cryptography: El-Gamal
• Notes 10: Public-key cryptography: Other ciphers
• Notes 11: Secret sharing and other matters
• Notes 12: Quantum effects; bibliography

Coursework

The recommended book for reading before taking the course is Simon Singh's The Code Book; the recommended course text is Paul Garrett's Making, Breaking Codes. (See below for bibliographical details.)

Web Resources
• Here is the list of ASCII 7-bit codes, and here are the International Telegraph Codes.
• Here are three samples of random text matching the letter, digram and trigram frequencies in a piece of English text (Lewis Carrol's Alice's Adventures in Wonderland).
• Here is "FISH and I" by W. T. Tutte (one of the Bletchley Park codebreakers).
• Here is a web page about the recent proof by Manindra Agrawal, Neeraj Kayal and Nitin Saxena that primality can be tested in polynomial time.
• Here is the Trinity College Historical Cryptography website.
• Here is a collection of Maple lessons on topics in cryptography from Adept Scientific, which can be downloaded free of charge.
• Here are some lecture notes on computational complexity.
• Here is the full text of Gadsby, by Ernest Vincent Wright (a novel which doesn't contain the letter E).
• Here are John Preskill's Caltech notes on quantum computing.
• General:
• Henry Beker and Fred Piper, Cipher Systems: The Protection of Communications, Northwood Books, London, 1982.
• Robert Churchhouse, Codes and Ciphers: Julius Caesar, the Enigma, and the Internet, Cambridge University Press, Cambridge, 2002.
• Paul Garrett, Making, Breaking Codes: An Introduction to Cryptology, Prentice-Hall, Upper Saddle River, 2001.
• Simon Singh, The Code Book: The Secret History of Codes and Code-Breaking, Fourth Estate, London, 1999.
• Douglas R. Stinson, Cryptography: Theory and Practice (2nd edition), Chapman & Hall/CRC, Boca Raton, 2002.
• Dominic Welsh, Codes and Cryptography, Oxford University Press, Oxford, 1988.
• Historical:
• Helen Fouché Gaines, Cryptanalysis: A Study of Ciphers and their Solution, Dover Publ. (reprint), New York, 1956.
• F. H. Hinsley and Alan Stripp (eds.), Code Breakers: The Inside Story of Bletchley Park, Oxford University Press, Oxford, 1993.
• Andrew Hodges, Alan Turing: The Enigma, Vintage, London, 1992.
• Leo Marks, Between Silk and Cyanide: The Story of SOE's Code War, HarperCollins, London, 1998.
• Doron Swade, The Cogwheel Brain: Charles Babbage and the Quest to Build the First Computer, Little, Brown & Co., London, 2000.
• Gordon Welchman, The Hut Six Story: Breaking the Enigma Codes, M & M Baldwin, Cleobury Mortimer, 1998.
• Peter Wright, Spycatcher: The Candid Autobiography of a Senior Intelligence Officer, Stoddart Publ. Co., Toronto, 1987.
• Fictional:
• Sir Arthur Conan Doyle, The Adventure of the Dancing Men, in The Complete Sherlock Holmes, Penguin (reprint), London, 1981.
• Edgar Allan Poe, The Gold-Bug, in Complete Tales and Poems, Castle Books, Edison, NJ, 1985.
• Dorothy L. Sayers, Have His Carcase, Victor Gollancz, London, 1932.
• Related topics:
• Richard Feynman, The Character of Physical Law, BBC publications, London, 1965.
• M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.
• Ray Hill, A First Course in Coding Theory, Oxford University Press, Oxford, 1986.
• Michael A. Nielsen and Isaac L. Chuang, Quantum Information and Quantum Computation, Cambridge University Press, Cambridge, 2000.
• Miscellaneous:
• G. Mander (ed.), wot txters hav bin w8ing 4, Michael O'Mara Books, London, 2000.
• Georges Perec (translated by Gilbert Adair), A Void, Harvill Press, 1994.
• Ernest Vincent Wright, Gadsby, Wetzel Publishing Co., Los Angeles, 1931.

Robert A. Wilson
(based on Peter Cameron's original page)
Created 5 January 2005
Updated 2 May 2006