Doubt in RSA Key Pair Generation - Follow-up

From: Sijo (s1717_at_rediffmail.com)
Date: 12/29/04 

Date: 28 Dec 2004 22:16:17 -0800

Many thanks to all those who replied :-)

So,we can have many "d" values for a particular "e", and specifically
in this example, we have d = 7, 27, 47...(or even 17,37,57...). But,
the decryption should return the same result for all these "d" values.

Let "m"(=7) be the original value and "c" be the encrypted value.

Encryption
----------
c=m^e mod n
Here, c=7^3 mod 33 = 343 mod 33 = 13.

Decryption
----------
Also, m=c^d mod n.
i.e m=13^7 mod 33 or 13^27 mod 33. or 13^47 mod 33.

Let me take the second one, i.e m=13^27 mod 33.
i.e m = ( 13^7 mod 33 * 13^20 mod 33) mod 33
       = (7 * 13^20 mod 33 ) mod 33

So, we must have 13^20 mod 33 = 1. (And it is !)

So, can we generalize it?

Is it true? c^phi mod n = 1 (where c < n)

or m^phi mod n =1 (where m < n) [Used m instead of c as they are
from the same set]

or m^(k*phi) mod n = 1 (where m < n, k is a positive integer)

regards
Sijo