COMP6300程序写作、辅导Java编程程序

” COMP6300程序写作、辅导Java编程程序COMP2300/COMP6300 Applied CryptographyAssignment 2Total marks: 30Weighting: 15%Deadline: Sunday (End of Week 12), 31 May 2020 (11:59 pm).Note: Submit the assignment via Turnitin (Include Student Name and ID in assignment).ObjectivesThis assignment has been designed to test your knowledge of number theory, abstract algebra, and public-keycryptography.Notes Assumptions (if any) must be stated clearly in your answers. There may not be one right answer for some of the questions. So, your explanations need to presentyour case clearly. The explanations you provide do not have to be long; conciseness is preferred tomeandering. It is recommended that you use Pari/GP for the numerical components of the assignment. However, youare free to use another programming language (such as Java) provided the question/answer/solutioncan be naturally translated into a similar problem in that programming language.1 The hints to solutions of almost all questions in this assignment are in the textbook [Sma16].Submission On line submission via Turnitin.Assignments will be marked and returned online. There are no hardcopy submissions for written assignments.Ensure you submit the correct file. The submission process shows you a complete preview of your entireassignment after you have uploaded it but before you have submitted it. Carefully check through everysingle page to ensure everything is there and the correct version has been uploaded.Multiple submissions may be possible via Turnitin prior to the final due date and time of an assessment taskand originality reports may be made available to students to view and check their levels of similarity prior tomaking a final submission. Students are encouraged to use these reports to ensure that they do not breachthe Academic Honesty Policy through high levels of similarity (plagiarism).Teaching staff will use the report to judge whether plagiarism has occurred and whether penalties shouldapply for breaches of the Academic Honesty Policy. Any similar text identified by Turnitin will be consideredcarefully to see if it is indeed a breach of the Academic Honesty Policy.2Question 1 (10 marks)This question tests your knowledge of what constitutes a group. Let n be a composite number. Let X ={1, 2, . . . , n 1}.(a) Let x X. Show that if there are integers a, b such that ax + bn = 1, then gcd(x, n) = 1. (2 marks)(b) Let x X. Show that if gcd(x, n) 6= 1 then ax 1 (mod n) has no solution for any integer a. (2marks)(c) Show that there is at least one element x X, such that gcd(x, n) 6= 1. (2 marks)(d) Let be multiplication modulo n. That is, for x, y X, x y = xy (mod n). Prove that (X, ) is not agroup. (2 marks)(e) Let n = 13424. Let a = 13314 and let b = 5889. What are the multiplicative inverses of a and b modulon? Show how you obtained the result. (2 marks)Question 2 (5 marks)Recall that a Carmichael number n is any composite number which satisfies Fermats little theorem, i.e.,COMP6300作业写作、辅导Java编程语言作业、写作Java实验作业、辅导data作业n1 1 (mod n),for every a such that gcd(a, n) = 1. Such a number is also called a pseudoprime. Write a PARI/GP scriptthat finds and prints all Carmichael numbers less than or equal to 10,000. (Hint: You may use the isprime()command in PARI/GP). (5 marks)Question 3 (5 marks)The discrete logarithm problem (DLP) is not always hard. In particular, we cannot simply choose any groupG with an operation (addition or multiplication; appropriately defined), and assume that DLP is hard inthat group. The following questions highlight this.(a) Show that the discrete logarithm problem (DLP) is easy on the group of integers modulo a prime n underaddition, i.e., the group (Zn, +). More precisely, given g, h Zn, find an x such that x g h (mod n). (3marks)(b) Let n = 1, 200, g = 23 and h = 25. Find x such that x g h (mod n). (Hint: You may use thegcdext() command in PARI/GP). (2 marks)Question 4 (6 marks)An encryption system is considered malleable if given a ciphertext of some unknown plaintext, it is possibleto obtain a valid ciphertext of a related plaintext without even knowing the contents of the plaintext.This is problematic depending on the application. For instance, in bidding for a contract, a companymight outbid its competitor by simply multiplying its rival companys encrypted bid by 0.9, without evenknowing the bid [DDN03]. The following questions relate to the malleability of versions of RSA and Elgamalcryptosystems taught in the lectures.3(a) Given the ciphertext c of an unknown message m encrypted using RSA with public key (e, N), showhow can you obtain a valid encryption of 2m under (e, N) without knowing m? (2 marks)(b) Given the following ciphertext c of some message m encrypted using RSA (parameters below), show thesteps to obtain the ciphertext c0 of 2m using PARI/GP.c = 2753530075851447763243109653595159359042630876252568885N = 3611071334998558413568664531648678147429348805583447333e = 3521903392012306527486431544128257140903969440488848271(2 marks)(c) Consider now the randomized Elgamal cryptosystem. We are given the ciphertext (r, c) of some unknownmessage m computed as r = gkfor some random integer k, and c = m hk, where h is the public key. Canwe obtain the ciphertext of the message 2m? (2 marks)Question 5 (4 marks)Let S be a set of size n, and let f be a random one-to-one map from S to itself. Starting with a randomelement x0 S, define:xi+1 = f(xi), for i 0.This creates the sequence x0, x1, x2, x3, . . .. The birthday paradox tells us that if we keep track of thesevalues, we will find a pair such thatxi = xj ,with i 6= j after O(n) evaluations of f. After this the sequence repeats itself, i.e., creates a cycle. Let t bethe smallest i for which we can find some j such that the above is true. Then, the sequence x0, x1, . . . , xt1forms a tail of length t, and for all i t, we have xi = xi+T , where T is the length of the cycle. InFigure 1, the tail is of length t = 4 and the length of the cycle is T = 11. Furthermore, for all i t, we seethat xi = xi+T . Thus, if xi = xj , then j = i + T.(a) In Pollards rho algorithm, we try to find an m such that xm = x2m. Show that if the sequence is cyclic,i.e., xi = xj for some i t and j 6= i, then there must exist an i, call it m, such that xm = x2m. (2 marks)(b) Why does Pollards rho algorithm, which seeks to find an m such that xm = x2m, only require constantspace? (2 marks)如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“