## Cryptography

Course Material Spring 2005

News
• For revision purposes, the 2004 exam gives the best guide to how this year's exam will look.
• Coursework 6 has now been marked. More than one-third of the essays handed in were awarded a mark of zero due to blatant copying. On your transcript of marks you will see a seventh mark, equal to the third mark. This is so that the marks for the cipher challenge count double.
• Solutions 5 and Coursework 6 now on the web.
• Details of how an audio CD is encoded and decoded are available here, for anyone who is interested.
• My office hours are Monday 3.30-4.30 and Wednesday 1-2 in room G51.

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.)

I have been asked to draw your attention to a possible answer to the question "What to do next?". The National University of Ireland, Galway do an M.Sc. in Communication Systems: you can find details here.

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 29 April 2005