University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
: CRYPTOGRAPHY
1. (a) Is the Feistel (F ) function used in the DES cryptosystem a one-to-one function?
(No – 1 mark). Explain in detail why DES encryption is invertible. Will need to
explain encryption and decryption in sufficient detail (2 marks) to then show that
each round of decryption reverses a round of encryption (3 marks). [6]
(b) A company creates a proprietary Substitution Permutation Network in which the S-
boxes are generated by using a pseudorandom function to match inputs to outputs.
Explain why this is insecure with reference to a chosen plaintext attack on the SPN,
giving the data requirements, objectives and each stage of the attack. 1 mark for
suggesting vulnerability to differential cryptanalysis (which is a chosen plaintext
attack). 2 marks for explaining that this is likely to lead to S boxes with differential
bias. 4 marks for detail in describing the attack. Is the cryptosystem secure against
known plaintext attack (give reasons)? (1 mark for suggesting that it is vulnerable
to linear cryptanalysis.) [8]
(c) Is the set of DES encryption functions closed under composition? (No – 1 mark)
What is the relevance of your answer to the security of Triple DES? (Encrypting
under multiple keys is distinct from (and more secure than) encrypting under a
single key – 1 mark)
There are 256 DES keys: what is the approximate minimum number of operations
an attacker will require to find a triple DES key (k1, k2, k3) (with high likelihood) by
exhaustive search? Explain your reasoning. (Approx 2114 – 1 mark (would accept
something close). 3 marks for explaining a meet-in-the-middle attack which achieves
this.) [6]
Page 2 of ??
2. (a) Give two applications for a cryptographic hash function. (1 mark for each). What
is the required security property (or properties) of the hash function in each case?
Justify your answers. (1 mark for each). Does second preimage resistance imply first
preimage resistance, in general? (No – there may be a unique, easy-to-find preimage
for each hash – 1 mark). Does collision resistance imply second preimage resistance?
(No, because it may be possible to find preimages in less than 2n operations, but
not possible to find a collision in less than 2
n
2 operations – 1 mark). [6]
(b) How could Alice and Bob use a MAC to establish authenticity of a message between
them? (2 marks for description of the creation, transmission and checking of a
message with authentication tag.)
Alice proposes creating a MAC by appending the message to the key and hashing
with SHA-1. Explain in detail why this is insecure.
(1 mark for noting that SHA-1 is a MD constructed hash function, 2 for describing a
length extension attack). Bob proposes using CBC to encrypt, and CBC-MAC with
the same key to authenticate messages. Explain why this is insecure. (3 marks for
that observing/explaining any messages can be changed by an attacker who leaves
the final block and authentication tag intact [8]
(c) Give examples (one for each) of modes of operation which:
• Allow decryption of different blocks of the same message to be computed in
parallel. (1 mark for e.g. CFB or CBC, 1 mark for showing that decryption of
each block is independent).
• Could be used for real-time encryption of streamed data using e.g. Triple DES.
(1 mark – precomputing key with OFB).
• Would be insecure for storing bitmap files. (1 mark for ECB).
• Could be used with an encryption function which is not injective. (1 mark for
OFB and CFB, 1 mark for showing that decryption does not use the decryption
function for the cipher.)
Justify your answers. [6]
Page 3 of ??
3. (a) Alice’s private RSA key is given by the primes p = 17 and q = 13, and encryption
exponent 5. What is her public key? (Show your working.) Modulus is 221 (1
mark). Encryption exponent is 5−1 mod(192) which is 77 (2 marks for the answer,
2 for the working). [5]
(b) Given the RSA public key (209, 7), find the private key by using the factor base {2}
and “random” square 152 to factorize the modulus of encryption. Give each step in
your working.
152 mod(209) is 16 which factorizes over the factor base (as 24). (2 marks
) Thus we have a non-trivial difference of squares 152 = 42mod(209), and so
gcd(209, (15 − 4)) = 11 is a non-trivial factor of 209, and 19 is the other. (3
marks). Now we need to calculate the private key by finding the multiplicative
inverse of 7 modulo 180 (i.e. (11− 1).(19− 1)), which is 103 (5 marks – 2 marks for
identifying the goal, and 3 marks for calculating correctly using extended Euclidean
algorithm.) [10]
(c) Alice and Bob trust each other enough to share all of their secrets. They use
RSA keys with the same encryption modulus but coprime encryption exponents.
Explain why this is insecure. (5 Marks for showing that any message encrypted
for Alice and Bob can be read by an attacker who uses the extended Euclidean
algorithm to find s, t such that s.e1 + t.e2 = 1. He can then recover the message as
ys1y
t
2mod(n) ≡ x
se1 .xte2mod(n) ≡ x1mod(n). )
[5]
4. (a) Bob signs two different messages using the El Gamal signature scheme, producing
signatures (γ, δ1) and (γ, δ2), where δ1 − δ2 is prime. Explain (with proofs, where
relevant) why this is insecure. 5 marks for showing that given two messages signed in
Zp∗ using the same ephemeral key, the latter can be recovered provided the difference
in message is coprime with p− 1. 3 marks for then deriving the signing key. [8]
(b) Give discrete logarithms for the factor base {2, 3} for the multiplicative group of
non-zero integers modulo 29 with generator 2. (Log of 2 base 2 is 1 (1 mark). 25 is
congruent to 3 base 29 so log of 3 is 5 – 2 marks). Use the factor base method to
calculate the discrete logarithm of 19 base 2, modulo 29, using the “random” value
s = 2. (3 marks — 22.19 mod(29) = 18 = 2 × 32, so 2 + log(19) = 1 + 2.5 and so
log(19) = 9.) [7]
(c) Explain how an attacker could obtain a 128-bit private key for elliptic curve digital
signatures in around 264 operations. (3 marks for identifying that Shanks’ algorithm
can be used to find the discrete logarithm of the relevant part of the key in
√
(2128)
operations. 3 marks for a description of the algorithm.) [5]
JDL/JHD Page 4 of ??