CM50210
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM50210: CRYPTOGRAPHY
Assessment Available from: 09:30, 23/08/2021
Latest Submission Time: 09:30 24/08/2021
All timings are given in British Summer Time (BST)
Please read the Guidance for Students
(https://www.bath.ac.uk/topics/exams-and-assessments) before attempting this exam.
The Guidance contains information about submitting your exam attempt and choosing to
defer.
This assessment is designed to take approximately 2 hours to complete.
Full marks will be given for correct answers to ALL FOUR questions.
This exam is an individual assessment.
Submitting your assessment: upload a single PDF before the hand-in cutoff. PDF is the
only format that will be accepted. You may use a word-processor or write by hand and scan
to PDF. Diagrams may be hand-drawn and scanned. Please check all scans are legible.
CM50210
CM50210
Academic Integrity for Remote Exams
When you registered as a student you agreed to abide by the University’s regulations and
rules, and agreed that you would access and read your programme handbook. These
documents contain references to, and penalties for, unfair practices such as collusion,
plagiarism, fabrication or falsification. The University’s Quality Assurance Code of Practice,
QA53 Examination and Assessment Offences (https:
//www.bath.ac.uk/publications/qa53-examination-and-assessment-offences/), sets
out the consequences of committing an offence and the penalties that might be applied.
By submitting your exam as instructed, you confirm that:
1. You have not impersonated, or allowed yourself to be impersonated by, any person for
the purposes of this assessment.
2. This assessment is your original work and no part of it has been copied from any other
source except where due acknowledgement is made.
3. You have not previously submitted this work for any other unit/course.
4. You give permission for your assessment response to be reproduced, communicated,
compared and archived for plagiarism detection, benchmarking or educational purposes.
5. You understand that plagiarism is the presentation of the work, idea or creation of
another person or organisation as though it is your own. It is a form of cheating and is
a very serious academic offence that may lead to disciplinary action.
6. You understand that this assessment is undertaken without invigilation, and that you
have not communicated with and will not communicate with anyone concerning this
assessment before the deadline for submission unless it is expressly permitted by the
assessment instructions.
7. No part of this assessment has been produced for, or communicated to, you by any
other person, unless it is expressly permitted by the assessment instructions.
If you have any questions about the exam you should contact the exams helpline.
Information and contact details can be found on our help and advice webpage
(https://www.bath.ac.uk/guides/exams-and-assessments-get-help-and-advice)
Page 2 of 4 CM50210
CM50210
1. (a) Alice encrypts her messages using a block cipher in output feedback mode, always
using the same initialization vector. Show that this is vulnerable to an attack
requiring the encryption of a single chosen plaintext to decrypt a given ciphertext
with minimal processing complexity. [10]
(b) Prove that for DES encryption with any key k and plaintext block x, ek(x)
c =
ekc(x
c), where ( )c is the bitwise complement operation — i.e. swapping 0s for 1s
and vice-versa. [15]
2. (a) Suppose h1 : {0, 1}2m → {0, 1}m is a collision-resistant hash-function. For
each i > 1, define the hash function hi : {0, 1}2
i.m → {0, 1}m by hi(x) =
h1(hi−1(x0)‖hi−1(x1)), if x = x0‖x1 where x0, x1 ∈ {0, 1}2
i−1.m. Prove that hi
is a collision-resistant hash function for each i ≥ 1. [15]
(b) Alice decides to sign messages by first hashing them using AES CBC-MAC with (the
first 128 bits of) her public RSA key (i.e. she will use CBC-MAC with a public key
as an unkeyed hash function) and then signing this value using the RSA signature
scheme. Show how an attacker could forge Alice’s signature on a message of the form
m‖m′, where m is his choice of message and m′ is computed by the attacker. [15]
3. (a) Bob accidently reveals the decryption exponent of his RSA key. He chooses a
new decryption exponent (which he keeps secret) and uses it, and his original
modulus, to calculate a new encryption exponent (which he publishes). Is this
secure? Explain. [5]
(b) 21733 has two prime factors. Find them, using the fact that φ(21733) = 21420.
Show your working. [10]
(c) Find the prime factors of 1537 using Dixon’s random squares with the factor base
{2, 3, 5, 7} and the “random” squares 402 and 572. Show your working. [10]
CM50210
CM50210
4. (a) Alice and Bob use Diffie-Hellman key exchange to agree a shared secret. Alice
chooses the prime 40973 which has primitive element 2, which she sends to Bob.
Alice and Bob then choose the secret values 1066 and 2021 respectively. What
values do they send to each other and what is their shared secret? [5]
(b) Alice uses the ElGamal signature scheme to sign her business and personal
correspondence with the distinct public keys (p, α, β) and (p, α, β′), where α is a
primitive element mod(p) and β′ = β−1 mod(p). Show that if Oscar has signatures
of the form (γ, δ) and (γ, δ′) on messages signed with the first and second keys,
respectively, then he may be able to compute her secret keys a and a′ without
solving the corresponding instance of the Discrete Logarithm problem. Indicate any
assumptions made. [15]
JDL/JHD Page 4 of 4 CM50210