RSA

Generating public key and private key

1. Select two distinct prime \(p\) and \(q\) .
2. Calculate the \(n\), product of \(p\) and \(q\) .
3. Calculate the \(\varphi(n)=(p-1)(q-1)\) .
4. Randomly select an integer \(e(1 and co-prime with \(\varphi(n)\) .
5. Calculate the \(d\) , inverse of \(e\) for \(\varphi(n)\) .
6. Put \(n\) and \(e\) as the public key, and \(n\) and \(d\) as the private key.

Encrypt and decrypt

Assume that \(m\) is the message that Bob need to send to Alice, now we need to encrypt the \(m\) .

1. Calculate \(c\) satisfied followed formula

   \[m^e \equiv c \mod{n} \]

2. Bob sends \(c\) to Alice.

3. It's proved that followed formula is established.

   \[c^d\equiv m\pmod{n} \]

4. Alice can solve the formula and get \(m\) .

Proving

Because

\[m^e\equiv c\pmod{n} \]

so \(c\) can be denoted as

\[c=m^e-kn \ (k\in \mathbb{Z}) \]

then plug this formula into the formula we need to prove

\[(m^e-kn)^d\equiv m\pmod{n} \]

it's equivalent to prove

\[m^{ed}\equiv m \pmod{n} \]

According to

\[ed\equiv 1\pmod{\varphi(n)} \]

we know

\[ed=h\varphi(n)+1 \ (h\in\mathbb{Z}) \]

so

\[m^{h\varphi(n)+1}\equiv m\pmod{n} \]

if \(m\) is co-prime with \(n\) , then

\[m^{\varphi(n)}\equiv1\pmod{n} \]

so

\[(m^{\varphi(n)})^h\times m \equiv m\pmod{n} \]

if \(m\) isn't co-prime with \(n\), then we can assume \(m\) must be \(tq\) or \(tp\) \((t\in \mathbb{Z})\) .

so

\[(tp)^{q-1}\equiv 1\pmod{q} \]

what's more,

\[[(tq)^{q-1}]^{h(p-1)}\times tp\equiv tp\pmod{q} \]

it's

\[(tp)^{ed}\equiv tp\pmod{q} \]

rewrite it

\[(kp)^{ed}=xp+xq \]

we can infer out that \(x\) must can be integral divided by \(p\) , it said \(x=x'p\) .

\[(kp)^{ed}=x'q+xq \]

because \(m=tp,n=pq\)

\[m^{ed}\equiv m\pmod{n} \]