Some project suggestions for MATC16
This list may take half an hour to read through, but I hope it will help. You can also choose a topic not mentioned here: for instance, you may get some ideas by browsing the cryptography pages of wikipedia, or you may have noticed something interesting in the book that was not explained properly. But in any case, this list still should give an idea how I imagine a project. The resources I gave here might not be exhaustive; if you get stuck, please seek my advice.
Breaking the Playfair and/or ADFGX. See Section 2.6 and the references there. (Among my suggestions, this project is the most similar to solving crossword puzzles.)
Breaking the Enigma. See Section 2.12 and http://en.wikipedia.org/wiki/Enigma_machine and http://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma. (This is a bit more challenging mathematically than the previous, e.g., you need to understand the cycle decomposition of permutations.)
What determines the period of an LFSR sequence, and how large can that be? See Section 2.11, the references there, and Section 3.11. (This uses a bit of Galois fields, but it isn't dangerous. It could be a not very difficult math project that mostly avoids cryptography, but please mention at least a bit the cryptographic relevance of the topic.)
There are many primality tests and factorization methods that we haven't touched. You may discuss some of them, with a bit of comparison which works better when. (Choose either primality tests or factorization, not both.) See Sections 6.3, 6.4, http://en.wikipedia.org/wiki/Primality_test and http://en.wikipedia.org/wiki/Integer_factorization.
Continued fractions and RSA. The goal is to prove the theorem of Subsection 6.2.1. You will need
Section 3.12 and the number theory textbooks cited there.
Further attacks on RSA. (This may mean factorization algorithms, but there's also e.g. the "timing attack", found by a Stanford undergrad in 1995; see Subsection 6.2.3. If you include the timing attack, make sure you explain the simple counterattack that Wikipedia mentions.) See Chapter 6, the reference [Boneh 1999], and http://en.wikipedia.org/wiki/RSA.
We have seen that one-way functions and pseudorandom generators are in the heart of most modern cryptosystems (see also http://en.wikipedia.org/wiki/One-way_function). However, the existence of neither has been proved; this is a major open problem in computer science and cryptography. It turns out that their existences are equivalent to each other: you can construct one from the other. A possible project is to give a proof of this theorem (assuming the Goldreich-Levin lemma about hard-core bits). You should of course include the necessary background and definitions. Our book has nothing about this topic, and you will need a little bit of probability and complexity theory. The Gács-Lovász lecture notes is a very nice source for this project. If you find something vague in those notes, you can turn to Goldreich's textbook for details.
The existence of one-way functions would imply that the complexity class NP is strictly larger than P, which might be the most important open problem of mathematics. See http://en.wikipedia.org/wiki/P=NP_problem. However, even P not being NP would not be enough for their existence! (So, modern cryptography might not be built on very firm grounds... But most people do believe that factorization is not in P hence one-way functions exist.) The project might explain the P and NP classes, and the relationship between the P/NP problem and the existence of one-way functions. A related project (maybe the same one, depending on how much you can write about either of them) is to discuss the use of NP-complete problems in cryptography. Possible sources again include the Gács-Lovász lecture notes or the Goldreich book cited above.
Scott Aaronson on P=NP (from Wikipedia, of course): If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in "creative leaps", no fundamental gap between solving a problem and recognizing the solution once it's found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss...
Security protocols are among the most important applications of cryptography (e.g., paying with a credit card on the internet), but we will have time only to mention the main questions and techniques. So, discussing any of the protocols in detail could be a project. See Chapter 10. A little example you may discuss: if you go to the UofT math department webmail page https://mail.math.toronto.edu for the first time with a given computer, you will get flashy alarming messages saying that this website has an invalid security certificate, which you may accept manually if you want, but you'd better get out of here immediately. What does this mean? Should you be really worried? When you look at the certificate, of how many of the entries can you figure out what they mean?
Chapter 11 describes a complicated protocol solving the rather tricky problem of how to make and pay with digital cash. You don't have to repeat the protocol, rather summarize the main parts of it, and explain the main ideas in setting up the scheme and the math tools that make it work. The existing wikipedia article is rather badly organized and the little content it has is hard to understand, so your primary goal could be to write a section into that article, maybe with some of the technicalities left out from there, only included in the project. (If you do a nice job, you may want to actually edit the wikipedia article. If you don't know how to do it, I can help.) One thing that wikipedia does have is a few actual realizations, like public transit in Hong Kong, but I'm not sure that that's the same sort of digital cash; for your project you can also look at those, if you want.
Secret sharing schemes. These solve a natural problem of cryptography using some nice non-complicated math. See Chapter 12 and http://en.wikipedia.org/wiki/Secret_sharing.
Playing games over the phone (Chapter 13) will not be covered on class, but I cannot right now imagine how a project that is not just a copy of the chapter would look like. But if you are very creative, e.g., come up with your own scheme for your own favourite game, that could be a nice project.
We will briefly discuss the technique of zero-knowledge proofs, but not much (Chapter 14). The Goldreich book makes the point that modern cryptography has three main tools: one-way functions, pseudorandom generators, and zero-knowledge proofs. Correspondingly, it has 180 pages on the topic, but I haven't found out yet a good project suggestion.
Zero-knowledge proofs can be used, for instance, to force parties to follow a security protocol without making them reveal any of their secrets to anyone, this shows their importance. http://en.wikipedia.org/wiki/Zero_knowledge may be a good starting point.
Information theoretical entropy (Chapter 15). Definition. Do you think it is related to the physics entropy? (See http://en.wikipedia.org/wiki/Entropy #Entropy_and_Information_theory.) Huffman code length is close to entropy (Section 15.3). The entropy of English (Section 15.5). (This project needs a bit of a probability background, or at least you shouldn't be afraid of probability. For the optimality of the Huffman code and its relation with entropy you will need some further reading, e.g. Cover-Thomas: Elements of Information Theory.)
A quote from Claude Shannon about information entropy (again from Wikipedia): My greatest concern was what to call it. I thought of calling it `information', but the word was overly used, so I decided to call it `uncertainty'. When I discussed it with John von Neumann, he had a better idea. Von Neumann told me, `You should call it entropy, for two reasons. In the first place your uncertainty function has been used in statistical mechanics under that name, so it already has a name. In the second place, and more important, nobody knows what entropy really is, so in a debate you will always have the advantage.'
Elliptic curves (Chapter 16): in class we will do at most the basics (definitions and basic factorization algorithm using them). Discussing any application in depth could be a project. For some of them, e.g., how the analogs of the attacks against discrete log systems work for elliptic curves, the book is very brief (Subsection 16.2.2), giving more-or-less only references. See also http://en.wikipedia.org/wiki/Elliptic_curve_cryptography.
The Reed-Solomon error correcting code (Section 18.9). How to decode? (You will need Section 18.8 for that.) Why and how is it used in CD players? (The emphasis might be on either the math or the application. For example, I have always been curious why my MacBook has no problem with playing CD's that my SONY compact hi-fi system has problems with.) See also http://en.wikipedia.org/wiki/Reed-Solomon_code.
The McEliece cryptosystem (Section 18.10), based on error correcting codes, is one of the few candidates for public key cryptography after quantum-computers will be built, or after factorization will be easy, whichever happens earlier, if ever. We might have time to define it, but certainly won't have time to discuss its properties. If you choose this project, you might consider contributing to http://en.wikipedia.org/wiki/McEliece.
We will not have time to do any quantum computing and cryptography (Chapter 19). So, one possibility is Shor's factorization algorithm (Section 19.3 and the wikipedia article). Many researchers say that the type of quantum computer needed for factorization will never be built, but attacking some other problems might be more realistic. One such example is quantum key exchange (see Section 19.2 and http://en.wikipedia.org/wiki/Quantum_cryptography), which has actually been implemented on several occasions in the past five years. Another problem is the quantum database search, which can be solved by http://en.wikipedia.org/wiki/Grover's algorithm, and in theory gives a quadratic speed-up for problems like breaking Triple DES or AES.