CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173
May 2013
No calculators may be brought in and used.
Full marks will be given for correct answers to THREE questions.
Only the best three answers will contribute towards the assessment.
Examiners will attach importance to the number of
well-answered questions.
CM30173
CM30173 2.
1. (a) Give the definition of a private key encryption system based on a Feistel cipher,
including the definition of the encryption function. [6]
(b) Describe the decryption function of a Feistel cipher, and show in detail that it is the
inverse to encryption. [6]
(b) Why is it significant that the encryption functions of the Data Encryption System
do not form a group under composition? Explain in detail why “2DES” is still not
considered secure, describing any relevant attack in detail. [8]
2. (a) Define the notion of unkeyed cryptographic hash fuction and explain how such a
function can be used to protect the integrity of a message sent over an unsecure
channel. [4]
(b) What is a collision for a hash function? Explain how a birthday attack may be used
to find collisions. What is the storage and processing complexity of such an attack?
Explain your reasoning. [7]
(c) What is a message authentication code? Describe the cipher-block-chaining mode
of operation and how it is used to create a MAC. Alice uses CBC-MAC to create
a message digest for Bob by sending him the MAC for her message along with the
key used to create it. Is this a good idea? Explain your answer. [9]
3. (a) Alice wants to allow Bob to communicate with her using RSA encryption. What
information does she send to him, what does she keep secret, and how is it computed
(explain any algorithms used)? How can Bob use it to encrypt his plaintext, and
how will Alice decrypt Bob’s ciphertext? Why might she — but not Bob — find
the Chinese Remainder Theorem useful? [8]
(b) How could Alice use RSA to send a message to Bob in such a way that he could
verify its authenticity? Does the method you have described also provide assurance
of the authenticity of the sender? If not, explain why not, and how Alice could
provide this assurance? [6]
(b) Alice and Bob are assigned RSA keys with the same modulus of encryption n, but
coprime encryption exponents e1 and e2. Charlie sends them encryptions of the
same plaintext. Explain how an attacker can easily recover it without their private
keys. [6]
CM30173 continued
CM30173 continued 3.
4. (a) Alice and Bob agree to establish a session key using Diffie-Helman key exchange,
based on the multiplicative group of integers modulo 23, with generator 5. If Alice
chooses the secret value 8, and Bob the secret value 16, what values will they send to
each other, and what will their shared secret be? How could an attacker able to find
discrete logarithms discover this secret? Explain why Diffie-Helman key exchange
is assumed to be secure, if the chosen multiplicative group is large enough. [8]
(b) Explain how multiplicative groups and discrete logarithms may be used to
authenticate a message. [4]
(c) Describe the index calculus method for computing discrete logarithms, explaining
how to collect linear relations for a factor base and use them to find discrete
logarithms. Is the index calculus method applicable in all groups (if not, why not)?
[8]
JDL/RJB CM30173