Skriftlig Eksamen Kryptologi

Institut for Matematik og Datalogi Odense Universitet

Tirsdag den 2. juni 1998, kl. 9–13

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

Eksamenssættet består af 3 opgaver på 3 nummererede sider (1–3). Fuld besvarelse er besvarelse af alle 3 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.

Bemærk, at hvis der er et spørgsmål i en opgave, man ikke kan besvare, kan man godt besvare de efterfølgende spørgsmål og blot antage at man har en løsning til de foregående spørgsmål.

Problem 1 (30%)

a. Suppose that a keystream is produced by a linear feedback shift register with m stages and that the period is r. Suppose the first m bits of the sequence are all ones. What value does bit r have, and why? (Hint: Consider separately the case where r = 1.)

b. Are there any linear feedback shift register sequences where within one period, the number of zeros and the number of ones differs by more than one? Prove your answer.

c. Consider the cryptosystem where a linear feedback shift register with m stages produces a keystream which gets XORed with messages from the English language represented in ASCII. The key for this system would be the tap sequence, plus the initial values in the shift register. Assume that the redundancy in the English language when expressed in ASCII is R_{L} = 0.97. What is the unicity distance of this cryptosystem? Why would one use this value for R_{L} rather than the value R_{L} = 0.75 which is suggested in the textbook as the redundancy in the English language?

Problem 2 (30%)

With RSA, there are often recommendations to use a public exponent e = 3.

a. What would the advanatage to this be?

b. If e = 3, the two prime factors dividing the modulus, p and q, must be such that p ≡ q ≡ 2 (mod 3). Why is it impossible to have one or both of p and q congruent to 0 or 1 modulo 3?

c. Suppose that e = 3, p = 3r+2 and q = 3s+2. What would the decryption exponent d be?

Problem 3 (40%)

Let N be an integer for which there exists a and b such that a^{2} ≡ b^{2} (mod N) and a and b have different Jacobi symbols. Suppose that N is given as input to a Prover and Verifier, and suppose the Prover knows the factorization. Consider the interactive protocol in which the following is repeated log_{2} N times:

Prover  Verifier

Choose a random quadratic

residue r ∈ Z_{N}^{∗}. r \overline{}

Choose a random s ∈ {−1, +1}.

s_{\overline{}}

Compute x such that

x^{2} ≡ r (mod N) and (\frac{x}{N} ) = s.

x \overline{}

Check that x^{2} ≡ r (mod N) and (\frac{x}{N} ) = s. If not, reject and halt.

a. Suppose that a^{2} ≡ b^{2} (mod N), (\frac{a}{N} ) = +1, and (\frac{b}{N} ) = −1. Consider y ∈ Z_{N}^{∗}. Prove that there exist c and d such that c^{2} ≡ d^{2} ≡ y^{2} (mod N) with (\frac{c}{N} ) = +1 and (\frac{d}{N} ) = −1.

b. Prove that the above protocol is an interactive proof system showing that every quadratic residue in Z_{N}^{∗} has both a square root with Jacobi symbol +1 and a square root with Jacobi symbol -1.

c. Prove that the above protocol is perfect zero-knowledge (use definition 13.2 in the textbook).