1. (a) Give the definition of a private key encryption system based on a Feistel cipher,
including the definition of the encryption function.
Describe the decryption function of a Feistel cipher, and show in detail that it is the
inverse to encryption. [8]
(b) Which feature(s) of the Data Encryption Standard were designed to resist differential
cryptanalysis? Explain the property that they have which makes this attack
infeasible, and why this is the case.
[4]
(c) Describe encryption and decryption under Triple DES (you do not need to give
details of DES itself). Why is 3DES encryption considered secure? Why is double
DES not considered secure (describe any relevant attack in detail)? [8]
2. (a) Define the notion of unkeyed cryptographic hash fuction. Explain how and why
hash functions are used in secure password storage. What property of the hash
function does this application require? Suggest a suitable hash function for this
purpose. [5]
(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. [6]
(c) What is a message authentication code? Describe the cipher-block-chaining mode of
operation and how it is used to create a MAC. Show that an attacker who possesses
two valid pairs (m,hk(m)) and (m
′, hk(m
′)) can use them to create a CBC-MAC
forgery. How could a forgery of this kind be prevented? [9]
Page 2 of 3 CM30173
3. (a) Explain how Alice can create an RSA key — what information does she publish and
what does she keep secret, and how is it computed?
State Fermat’s little theorem and use it to prove that decryption and encryption in
RSA are inverse to each other. [7]
(b) A developer creates an app to allow its users to share information securely among
their social group without storing it on a central server. Each user is assigned an
RSA key, and any information which is to be shared with that user is encrypted
using their key and sent to them. For efficiency reasons, a single, small, encryption
exponent is used for each key. Explain why this is insecure by describing a potential
attack in detail.
The developer tries to fix this problem by adding the recipient’s name to each
plaintext before encrypting it. With reference to Coppersmith’s theorem, explain
(briefly) why this is not sufficent to make the system secure. [8]
(c) Describe how RSA can be used to (securely) digitally sign a document. Explain
how this scheme is secure against existential forgery (by an attacker without any
valid signatures) specifying any assumptions about the cryptographic primitives
involved. [5]
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? How could an attacker compromise Alice
and Bob’s session without solving the computational Diffie-Helman problem. [8]
(b) 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. [6]
(c) Why is the index calculus method not applicable in all cyclic groups, such as the
points on an elliptic curve? Describe a method of computing discrete logarithms
which is applicable in any cyclic group, and at least as (time) efficient as any other
such general method. [6]
JDL/RJB Page 3 of 3 CM30173