Paper Help | The University of Sydney

The University of Sydney

The University of Sydney The University of SydneySchool of Mathematics and Statistics Assignment 2MATH2068/2988: Number Theory and Cryptography Semester 2, 2016 Web Page: http://www.maths.usyd.edu.au/u/UG/IM/MATH2068/Lecturer: Anthony Henderson Like Assignment 1, this assignment is in two parts: a “non-computer part” and a “computer part”. Each part consists of two questions: in the non-computer part, which twoquestions you need to do depends on whether you are enrolled in the mainstream unitMATH2068 or the advanced unit MATH2988; in the computer part, all students do thesame two questions. Each part will be marked out of 10 and is worth 5% of your totalmark, so the assignment as a whole is worth 10% of your total mark.Both parts of the assignment must be submitted through Turnitin on the MATH2068Blackboard page or the MATH2988 Blackboard page, as appropriate. Note that there isa separate Turnitin submission for each part; please make sure you submit the rightfile to the right Turnitin submission. On the Blackboard page, the submission linksappear in the menu on the left as “MATH2068 Assignment 2 Non-Computer Part” and“MATH2068 Assignment 2 Computer Part”, or the equivalent with MATH2988. You donot need to submit the two parts at the same time, but the same deadline applies to bothof them.For the non-computer part, your submission can be either typed or a scan/photo ofhandwritten answers, but it must be submitted as a single file that can be viewed inTurnitin: for example, a single PDF or a Word document, but not a Zip file. Checkthat your file displays correctly in the Turnitin preview window before you submit it.Unviewable or illegible submissions will get a mark of 0. For the computer part,your submission will be a text file which is the record of a MAGMA session (perhapsedited), and should be given the name “asst2-[sid].txt” where “[sid]” is your student ID.As always with Turnitin, a submission is not complete until you see the Digital Receipt, including the submission ID number and time. You should either print this DigitalReceipt or email it to yourself so that you have a copy, for each of the two submissions;in the (unlikely) event of database error, this Digital Receipt is the only acceptable proofof the time of your submissions. It is your responsibility to leave enough time beforethe assignment deadline to complete both Turnitin submissions: if you forget to do aTurnitin submission before the deadline, or fail to complete the submission,you will get 0 for that part of the assignment even if you can prove that youdid it before the deadline. If you discover a problem with a file you have submitted,you can submit a new version before the deadline (which will simply replace your previoussubmission).Except for students who have registered with Disability Services or who apply successfully for Special Consideration or Special Arrangements (see the Information Sheet),the due date for this Assignment is Thursday 20 October, 2016, before 11:59pm. c 2016 The University of SydneyCopyright 1 Non-computer part: Write or type complete answers to the two questions appropriateto the level of unit you are enrolled in, showing all working.1. This question is for students enrolled in the mainstream unit MATH2068only. Do not answer this if you are in the advanced unit MATH2988.(a) Suppose that you are an Elgamal user with public key (83, 2, 45) and privatekey 7. Note that this is consistent, because 27 ? 45 (mod 83). If you receivethe ciphertext h3, [58, 4]i, what is the decrypted message?(b) Find a quadratic polynomial P (x) = ax2 + bx + c, where the coefficientsa, b, c belong to {0, 1, 2, 3, 4}, such that the following all hold:P (1) ? 1 (mod 5),P (2) ? 2 (mod 5),P (3) ? 4 (mod 5).2. This question is for all students.Throughout this question, p denotes an odd prime number, and a, b denote integerssuch that ab ? 1 (mod p). Note that we must have gcd(a, p) = gcd(b, p) = 1.As seen in lectures, when working modulo p, instead of the standard reducedsystem {1, 2, · · · , p ? 1}, it is often more convenient to use the reduced systemM ? N where M = {1, 2, · · · , p?1} and N = {?1, ?2, · · · , ? p?1}. Note that if22x ? M then ?x ? N, and if x ? N then ?x ? M.Define a function f : M ? N ? M ? N by setting f (x) to be the unique elementof M ? N which satisfies f (x) ? ax (mod p), and similarly define a functiong : M ? N ? M ? N by setting g(x) to be the unique element of M ? N whichsatisfies g(x) ? bx (mod p). Notice that f (?x) = ?f (x) and g(?x) = ?g(x) forall x ? M ? N.(a) Show that the functions f and g are inverse to each other: that is, for anyx ? M ? N we have f (g(x)) = x and g(f (x)) = x.(b) Let k be the number of negative integers in the set {f (x) | x ? M}. ShowthatY!.f (x) = (?1)k p?12x?M (c) Deduce that a p?12 ? (?1)k (mod p). 2 3. This question is for students enrolled in the advanced unit MATH2988only. Do not answer this if you are in the mainstream unit MATH2068.Throughout this question, k ? 3 is an integer. Note that ?(2k ) = 2k?1 , so everyodd integer a satisfies ord2k (a) | 2k?1. It was shown in Tutorial 8 that there is noprimitive root modulo 2k , i.e. no odd integer a such that ord2k (a) = 2k?1 .(a) Show by induction that for all positive integers ?, the highest power of 2?dividing 32 ? 1 is 2?+2.(b) Hence show that ord2k (3) = 2k?2.(c) It follows from the previous part that exactly a quarter of the elementsn ? {0, 1, 2, · · · , 2k ? 1} have the property that n ? 3x (mod 2k ) for somex ? N. Since we have 3x ? 1 (mod 8) when x is even and 3x ? 3 (mod 8)when x is odd, it must be precisely those elements n ? {0, 1, 2, · · · , 2k ? 1}satisfying either n ? 1 (mod 8) or n ? 3 (mod 8) which have this property.Describe a polynomial-time algorithm which, given k ? 3 and an arbitraryn ? {0, 1, 2, · · · , 2k ? 1} satisfying either n ? 1 (mod 8) or n ? 3 (mod 8),determines a nonnegative integer x such that 3x ? n (mod 2k ).Here, to say that the algorithm is polynomial-time means that there is somepositive integer a such that the maximum number of bit operations requiredwhen the algorithm is applied to an input k and n as above is O(k a ). (Forexample, an algorithm that, regardless of the input n, computes the residueof 3x modulo 2k for every x up to 2k?2 is not a polynomial-time algorithm,because 2k?2 is not O(k a ) for any positive integer a.) You should explainwhy the algorithm you describe works, i.e. why the nonnegative integer xthat it returns does always satisfy 3x ? n (mod 2k ), but you do not haveto formally prove that it is polynomial-time or write specific code for it.(However, if you are able to write MAGMA code for the algorithm, you couldof course then test actual large numbers to see whether it works and whetherthe growth rate of the time appears to be as expected.) Computer part: This is to be done using MAGMA, either in the computer labs (thelab session in Week 12 has been set aside for this purpose) or on your own computer ifyou 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 file2016asst2definitions.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 getMAGMA to generate this automatically and give it the right name, you can make your firstcommand SetLogFile("asst2-[sid].txt"); where [sid] is replaced by your studentID. You could answer the two questions in different MAGMA sessions, but in that case youwould have to concatenate the log files (e.g. using a text editor) so that you have a singletext file to submit to Turnitin. In case of problems with the SetLogFile command, youcan alternatively create the text file yourself by copying and pasting from your MAGMAsession into a text editor.As well as the MAGMA commands, you may wish to add comments such as Question4” 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 Turnitinsubmission there too, but in any case please email yourself a copy of your log file(s).3 4. In MAGMA define p to be the smallest prime which is greater than or equal toyour student ID and is also congruent to 1 modulo 4. Ask MAGMA to choose aprimitive root b modulo p with the command b:=PrimitiveRoot(p);. Then useappropriate MAGMA commands to find a nonnegative integer less than p which isa square root of ?1 modulo p. There are two such integers; you can stop once youhave found one of them, except that you should then get MAGMA to check thatyour answer does square to something congruent to ?1 modulo p.5. Load the file 2016asst2definitions.txt. It defines an RSA public key (n,e) and aciphertext ct which has been encrypted using this public key; ct is a sequence ofresidues modulo n, which happens to consist of just a single residue. (To avoidantagonizing Turnitin, it is best not to print n, e or ct in your MAGMA session. Ifyou want to see them, look in the file 2016asst2definitions.txt.)Before encryption, the original message (four words in ordinary Roman letters)was encoded as a residue modulo n using the NaiveEncoding function in the fileMagmaProcedures.txt. Your task is to find this original message by decryptingct as in Computer Tutorial 6, for which you will first need to find the decryptionexponent d, the inverse of e modulo ?(n).The problem is that n has 1250 decimal digits, which is far too large to use theMAGMA commands Factorization(n); or EulerPhi(n); (don’t bother tryingthem; MAGMA will just hang or run out of time). This RSA cryptosystem wouldbe unbreakable, except that someone has let slip the information that the twoprimes of which n is the product are a Germain prime x and its corresponding safeprime 2x + 1. Knowing this, you can find x as the unique positive solution of thequadratic equation 2×2 + x ? n = 0. To apply the quadratic formula, you will needto find the square root of the discriminant D as an exact integer: Q4 of Computer