COMP41280: Second Assignment
• Upload a single PDF file with your answers through Brightspace.
• Only one submission attempt is allowed, so please double-check your assignment before
submitting.
• Your answers must be typed and the PDF must be searchable; no handwritten scanned
materials are allowed.
• Do not submit any programs that you may have created to complete the assignment.
• Your submission is individual work; by submitting your assignment you acknowledge
that you have read and understood the plagiarism policies discussed in the course intro-
duction.
• Indicative submission length: around four pages, please.
Exercise 1: Number Theory
1. Consider the problem of finding two integers x and y such that 2731y + 327x = 1. Does
this problem have a solution? If so, give the steps and all intermediate results of your
computation explicitly (preferably in a table). If not, explain why. [10 marks]
2. Solve 327z ≡ 1 (mod 2731). Your answer z must belong to the standard complete residue
system Z2731. [5 marks]
3. Evaluate 3272729 (mod 2731). Can you obtain this result by direct exponentiation? If not,
carry out the exponentiation efficiently in less than 25 steps, giving all your intermediate
results. [10 marks]
4. Is your result in 3. congruent with your result in 2.? Why or why not? [5 marks]
Exercise 2: Diffie-Hellman
1. Find the set G ⊂ Z101 of all elements g ∈ Z∗101 that would allow you to implement
Diffie-Hellman with p = 101 and maximum security. What would happen if g /∈ G? [5
marks]
2. Assume that Mallet intercepts X = 25 and Y = 36 (i.e. the two values interchanged by
Alice and Bob in the Diffie-Hellman algorithm) and that p = 101. Propose an algorithm
for Mallet to compute the discrete logarithm of these values and thus recover the secret
exponents. Give the discrete logarithms of X and Y for the two biggest values of g in 1. [5
marks]
© UCD 2023 Page 1 of 2
Exercise 3: RSA
1. In a 36-bit RSA system, the public key of a given user is e = 31 and the modulus is
n = 57759671419. Assume that you are Mallet and you wish to attack this system.
• Factor n into p and q using the three methods discussed in the class, and discuss
the number of steps needed (give the parameters that you used, if required by the
algorithm). [10 marks]
• If possible, find the private key d for the two possible choices of t. If not possible,
discuss why not. [10 marks]
2. Discuss whether the following assertions are true or false:
• e = 2 cannot be used in RSA as encryption key, neither using the totient function
nor the Carmichael function. [5 marks]
• We discussed in the lectures that RSA encryption keys are many times of the form
e = 2m + 1. Are exponents of the form e = 2m − 1 equally advantageous? [5 marks]
• If you have two different sets of encryption and decryption keys (e1, d1) and (e2, d2),
can the cascade of encryption using e1 with encryption using e2 increase security in
RSA? [5 marks]
Exercise 4: Birthday attack
Write a program to estimate empirically the probability of collision of at least two 16-bit hashes
in a group of N , where N = 2t and t = 2, 3, . . . , 16.
Notes:
• The N 16-bit hashes can be simulated by generating N 16-bit numbers uniformly at
random; you can use any pseudorandom number generator to accomplish this.
• Empirical probabilities are just empirical frequencies from your experiments (i.e. the
number of times that you obtained at least one collision in N hashes, divided by the total
number of times you have done the experiment)
Plot your empirical results versus the analytical formula for γ given in the lectures. Do they
match? Does N = 216 guarantee a collision with probability 1? Discuss in some detail both
the approach followed in your experiments and your results. [25 marks]
© UCD 2023 Page 2 of 2