MATH10001 Cryptography Project

You should write your report in LATEX and submit both the PDF file and the LATEX source file (the file with .tex extension). Include your MATLAB code in your report, do not submit it in separate files. If you use a word processor such as Microsoft Word or LibreOffice, you can submit your work as a .doc, .docx, .odt or .pdf file (still a single file containing all your MATLAB code) and it will be marked but you will not get any marks for LATEX and presentation. Your report must be suitable for automated plagiarism checking.

The calculations must be done in MATLAB (use MATLAB R2020b or any other 2020 or 2021 version of MATLAB or MATLAB Online).  Include your MATLAB code and the output in your report as text, not as images. Your code should be self-contained, it should not require any input from the user. Aim to do the calculations efficiently, your code should not produce large amounts of unnecessary output and you should explain what your code does in comments included in the code or in the text of your report. Put MATLAB code and output between “begin–verbatim˝ and “end–verbatim˝ or use the listings package.  Long lines in verbatim text should be split so that they fit on the page. Short MATLAB expressions can be included between “verb@ and @ in the text. The congruence a ⌘ b mod n can be typeset as $a“equiv b  “bmod n$.

You should answer the questions in the text of your report, merely including the MATLAB output verbatim is not sufficient, and you should include explanations and interpretations of the results, where appropriate.

There are 30 marks available for this project:

• 20 marks for the mathematical content (correct calculations and explanations),

• 5 marks for group work (1/4 of the average content mark for your group, excluding those who did not attend the labs, failed to submit the project or whose work does not appear to be a serious attempt) and

• 5 marks for the quality of LATEX and presentation.

Questions 1–2 are the same for everybody in a group, in question 3 you will have to calculate your own primes. You should work together on the methods to carry out the calculations, implementing them in MATLAB and on interpreting the results, but you must write your own MATLAB code and carry out the calculations yourself, you must not copy them from someone else or let someone else copy yours, and your report must be your own work.  See alsohttp://documents.manchester.ac.uk/display.aspx? DocID=2870.

The project, including writing up should not take more than 10 hours (including the time spent in class).

If you have any questions, e-mail [email protected].

Question 1.  [4 marks in total] Find the numbers p , a and v for your group in the file Table1.pdf.  You are Alice in the Diffie-Hellman key exchange.  p is your prime.  You agreed with Bob that you will use as g the smallest primitive root modulo p which is greater than or equal to 20. a is your random number and v is the number sent to you by Bob.

(a) Find g, the smallest primitive root modulo p which is greater than or equal to 20. (b) Calculate the number u you send to Bob and the shared key k .

Question 2.   [9 marks in total] A digital signature scheme uses q = 89, p = 5519, g = 2835 and y = 4716.  H is group number.  For r = 0, 1,...,q − 1, let σ(r) be the number of integers s, 1  s  q − 1, such that (r,s) is a valid signature for H .             (a) Calculate σ(r) for every r, 0  r  q − 1, and hence find the total number of pairs (r,s) (0  r  q − 1, 1  s  q − 1) such that (r,s) is a valid signature for H.  Print out σ(0), σ(1),...,σ(5) and the total number of valid signatures (r,s) for H .               (b) What do you observe about the behaviour of σ(r)? On the basis of the total number of valid signatures calculated in (a), try to make a conjecture valid for any q , p , g and y about the probability that a randomly chosen pair (r,s) is a valid signature for a given H . (Use appropriate loops to check every pair (r,s).   Try to make your code efficient. Efficient code can do the calculation in (a) in about 1 second, less efficient code may take a couple of minutes.  For example, the verification of a signature involves solving the congruence su1  ⌘ H (mod q) and calculating the remainder ofgu1   on division by q . You should try to write your code so that you only do this calculation once for each s and reuse the results when needed.  In this question you should not use symbolic numbers, as they are not needed and the calculations with them are much slower.)

Question 3.   [7 marks in total]  Find your student number,  it is an 8 digit number beginning with 1, it will be denoted by S in this question. Make sure that you have the correct number before continuing.

(a) Find the smallest prime p such that p >  14S4  and exactly one of 2 and 3 is a primitive root modulo p.  Find the largest prime q such that q < 12S5  and its last 3 digits are equal.  p and q will be your personal primes for RSA. Your public key will be e = 65537. Calculate the corresponding private key d .

(You have to use symbolic numbers and you will probably need to use some of the MATLAB functions and, or, xor and not to find p and q. It should take at most a few seconds to calculate p, q may take longer, but not more than a minute or two.  If your code takes much longer, then check it to make sure it that it does not go into an infinite loop.  You should try your program on smaller numbers first to ensure that it works.)     (b) Find the two encrypted messages corresponding to your student number in the file Table3.pdf and decrypt them with your private key.  Divide the decrypted messages into 2 digit blocks from the right, 00 denotes a space, convert the other 2 digit blocks to letters by using the table below and then join the messages.  (You can do this by hand, you do not have to write a MATLAB program to do it.) What text do you get?