286 16. Answers to Exercises
sage the next morning will not be meaningful. But now Bob has the ad-
vantage: He can try out all “random but meaningful” keys, since there are
not so many of them.
15.6 Public Key Cryptography
15.6.1. (a) Pick random numbers (public keys)e 1 ,e 2 ,...eMand apply
the hypothesized algorithm to compute the the corresponding secret keys
d 1 ,d 2 ,...,dM. The numberk=(p−1)(q−1) is a common divisor of
e 1 d 1 − 1 ,e 2 d 2 − 1 ,...,eMdM−1, so it is a divisor ofK = gcd(e 1 d 1 −
1 ,e 2 d 2 − 1 ,...,eMdM−1), which we can compute. IfK<m, then we
know that in factk=K, sincek=(p−1)(q−1)>pq/2=m/2. Otherwise
we pick another public keyeM+1and repeat. One can show that after no
more than about logmiterations, we findkwith large probability.
(b) If we knowm=pqandk=(p−1)(q−1), then we knowp+q=m−k+1,
and sopandqcan be determined as the solutions of the quadratic equation
x^2 −(m−k+1)x+m=0.