Exponential Ciphers - Introduction to Cryptography with Java Applets - page 270

n should be at least 1024 bits in length. Everyone knows n , but not its two factors, p or
q .

2. The receiver then chooses an integer e < n , such that ( e ,( p 1)( q 1)) = 1. The value

for e is made public.

3. The receiver also computes a decryption key, d , which is an inverse of e modulo

( p 1)( q 1). This inverse exists since e was chosen relatively prime to ( p 1)

( q 1). That is, d must satisfy the congruence

ed 1 (mod ( p 1)( q 1)).

The sender of the message can send a message P < n by computing with the encipher-
ing transformation

C P e (mod n ) 0 ≤ C < n .

The receiver gets the ciphertext message C , and can retrieve the plaintext by computing
P C d (mod n ).

5.

This cipher looks remarkably similar to the Pohlig-Hellman exponentiation cipher.
Decryption worked in that case because of Fermat's Little Theorem. FLT will also help us
prove that decryption works here. Note that since

ed 1 (mod ( p 1)( q 1))

there is an integer k such that ed = 1 + k ( p 1)( q 1). Now, suppose the plaintext mes-
sage P is relatively prime to p ; that is, ( P , p ) = 1. Then, by FLT,

P p 1

1 (mod p ).

Thus, we also have the following:

P ed

P 1 k ( p 1)( q 1) P ( P ( p 1) ) k ( q 1) P 1 k ( q 1) P (mod p ).

On the other hand, even if P is not relatively prime to p , we still have

P ed

P (mod p ),

since both sides are congruent to 0 modulo m . Similarly, we can also show that in all cases,

P ed

P (mod q ).
Now, since p and q are certainly relatively prime, by proposition 26 we have

P ed

P (mod n ).

Now, simply note that

C d ( P e ) d

P ed

P (mod n )

and we have our proof that decryption always works, whether or not the plaintext message
P is relatively prime to the modulus n .