1. (a) What is a substitution-permutation network? How is it used to encrypt a block of
plaintext?
4 marks for defining iterated block cipher incorporating substitutions, permutations,
and mixing of round keys according to a key schedule.
Explain how the same encryption algorithm for an SPN can be used for decryption
by describing the required changes to its components.
3 marks for inverting the S boxes and permutation, reversing the key schedule and
permuting round keys except in the first and final rounds.
(b) How you would design an SPN which is resistant to differential cryptanalysis (give
the required properties of its components, justifying your answer)?
4 marks — 2 for requiring S boxes to have a low bias (explained) — 2 for
permutations producing wide differential trails (explained).
What data would an adversary require to mount this attack? How would you
estimate how much data would be required?
(3 marks — 2 for explaining that the attacker requires ciphertexts for chosen pairs of
plaintexts with a given difference, and 1 for stating that c/p such pairs are required,
where c is a constant and p is the bias of the differential trail.)
(c) Explain why electronic code book is not considered a secure mode of operation for
block ciphers.
(2 marks for knowing what ECB is and that repeated plaintext blocks are
observable.)
Define the encryption of a sequence plaintext blocks x1, . . . , xn, using encryption
function ek in cipherblock chaining mode. Define the 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 decryption returns the plaintext.
(1 mark each for giving inductive definitions for encryption and decryption, 2 marks
for applying the formulas to show by induction that zi = xi for each i ≤ n.)
Page 2 of 5 CM30173
2. (a) Define the notion of (unkeyed) cryptographic hash function.
1 mark (bookwork).
Give two applications for such a function, explaining the security properties it
provides and why it provides them in each case.
(2 marks for each, for applications including password storage, digital signatures,
message integrity.)
(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.)
6 marks, 1 for correctly describing a collision, and 1 for stating that a hash function
is collision resistant if the most efficient method for finding collisions is a birthday
attack. 3 marks for describing the birthday attack and estimating its complexity
as O(N
1
2 ), e.g. by arguing that K messages form (K2 −K)/2 distinct, unordered
pairs, each of which may be a collision.
Does collision resistance imply pre-image resistance (explain)?
No – because preimage resistance requires that finding a pre-image requires O(N)
steps. (1 mark).
(c) Explain how Alice and Bob would use a message authentication code to provide data
integrity and message authenticity without confidentiality.
Alice sends Bob (m,hk(m)) where m is her message, and k is her shared key with
Bob. If Bob receives (m,hk(m)) he knows that it was created by someone who
knows k (i.e. Alice) and has not be altered.
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.
4 marks to describe a length extension attack on a hash function such as SHA-2
based on the Merkle-Damgaard construction (if a MAC is created by hashing a key
concatenated with the message using a Merkle-Damgaard construction, this can be
used to create a MAC for an extension of the message (without knowing the key)
by using it as the initial value in computing the hash of the extension. 2 marks to
describe an alternative such as HMAC or CBC-MAC
Page 3 of 5 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?
Private key is 247 — multiplicative inverse of 7mod(288), computed using extended
Euclidean algorithm (4 marks).
Bob uses the public key to encrypt the message 18: what value does he send to
Alice? How would Alice decrypt this ciphertext?
Encryption of 18 is 187mod(323), which is 18 (as 182 ≡ 1mod(323)). (2 marks) Alice
decrypts by computing 18247mod(323) (1 mark).
(b) Is it possible that it is easier to compute the totient of an RSA modulus than to
factorize it? (Justify your answer.)
No — φ(p.q) = (p− 1).(q − 1) gives a quadratic for which the roots are the factors
of the modulus (2 marks).
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.
2 marks for proof that if m divides x2− y2 but not x− y or x+ y then gcd(x− y,m)
must be a non-trivial factor of m. 4 marks for using this to define a procedure for
factorizing the modulus, using the fact that for any x, xde−1 ≡ 1mod(m), by testing
whether x
de−1
2 ≡ 1mod(m).
What is the RSA problem? Is solving it necessarily as hard as factorizing the
modulus?
1 mark for defining RSA problem, 1 for observing that it is not know whether it is
as hard as factorization.
(c) Explain why basic RSA is not semantically secure, and how it can be made
semantically secure in practice.
Basic RSA is deterministic — i.e. encrypting the same message twice will give the
same cipehrtext and so does not possess the ciphertext indistinguishability property
(semantic security) — 2 marks. In practice, semantic security is obtained by optimal
asymmetric encryption padding (OAEP) 1 mark.
Page 4 of 5 CM30173
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.
Bookwork — 2 marks to define the digital signature, 2 marks for the verification
procedure, 2 marks for showing that correct signatures are verified, and 2 for showing
that verified signatures are correct.
(b) Show that the basic ElGamal digital signature scheme is susceptible to existential
forgery and explain how this could be prevented. 2 marks for describing an
existential forgery — e.g. choosing i, j ≤ p − 2 and setting γ = αiβj , δ = −γ.j−1
and x = iδ and 2 marks for showing that it satisfies the verification procedure. 1
mark for use of hashing to prevent this forgery.
(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.
1 mark for identifying Shanks’ algorithm (or equivalent), 4 more for an accurate
description. 1 mark for an estimate of its complexity based on the requirement to
compute 2
√
|G| values to search for discrete logarithms in G.
What are the implications for key length in (e.g.) the Elliptic Curve Digital
Signature Algorithm?
1 mark for observing that gives a lower bound for key length of twice the number of
bits of security required for the signature.
JDL/RJB Page 5 of 5 CM30173