Topic outline

  • General

    • View 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.
  • Week 1 : 25 Sep 2023 - 1 Oct 2023

    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, BolognaSuba 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.

    Quick way to do affine maps

    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)

  • Week 2 : 2 Oct 2023 - 8 Oct 2023

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

  • Week 3: 9 Oct 2023 - 15 Oct 2023

    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 3Solutions

    Upload your solutions for feedback

    Extras

    Prof. Cameron's notes. See pages 34-48 (optional).

    Sample quiz hints.

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

  • Module Description

    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.

  • Week 4: 16 Oct 2023 - 22 Oct 2023

    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 4Solutions 

    Upload your solutions for feedback

    Extras

    Prof. Cameron's notes. See pages 43-51 (optional).

  • Week 5: 23 Oct 2023 - 29 Oct 2023

    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 5Solutions

    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.

  • Week 6: 30 Oct 2023 - 5 Nov 2023

    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 6Solutions

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

  • Week 7: Reading Week, 6 Nov 2023 - 12 Nov 2023

  • Week 8: 13 Nov 2023 - 19 Nov 2023

    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. NotesAdditional 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 8Solutions

    Upload your solutions for feedback

    Extras

    Prof. Cameron's notes. See pages 23-26 and 83-87 (optional).

  • Week 9: 20 Nov 2023 - 26 Nov 2023

    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 9Solutions

    Upload your solutions for feedback

    Extras

    Prof. Cameron's notes. See pages 87-93 (optional).

    ASSESSED COURSEWORK: QUIZ 3

  • Week 10: 27 Nov 2023 - 3 Dec 2023

    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 10Solutions

    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

  • Week 11: 4 Dec 2023 - 10 Dec 2023

    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 11Solutions

    Upload your solutions for feedback

    Extras

    Prof. Cameron's notes. See pages 100-106, and page 113 (optional).

  • Syllabus

    • Module Syllabus, roughly in the order of appearance (numbers do not refer to weeks)


      1. Classical (symmetric key) cryptography

      General setup, substitution and transposition ciphers,  frequency analysis, Caesar shift and affine cipher. (Also, modular arithmetic).

      2. Stream ciphers

      Vigenère cipher and Kasiski's method, general stream ciphers, one-time pads, Shannon's theorem.

      3. Randomness

      Shift registers and primitive shift registers, pseudo-noise sequences (Golomb's postulates).

      4. Public-key cryptography

      Diffie-Hellman's idea, complexity vs information theory, complexity classes of problems, one-way functions, signatures.

      5. Review of modular arithmetic

      Fermat's and Euler's theorems, order, primitive roots, Euler's and Carmichael's functions.

      6. RSA cryptosystem

      RSA, fast power calculation, prime factorisation, Miller-Rabin primality test, Pollard's (p-1)-method.

      7. Diffie-Hellman key exchange and Diffie Hellman key establishment

      8. El-Gamal

      El-Gamal, signatures, finding primitive roots, Sophie Germain pairs.

      9. Knapsack

      Knapsack cipher, Greedy algorithm.



  • Module aims and learning outcomes

    • Academic content

      This module covers:

      • An introduction to standard methods in cryptography, including classical and public-key cryptography.
      • Basic ideas in complexity theory and their application to cryptography.


      Disciplinary skills

      At the end of this module, students should be able to:

      • Describe basic concepts of cryptography and steganography; define plaintext, ciphertext and key.
      • Describe substitution and other traditional ciphers and perform encryption/decryption with them.
      • Describe stream ciphers including the Vigenère cipher, one-time pad and shift registers, explain their advantages and disadvantages, and perform encryption/decryption with them for simple situations.
      • Construct the associated polynomial for a shift register and use it to determine if the shift register is primitive.
      • Explain simple concepts associated with security of ciphers, including statistical attack methods; calculate the number of possible keys for simple substitution and stream ciphers.
      • Define Euler’s function and Carmichael’s function; calculate them for small integers.
      • Define a Latin square and perform actions on it such as finding the transpose or adjugate.
      • State and prove Shannon’s Theorem (for one-time pads).
      • Describe the basic principles of public-key cryptography including complexity issues and knapsack, RSA and El-Gamal ciphers.
      • Describe the basic principles of digital signatures and authentication; secret sharing.


      Attributes

      At the end of this module, students should have developed with respect to the following attributes:

      • Acquire and apply knowledge in a rigorous way.
      • Adapt their understanding to new and unfamiliar settings.
      • Explain and argue clearly and concisely.
      • Apply their analytical skills to investigate unfamiliar problems.
      • Work individually and in collaboration with others.
      • Initiative and resilience in meeting challenges.

  • Assessment

    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, Tutorials, Notes

     

    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.

  • Non-assessed coursework

    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.

  • hints and tips

  • where to get help

  • exam papers

  • Week 12: 11 Dec 2023 - 17 Dec 2023

    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 12Solutions

    Upload your solutions for feedback

    Extras

    Prof. Cameron's notes. See pages 73-77 (optional).

    ASSESSED COURSEWORK: QUIZ 4

  • Non-assessed exercise sheet solutions portal

  • Q-Review

  • Assessment information

    • Assessment Pattern:  final exam 80%, four assessed courseworks 5% each

      Format and dates for the in-term assessments: QMplus quizzes on Weeks 3, 6, 9, and 12

      Format of final assessment: on-campus written exam, designed for 2 hours (but you will be given 3 hours to complete it). 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.

      Link to past papers

      It is school's policy that past exam solutions will not be made available, but I have included three below. The 2023 solutions also include a marking scheme so you get a rough idea how partial marks are allocated. Only look at the solutions after you have attempted the questions and only to assess your own work; the solutions are not meant for revision and don't replace the lecture notes.

      2012 exam solutions

      2014 exam,  solutions 

      2023 examsolutions

  • Reading List Online

  • Q-Review