Question

In the RSA cryptosystem, Alice’s public key (N, e) is available to everyone. Suppose that her private key d is compromised and becomes known to Eve. Show that if e = 3 (a common choice) then Eve can efficiently factor N.

Answer 1

Solution:

From the RSA cryptosystme specification, recall that ed ≡ 1 (mod φ(N)). Thus, there exists an integer k, such that ed −1 = kφ(N). Replacing φ(N) with (p−1)(q−1), we get

(or)

First pick an appropriate message m such that m(ed−1/2) is neither 1 nor −1 mod N.

Then m^(ed−1) ≡ 1 mod N ⇒ (m(ed−1/2) −1)(m(ed−1/2)+1) ≡ 0 mod N ⇒one of the gcd(N, (m(ed-1)/2 −1)) or

gcd(N, (m(ed−1/2) +1) is a non-trivial factor of N.

Since N = qp and we have determined, say p,

we can just divide

N/p = q.

--------------------------------------------------------------------------------------------------------------------------------

Hope it helps. Please upvote if you are happy with the answer