首页 » 密码学代写 » 密码学代写 | COMP2300/COMP6300 Applied Cryptography

密码学代写 | COMP2300/COMP6300 Applied Cryptography

这个作业是测试对数论,抽象代数和公钥的知识密码学的掌握
COMP2300/COMP6300 Applied Cryptography
Assignment 2
Total marks: 30
Weighting: 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).
Objectives
This assignment has been designed to test your knowledge of number theory, abstract algebra, and public-key
cryptography.
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 present
your case clearly. The explanations you provide do not have to be long; conciseness is preferred to
meandering.
• It is recommended that you use Pari/GP for the numerical components of the assignment. However, you
are free to use another programming language (such as Java) provided the question/answer/solution
can 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 entire
assignment after you have uploaded it but before you have submitted it. Carefully check through every
single 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 task
and originality reports may be made available to students to view and check their levels of similarity prior to
making a final submission. Students are encouraged to use these reports to ensure that they do not breach
the Academic Honesty Policy through high levels of similarity (plagiarism).
Teaching staff will use the report to judge whether plagiarism has occurred and whether penalties should
apply for breaches of the Academic Honesty Policy. Any similar text identified by Turnitin will be considered
carefully to see if it is indeed a breach of the Academic Honesty Policy.
2
Question 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. (2
marks)
(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 a
group. (2 marks)
(e) Let n = 13424. Let a = 13314 and let b = 5889. What are the multiplicative inverses of a and b modulo
n? Show how you obtained the result. (2 marks)
Question 2 (5 marks)
Recall that a Carmichael number n is any composite number which satisfies Fermat’s little theorem, i.e.,
a
n−1 ≡ 1 (mod n),
for every a such that gcd(a, n) = 1. Such a number is also called a pseudoprime. Write a PARI/GP script
that 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 group
G with an operation (addition or multiplication; appropriately defined), and assume that DLP is hard in
that 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 under
addition, i.e., the group (Zn, +). More precisely, given g, h ∈ Zn, find an x such that x · g ≡ h (mod n). (3
marks)
(b) Let n = 1, 200, g = 23 and h = 25. Find x such that x · g ≡ h (mod n). (Hint: You may use the
gcdext() 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 possible
to 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 company
might outbid its competitor by simply multiplying it’s rival company’s encrypted bid by 0.9, without even
knowing the bid [DDN03]. The following questions relate to the malleability of versions of RSA and Elgamal
cryptosystems taught in the lectures.
3
(a) Given the ciphertext c of an unknown message m encrypted using RSA with public key (e, N), show
how 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 the
steps to obtain the ciphertext c
0 of 2m using PARI/GP.
c = 2753530075851447763243109653595159359042630876252568885
N = 3611071334998558413568664531648678147429348805583447333
e = 3521903392012306527486431544128257140903969440488848271
(2 marks)
(c) Consider now the randomized Elgamal cryptosystem. We are given the ciphertext (r, c) of some unknown
message m computed as r = g
k
for some random integer k, and c = m × h
k
, where h is the public key. Can
we 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 random
element 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 these
values, we will find a pair such that
xi = xj ,
with i 6= j after O(

n) evaluations of f. After this the sequence repeats itself, i.e., creates a cycle. Let t be
the smallest i for which we can find some j such that the above is true. Then, the sequence x0, x1, . . . , xt−1
forms a “tail” of length t, and for all i ≥ t, we have xi = xi+T , where T is the length of the cycle. In
Figure 1, the tail is of length t = 4 and the length of the cycle is T = 11. Furthermore, for all i ≥ t, we see
that xi = xi+T . Thus, if xi = xj , then j = i + T.
(a) In Pollard’s 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 Pollard’s rho algorithm, which seeks to find an m such that xm = x2m, only require constant
space? (2 marks)
References
[DDN03] Danny Dolev, Cynthia Dwork, and Moni Naor. Nonmalleable cryptography. SIAM review,
45(4):727–784, 2003.
[Sma16] Nigel P Smart. Cryptography made simple, volume 481. Springer, 2016.
4
x8
x9
x10
x11
x12
x13
x14
x4
x5
x6
x7
x3
x2
x1
x0
Figure 1: Pollard’s rho.
5


程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论

您的电子邮箱地址不会被公开。