Description
Ex. 1 — Cramer-Shoup cryptosystem
1. Detail the construction of the Cramer-Shoup cryptosystem.
2. Explain why this cryptosystem is secure even against adapative chosen ciphertext attacks (no
formal proof is required, only some basic explanations).
3. Compare this construction to the Elgamal cryptosystem (highlight the similarities and differences).
Ex. 2 — Simple questions
1. Let p be a prime and α be an integer such that p – α. Explain why h(x) ≡ α
x mod p is not a
good cryptographic hash function.
2. Express b2
30√
ic for i = 2, 3, 5 and 10, in hexadecimal. Compare your results to the constants
Ki
, 0 ≤ i ≤ 79, in SHA-1.
Ex. 3 — Birthday paradox
In this exercise we derive the approximation of the probability of having at least one match in a list of
length r over n possible birthdays.
1. Let f (x) = ln(1 − x) and g(x) = ln(1 − x) + x + x
2
. Study the functions f and g over [0, 1/2]
and conclude that over this interval
−x − x
2 ≤ ln(1 − x) ≤ −x.
2. Prove that if r ≤ n/2 then
−
(r − 1)r
2n
−
r
3
3n
2 ≤
Xr−1
j=1
ln
1 −
j
n
≤ −
(r − 1)r
2n
.
3. Let λ = r
2/(2n), and suppose λ ≤ n/8. Prove that
e
−λ
e
c1/sqrtn ≤
rY−1
j=1
1 −
j
n
≤ e
−λ
e
c2/sqrtn, where c1 =
r
λ
2
−
(2λ)
3/2
3
and c2 =
r
λ
2
.
4. Prove that when n is large and λ is a constant less than n/8, then
rY−1
j=1
1 −
j
n
≈ e
−λ
.
Ex. 4 — Birthday attack
Suppose we observe 40 licence plates, each ending with a 3-digit number.
1. What is the probability of seeing two plates ending with the same three digits?
2. Assuming we have one ending with 123. What is the probability that one of the 40 license plates
observed has the same 3 last digits?
3. Explain how these results relate to how Alice overcomes the birthday attack in chapter 5.
Ex. 5 — Faster multiple modular exponentiation
Let α, β, a, b and n be five integers. The most obvious strategy for compute α
aβ
b mod n consists in
using the modular exponentiation (Square and Multiply) algorithm (3.38) to compute α
a mod n, and
β
b mod n and then multiply the results mod n.
1. What is the time complexity of this method?
2. Assuming the product αβ is known, rewrite the square and multiply algorithm, such that at most
one multiplication is calculated at each iteration.
3. Suppose a and b are l bits long; how many squaring and multiplications are necessary to compute
α
aβ
b mod n?
4. Implement the two strategies and compare their speed on large numbers.
