Faculty of Science
Final Examination

Computer Science 308-547A
Cryptography and Data Security

Examiner:

Prof. Claude Crépeau

Date:

### Dec 3rd, 2001

Associate Examiner:

Prof. David Avis

Time:

9:00 – 12:00

INSTRUCTION:

·         This examination is worth 50% of your final grade.

·         The total of all questions is 110 points.

·         Each 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 6 questions on 3 pages, including title page.

 Suggestion: read all the questions and their values before you start.

#### Question 1. Easy bits (12 points)

Let p be an odd prime and g be a primitive element mod p.

• Show that given p, g, gx mod p, the predicate lsbp(x) is easy to compute.

• Show that given p, g, ga mod p, gb mod p there is a predicate of gab mod p that is easy to compute.

#### Question 2. Public Identification (20 points)

Consider the following identification system using a 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.

• When Alice wants to identify to Bob, she picks a random message m and signs it (with the ElGamal signature scheme). She gives Bob the message m and its signature s. Bob can check the signature from Alice’s public key (Bob keeps track of Alice’s ms to prevent replay attacks). What is (still) wrong with this identification protocol ?

• 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 exact same pseudo-random sequence next time around. What is wrong with this identification protocol ?

#### Question 3. Number Theoretic Algorithms (15 points)

Consider the following number theoretic problems:

(1) :   Computing Legendre symbols

(2) :   Computing Jacobi symbols

(3) :   Deciding quadratic residuosity modulo a prime p

(4) :   Deciding quadratic residuosity modulo a product of two primes n=p*q

(5) :   Factoring a product of two primes n=p*q

(6) :   Extracting square roots modulo a prime p

(7) :   Extracting square roots modulo a product of two primes n=p*q

(8) :   Extracting discrete logarithms modulo a prime p

(9) :   Extracting discrete logarithms modulo a product of two primes n=p*q

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 don’t 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.

(false) Example : (1) is HARD and (9),(2),(6) would be EASY if (1) was EASY.

#### Question 4. WC class (20 points)

Consider the following class of hash functions {0,1}m ® {0,1}m

HM = { h(x)= (Mx)Åb |  M is an mxm matrix over F2, and b is an m-bit vector }

• Show that HM is a strongly universal2 class of hash functions.

• Show that for any a of F2m, there exists an mxm matrix A such that for all x of F2m

a•x = Ax

where the leftmost product is over F2m, whereas the rightmost is the product over F2 of a matrix by a vector.

( Thus showing that H1 = { h(x)= a•xÅb |  a,b are over F2m } is a subclass of HM. )

• If you are unable to show the result in general, for partial credits, provide the matrix A0 corresponding to a=0 and the matrix A1 corresponding to a=1.

#### Question 5. Short and Sweet(25 points)

(a) (5 points)

Which “component” of DES makes it less vulnerable to differential cryptanalysis attacks?

(b) (5 points)

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

(c) (5 points)

Explain how compression improves the security of most cryptosystems.

(d) (5 points)

Show how to construct a PRBG from a PRFG.

(e) (5 points)

Explain why in AES more rounds of encryption are used when longer keys are used.

#### Question 6. Block-ciphers à la modes (18 points)

• For each of CBC, CFB, and OFB modes explain why it is suitable or not to combine with a PKC.