Book An Introduction to Number Theory with Cryptography Craf

Book: (An Introduction to Number Theory with Cryptography. Craft and Washington)

Solution

Suppose gcd(m, n) = 1. The relation ed 1 (mod (n)) gives that ed = 1 + k(n) for some integer k. If c m^e (mod n) then, working modulo n,

c^d m^ed
   m^1+k(n)
   m.(m⁽ⁿ⁾)^k
   m.1^k, since m⁽ⁿ⁾ 1 (mod n), by the Euler-Fermat theorem, as gcd(m, n)=1
   m (mod n).

Hence m = c^d mod n is a unique integer in the range 0 m < n.

uppose one of the primes, say q, divides m. Then m 0 (mod q) and so, trivially, we have

0 m^1+k(n) m (mod q).

If q divides m then p cannot also divide m since m < n = pq and so we must have gcd(m, p) = 1. By Fermat\'s Little Theorem we have

m^p-1 1 (mod p)
m^(p-1)(q-1) 1^q-1 1 (mod p), raising both sides to the power q-1
m⁽ⁿ⁾ 1, since (n) = (pq) = (p-1)(q-1)
m^k(n) 1^k 1 (mod p), raising both sides to the power k
m^1+k(n) m (mod p), multiplying both sides by m.

Now since m^1+k(n) m (mod q) and m^1+k(n) m (mod p), and p and q are coprime, then it follows that (see † above)

m^1+k(n) m (mod pq) m (mod n), for all integers m.

We have ed 1 (mod (n)) ed = 1 + k(n). So, if c m^e (mod n) then c^d m^ed m^1+k(n) m (mod n). Hence m = c^d mod n is a unique integer in the range 0 m < n.

The original version of RSA defined the secret exponent as d = e^-1 (mod (n)), where is the Euler totient function and (n) = (pq) = (p-1)(q-1). In fact you can use the smaller Charmichael function instead, so that an alternative secret exponent (we\'ll call it d\') is defined by d\' = e^-1 (mod (n)), where (n) = lcm(p-1, q-1) = (p-1)(q-1)/gcd(p-1, q-1). Later refinements of the RSA algorithm like PKCS#1 use this definition.

But it doesn\'t matter which one you use. Both d and d\' will give you the same results.

Note that the proofs above use the fact that x^1+k(n) x (mod n) for any integer x. Well, by definition, x⁽ⁿ⁾ 1 (mod n), so we can just write x^1+k(n) x (mod n), and all the proofs will still work.

Both values of d and d\' will uniquely decrypt a message c encrypted with c = m^e mod n, and both will give the same signature s = m^d mod n = m^d\' mod n.

In fact, any secret exponent of the form d\' + r(n) will work, for any integer r. Since (n) divides (n), then our d is one of these.