Correctness Proof of RSA
Yufei Tao
Department of Computer Science and Engineering
Chinese University of Hong Kong
Correctness Proof of RSA
The previous lecture, we have learned the algorithm of using a pair of
private and public keys to encrypt and decrypt a message. In this lecture,
we will complete the discussion by proving the algorithm’s correctness.
Correctness Proof of RSA
We will need some definitions and theorems from number theory.
Definition
Given an integer p > 0, define Zp as the set {0, 1, ..., p − 1}.
If a = b (mod p), then all the following hold for any integer c ≥ 0:
a+c = b + c (mod p)
a−c = b − c (mod p)
ac = bc (mod p)
c
a = b c (mod p)
Correctness Proof of RSA
Theorem
Let a, p be two integers that are co-prime to each other. Then, there is
only a unique integer x ∈ Zp satisfying
ax = b (mod p)
regardless of the value of b.
The proof is elementary and left to you.
Example: In Z8 , 3x = 2 has a unique x = 6.
Corollary
If a and p are co-prime to each other, then 0, a, 2a, ..., (p − 1)a are all
distinct after modulo p.
Correctness Proof of RSA
Theorem (Fermat’s Little Theorem)
If p is a prime number, for any non-zero a ∈ Zp , it holds that
ap−1 = 1 (mod p).
Example: In Z5 , 14 = 1 (mod p), 24 = 1 (mod p), 34 = 1 (mod p), and
44 = 1 (mod p).
Proof.
By the corollary in Slide 4, we know that a, 2a, ..., (p − 1)a after modulo
p have a one-one correspondence to the values in {1, 2, ..., p − 1}.
Therefore:
a · 2a · ... · (p − 1)a = (p − 1)! (mod p).
p−1
⇒a (p − 1)! = (p − 1)! (mod p).
The above implies ap−1 = 1 (mod p).
Correctness Proof of RSA
Theorem (Chinese Remainder Theorem)
Let p and q be two co-prime integers. If x = a (mod p) and
x = a (mod q), then x = a (mod pq).
Example: Since 37 = 2 (mod 5) and 37 = 2 (mod 7), we know that 37
= 2 (mod 35).
Proof.
Let b = x (mod pq). We will prove b = a. Note that b < pq.
First observe that because x = a (mod p), we know b = a (mod p).
Similarly, b = a (mod q). Hence, we can write b = pt1 + a = qt2 + a for
some integers t1 , t2 . This means that pt1 = qt2 , and they are a common
multiple of p and q. However, as p and q are co-prime, the smallest
non-zero common multiple of p and q is pq. Given the fact that b < pq.
we conclude that pt1 = qt2 = 0.
Correctness Proof of RSA
Review: RSA Preparation
Bob carries out the following:
1 Choose two large prime numbers p and q randomly.
2 Let n = pq.
3 Let φ = (p − 1)(q − 1).
4 Choose a large number e ∈ [2, φ − 1] that is co-prime to φ.
5 Compute d ∈ [2, φ − 1] such that
e ·d = 1 (mod φ)
There is a unique such d. Furthermore, d must be co-prime to φ.
6 Announce to the whole word the pair (e, n), which is his public key.
7 Keep the pair (d, n) secret to himself, which is his private key.
Correctness Proof of RSA
We now prove the statement at line 5 of the previous slide:
There is a unique such d.
Proof.
Follows directly from the theorem in Slide 4.
d must be co-prime to φ.
Proof.
Let t be the greatest common divisor of d and φ, and suppose d = c1 t
and φ = c2 t. From ed = 1 (mod φ), we know ed = c3 φ + 1 for some
integer c3 . Hence:
ec1 t = c3 c2 t + 1
⇒ t(ec1 − c3 c2 ) = 1
which implies t = 1.
Correctness Proof of RSA
RSA Review: Encryption and Decryption
Encryption: Knowing the public key (e, n) of Bob, Alice wants to send a
message m ≤ n to Bob. She converts m to C as follows:
C = me (mod n)
Decryption: Using his private key (d, n), Bob recovers m from C as
follows:
C d (mod n)
Correctness Proof of RSA
Theorem (RSA’s Correctness)
m = C d (mod n).
Proof.
It suffices to prove m = C d (mod p) and m = C d (mod q), because they
lead to m = C d (mod n) by the Chinese Remainder Theorem.
First, we prove m = C d (mod p). From C = me (mod n), we know
C = me (mod p), and hence, C d = med (mod p). As ed = 1 (mod
(p − 1)(q − 1)), we know that ed = t(p − 1)(q − 1) + 1 for some integer
t. Therefore:
med = m · mt(p−1)(q−1) (mod p)
= m · (m(p−1) )t(q−1) (mod p)
(Fermat’s Little Theorem) = m · (1)t(q−1) (mod p)
= m (mod p)
By symmetry, we also have med = m (mod q).
Correctness Proof of RSA