Faculty of Science
Final Examination

Computer Science 308-547A
Cryptography and Data Security

 Examiner: Prof. Claude Crépeau Date: Dec. 10, 1999 Associate Examiner: Prof. David Avis Time: 9:00 — 12:00

INSTRUCTION:

• This examination is worth 40% of your final grade.
• The total of all (sub-)questions is 100 points.
• Each (sub-)question is assigned a value found in parenthesis next to it.
• This is an open book examination. All documentation is permitted.
• Faculty standard calculator permitted only.
• This examination consists of 3 pages including title page.

 Suggestion: look at all the questions and their values before you start answering.

Question 1. DES (20 points)

Consider the following plaintext

00001111 00001111 00001111 00001111 00001111 00001111 00001111 00001111

and DES key (including parity bits in bold)

00001110 00001110 00001110 00001110 00001110 00001110 00001110 00001110

Calculate the first and last bits of R0 , L0 , R1 and L1. (8 bits altogether)

Show all your intermediate calculations.

Question 2. Number Theoretic Algorithms (15 points)

Consider the following number theoretic problems:

A: Factoring a product of two primes n=p*q

B: Deciding quadratic residuosity modulo a prime p

C: Deciding quadratic residuosity modulo a product of two primes n=p*q

D: Extracting square roots modulo a prime p

E: Extracting square roots modulo a product of two primes n=p*q

F: Extracting discrete logarithms modulo a prime p

G: Extracting discrete logarithms modulo a product of two primes n=p*q

H: Computing Legendre symbols

J: Computing Jacobi symbols

For each of these, say if it is EASY or HARD, meaning that

EASY: we know an efficient (probabilistic or deterministic) algorithm to solve it

HARD: we do not know any efficient (probabilistic or deterministic) algorithm to solve it

When a problem is HARD, list the other problems that would be EASY if this one was.

Example (false) : J is HARD and C,F,H would be EASY if J was EASY.

Question 3. Double RSA (10 points)

Alice is a bit paranoid. She already has a public RSA key (n,e) (and related private key d) but has decided to supplement it with another exponent e* (and related private key d*). Her new public key is now (n,e,e*). She requests everyone to double encrypt messages (m) for her as RSAe*(RSAe(m)) for more security.

Explain why doing this is completely pointless…

Question 4. Public Identification (10 points)

Consider the following identification system using a universally accepted public prime p and generator a. Suppose Alice is a smart-card whose public identity is given by a value b = a a mod p. The smart-card proves its identity by signing (with the ElGamal signature scheme) a message chosen by the verifier Bob. Bob checks the validity of the signature to confirm Alice’s identity. Whenever Alice needs randomness she uses a pseudorandom number generator (unknown to Bob). However, when the smart-card is turned off it resets to the same standard state and will use the same pseudorandom sequence next time around...

What is wrong with this identification protocol ?

Question 5. Short and Sweet (25 points)

(a) (4 points)

Explain the "property" of Enigma that made it more vulnerable to "known plaintext" attacks.

(b) (5 points)

Use the notion of entropy to define a perfect authentication code.

(c) (4 points)

Explain the difference between "weakly collision free" and "strongly collision free".

(d) (6 points)

Show how to construct a PRBG from a PRFG.

(e) (6 points)

Explicit the computational assumptions underlying the security of the ElGamal Cryptosystem (3 points) and Signature scheme (3 points).

Question 6. Triangle (20 points)

(a) Extend the Diffie-Hellman Key Exchange protocol to allow three people, Alice, Bob and Charles, to distribute among themselves a common cryptographic key publicly.

(b) Explicit the computational assumption underlying the security of your protocol and compare it with the standard Diffie-Hellman assumption (is it stronger, weaker or equivalent?) .