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

bert <bert.hutchings@xxxxxxxxxxxxxx> wrote:
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...

Sorry. I'll try to sketch the argument below, with as little
mathematics as possible.

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)).

I guess hcf is greatest common divisor (gcd).

This describes the possible decryption exponents, but does not actually
prove that they are valid decryption exponents.

For any x with gcd(x, n) = 1, the order of x divides lambda(n), that is,

x^lambda(n) = 1 (mod n) .

Second, gcd(p-1,q-1) must be at least 2, so lambda(n) <= phi(n)/2.
If 1 < d < phi(n)/2 is the inverse of e, then d+lambda(n) is also a
valid decryption exponent, since for any m relatively prime to n,

(m^e)^(d+lambda(n)) = (m^e)^d (m^e)^lambda(n) = m (mod n).

Filling in the missing cases should be easy. If it isn't, please
ask.

--
Kristian Gjøsteen
.