Re: RSA: more than one secret exponent d exists ???

georgezhim@xxxxxxxxx wrote:
hi all,

In a given RSA system with public (n,e), how do I prove that there
exist more than
one possible secret exponent d that works ?
In other words, how can I show that there exists d' < phi(n), d' !=
e^(-1) mod(phi(n))
which correctly decrypts every message C =m^e modn ?

thanks alot!!
George

I don't know enough real mathematics to understand
Kristian Gjosteen's replies in this thread either, but...

If n = p*q, phi(n) = (p-1)*(q-1) as I'm sure you already
know, but take lambda(n) = phi(n)/hcf(p-1, q-1), and
d = e^(-1) mod(lambda(n)). Then there at least two
exponents, d and d + lambda(n), which correctly
decrypt every message. In fact there are precisely
hcf(p-1, q-1) such exponents less than phi(n), only
one of which is e^(-1) mod(phi(n)).
--

.