1. (a) Give the definition of a Feistel cipher encryption system, including the definition of
the encryption and decryption functions. [6]
(b) Give an example of an encryption system based on a Feistel cipher. [2]
(c) What is an S-box? Describe a property of the S-boxes used in a block cipher which
is necessary for its security and explain why this is the case. [6]
(d) What is a product cipher? Describe a cryptanalytic attack which can reduce the
problem of breaking a product cipher to the problem of breaking its components.
Give an example of a product cipher in current use: is it secure against this attack?
Why? [6]
2. (a) What is a message authentication code? Explain how and why a MAC might be
used. Give an advantage and a disadvantage of MACs in comparison with digital
signatures. [4]
(b) What is a length extension attack on a MAC? Describe how to create a MAC using
an unkeyed hash function which is secure against this attack. What property does
the unkeyed hash function require, if this MAC is to be resistant to forgery? [5]
(c) Name and describe a mode of operation for a block cipher which can be used to
create a MAC. Explain why it is insecure to use this to authenticate messages which
have been encrypted using the same key and mode of operation. [7]
(d) Alice knows that she will need to transmit confidential data to Bob as it is generated,
at a rate which is faster than their block cipher can encrypt or decrypt it. Explain
precisely how they could achieve this. [4]
Page 2 of 3
3. (a) What is a public key encryption system? Is it possible for such a system to be
unconditionally secure (explain)? [3]
(b) Alice wants to allow Bob to communicate with her using RSA encryption. She
chooses 323 = 17.19 to be her modulus of encryption, and 5 to be her encryption
exponent. What is her private key? Bob uses the public key to encrypt the
message 18: what value does he send to Alice? How would Alice decrypt this
ciphertext? [6]
(c) What is meant by:
• malleability of an encryption system?
• semantic security of a public key encryption system?
Why is basic RSA malleable, and not semantically secure? How is malleability
prevented, and semantic security obtained, in practice? [5]
(d) Show that if x2 ≡ y2 mod(m), x 6≡ y mod(m) and x 6≡ −y mod(m), then gcd(x−y,m)
is a non-trivial factor for m. How can this be used to factorize the modulus of
encryption, if the decryption key is known? [6]
4. (a) Explain the steps of key generation, message signing and signature verification for
the ElGamal digital signature scheme. [5]
(b) Show that the ElGamal digital signature scheme is correct — i.e. the verification
procedure accepts precisely the correctly signed messages. Is the security of the
scheme reducible to the hardness of a specific problem? [5]
(c) Show that digital signature using (basic) RSA is susceptible to existential forgery.
Are digital signatures created using the (basic) ElGamal scheme also susceptible to
existential forgery? How is such forgery prevented in practice? [4]
(d) Describe Shanks’ algorithm for computing discrete logarithms, and estimate its
complexity in a group of given size. [6]
JDL/RJB Page 3 of 3