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. |
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.
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 ?
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
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.
(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.