1. (a) 2 marks for overall definition (an iterated cipher with two state values, a fixed
round function and a key schedule). 2 for getting the operation of each round
right (Li+1 = Ri, Ri+1 = Li ⊕ f(Ri,Ki)) and 2 for decryption being the same as
encryption , but with the key schedule reversed). [6]
(b) e.g. DES, Blowfish or Twofish. [2]
(c) An S-box or substitution is a fixed, public subsitution of input values for output
values. (1 mark) If the cipher is to be resistant to differential cryptanalysis, for
example, then its S-boxes should have a low bias in terms of the propagation ratios
for the various input differences — i.e. if we take pairs of inputs with a fixed
difference, then there should be no difference between the outputs which occurs
with high frequency. (5 marks). Alternatively, could describe resistance to linear
cryptanalysis.
[6]
(d) 2 marks for defining a product cipher (bookwork). 3 marks for describing a meet-
in-the-middle attack. 1 mark for giving an example — e.g. triple DES — and
explaining why reducing this to a product of DES with itself is still secure against
brute force attack. [6]
2. (a) 1 mark for defining a MAC, 1 mark for giving an example of use in message
authentication. 1 mark each for an advantage (computational simplicity, fewer
authentication problems) and a disadvantage (need to securely share a key, lacks
non-repudiation). [4]
(b) 3 marks for describing length extension attack (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 for
describing HMAC, which avoids this. [5]
(c) 1 mark for naming CBC-MAC, 2 for defining Cipher-block-chaining accurately and
1 for defining the MAC. It is insecure to use the same key for encryption and
authentication as the MAC will be the final block of the ciphertext — any of the
preceding blocks can be changed without invalidating the MAC, so it does not
preserve integrity (3 marks). [7]
(d) They could precompute a stream cipher using OFB mode or possibly parallelize
encryption using counter mode. (2 marks for one of these, 2 more for a correct
definition). [4]
Page 2 of 3 –
3. (a) 2 marks for definition of a public key encryption system, 1 for observing that
it cannot be unconditionally secure, as the possibility of brute force attack by
encrypting all possible plaintexts with the public key always exists. [3]
(b) Private key is 173 — multiplicative inverse of 5mod(288). (3 marks) Encryption of
18 is 185mod(323), which is 18 (as 182 ≡ 1mod(323)). (2 marks) Alice decrypts by
computing 18173mod(323) (1 mark). [6]
(c) An encryption system is malleable if it is possible to transform the encryption of one
plaintext into the encryption of a related plaintext, without knowing the decryption
function. (1 mark). Semantic security is indistinguishability under chosen plaintext
attack (1 mark). RSA is malleable, due to its multiplicative property (1 mark) and
not semantically secure, due to its determinacy (1 mark). In practice, RSA is used
with random padding (OAEP) (1 mark). [5]
(d) 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). [6]
4. (a) 2 marks for key generation, 2 marks for defining the signature, 1 mark for the
verification function. [5]
(b) 2 marks for showing that correctly signed messages are accepted, and 2 for showing
that only correctly signed messages are accepted. Security does not reduce to any
particular computational hardness assumption. [5]
(c) We can create existential forgeries of RSA signatures by choosing a signature,
encrypting it using the public key, and using this as the corresponding message.
(2 marks) ElGamal is also susceptible to existential forgery (1 mark). In practice,
both are avoided by signing the hash of the message, rather than the message itself.
(1 mark) [4]
(d) 5 marks for accurate description of Shanks’ algorithm, 1 mark for an estimate of its
complexity based on the requiement to compute 2
√
|G| values to search for discrete
logarithms in G. [6]
JDL/RJB Page 3 of 3 –