RSA Principle 5

Proving

Why?

$$c^d \equiv m \quad (mod \quad n)$$

Base on encrypt rule:

$$m^e \equiv c \quad (mod \quad n)$$

->

$$c = m^e - kn$$

Put it into the target

$$(m^e - kn)^d \equiv m \quad (mod \quad n)$$

The n in left part of equal could all be divided by n. So it’s same as this:

$$m^{ed} \equiv m \quad (mod \quad n)$$

Bacause

$$ed \equiv 1 \quad(mod \quad\phi(n))$$

->

$$ed = h\phi(n) + 1$$

Put it into above, prove this work

$$m^{h\phi(n) + 1} \equiv m \quad (mod \quad n)$$

Then divide into two condition

m and n has coprime relation

In this condition base on euler theorem

$$m^{\phi(n)} \equiv 1 \quad (mod \quad n)$$

Put it into above:

$$(m^{\phi(n)})^h \times m \equiv m \quad (mod \quad n)$$

Proved

m and n has no coprime relation

In this condition, bacause m and n has no coprime relation, so m and n must have common factor that is not 1.
n come from two coprime factor p and q, so m must multiply with p or q.
m = kp or m = kq

Choose m = kp for example
Because q is a coprime number, and k has no possible multiply q[or will cross m], so k and q has coprime relation.
Base on euler theorem:

$$\varphi(q) = q-1$$ $$(kp)^{q-1} \equiv 1 \quad (mod \quad q)$$

Further

$$[(kp)^{q-1}]^{h(q-1)} \times kp \equiv kp \quad (mod \quad q)$$

Bascause

$$ed = h\phi(n) + 1$$

so:

$$(kp)^{ed} \equiv kp \quad (mod \quad q)$$ $$(kp)^{ed} = kp + tq$$

This time t definitely could be divided be p. Why?

$$p((kp)^{ed-1}-k) = tq$$

$((kp)^{ed-1}-k)$ is an integer and p q has coprime relation
So definitely has integer $t’ = t/p$

$$(kp)^{ed} = kp + t'pq$$

m=kp, n=pq then:

$$m^{ed} = m \quad (mod \quad n)$$

Proved