## Cryptography

Course Material Spring 2008

News
• Apologies for the mistakes in the scaling of the marks for CW5 (the second part of the cipher challenge). You should multiply the marks sent to you by 5/4 to get the correct mark. The marks are still a bit low, due to everyone going for the same ciphers, but since the marks for the first half of the cipher challenge were correspondingly high, the second examiner and I felt that on average the marks are reasonable.
• The marks for the cipher challenge are now available.

Marks for the encryptions are generally good (average above 80), and I hope to get individual feedback to you tomorrow.

The numbers of solutions received to each cipher was as follows:  Cipher Number of solutions 4 11 5 1 11 25 24 23 35 3 37 4 40 25 43 9 45 9 51 2 53 5 55 3 59 3 61 23 76 11 78 13 83 3 84 22 91 24 93 2 97 1 98 8

• The ciphers which were broken this year are numbers 4, 5, 11, 24, 35, 37, 40, 43, 45, 51, 53, 55, 59, 61, 76, 78, 83, 84, 91, 93, 97 and 98.
• Assignment 8 is now available from the link below.
• Cipher challenge web page is now available here.
• Tuesday 19th February, 10.45 am. I am putting the finishing touches to the cipher challenge web page, and will put the link here shortly. I have changed the rules this year, so that there is no great advantage to starting work on the ciphers straight away.
• Cipher challenge: I have managed to process all the ciphers (L-Z) sent to me, with two exceptions: Wong HC still needs to send me the full message in shorter lines (see email). I have received nothing at all from Tran K or Zhang L: this is your last chance to send something in.
• Reminder: NO lectures in Reading Week: 18th/19th February.
• Note that the Cipher Challenge consists of two parts: part 1 is encryption, which counts 7.5% overall. Part 2 is decryption, which also counts 7.5%. The precise marking scheme for part 2 will be decided once I have assessed the difficulty of the ciphers submitted.
• Marked work and solutions can be collected in the tutorials. Any work which is not collected will be deposited in the cabinet in the School Office in the usual way.
• The Tuesday tutorial has been moved from Eng 324 to Eng 325. Or possibly not.
• Web pages in preparation. For back-up here is a link to last year's web-pages.

Course descriptions and course information
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

The first ELEVEN instalments of the notes have been revised (very slightly) for 2008. Instalment 12, which will not be lectured this year, is the 2006 version.
• 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

Other course material

• Here is the worked example of breaking a substitution cipher, done in Lecture 3.

The recommended book for reading before taking the course is Simon Singh's The Code Book; the recommended course text is Douglas Stinson's Cryptography: theory and practice (unfortunately, Paul Garrett's Making, Breaking Codes is out of print). (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 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 by Peter Cameron on computational complexity.
• Here are John Preskill's Caltech notes on quantum computing.
• Here is Sir Arthur Conan Doyle's "The Adventure of the Dancing Men"
• Here is Edgar Allan Poe's "The Gold-Bug"
• .
• 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.
• John Talbot and Dominic Welsh, Complexity and cryptography: An introduction, Cambridge University Press, Cambridge, 2006.
• Dominic Welsh, Codes and Cryptography, Oxford University Press, Oxford, 1988.
• Susan Loepp and William K. Wootters, Protecting information: from classical error correction to quantum cryptography, Cambridge University Press, 2006.
• 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 22 May 2008