tutorial.kabarku.com

Java

Proof of the RSA Algorithm

09-Mar-2010 12:04:35

Given positive integers n, e, and d such that

(1) n = pq, where p and q are distinct primes
(2) gcd (e, ϕ(n)) = 1
(3) de ≡ 1 (mod ϕ(n))

Define the public and private key algorithms of a message m to be respectively, for 0 ≤ m < n,

(4) RSAPublic(m) = me mod n,
(5) RSAPrivate(m) = md mod n.

Prove that

(6) m = RSAPrivate (RSAPublic(m)), and that

(7) m = RSAPublic (RSAPrivate(m)).

(Prove that the two algorithms (6) and (7) can be used inversely to obtain the message m, or "Does RSA Encryption actually work?")

Proof. By substituting equations (4) and (5) into (6) and (7) respectively, we can say that

RSAPrivate (RSAPublic(m)) = (me mod n)d mod n

= mde mod n.

We can also say that

RSAPublic (RSAPrivate(m)) = (md mod n)e mod n

= mde mod n.

Therefore, equations (6) and (7) are equivalent, or

RSAPrivate (RSAPublic(m)) = RSAPublic (RSAPrivate(m)).

If we can prove

m = mde mod n

Then the proof will be complete.

It is given that

(3) de ≡ 1 (mod ϕ(n)).

By definition of mods we can write (3) as

(8) ϕ(n) l de - 1.

Since ϕ(n) = ϕ(p)ϕ(q) only when p and q are relatively prime, as in this case, we have

ϕ(n) = ϕ(p)ϕ(q)

And by substitution into (8) we have

ϕ(p)ϕ(q) l de - 1.

By properties of divisors, we can write

ϕ(p) l de - 1,

ϕ(q) l de - 1

Where there must be an integer k such that

de - 1 = kϕ(p).

Since p is prime, the Euler phi function states that ϕ(p) = p - 1, so

(9) de - 1 = k(p - 1).

By the symmetric property of mods, we can write

mde ≡ mde (mod p)

≡ mde - 1 + 1 (mod p)

Which can also be written as

(10) mde ≡ (mde - 1) * m (mod p).

Substituting (9) into (10), we obtain

(11) mde ≡ (mk(p - 1)) * m (mod p).

Since p is prime, any integer m for (11) will be either 1) relatively prime to p or will 2) be a multiple of p.

When 1) m is relatively prime to p, Fermat's Little Theorem states that

mp - 1 ≡ 1 (mod p).

By properties of mods, we can write

mk(p - 1) ≡ 1k (mod p), or

(12) mk(p - 1) ≡ 1 (mod p).

By combining (11) and (12), we obtain

mde ≡ 1 * m (mod p), or

(13) mde ≡ m (mod p).

In the second case where 2) m is a multiple of p, if

p l m, then for any integer k

p l mk.

From the properties of mods we can write

mde ≡ 0 (mod p),

m ≡ 0 (mod p).

Thus we can write

mde ≡ m (mod p).

Therefore, for all m,

mde ≡ m (mod p), and applying the same process for q we can write

mde ≡ m (mod q).

By the modular property of congruence which states that when m and n are relatively prime (as in our given statements), a ≡ b (mod m), and a ≡ b (mod n), then a ≡ b (mod mn), we can write

mde ≡ m (mod pq)

≡ m (mod n).

By the modular property of symmetry, we can write

(15) m ≡ mde (mod n).

Since we have limited m to 0 ≤ m < n, only one integer will satisfy (15), and so

(16) m = mde mod n.

If we substitute (16) with our original equations

RSAPrivate (RSAPublic(m)) = mde mod n, and

RSAPublic (RSAPrivate(m)) = mde mod n

We obtain, for 0 ≤ m < n,

RSAPrivate (RSAPublic(m)) = m, and

RSAPublic (RSAPrivate(m)) = m.