VE475 Introduction to Cryptography Homework 7 Solved

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 ⌊230√i⌋ 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 + x2. Study the functions f and g over [0, 1/2] and conclude that over this interval

−x − x2 ≤ ln(1 − x) ≤ −x.

2.   Prove that if r ≤ n/2 then

(r − 1)r         r3

______ −____ ≤

2n           3n2


(r − 1)r.

'        n)≤ −______

2n

3.   Let λ = r2/(2n), and suppose λ ≤ n/8. Prove that

e−λec1/sqrtn ≤
jjj (1 −   where c1 = Iλ − (2λ)3/2 and c2 =
'               n),      V2            3                    V2
j=1
 

4.   Prove that when n is large and λ is a constant less than n/8, then r−1~        ~

~ 1 − j ≈ e−λ.
n

j=1

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.