INSTITUT FOR MATEMATIK OG DATALOGI

ODENSE UNIVERSITET

Skriftlig eksamen

Kryptologi

Mandag den 12. juni 1995 kl. 9.00 – 13.00

Opgavesættet består af 4 nummererede sider og indeholder 9 opgaver. Opgaverne vægtes sådan: Opgave 1: 5% Opgave 2: 5% Opgave 3: 15% Opgave 4: 5% Opgave 5: 15% Opgave 6: 10% Opgave 7: 20% Opgave 8: 10% Opgave 9: 15%

Alle skriftlige hjælpemidler samt brug af lommeregner er tilladt.

Problem 1

Use the output of the following linear feedback shift register as a one-time pad to encode the message “0110101000110”. The register of the linear feedback shift register initially contains (0,1,1,1), and the tap sequence is (0,1,0,1).

a What is the cryptotext?

b What is the length of the period of the sequence generated by the linear feedback shift register?

Problem 2

Suppose that user A wants to send a message s ∈ {s_{1}, s_{2}, ..., s_{k}} to user B, where s_{i} < 1024 for 1 ≤ i ≤ k. Assume that RSA is secure (when the modulus is large enough and is the product of two equal length prime factors).

a Why would you still advise user A not to use RSA directly?

b What would you recommend instead?

Problem 3

Suppose you, as a cryptanalyst were interested in an RSA modulus N, and you were given a t such that a^{t} ≡ 1 (mod N) for all a ∈ Z_{N}^{∗}. (Note that t is not necessarily ϕ(N). In the case N = 69841, ϕ(69841) = 69300, but t could have many other values including 2310 and 138600.)

a Give an efficient algorithm for determining the message m which was encrypted using the public exponent e, producing the cryptotext c.

b Give an efficient algorithm for factoring N. (Hint: some ideas from the Miller-Rabin primality testing algorithm may be helpful.)

Problem 4

In the Diffie-Hellman key-exchange system, consider the possibility that the number g is not a generator.

a Would a pair of users still be able to agree on a key?

b When the two users agree on a key, what effect would the fact that g is not a generator have on an eavesdropper’s ability to determine that key?

Problem 5

Suppose you have strings of n bits which you wish to hash down to strings of length k bits. A hash function is cryptographically secure if the problem of finding two strings which hash to the same value is infeasible. Suppose that choosing a random n bit string and hashing it takes time h and that you consider anything which takes more than w units of time infeasible.

a Clearly, if k is only one or two, no cryptographically secure hash function exists. Why?

b How large must k be for there to be some possibility of a cryptographically secure hash function?

Problem 6

In class, we looked at a probabilistic encryption scheme which had its security based on the Quadratic Residuosity Assumption, and we observed that this scheme could be used for bit commitments (blobs). User A has a public key pair (N, y), where N is the product of two large primes and y is a quadratic nonresidue with Jacobi symbol +1. To commit to a bit b, user A chooses a random r ∈ Z_{N}^{∗} and produces the blob y^{b}r^{2} (mod N). Suppose that user A has committed to two bits b_{1} and b_{2}, producing blobs B_{1} and B_{2}. Show how A can use the blobs B_{1} and B_{2} to reveal c such that c = b_{1} XOR b_{2}, and to prove to another user B that c = b_{1} XOR b_{2}, without revealing b_{1} or b_{2}. (The fact that this can be done means that this system for producing blobs has what is called the equality property, because it can be used to show that two blobs are commitments to equal bits, showing that the XOR is zero.)

Problem 7

Consider MAJORITY gates with fan-in n, where n = 2m + 1. The output should be one if at least m+1 of the inputs are one, and zero if at least m+1 of the inputs are zero. Suppose that user A has committed to n input bits, b_{1}, b_{2}, ..., b_{n}, and one output bit b_{n+1}, and produced blobs B_{1}, B_{2}, ..., B_{n}, B_{n+1}, using the scheme described in problem 6. If user A wishes to prove to user B that B_{1}, B_{2}, ..., B_{n}, are commitments to the inputs to a MAJORITY gate and B_{n+1} is a commitment to the output of that same MAJORITY gate, user A only need show that there are m + 1 inputs which are equal to the output. In order to hide which of the inputs are the same as the output, user A will produce n more blobs corresponding to the original input blobs for that gate. These additional n blobs will be encryptions of the same bits as the input blobs, but user A will send them to user B in random order, so user B will be unable to determine the correspondence. Now, user B will send user A a challenge c ∈ {0, 1}. If c = 0, user A will show user B the correspondence between the input blobs and the n additional blobs, telling user B which additional blob corresponds to which original input blob and proving it using the equality property (see problem 6). If c = 1, user A will show that m + 1 of the additional blobs are commitments to the same bit as B_{n+1} is, again using the equality property. Thus, the protocol is as follows (“random” means independently, from a uniform distribution):

Repeat the following k(n + 1) times, where k is the length of the blobs produced:

User A: Choose random r_{1}, r_{2}, ..., r_{n} ∈ Z_{N}^{∗}. Create C_{i} = y^{b_{i}}r^{2} (mod N), for 1 ≤ i ≤ n. Choose a random permutation σ of the numbers 1, 2, ..., n. Send user B the blobs (D_{1}, D_{2}, ..., D_{n}) = (C_{σ(1)}, C_{σ(2)}, ..., C_{σ(n)}).

User B: Choose random e ∈ {0, 1}. Send e to user A. User A: Case e = 0: Send σ to user A.

Use the equality propoerty to show that B_{σ(i)} and D_{i}

are encryptions of the same bit, for 1 ≤ i ≤ n.

Case e = 1: Choose a subset {D_{i_{1}}, D_{i_{2}}, ..., D_{i_{m+1}}} of the D_{i}s of size m + 1, such that those D_{i}’s are encryptions of the same bit as the output blob B_{n+1}. (If there are more than m + 1 satisfying this, choose among them randomly.) Use the equality property to show that D_{i_{j}} and B_{n+1} are encryptions of the same bit, for 1 ≤ j ≤ m + 1.

User B accepts if user A has correctly answered all challenges and rejects otherwise.

a Show that the protocol described above is an interactive proof system proving that B_{1}, B_{2}, ..., B_{n}, are commitments to the inputs to a MAJORITY gate and B_{n+1} is a commitment to the output of that same MAJORITY gate.

b Show that the protocol described above is computational zero-knowledge, assuming the Quadratic Residuosity Assumption.

Problem 8

Use problem 7 to design a computational zero-knowledge interactive proof system proving that B_{1} and B_{2} are commitments to the inputs to an OR gate and B_{3} is a commitment to the output to that same OR gate. (Hint: note that an OR gate has an even number of inputs, but the MAJORITY gate described above has an odd number of inputs. Try adding a special extra input to the OR gate.)

Problem 9

Suppose that user A has committed to two bits b_{1} and b_{2}, producing the blobs B_{1} and B_{2}, using the bit commitment scheme described in problem 6. Suppose that he wants to let user B choose one of the two blobs, B_{i}, learn the value of b_{i}, and see a proof that B_{i} is a commitment to b_{i} (user A want to let user B choose one of the blobs and open it), but user B does not want user A to know which blob he chose. Design a protocol for this purpose, which allows user B to choose a blob and open it, but which does not allow user A to learn which blob user B could open. (You may assume that user A is honest.)