Skriftlig Eksamen Kryptologi

Institut for Matematik og Datalogi Odense Universitet

Mandag den 10. juni 1996, kl. 9–13

Alle sædvanlige hjælpemidler (lærebøger, notater, etc.) samt brug af lommeregner er tilladt.

Eksamenssættet består af 7 opgaver på 4 nummererede sider (1–4). Fuld besvarelse er besvarelse af alle 7 opgaver. Opgavernes vægt ved bedømmelsen er angivet i parenteser ved starten af hver opgave.

Der må gerne refereres til algoritmer og resultater fra lærebogen inklusive øvelsesopgaverne. Specielt må man gerne begrunde en påstand med at henvise til, at det umiddelbart følger fra et resultat i lærebogen (hvis dette altså er sandt!). Henvisninger til andre bøger (udover lærebogen) accepteres ikke som besvarelse af et spørgsmål.

Problem 1 (7%)

Suppose you are using a known plaintext attack to break a system based on a linear feedback register of length 3, and you learned that part of the message was M = 100011 and the corresponding ciphertext was C = 101101. What was the tap sequence? (Suppose that the bits initially in the register are used as the first bits of the key string and that the bits of the message were encrypted going from right to left.)

Problem 2 (7%)

Suppose you are using DES and you found a key k, such that for any 64bit message m, DES(k,(DES(k, m)))=m. Let k̄ denote the key which is the bitwise complement of k. Show that k̄ has the same property.

Problem 3 (21%)

Suppose that user A wants to have a cryptosystem which is more secure. She tries the following: She has two pairs of public and secret keys for RSA, ((n_{1}, e_{1}), d_{1}), ((n_{2}, e_{2}), d_{2}). To encrypt a message m, where 0 ≤ m < n_{1} < n_{2}, another user first encrypts with the first key and then encrypts the result with the second, so the ciphertext is ((m^{e_{1}} (mod n_{1}))^{e_{2}}) (mod n_{2}).

a How would user A decrypt this message? Show that the result would be the original message m.

b Suppose n_{1} = n_{2}. Explain why in this case applying RSA twice is no more secure than just applying it once.

c What is the unicity distance of RSA (applied only once as it usually is)?

Consider a cryptosystem in which the substitution cipher is applied twice. Thus, two users exchanging messages would share two keys. When a message is encrypted, first it is encrypted with a substitution cipher with the first key, and then with a substitution cipher using the second key. What is the unicity distance of this cipher? Assume that all messages are in English, so there are 26! different keys. Use 1.25 as your estimate of H_{L}, the entropy of English.

Problem 5 (21%)

Sometimes the Rabin cryptosystem is defined differently (and more simply) than in the textbook. Each user has a public key n, where n is the product of two large primes p and q. The values p and q are the secret key. To encrypt a message, M, where 0 ≤ M ≤ n − 1, one computes, C = M^{2} (mod n).

a How does this user decrypt the ciphertext C?

b Suppose two users in the system have keys n_{1} = p_{1}q_{1} and n_{2} = p_{2}q_{2} respectively. Explain why a third user would not want to send exactly the same message to these two users.

c Explain why this system is insecure against a chosen ciphertext attack.

Problem 6 (7%)

Give an intuitive reason for believing that the verification protocol for the Chaum-Antwerpen Undeniable Signature Scheme (Figure 6.7 on page 219) is not a zero-knowledge protocol.

Consider the following verification protocol which we showed in class could be used instead of the one in Figure 6.7 in the textbook. The keys and signing algorithms are exactly the same as described in the textbook, as is the notation. Thus, β = α^{a} (mod p), and y = x^{a} (mod p), and the signer needs to prove that log_{x}(y) = log_{α}(β) (= a).

Signer  Verifier
Choose e_{1}, e_{2} ∈ ZZ_{q}^{∗} and com-
pute c = x^{e_{1}}α^{e_{2}} (mod p).

c_{\overline{}}

Choose t ∈ ZZ_{q}^{∗} and compute h_{1} = c^{t} (mod p) and h_{2} =

h_{1}^{a} (mod p). (h_{1}, h_{2})_{\overline{}}

(e_{1}, e_{2})_{\overline{}}

Verify that c = x^{e_{1}}α^{e_{2}} (mod p).

t \overline{}

Verify that t ≠ 0 (mod q) and that h_{1} = (x^{e_{1}}α^{e_{2}})^{t} (mod p) and h_{2} = (y^{e_{1}}β^{e_{2}})^{t} (mod p).

Prove that this protocol is zero-knowledge. (Hint: Recall the zero-knowledge proof system for Quadratic Non-residues which we discussed in class.) Is it perfect zero-knowledge?