MTH6115 - Cryptography - 2023/24
Topic outline
-
-
Students mustMark as doneView all general news and announcements from the your module leaders.
-
Forum Description: This forum is available for everyone to post messages to. Students can raise questions or discuss issues related to the module. Students are encouraged to post to this forum and it will be checked daily by the module leaders. Students should feel free to reply to other students if they are able to.
-
-
Overview: This week we will introduce the set up of classical (symmetric key) cryptography. After talking about Substitution and Transposition (and Codebook) we will mainly focus on the former. We discuss Caesar Shifts, Affine Ciphers, and explain how frequency analysis is used to attack substitution (and transposition) cipher.
For this week's (and upcoming) lectures you need to revise congruences and basics of group theory.
Lectures
- Lectures 1, 2, Tuesday 26/09. Notes
Summary: General set up. Main types of ciphers: Substitution, Transposition and Codebook.
Have a go at the following substitution cipher: BolognaSub. We will crack it on Friday, but try to see how far you can go. Frequency tables come handy for this.
- Lecture 3, Friday 29/09, 14:00--15:00. Notes
Summary: Frequency analysis (on letters, digrams, and trigram). An example in detail (Bologna). Methods to make substitution ciphers more secure (nulls and homophones, composing ciphers, etc.). Affine ciphers and their main properties (composition, identity, inversion) .
Supplementary material: Frequency tables, BolognaSub, a paragraph from Gadsby (all taken from Prof. Cameron's notes; see below)
Tutorial
- Tutorial, Friday 29/09, 15:00--16:00.
Summary: used for teaching (exceptionally this week). See Notes above.
Exercises
Non-assessed Exercise Sheet 1. Solutions [You can skip Q4 and Q5 until Tuesday Week 2 when I cover the necessary material.]
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 1-21 (optional).
Introduction to Algebra (MTH4104) notes by Dr. Fink. Revise Section 4 for Modular Arithmetic, and try this exercise sheet (I cannot make the solutions available unfortunately). For group theory and permutation groups see Sections 7, 8 (but we won't go into these too deeply). Section 1 (Euclid's algorithm, etc.) will be needed too as well as some familiarity with Section 2.
There are YouTube videos to help you revise modular arithmetic. For instance, this one:
This guy (who seems to have +4 videos on the subject) keeps thing very simple and basic.
Example of breaking a substitution cipher
Substitution tool (you can use this tool to replace letters in a substitution ciphertext as you break the cipher step by step)
-
Overview: We will continue with affine ciphers and do more examples. Then, we will introduce stream ciphers as fancier versions of substitutions ciphers which are designed to confuse frequency analysis. We look at the special case of Vigenère, and note that it is still vulnerable (to Kasiski's attack). We briefly discuss how random keys and substitution tables that are Latin squares will allow us to remedy this.
Lectures
- Lecture 1, Tuesday 03/10, 11:00--12:00. Notes
Summary: Composition and inverses of affine ciphers. An example of affine cipher decryption.
- Lecture 2, Thursday 05/10, 13:00--14:00. Notes
Summary: A new topic: Stream Ciphers. A special case of a stream cipher: Vigenère. Kasiski's method for cracking stream ciphers. An example of Kasiski's method.
Another example of a Vigenère cipher. Have a go at it using the Kasiski's method.
- Lecture 3, Friday 06/10, 14:00--15:00. Notes Solutions to extra exercies
Summary: General stream ciphers. Randomness of the key and the substitutions table being a Latin square make the stream cipher more secure (more on this next week). Examples of substitution tables (more next week).
Here are a few simple examples of substitution tables to play around with.
Tutorial
- Tutorial, Friday 06/10, 15:00--16:00. Notes Solutions to extra exercises
Summary: Review of congruences and examples of finding inverses modulo n. (I have added a few new exercises at the end of the notes. Please try these yourselves. You should be able to do most of them. I will upload the solutions at a later time.)
Exercises
Non-assessed Exercise Sheet 2. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 27-34 (optional). Chi-squared method is discussed on pages 31-32 (optional).
Another example of breaking a Vigenère cipher (typo: in the last formula on page 4, the p_i in the denominator should be p_{i-5})
-
Disclaimer: The actual assessed coursework quizzes may have more questions, the questions may be different, and possibly more difficult.
-
Overview: This week we will continue with stream ciphers. Then we will explore random sequences (to be used as keys for stream ciphers). Our main focus will be on shift registers and sequences generated by them. We notice periodicity properties of such sequences, and observe some shift register generate more interesting outputs (ie, primitive ones). We see how polynomials associated to shift register help to detect primitive ones. We give formulas for numbers of irreducible and primitive polynomials (using Möbius function and Euler phi function). We also briefly discuss the matrix presentation of shift register (to be continued next week).
Lectures
- Lectures 1, 2, Tuesday 10/10. Notes
Summary: We looked at general stream ciphers and worked out some examples. Then we considered the following question: How do we generate a random sequence? In Vigenere, we can try "adding keys". Another method (for binary sequences): shift registers. We look at shift registers in this and the next couple of lectures.
- Lecture 3, Friday 13/10, 14:00-15:00. Notes
Summary: Primitive shift registers: these are particularly interesting as they generate output sequences with longer periods. Polynomial associated to a shift register. Every primitive polynomial is irreducible (but not conversely). This can be used to work out examples of primitive shift registers.
Tutorial
- Tutorial, Friday 13/10, 15:00--16:00.
Summary: Part of the tutorial was used for teaching. Then I answered some questions about the sample quiz and I did some example of shift registers. Notes are included with the lecture notes.
Exercises
Non-assessed Exercise Sheet 3. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 34-48 (optional).
ASSESSED COURSEWORK: QUIZ 1
-
The quiz has 9 questions. The first 8 questions are worth 1 marks and the last one is worth 2 marks. This quiz will constitute 5% of your module mark.
After submitting the quiz, please include a brief explanation of how you came up with your solutions at the link below. For this you need to include up to three lines of explanation for each problem. I will check these and if the explanation is not clear/convincing enough I will contact you for further explanation.
In the event that there was an error in the question which resulted in you loosing marks, your explanation will be used to adjust your mark.
Please upload only one file (preferably pdf, but a standard image file would also be fine).
-
-
Cryptography lays the foundations of secure communication ("crypto" means "hidden" in Greek) through a range of protocols so that only the person for whom the message is intended can actually read (decode) it. This is of fundamental importance in many aspects of the modern world.
In this module, you will study the mathematical machinery behind classical and public-key cryptography, as well as the significance of digital signatures and authentication. You will see how pure mathematical concepts from group theory and number theory can have practical applications. We also introduce some ideas of complexity theory which formally expresses how hard it is to find a solution to a problem; this is relevant for giving mathematical guarantees that communication is secure. -
Overview: First we cover some leftover material postponed from last week due to a lecture getting cancelled. Namely, we see how polynomials associated to shift register help to detect primitive ones. We give formulas for number of irreducible and primitive polynomials (using Möbius function and Euler phi function).
We then continue our discussion of randomness by looking at Kolmogorov's definition and Golomb's notion of a pseudo-noise sequence. We see that output sequence of a primitive shift register is pseudo-noise, but we show that if it is used as a key for a stream cipher it is still not secure.
For this and next week, you need to revise some basic probability theory.Lectures
- Lectures 1, 2, Tuesday 17/10. Notes
Summary: Polynomial associated to a shift register. Every primitive polynomial is irreducible (but not conversely). Examples of primitive shift registers. Formulas for numbers of irreducible and primitive polynomials (using Möbius function and Euler phi function).
- Lecture 3, Friday 20/10, 13:00--14:00. Notes
Summary: Definition of Golomb's postulates and pseudo-noise sequences using the notions of run and correlation. Pseudo-noise sequences present some kind of random behaviour, but not in Kolmogorov's sense. Output sequence of a primitive shift register is pseudo-noise. A method to determine a primitive shift register using 2n consecutive bits of the output sequence.
Tutorial
- Tutorial, Friday 20/10, 15:00--16:00. Notes (I updated the notes with small correction.)
Summary: I did two examples of determining a shift register using 2n consecutive bits (for continuity, these examples have been included with the notes of the lecture). Then I did examples of periods of shift registers. I have added more example to the notes.
Exercises
Non-assessed Exercise Sheet 4. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 43-51 (optional).
-
Overview: We see that if the key for a stream cipher is truly random and the substitution table is a Latin square (ie, we have a one-time pad), then it produces ciphers that are impossible to crack (Shannon's theorem). We discuss how this fails when the substitution table is not Latin by doing two examples where the ciphertext does give information about the plaintext.
Lectures
- Lecture 1, 2, Tuesday 24/10. Notes Tutorial tasks (for this week's tutorial)
Summary: Quantify information using probability; application to cryptography. One-time pads (i.e., a stream cipher with a random key and a Latin sub table). Shannon's theorem: a ciphertext encrypted using a one-time pad reveals no information about the plaintext. Examples of stream ciphers that are not one-time pad; quantifying how much information about plaintext is revealed by such ciphertexts.
- Lecture 3, Friday 27/10, 14:00--15:00. Notes
Summary: Finished the stream cipher example. Adjugate and transpose Latin squares.
Tutorial
- Tutorial, Friday 27/10, 15:00--16:00. Notes
Summary: We did some of the exercises from the tutorial tasks sheet. I added the solutions of the ones we didn't get to do to the notes.
Exercises
Non-assessed Exercise Sheet 5. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 54-58 (optional).
Optional reading: this is paper by Alan Turing in which he discusses the application of probability theory in cryptography.
Optional reading: an article about the WW2 Japanese code JN-25.
Shannon's theorem and the probability computations we saw are examples of Bayesian Probability. Here is the Wikipedia link, and here and here are two blog posts by one of the masters of the subject (and many other subjects), Terrence Tao.
-
Overview: This week we will starts a new topic: public-key cryptography. In contrast to what we have seen so far, in public-key cryptography one makes an extra assumption: Eve can also see the key! How is the communication safe then? This is where ideas from Complexity Theory come in. We will discuss notions of easy/hard problems, and show how they apply to public-key cryptography.
Lectures
- Lecture 1, 2, Tuesday 31/10. Notes
Summary: What is the best way to sharing the key between Alice and Bob? Diffie-Hellman's big idea behind public-key cryptography: using Complexity Theory (as opposed to Information Theory) to design cryptosystems.
- Lecture 3, Friday 03/11, 14:00--15:00. Notes
Summary: General idea behind complexity theory. Several complexity classes of problems (the ones we are interested in are P, NP and NP-complete). The general abstract framework for public-key cryptography, emphasizing the role of easy/hard functions; this involves a new ingredient: the secret key. One-way and trapdoor functions.
Tutorial
- Tutorial, Friday 03/11, 15:00--16:00.
Summary: Tutorial was mostly used for teaching. I covered one example explaining why the problem of factorising an integer is in ExpTime, but is expected not to be in P.
Exercises
Non-assessed Exercise Sheet 6. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 63-73 (optional).
Wikipedia entry on Turing Machines (optional).
A list of NP-complete problems (optional). If you can prove (or disprove) that any of these problems can be solved in polynomial time you will win the $1000000 Clay Institute prize!
Decimal and binary numbers
A video on writing numbers in the binary base.
ASSESSED COURSEWORK: QUIZ 2
-
Note that this quiz has 9 questions: questions 6 is worth 2 points, while the other questions are worth 1 point. This quiz will constitute 5% of your module mark.
After submitting the quiz, please include a brief explanation of how you came up with your solutions at the link below. For this you need to include up to three lines of explanation for each problem. I will check these and if the explanation is not clear/convincing enough I will contact you for further explanation.
In the event that there was an error in the question which resulted in you loosing marks, your explanation will be used to adjust your mark.
Please upload only one file (preferably pdf, but a standard image file would also be fine).
-
-
-
Overview: This week we will cover the necessary number theoretic background for the implementation of various public-key cryptography systems that we will encounter in the upcoming weeks. This includes Euler's and Fermat's theorems, power functions, order of elements mod n, primitive roots, etc.
Lectures
- Lecture 1, 2, Tuesday 14/11. Notes, Additional exercises (to try before Friday tutorial)
Summary: Quick review of modular arithmetic: congruences, unit elements and their inverses, Euler's phi function, Euclid's algorithm for finding inverses modulo n. Two important lemmas: Lemma A and Lemma B, which will be very useful in working out powers of elements modulo n, that is, am (mod n). Order of an element modulo n: it always exists and divides the phi function. Proof of Euler's theorem using Lagrange's theorem in group theory.
- Lecture 3, Friday 17/11, 14:00--15:00. Notes
Summary: Proof of Lemma B and Euler's theorem (and Fermat's Little Theorem). Important fact: ordna is the period of the sequence {a0, a1, a2,...}. Definition of the Carmichael's Lambda function and a formula for computing it. Primitive elements.
The above facts about orders of elements, primitive elements, etc., are useful when computing powers ak mod n. Such computations are crucial in various public-key cryptosystems.
The topics discussed in the lecture will play an extremely important role in the study of power functions that appear in the context of pubic-key cryptography.
Tutorial
- Tutorial, Friday 17/11, 15:00--16:00. Notes
Summary: We did examples of the lambda function, some power calculation and order calculation.
Exercises
Non-assessed Exercise Sheet 8. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 23-26 and 83-87 (optional).
-
Overview: This week we introduce the power map and study the "easy" and "hard" problems that play a key role in public-key cryptography (eg, in RSA). Along the way we introduce certain important algorithms (eg, a factorisation algorithm). For this and upcoming weeks' material you need to revise Week 6.
Lectures
- Lecture 1, 2, Tuesday 21/11. Notes (I added a few extra exercises, to be attempted before Friday tutorial.)
Summary: Power maps and an important criterion for bijectivity of power maps in terms of the Carmichael function. (Power maps will later be used as encryption/decryption functions, among other things.) Easy and hard problems on which the RSA cryptosystem is based. Easy problems: 1) primality testing, 2) calculating gcd and finding inverse mod n, 3) calculating powers of a (mod n).
- Lecture 3, Friday 24/11, 14:00--15:00. Notes
Summary: An example of the fast method for calculating powers of x (mod n). The hard problems in RSA: 4) factorisation, 5) computing φ(N) and λ(N), 6) finding the inverse Td of the power map Te.
Tutorial
- Tutorial, Friday 24/11, 15:00--16:00.
Summary: I finished the (6) => (4) part of the hard problems, then I did some examples. Notes are combined with the lecture notes.
Exercises
Non-assessed Exercise Sheet 9. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 87-93 (optional).
ASSESSED COURSEWORK: QUIZ 3
-
Overview: After covering a bit more background in number theory (e.g., factorisation algorithms and Miller-Rabin primality test), we are finally ready to introduce RSA, one of the most commonly used public-key cryptosytems. We also discuss digital signatures in RSA.
Lectures
- Lecture 1, 2, Tuesday 28/11. Notes (I corrected an error in the statement of the Prime Number Theorem.)
Summary: Miller-Rabin primality test which is a variant of the factorisation algorithm from last week. For Bob's RSA key to be secure he needs to choose two prime numbers p and q so that N=pq is hard to factorise: one obvious condition for this is that p and q should be large, but even so it may still be easy to factorise N if p and q are not chosen carefully, for example using Pollard's p-1 method.
- Lecture 3, Friday 01/12, 14:00--15:00. Notes
Summary: RSA, one of the most commonly used public-key cryptosytems. Digital signature in RSA.
Tutorial
- Tutorial, Friday 01/12, 15:00--16:00. Notes
Summary: We did an example of RSA. We also looked at past year's final exam. Here is the link if you want to have a go at it. If there is interest we can go over some of the questions in the upcoming tutorials. (Note that the front cover will be different this year: the exam will be 3 hours and in-person. You will be allowed to bring 3 sheets of (two-sided) A4 notes. Certain non-programmable calculators are allowed.)
Exercises
Non-assessed Exercise Sheet 10. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 93-94, 97-98 (optional).
Optional reading: an article on integer factorisation algorithms
-
Overview: This week we will see various public-key cryptography schemes, namely: Diffie-Hellman key exchange, Diffie-Hellman key establishment, and El Gamal. The latter two are based on the following hard problem, which is actually not known to be NP-complete: Discrete Log Problem (DLP). Primitive roots play an important role here, so we will also discuss how one can try to find primitive roots modulo a given prime number.
Lectures
- Lecture 1, 2, Tuesday 05/12. Notes
Summary: Implementation of the three step Diffie-Hellman key exchange (seen in Week 6) using power maps. A related, but different, procedure called Diffie-Hellman key establishment. The security of both of these methods rely on the Discrete Log Problem (DLP). Using primitive roots module large primes makes these systems more secure.
- Lecture 3, Friday 08/12, 14:00--15:00. Notes
Summary: El-Gamal cryptosystem (rival to RSA) -- it relies on DLP. Discussion about finding primitive roots modulo a prime p (this is relevant because we have seen that primitive roots are used in, say, Diffie-Hellman key establishment and in El-Gamal). This in general is not easy, but there is a simple criterion that is very useful in the case where p is the bigger prime in a Sophie Germain pair.
Tutorial
- Tutorial, Friday 08/12, 15:00--16:00. Notes
Summary: I discussed some of the Quiz 3 questions and also went over the solution of one of the questions from last year's exam.
Non-assessed Exercise Sheet 11. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 100-106, and page 113 (optional).
-
-
-
The assessment for this module consists of a written on-campus final exam 80% and four assessed courseworks 5% each.
The assessed coursework, which will be in the form of QMplus quizzes, will take place on Weeks 3, 6, 9, and 12.
On Week 2 I will upload a sample non-assessed quiz so that you can become familiar with the format of the quizzes.
The final exam will be a 3-hour in-person hand-written exam and it will take place on campus. You are allowed to bring three sheets of A4 notes (two-sided). Non-programmable calculators are allowed. More information about allowed calculators can be found at this link.
-
Lectures
Two 1-hour slots and a 2-hour slot are allocated to this module: Tuesday 11:00-12:00 (Bancroft 1.13) and 13:00-14:00 (Bancroft 1.13a), and Friday 14:00--16:00 (Bancroft 1.13). The two hours on Tuesday and the first hour on Friday will be used for teaching, and the second hour on Friday will be used for tutorial.
[NOTE. Week 1 will be slightly different: part of the Tuesday slot will be used as introduction. Both hours on Friday will be used for teaching. Week 2 will also be different: there is no lecture Tuesday 13:00-14:00. Instead there will be a lecture on Thursday 13:00-14:00 at Bancroft, David Sizer LT.]
The lectures and tutorials are going to be in-person. They will be available on Qreview, and I am told they are also streamed live on Qreview. But please don't make live streams your regular mode of attenence.
Zoom is no longer a requirement, so I may not set up Zoom links at all. You are expected to attend lectures in person and only in exceptional situation where you are unable to come to uni to use Qreview.
Lecture notes. The notes for the lectures will be published on the following blog:
https://mth6115cryptography.wordpress.com/
You will be able to make comments and ask questions (and answer each other's questions) in the comments section of the blog. I will also occasionally look at the comments/questions and give you feedback (on the blog or in tutorials). I strongly encourage you to use this feature.
Apart from being more organised, and also the possibility to leave comments/questions/answers below each lecture note, another advantage of using the blog is that topics can be accessed using tags: I will add a tag for each topic covered in lectures. For instance, if you are looking for, say, Affine cipher, you can simply click on the tag with the same name and you will see all the lecture notes in which Affine ciphers have been discussed
The blog is password protected; the password is: 5116HTM. Anyone with the password can access the blog. If you prefer you can ask questions or make comments anonymously (suitable for shy students!).
Prof. Peter Cameron's notes. The module is designed by and is based on Prof. Peter Cameron's notes. You can consult these notes for further details and better understanding of the subject, but this is optional and anything you find there that is not covered in lectures is non-examinable.
Tutorials
The second hour of the Friday lecture will be used as a tutorial (except for Week 1 where it will be used for teaching). As this is a continuation of the Friday lecture, the same Zoom link for the Friday lecture will continue to work for the tutorial.
Ideally, in the tutorial I would like to answer questions you may have about material covered in lectures and/or coursework problems, so I hope the tutorials will be quite interactive. Please do get involved and ask/answer questions. You can also email me your questions, or requests (e.g., if you want me to go over a topic), the day before the lecture.
I may also use the tutorial time to recap/expand on key points from lectures, discuss more examples, and give you exercises to work on during the tutorial. It really depends on what you want me to do. Just tell me. The more engaged you are, the more useful the tutorial time will be for you.
-
There will be optional non-assessed weekly problem sheets which you are encouraged to do, as much as you can. There will be a link to submit your solutions and depending on how many submissions there are and how much time I have I will give you feedback on your work, in person or in tutorials.
-
-
-
-
Overview: This week we will look at the Knapsack Cipher, a cryptosystem based on the Knapsack Problem which is known to be NP-complete.
Lectures
- Lecture 1, 2, Tuesday 12/12. Notes
Summary: Knapsack Problem; this is an NP-complete problem which was used in the very first public-key cryptography scheme after Diffie-Hellman came up with the idea, namely the Knapsack Cipher. The Knapsack Problem is easily solved using the Greedy Algorithm if the given sequence of {ai} is super-increasing. This can be used to implement the Knapsack Cipher. It turns out, however, this implementation of the Knapsack Cipher is vulnerable (eg, by an attack introduced by Shamir). For this reason Knapsack Cipher is not popular these days.
- Lecture 3, Friday 15/12, 14:00--15:00. Notes
Summary: I gave a general summary of what we have learned in this module, highlighting the key concepts. This should hopefully be useful when you revise for the final exam in January.
Tutorial
- Tutorial, Friday 15/12, 15:00--16:00. Notes
Summary: I discussed past exams and went over some questions from the 2019 paper.
Exercises
Non-assessed Exercise Sheet 12. Solutions
Upload your solutions for feedback
Extras
Prof. Cameron's notes. See pages 73-77 (optional).
ASSESSED COURSEWORK: QUIZ 4
-
-
-
-
