Faculty of Science
Final Examination
Computer Science 308-547A
Cryptography and Data Security
Examiner: |
Prof. Claude Crépeau |
Date: |
Dec. 18, 2000 |
Associate Examiner: |
Prof. David Avis |
Time: |
9:00 — 12:00 |
INSTRUCTION:
Suggestion: read all the questions and their values before you start answering. |
Question 1. Combining RSA and El Gamal (20 points)
Alice is a bit paranoid. She has a public RSA key (n,e) (and related private key d) but has decided to supplement it with an El Gamal public key (p,g,a,b=a^{a} mod p) (and related private key a).
Question 2. Enigma (10 points)
Consider the following Enigma ciphertext c and plaintexts p_{1},p_{2},p_{3},p_{4},p_{5} :
c_{1}:loteq nfaxz plued mcbge hhedw iiedw luhve yfbcw uhuhj lmqad yrscf …
p_{1}:Diesi stein eJAVA Imple menta tiond esbek annte nWUrf elsvo nRubi …
p_{2}:Puzzl eSpie lzeug derfr Uhen8 0erJa hreer lebtm itRub iKsGa messe …
p_{3}:MitRu biKsG amesf UrPCC DROMz eigtH asbro Inter activ eeinm almeh …
p_{4}:Dochk eineA ngstb eiall enRub ikVar iante nsind versc hiede neSch …
p_{5}:MitSm ische nSied enRub iksCu bedur chmit Rsetz enSie Ihnwi ederi …
for each of these five plaintexts p_{i} (1£i£5), say whether or not ciphertext c is a possible encryption of p_{i}.
Question 3. Shared RSA (20+5 points)
Alice is a bit hypochondriac. She has a public RSA key (n,e) (and related private key d) but has decided to provide her best friends Bob and Cole with private keys d_{b},d_{c} such that d=d_{b}*d_{c} mod f(n), in case she dies.
Question 4. Private Key cryptosystem (10 points)
Consider the following family of permutations { p_{k} : {0,1}^{2n} Æ {0,1}^{2n} }_{k} defined from a Pseudo-Random Function Generator { f_{k} : {0,1}^{n} Æ {0,1}^{n} }_{k} :
p_{k}(x,y) = [ y , x‰f_{k}(y) ]
Explain how Alice and Bob could share a secret key k_{ }and use both p_{k} and p_{k}^{-1} to do encryption/decryption of bit-strings of size n. What would be the security properties of such a system ? (Make the strongest possible statement among - "cipheretext only attack" - "known plaintext attack" - "chosen plaintext attack" - "chosen ciphertext attack" - and justify your answer).
Question 5. Short and Sweet (25 points)
(a) (4 points)
Explain the difference between the concepts of "digital signature" and "undeniable signature".
(b) (5 points)
In the Diffie-Hellman key exchange protocol with public parameters (p,g), exhibit one bit of information about the key g^{ab} mod p that can be easily computed from g^{a} mod p and g^{b} mod p.
(c) (4 points)
Suggest a simple way of reducing the redundancy of English without loosing any of its expressive power.
(d) (6 points)
Show how to construct a cryptographic hash function using x^{2} mod n and argue that it is collision free.
(e) (6 points)
Modify the OFB and CFB modes of DES so that the encryption schemes remain the same but in a way that only the decryption function of DES is used to do the decryption of long messages.
Question 6. Small RSA (15 points)
Define, for n=pq, the function l(n)=f(n)/gcd(p-1,q-1). An extension of Euler's theorem is that for all x, 0<x<n, such that gcd(x,n)=1, we have x^{ l(n)} † 1 (mod n).