关键词 > MATH2088/2988
MATH2088/2988: Number Theory and Cryptography Semester 2, 2022 Assignment 2
发布时间：2022-10-17
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Assignment 2
MATH2088/2988: Number Theory and Cryptography
Semester 2, 2022
1. This question is for students enrolled in the mainstream unit MATH2088 only. Do not answer this if you are in the advanced unit MATH2988.
(a) Suppose you are an RSA user with public key (5251, 1021) and private key 5.
If you receive a ciphertext [5182, 308, 239], what is the decrypted message? (b) (i) Verify if 3 is a primitive root modulo 67.
(ii) Find the order of 3 − 1 (mod 67).
2. This question is for all students.
(a) Find an integer x e {0, . . . , 192} which solves the equation
x77 三 7 (mod 193).
(b) You are given
, 2
τ1 (k) = ． 3
( 5
if k 三 0 (mod 3) if k 三 1 (mod 3) , if k 三 2 (mod 3)
, 7
τ2 (k) = ． 4
( 3
if k 三 0 (mod 3)
if k 三 1 (mod 3) ,
if k 三 2 (mod 3)
f (k) = τ1 (k) . kk and g(k) = τ2 (k) . 2(k2 ) . Verify, which one of the two statements is true:
● f (k) is O(g(k)) or
● g(k) is O(f (k)).
Justify your answer. [hint: you may use the properties of powers and loga- rithms from high school without justification]
3. This question is for students enrolled in the advanced unit MATH2988 only. Do not answer this if you are in the mainstream unit MATH2088.
(a) You are given that a is a primitive root modulo 89. How many solutions
modulo 89 does the following congruence have:
x6 三 a (mod 89)?
(b) You are given that the order of a modulo a prime number p is 5 and the
order of b modulo p is 7. Find the order of ab modulo p.
(c) Bob uses an RSA cryptosystem with the open key
n = 67984834185905321924048762997660922783819131148076624988012674337594370268801455146689928232342821667
and e = 9617744363. His ciphertext appears to be [1, n - 1]. What was the plaintext?
Computer part: This is to be done using MAGMA, either in the computer labs (the lab session in Week 11 has been set aside for this purpose) or on your own computer if you have successfully installed MAGMA there (see the instructions on the unit web page). If you are completing Q5 outside the computer labs, you will need to download the file asst2definitions.txt from the Resources Table on the web page.
What you need to submit is a “log file” or record of your MAGMA session; to get MAGMA to generate this automatically and give it the right name, you can make your first command SetLogFile("asst2- [sid] .txt"); where [sid] is replaced by your student ID. You could answer the two questions in different MAGMA sessions, but in that case you would have to concatenate the log files (e.g. using a text editor) so that you have a single text file to submit to Turnitin. In case of problems with the SetLogFile command, you can alternatively create the text file yourself by copying and pasting from your MAGMA session into a text editor.
As well as the MAGMA commands, you may wish to add comments such as “Question 4” or “This is my answer”: you can start and end comments by typing /* and */.
If you complete the assignment in the labs, you could (probably) do the Turnitin submission there too, but in any case please email yourself a copy of your log file(s).
4. In MAGMA define p to be the smallest prime which is greater than or equal to your student ID and is also congruent to 1 modulo 4. Ask MAGMA to choose a primitive root b modulo p with the command b:=PrimitiveRoot(p);. Then use appropriate MAGMA commands to find a nonnegative integer less than p which is a square root of -1 modulo p. There are two such integers; you can stop once you have found one of them, except that you should then get MAGMA to check that your answer does square to something congruent to -1 modulo p.
5. Load the file asst2definitions.txt. It defines an RSA public key (n,e) and a cipher- text ct which has been encrypted using this public key; ct is a sequence of residues modulo n, which happens to consist of just a single residue.
Before encryption, the original message (four words in ordinary Roman letters) was encoded as a residue modulo n using the NaiveEncoding function in the file MagmaProcedures.txt. Your task is to find this original message by decrypting ct as in Computer Tutorial 6, for which you will first need to find the decryption exponent d, the inverse of e modulo ϕ(n).
The problem is that n has 1250 decimal digits, which is far too large to use the MAGMA commands Factorization(n); or EulerPhi(n); (don’t bother trying them; MAGMA will just hang or run out of time). This RSA cryptosystem would be unbreakable, except that someone has let slip the information that the two primes of which n is the product are a Germain prime x and its corresponding safe prime 2x + 1. Knowing this, you can find x as the unique positive solution of the quadratic equation 2x2 + x - n = 0. To apply the quadratic formula, you will need to find the square root of the discriminant D as an exact integer: Q4 of Computer Tutorial 8 explains how to do this.
