Faculty of Science
Computer Science 308-547A
Prof. Claude Crépeau
Dec. 10, 1999
Prof. David Avis
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 generatora. 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 Alices 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?) .