Modern Cryptology (236506) – Exercise no. 5

Technion – Israel Institute of Technology, Computer Science Department
23/12/2014
Modern Cryptology (236506) – Exercise no. 5
Submission in singles until 6/01/2015.
5 bonus points will be given to two sided, printed submissions.
1. Bob uses the RSA encryption with the public key: (n, e) = (187, 23). Alice encrypted a
message for Bob, and sent him the encrypted message, which was 11. What was the original
message Alice sent? Explain your calculations.
2. A student observed that in the Diffie-Hellman key exchange protocol, user U publishes YU =
g XU mod p, where p is a known large prime number, and g ∈ Zp∗ is an element of high order
in Zp∗ . In this question we assume that g is a generator.
(a) Given p, g, YU = g XU mod p, show how to reveal the least significant bit of xU .
His friend proposed the following algorithm to compute DLOGs, given an algorithm that
computes the least significant bit of XU :
• Compute the least significant bit of XU .
• If the LSB is 1, let YU0 = YU · g −1 , otherwise let YU0 = YU .
• Compute the square root of YU0 , and repeat the algorithm on the square root until
YU0 = 1. (As we will see in class, there exists an efficient algorithm that computes the
square roots of a QR modulo a prime number.)
• By collecting the LSBs one can reconstruct XU .
(b) Show that each YU0 is a quadratic residue modulo p.
(c) Let X 0 be the number composed of the LSBs computed by the algorithm. Show that X 0
0
satisfies g X ≡ YU (mod p). Conclude that the secret key of U is XU ≡ X 0 (mod p − 1).
(d) Explain why the above algorithm cannot compute the DLOG XU in spite of the above.
3. This question deals with weaknesses of the ElGamal signature scheme.
(a) Show that given a legal signature (R, S) on a message m, an attacker can compute
signatures for messages of the form m0 ≡ (m + bS)a (mod p − 1), where b ∈ Z∗p can be
chosen arbitrarily and a ≡ g b (mod p).
Hint: Look at the value of g ma+baS (mod p).
(b) Show that the ElGamal scheme is vulnerable to existential forgery attacks. I.e., show
that an attacker can produce a combination of a message m and a legal signature on it
(R, S), but he cannot necessarily choose the value of m.
Hint: Choose R to be of the form R ≡ g α+βx (mod p − 1) for some α, β ∈ Zp such that
gcd(β, p − 1) = 1 (in practice, α and β are chosen randomly).
1
4. The following generalization of the Diffie-Hellman algorithm was suggested:
• Choose two large prime numbers p, q, and compute n = pq.
• Choose g ∈ Zn∗ .
• Each user chooses ru ∈ Zn , and computes his public key g ru mod n.
(a) Show that in this settings, two users can use the original Diffie-Hellman algorithm (with
the modified modulus and keys) to share a secret.
(b) Suppose ALG is an algorithm that solves the generalized DH problem: given x, xra , xrb ,
and n, find xra rb mod n.
Show how to use this algorithm to solve the RSA problem: given n, e, and me mod n,
find m mod n.
(c) Suppose ALG2 is an algorithm that solves the RSA problem for all e ∈ Zn∗ . Can you
use ALG2 to solve the generalized Diffie-Hellman problem? Explain your answer.
5. Random self reducibility of DLOG.
Let p be a prime and let g ∈ Zp∗ be a generator. Suppose that there exists a polynomial-time
1
algorithm A that given p, g, g x mod p finds x for 1000
of the possible x’s. Show how to use A as
a subroutine to construct a probabilistic polynomial time algorithm B that solves the DLOG
problem for all instances (i.e., for every x ∈ Zp−1 ) with probability 32 . Analyze the running
time of B as a function of the running time of A and the length of the binary representation
of p.
2

Download Report