Faculty
of Science
Final Examination
Computer
Science 308547A
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. 
Let p
be an odd prime and g be a primitive element mod p.
• Show that
given p, g, g^{x} mod p, the predicate lsb_{p}(x)
is easy to compute.
• Show that
given p, g, g^{a} mod p, g^{b} mod p
there is a predicate of g^{ab} mod p that is
easy to compute.
Consider the
following identification system using a public prime p
and generator a. Suppose Alice is a smartcard
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
smartcard 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 smartcard is
turned off it resets to the same standard state and will use the exact same
pseudorandom sequence next time around. What is wrong with this
identification protocol ?
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.
Consider the
following class of hash functions {0,1}^{m} ®
{0,1}^{m}
H_{M}
= { h(x)=
(Mx)Åb
 M is an mxm
matrix over F_{2}, and b
is an mbit vector }
• Show that H_{M}
is a strongly universal_{2}
class of hash functions.
• Show that
for any a of F_{2}m,
there exists an mxm matrix A
such that for all x of F_{2}m
a•x
= Ax
where the
leftmost product is over F_{2}m,
whereas the rightmost is the product over F_{2} of
a matrix by a vector.
(
Thus showing that H_{1} = {
h(x)= a•xÅb
 a,b are over F_{2}m }
is a subclass of H_{M}.
)
• If you are
unable to show the result in general, for partial credits, provide the matrix A_{0}
corresponding to a=0 and the matrix A_{1}
corresponding to a=1.
(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.
• For each of CBC, CFB, and OFB modes explain why it is suitable or not to combine with a PKC.