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=aa mod p) (and related private key a).

  1. Explain how Alice can sign messages using both systems in such a way that an adversary must break both signature schemes in order to forge her signature.
  2. Explain how Bob can encrypt messages for Alice using both systems in such a way that an adversary must break both cryptosystems in order to discover the message transmitted.

 

 

Question 2. Enigma (10 points)

 

Consider the following Enigma ciphertext c and plaintexts p1,p2,p3,p4,p5 :

c1:loteq nfaxz plued mcbge hhedw iiedw luhve yfbcw uhuhj lmqad yrscf …

p1:Diesi stein eJAVA Imple menta tiond esbek annte nWUrf elsvo nRubi …

p2:Puzzl eSpie lzeug derfr Uhen8 0erJa hreer lebtm itRub iKsGa messe …

p3:MitRu biKsG amesf UrPCC DROMz eigtH asbro Inter activ eeinm almeh …

p4:Dochk eineA ngstb eiall enRub ikVar iante nsind versc hiede neSch …

p5:MitSm ische nSied enRub iksCu bedur chmit Rsetz enSie Ihnwi ederi …

for 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.

  1. Show that individually db or dc is useless to decipher messages encrypted with (n,e).

  2. Show how Bob and Cole can decrypt a ciphertext c intended to Alice without revealing db or dc.

  1. Show how they can make sure that the decryption process was successful.

  2. Show how they can convince each other that they jointly have the power to decrypt ciphertexts intended for Alice without revealing db or dc to each other, before such a ciphertext is given to them.

  3. (5 bonus points) Show that if they share db and dc then they can factor n and compute d.

 

 

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 :

pk(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).

  1. Let (n,e) be an RSA public key and d be the corresponding RSA private decryption key. Show that for at least half the e's, there exists a d', 0<d'<l(n)<d, such that d' may be used to decrypt instead of d.

  2. Discuss the pros and cons of having gcd(p-1,q-1) be fairly large with respect to n, in terms of efficiency and security.