CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173: Cryptography
No calculators may be brought in or used.
Full marks will be given for correct answers to THREE questions. If you opt to answer more
than the specified number of questions, you should clearly identify on the cover sheet which
of your answers you wish to have marked. In cases you have failed to identify the correct
number of answers the marker is only obliged to consider the answers in the order they
appear up to the number of questions required.
PLEASE FILL IN THE DETAILS ON THE FRONT OF YOUR ANSWER BOOK/COVER
AND SIGN IN THE SECTION ON THE RIGHT OF YOUR ANSWER BOOK/COVER,
PEEL AWAY ADHESIVE STRIP AND SEAL.
TAKE CARE TO ENTER THE CORRECT CANDIDATE NUMBER AS DETAILED ON
YOUR DESK LABEL.
DO NOT TURN OVER YOUR QUESTION PAPER UNTIL INSTRUCTED TO BY THE
CHIEF INVIGILATOR.
CM30173
CM30173
1. (a) Give the definition of a private key cryptosystem. Show that a Feistel cipher meets
this definition (you will need to include the details of the encryption and decryption
functions). [6]
(b) What data (and how much) are required to mount an attack on a Feistel cipher
using differential cryptanalysis? (Explain.) Which feature(s) of the Data Encryption
Standard were designed to resist this attack? Explain the property they have which
makes it infeasible, and why this is the case. [8]
(c) Describe encryption and decryption under Triple DES (you do not need to give
details of DES itself). Explain, with reference to relevant attacks, why 3DES
encryption is considered secure but 2DES is not. [6]
2. (a) What is the electronic code book mode of operation for a cryptosystem? Why is
it considered insecure? Define encryption and decryption using (i) cipher block
chaining and (ii) ciphertext feedback modes, and show that decryption of a ciphertext
returns the corresponding plaintext in the case of CFB. [6]
(b) What is an unkeyed cryptographic hash function? Define the notion of collision
resistance and explain and justify this definition in terms of computational security.
Why is collision resistance an important property? Describe the Merkle-Damg̊ard
construction of a collision resistant hash function, stating the properties of any
primitives used. [8]
(c) How could a message authentication code be used to provide assurance of
authenticity and integrity for client-server communication? Explain why defining
a MAC by setting hk(m) = h(k|m) (where h is SHA-2) is insecure. How can a
secure MAC be derived from SHA-2? [6]
Page 2 of 3 CM30173
CM30173
3. (a) Define the RSA public key cryptosystem. Using Fermat’s little theorem, show that
it meets the requirement that encryption followed by decryption returns the original
plaintext. [6]
(b) Show that the (assumed) difficulty of the factorization problem for large moduli
implies that deriving a private RSA key from the corresponding public key is
computationally infeasible. Does this also imply that the RSA problem is hard?
(Explain.) [8]
(c) Explain why it would be insecure to encrypt the same message for several principals
using RSA with a single, small encryption exponent and different moduli? What is
semantic security of a public key encryption system? How is semantic security of
RSA ensured, in practice? [6]
4. (a) Alice and Bob agree to establish a session key using Diffie-Hellman key exchange,
based on the multiplicative group of integers modulo 23, with generator 5. If Alice
chooses the secret value 4, and Bob the secret value 16, what values will they send
to each other, and what will their shared secret be? [6]
(b) Using the values computed in part (a), give discrete logarithms (modulo 23, base
5) for the factor base {2, 3, 5}. How could you use this information to calculate the
discrete logarithm for any element of the group? Apply this method to calculate the
discrete logarithm of 19, using the random value s = 2.
Is the index calculus method applicable in all groups (if not, why not)? [8]
(c) Describe a digital signature scheme based on discrete logarithms and prove that it
is correct (i.e. message verification succeeds if and only if the message was correctly
signed). [6]
JDL/RJB Page 3 of 3 CM30173