1. (a) What is a substitution-permutation network? How is it used to encrypt a block of
plaintext?
Explain how the same encryption algorithm for an SPN can be used for decryption
by describing the required changes to its components. [7]
(b) How you would design an SPN which is resistant to differential cryptanalysis (give
the required properties of its components, justifying your answer)?
What data would an adversary require to mount this attack? How would you
estimate how much data would be required? [7]
(c) Explain why electronic code book is not considered a secure mode of operation for
block ciphers.
Define the encryption of a sequence of plaintext blocks x1, . . . , xn, using encryption
function ek in cipherblock chaining mode. Define the CBC decryption of ciphertext
blocks y1, . . . , yn using decryption function dk, and prove that if dk(ek(x)) = x for all
x, then CBC encryption followed by CBC decryption returns the plaintext. [6]
2. (a) Define the notion of (unkeyed) cryptographic hash function. Give two applications
for such a function, explaining the security properties it provides and why it provides
them in each case. [5]
(b) What does it mean for a hash function to be collision resistant? (Explain your
answer with reference to an attack for finding collisions and its complexity, which
you should establish.) Does collision resistance imply pre-image resistance? [7]
(c) Explain how Alice and Bob would use a message authentication code to provide data
integrity and message authenticity without confidentiality.
Alice creates a MAC by prepending her message with a secret key and hashing
the result with SHA-2. Explain why this is insecure by describing an attack which
compromises it, and describe a way in which she could construct a MAC which is
secure against this attack. [8]
Page 2 of 3 CM30173
3. (a) Alice wants to allow Bob to communicate with her using RSA encryption. She
chooses 323 = 17.19 to be her modulus of encryption, and 7 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? [7]
(b) Is it possible that it is easier to compute the totient of an RSA modulus than to
factorize it? (Justify your answer.) 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. Use this to
show that any method for deriving the decryption exponent from the public key can
also be used to factor the modulus.
What is the RSA problem? Is solving it necessarily as hard as factorizing the
modulus? [10]
(c) Explain why basic RSA is not semantically secure, and how it can be made
semantically secure in practice. [3]
4. (a) Explain the steps of key generation, message signing and signature verification for
the ElGamal digital signature scheme. Show that it is correct — i.e. the verification
procedure accepts precisely the correctly signed messages. [8]
(b) Show that the basic ElGamal digital signature scheme is susceptible to existential
forgery and explain how this could be prevented. [5]
(c) Describe a method of computing discrete logarithms in any cyclic group which is no
less efficient than any other such general method. Establish its complexity. What
are the implications for key length in (e.g.) the Elliptic Curve Digital Signature
Algorithm? [7]
JDL/RJB Page 3 of 3 CM30173