School of Computing: assessment brief
Module title Cryptography
Module code COMP3223
Assignment title Coursework 2
Assignment type
and description
Coursework assignment
Learning the mathematical basis of asymmetric cryp-
Weighting 20% of total mark
Submission dead-
March 31st 2023 at 16:00
Submission
Turnitin submission through Minerva
Feedback provision Feedback provided on Minerva
Learning outcomes
(i) Understand and apply in practice the fundamen-
tal principles of cryptography and information security.
(ii) Analyse and evaluate the strengths and weaknesses
of cryptosystems. (iii) Apply mathematical analysis
to understand how asymmetric cryptosystems are con-
Module lead Dr Toni Lassila
1. Assignment guidance
Provide answers to the three exercises below. Answer all three exer-
2. Assessment tasks
Exercise 1: Answer the following questions on group theory.
(a) Consider the multiplicative group G = (Z∗26, ·). Show that the
inverse of any element g ∈ G can be found as g−1 ≡ g11 mod 26.
(b) Consider the multiplicative group G = (Z∗119, ·).
i. Is G cyclic? Justify your answer. [1 mark]
ii. Find the solution x ∈ G of the equation
11x ≡ 3 mod 119
using extended Euclid’s algorithm. [4 marks]
Exercise 2: The following exercises are on primality testing.
(a) Is n = 721 a (Fermat) pseudo-prime in base a = 46? Explain how
to test a number for pseudo-primality. [2 marks]
(b) Use the Miller-Rabin Primality Test to test whether n = 721 is a
strong pseudo-prime in the base a = 46. [3 marks]
(c) Is n = 721 prime? How can we use the Miller-Rabin test to find
this out given the result of b)? [2 marks]
Exercise 3: Alice and Bob use the RSA cryptosystem for encrypted
communications.
(a) Show that the multiplicative property holds for RSA, i.e., show
that the product of two ciphertexts y1,y2 is equal to the encryption
of the product of the two respective plaintexts x1,x2:
y1y2 mod n = RSAe(x1x2).
(b) Bob receives an encrypted message y1 from Alice using the RSA
keys (d, e) and the exponent n. Eve obtains y1 by eavesdropping
and is able to encrypt some other plaintext x into a ciphertext y
using the public key e and the exponent n. She then sends Bob
a new ciphertext y2 = yy1 mod n. Bob doesn’t suspect anything
and decrypts it to find that corresponding plaintext x2 doesn’t
make any sense and discards it. Eve is then able to obtain x2 too.
Describe a chosen-ciphertext attack against RSA in this setting
that allows Eve to obtain the original plaintext x1 from the infor-
mation known to her. Which condition should x satisfy for this
attack to work? [3 marks]
3. General guidance and study support
The MS Teams group for COMP3223 Cryptography will be used for
general support for this assignment. If your question would reveal parts
of the answer to any problem, please send instead a private message to
the module leader on MS Teams.
4. Assessment criteria and marking process
Assessment marks and feedback will be available on Minerva within
three weeks of the submission deadline. Late submissions are allowed,
standard late penalties apply.
5. Presentation and referencing
When writing mathematical formulas, use similar notation and sym-
bols as during the lectures and tutorials. Hand-written sections for
mathematical notation are acceptable but need to be clearly readable.
You may assume theorems and other results that have been presented
during lectures and tutorials as known. Any other theorems need to be
cited using standard citation practice.
6. Submission requirements
Submit your answers through Turnitin as one PDF document (gener-
ated either in Word or with LaTeX). You may use hand-written and
scanned pages for mathematical formulas, but these need to be clearly
legible and the document must contain at least some typeset text or
Turnitin will reject in. All submissions will be checked for academic
integrity.
7. Academic misconduct and plagiarism
Academic integrity means engaging in good academic practice. This
involves essential academic skills, such as keeping track of where you
find ideas and information and referencing these accurately in your
By submitting this assignment you are confirming that the work is a
true expression of your own work and ideas and that you have given
credit to others where their work has contributed to yours.
8. Assessment/marking criteria grid
Total number of marks is 20, divided as follows:
Exercise 1 (multiplicative groups): 8 marks
Exercise 2 (primality testing): 7 marks
Exercise 3 (RSA cryptosystem): 5 marks