CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173
May 2013
No calculators may be brought in and used.
Full marks will be given for correct answers to THREE questions.
Only the best three answers will contribute towards the assessment.
Examiners will attach importance to the number of
well-answered questions.
CM30173
CM30173 2.
1. (a) 2 marks for description of a Feistel cipher as an iterated block cipher, with 3 more
for an accurate description of the round function, and 1 for noting that the left and
right blocks of state are not swapped in the final round.
(b) Encryption is just the same as encryption, but with the key schedule reversed. (2
marks). 2 marks for showing that each round of decryption reverses a round of
encryption, 2 more marks for a full proof which also notes the importance of not
reversing blocks on the final round.
(c) Importance is that if DES were a group, it would be equivalent to triple DES,
which is supposed to be more secure. (2 marks). Should describe the “meet-in-the
middle” attack on 2DES: collection of candidate keys by searching tables of single
encryptions of a plaintext and single decryptions of a ciphertext for collisions, and
verification of the correct key by testing another plaintext/ciphertext pair. This
allows brute forcing of 2DES keys in around twice the time of DES keys (although
requiring much more storage space) which is known to be very feasible. (6 marks)
2. (a) 2 marks for defining a hash function, 2 for an explanation of use of hashing for
integrity testing.
(b) A collision is a pair of distinct messages which hash to the same value. (1 mark) A
birthday attack just computes valid pairs (x, h(x)) until a collision is found — which
is expected after O(N
1
2 ) hash values have been computed and stored (3 marks).
Some explanation of why this is the case — e.g. that n hash values give (n
2−n)
2
unordered pairs of hash values for distinct messages, each of which has probability
1
N
of being a collision, so we can expect to find one when n is O(N
1
2 ). (3 marks).
(c) 1 mark for definition of MAC/keyed hash function. 2 marks for description of cipher-
block chaining mode, 2 marks for CBC-MAC (prepend length and take final block
as the authentication tag),
Using CBC-MAC with a known key is susceptible to preimage attack: an attacker
can take any message m of length n, prepend it with n + 1, encrypt using CBC and
XOR the final block with the decryption of the original message digest to get mn+1,
and use m‖mn+1 as a forged message having the same digest. (4 marks).
CM30173 continued
CM30173 continued 3.
3. (a) Describe generation of RSA public and private key (including use of extended
Euclidean algorithm to find moduli of encryption (4 marks). Description of
encryption and decryption as modular exponentiation (2 marks). Alice can use
CRT to simplify decryption becuase she can factorize the modulus and compute in
the factor fields, Bob cannot, because he doesn’t know the factorization (2 marks).
(b) Description of basic use of RSA encryption by private key encryption (2 marks)
(with or without hashing). This doesn’t provide sender authentication because (a)
if unhashed there is the possibility of existential forgery – e.g. attacker obtains
a message by encrypting his proposed signature value using the public key —
solution, sign a hash of the message. (b) The holder of the private key needs to
be authenticated as Alice – solution: she could provide a digital certificate signed by
a TTP containing her public key. (5 marks).
(c) An attacker can use 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). (6 marks).
4. (a) Alice sends Bob 58mod(23), which is (52)4mod(23) — i.e. 16 (2 marks). Bob sends
516mod(23), which is (58)2mod(23) — i.e. 3 (3 marks). Shared vaue is 58.16mod(23)
which is 38mod(23) — i.e. 6 (2 marks). Attacker could compute this by obtaining
e.g. the discrete log5 of either 16 or 3, and hence computing 58.16mod(23) (1 mark).
The computational Diffie Helman assumption states that recovering gabmod(p) from
gamod(p) and gbmod(p) is a computationally intractable problem, and that DH key
exchange is therefore computationally secure (1 mark).
(b) Description of digital signature algorithm: signing (2 marks) and verification (2
marks).
(c) Description of factor base method: select factor base of small primes {p1, . . . , pB}
and collect enough congruences of the form gx ≡ pn11 . . . p
nB
B , giving relations
between the discrete logs of the factor base, sufficient to compute them. (4 marks)
To compute the discret log of β, attempt to factorize γ = β.gsmod(p) over the
factor base (for random s), and so compute the discrete logarithm of γ as a linear
combination of logarithms of primes in the factor base. (3 marks)
The index calculus method is only applicable in groups where the notion of prime
element makes sense — not e.g. in elliptic curve groups (1 mark)
JDL/RJB CM30173