Faculty of Science
Final Examination
Computer Science 308-547A
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=aa mod p) (and related private key a).
Question 2. Enigma
(10 points)
Consider the following Enigma ciphertext
c and plaintexts p1,p2,p3,p4,p5 :c
1:loteq nfaxz plued mcbge hhedw iiedw luhve yfbcw uhuhj lmqad yrscfp1
:Diesi stein eJAVA Imple menta tiond esbek annte nWUrf elsvo nRubip2
:Puzzl eSpie lzeug derfr Uhen8 0erJa hreer lebtm itRub iKsGa messep3
:MitRu biKsG amesf UrPCC DROMz eigtH asbro Inter activ eeinm almehp4
:Dochk eineA ngstb eiall enRub ikVar iante nsind versc hiede neSchp5
:MitSm ische nSied enRub iksCu bedur chmit Rsetz enSie Ihnwi ederifor each of these five plaintexts pi (1£i£5), say whether or not ciphertext c is a possible encryption of pi.
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 db,dc such that d=db*dc mod
f(n), in case she dies.
Question 4. Private Key cryptosystem
(10 points)
Consider the following family of permutations {
pk : {0,1}2n Æ {0,1}2n }k defined from a Pseudo-Random Function Generator { fk : {0,1}n Æ {0,1}n }k :p
k(x,y) = [ y , x‰fk(y) ]Explain how Alice and Bob could share a secret key k and use both
pk and pk-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 gab mod p that can be easily computed from ga mod p and gb 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 x2 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).