CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173: CRYPTOGRAPHY
Tuesday, 19 May 2009, 9.30–11.30
No calculators may be brought in or used.
Full marks will be given for correct answers to THREE questions. If you opt to answer more
than the specified number of questions, you should clearly identify which of your answers you
wish to have marked. In cases where you have failed to identify the correct number of answers
the marker is only obliged to consider the answers in the order they appear up to the number
of answers required.
CM30173
CM30173 2.
1. (a) Describe a substitution-permutation network (SPN), explaining how it is made up
from S-boxes, permutations and boolean operations. Diagrams can be used but
should be clearly labelled. [6]
(b) Sketch a differential cryptanalysis attack on an SPN. You should describe the goal
of the attack, the inputs and outputs and the main steps an attacker would have to
work through. Diagrams can be used but should be clearly labelled. [8]
(c) Referring back to your answer to part (a) explain how AES has the structure of an
SPN. How is AES protected against differential cryptanalysis? [6]
2. (a) Define the terms message authentication code (MAC) and message digest code
(MDC). [4]
(b) What does it mean for a MAC to be subject to MAC forgery? [1]
The CBC mode of a block cipher such as DES can be used to produce a MAC by
using a fixed public initialisation vector and for input x = x1‖x2‖ · · · ‖xn calculating
y0 = 00 . . . 00
yi = DESk(yi−1 ⊕ xi), 1 ≤ i ≤ n
where DESk is DES encryption with key k, and returning MACk(x) = yn.
Describe the ECB and OFB modes of a block cipher. [3]
Can we use ECB or OFB in a similar fashion to produce a secure MAC? Explain
your answers. [4]
(c) Alice decides to use DES as a fixed-length MDC by defining
h : {0, 1}112 → {0, 1}64
h(x1‖x2) = DESx1(DESx2(0
64))
where DESk is DES encryption with key k and |x1| = |x2| = 56.
What does it mean for an MDC to be pre-image resistant? [1]
Explain how to find a pre-image for a given y in roughly 256 DES operations. Is this
a problem for Alice? [7]
CM30173 continued
CM30173 continued 3.
3. (a) Describe RSA including parameter generation, encryption and decryption. How is
the extended Euclidean algorithm used? [6]
(b) Suppose an attacker has discovered Alice’s decryption exponent, argue that Alice
cannot reuse her RSA modulus when generating her new private-public key pair.
You may quote without proof any theorems or propositions from lectures which you
use in your argument. [6]
(c) What are the main components of a public key infrastructure (PKI)? Give an
example of how such an infrastructure can be used to provide secure communication
between parties who have not met each other or previously agreed a secret key. To
what extent must they have “met” the PKI? [8]
4. For p prime and α ∈ Z∗p a primitive element, let k ∈ {(p, α, a, β) | β ≡ αa (mod p)}, and
for a random number r ∈ Z∗p−1 define the ElGamal signing function to be
sigk(x, r) = (γ, δ)
where
γ = αr (mod p) and δ = (x− aγ)r−1 (mod p− 1).
Given x, γ ∈ Z∗p, δ ∈ Zp−1 define the verfication function to be
verk(x, (γ, δ)) = t ⇔ βγγδ ≡ αx (mod p).
(a) Describe how to create an ElGamal public-private key pair and then a digital
signature on some message x ∈ Z∗p. [2]
State the discrete logarithm problem. What necessary condition for security does
this place on the selection of p? [2]
Why must r be kept secret? [1]
(b) Show that verification succeeds on a correctly constructed signature. [5]
(c) Explain why it is possible to create a key-only existential forgery of an ElGamal
signature. How can we use a secure hash function to avoid this? [4]
(d) Digital signatures can be used to ensure integrity of transmitted messages. Explain
the advantages and disadvantages that digital signatures have over private key
schemes for data integrity. [6]
EHC/RJB CM30173