CM30173
University of Bath
DEPARTMENT OF COMPUTER SCIENCE
EXAMINATION
CM30173: Cryptography
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 series of dams in remote parts of Canada are controlled from a single command centre.
Messages are of the following form.
Dam number When to obey Sluice 1 Sluice 2 . . .
the command new height new height . . .
32-bit integer 32-bit integer 32-bit integer 32-bit integer . . .
The times are seconds from 1 January 1970, and you may assume that the clocks at the
dams and control centre are sufficiently accurate. Each dam has a large number of sluices
and hence the messages are of a substantial size, communication is somewhat slow and
unreliable, but messages will eventually get through.
(a) New management has cause to worry about terrorists causing a massive flood by
sending false commands to open the sluices, and think some form of encryption
might prevent this. They believe that attackers could be intercepting messages
sent from the command centre but that attackers do not currently have the ability
to broadcast messages accepted by the dams or the control centre. It is winter
and physical access to the dams is not possible however management feels that the
security issues should be dealt with immediately.
Write a (probably one-page) memorandum saying precisely which technologies you
would use to prevent, or at least minimise, the risks from attackers, and explain
which risks you have prevented and which are still possible. [10]
(b) Obviously, if terrorists capture a dam, they can open the sluices on it. To what
extent does your solution prevent them from commanding other dams to open as
well? [3]
(c) Since dams are not perfect, management also want reports back from dams on how
well they have obeyed their orders, and again are worried about false reports.
To what extent does your current solution guard against this? How would you need
to change your solution so that, even if terrorists capture one dam, they cannot fake
reports about others. Clearly explain why you have chosen the solution you put
forward. [7]
CM30173 continued
CM30173 continued 3.
2. (a) Describe the DES encryption algorithm, explaining how it is made up from S-boxes,
permutations and boolean operations. Diagrams can be used but should be clearly
explained. [7]
(b) Describe how the modes of operation ECB and CBC work for a block cipher. Explain
the advantages and disadvantages of these modes. [6]
(c) Let ek(x) denote encryption of x with DES using key k. Let a denote the bitwise
complement of a. Explain why if ek(x) = y then ek(x) = y.
Using this fact, design a chosen plaintext attack to find a fixed unknown key, which
allows an attacker to test only half the keyspace. Why is this not a practical
concern? [7]
3. (a) Define the term message digest code (MDC). What does it mean for an MDC to be
preimage resistant, second preimage resistant and collision resistant? [4]
(b) Let g be a collision resistant MDC which produces message digests of bitlength n.
Define a new MDC h which produces message digests of length n + 1:
h(x) =
{
1 ||x if x has bitlength n
0 || g(x) otherwise.
Show that h is collision resistant but not preimage resistant. [5]
(c) Define the term signature scheme. Explain why an MDC used with a signature
scheme must be second preimage resistant to avoid known-message existential
signature forgeries. [5]
(d) Both message authentication codes and digital signatures can be used to ensure
integrity of transmitted messages. Explain the advantages and disadvantages that
digital signatures have. [6]
CM30173 continued
CM30173 continued 4.
4. (a) Describe RSA including parameter generation, encryption and decryption. How is
the extended Euclidean algorithm used? [6]
(b) Can a public key cryptosystem be unconditionally secure? Explain. [2]
(c) Alice wishes to send a message x to three people with public RSA keys (n1, 3), (n2, 3)
and (n3, 3). She encrypts x with each key producing ciphertexts y1, y2 and y3 which
she sends over insecure channels. Assuming that she did not pad the message before
encrypting conclude that an attacker can determine the plaintext x using only public
information.
[3]
(d) Let ek be RSA encryption and dk be RSA decryption. Stating any results that you
use from lectures, prove that
dk(ek(x)) = x ∀x ∈ Zn.
[6]
(e) Alice generates her RSA modulus n by finding p and q in the following fashion:
• She finds many small primes (always including 2), multiplies them together and
adds 1, forming a number of length 512 bits.
• She tests the result for primality. If it is not prime she starts the process again.
Ignoring for now the problem of how likely such a number is to be prime, what do
you think of this idea? [3]
5. (a) Describe Diffie-Hellman key exchange. [4]
(b) The practical hardness of Diffie-Hellman key exchange is based on the presumed
mathematical hardness of precisely which problem? [4]
(c) Alice and Bob use Diffie-Hellman key exchange to establish a shared key. Oscar
performs a man in the middle attack on their exchange. What does this mean?
Can Alice and Bob detect Oscar’s attack by asking each other encrypted questions
to which only they know the answers? Can they avoid the man in the middle
attack by proving their identities before they start the key exchange? Explain your
answers. [4]
(d) 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]
EHC/JHD CM30173