This post is about RSA algorithm and its mathematical proofs.

# Overview of Symmetric/Asymmetric Cipher Model

In Symmetric Cipher, Sender (encrypter) and receiver (decrypter) use a single(same) key to encrypt and decrypt the file. If the key is compromised, everything will be compromised too.

Another problem with Symmetric Cipher is that, if the sender and the receiver don’t have chance to share the key beforehand(without letting anyone else to know it), the encrypt method won’t work.

Asymmetric Cipher uses a key pair (private key and public key) separately for decrypting and encrypting processes. The two parts are mathematically related. It’s impossible(at least for today’s computers) to calculate the private key from the public key.

Both parties of the communication generate their own key pair, and post their public keys in plain text on the internet. The sender can now use the receiver’s public key to encrypt a message, it can only be decrypted with the corresponding private key. Of course the private key has to be kept very carefully.

# Usage of RSA

overview:

• It can be used for digital signatures or certificates to prove the authenticity and integrity of a message.
• It’s not generally used to encrypt entire file, because it’s less efficient.
• It can be conbined with other encryption schemes. e.g. use RSA to encrypt the symmetric key, which encrypt the file.
• Systems like: OpenSSL,TLS,PGP,VPNs..

# The math behind RSA:

Note: I only list out the neccessary parts.

# Background Knowledge

Modular arithmetic

all number below are positive integers

0. if $a = k_1 m + c$ and $b = k_2 m + c$, we say $a$ and $b$ are in a congruence relation, which is noted as $a \equiv b \pmod m$
1. $a\equiv a \pmod m$
2. if $a\equiv b \pmod m$ then $b\equiv a \pmod m$ 3. if $a\equiv b \pmod m$ and $b\equiv c \pmod m$ then $a\equiv c \pmod m$
3. if $a\equiv b \pmod m$ and $c\equiv d \pmod m$ then $a\pm c\equiv b\pm d \pmod m$ and $ac\equiv bd \pmod m$
4. if $a\equiv b \pmod m$ then $an\equiv bn \pmod m$
5. if $a\equiv b \pmod m$ then $a^n\equiv b^n \pmod m$

see https://en.wikipedia.org/wiki/Modular_arithmetic for details

Modular multiplicative inverse

$$ax\equiv 1 \pmod n$$

Euler’s Totient Function

1. Euler’s totient function $\varphi(n)$ equals to the count of positive integers that are smaller than n and relatively prime to n.
2. When $n=p\times q$ (p and q are prime numbers), $\varphi(n)=(p-1)(q-1)$

Euler’s theorem

$$a^{\varphi(n)} \equiv 1 \pmod n$$

Specially when n is a prime number (let’s say $p$), Euler’s theorem becomes Fermat’s little theorem.

$$a^{p-1} \equiv 1 \pmod n$$

# Generating the RSA keys

Here is how is the key pair actually generated.

1. First find 2 prime (big enough) numbers p and q
2. Let $n = p\times q$
3. Calculate: $\varphi(n) = (p-1) (q-1)$
4. Find a number $e$, which satisfy that $1<e<\varphi(n)$ and $e$ is relatively prime with n. In practice we often take 65537 as $e$, $65537=2^{16}+1$, is prime.
5. Find the modular multiplicative inverse $d, ed\equiv 1 \pmod {\varphi(n)}$
6. Pack $(n,e)$ as the public key, and $(n,d)$ as the private key.

# Encrypting and Decrypting with RSA keys

Let’s say we have a message $m$, and it will encrypted to code $c$. $m$ must be smaller than $n$. In practice $m$ is ususally the ascii or unicode of each character.

$$m^e \equiv c \pmod n$$$$c^d \equiv m \pmod n$$

Security it’s impossible to find $d$ from $e$ and $n$:

• To find $d$, since $ed \equiv 1 \pmod \varphi(n)$, $\varphi(n)$ must be found first.
• To calculate \varphi(n), must find $p$ and $q$, then calculate $\varphi(n)=(p=1)(q-1)$,(There is no better way to calculate $\varphi(n)$!
• Which is impossible for computer to find p and q from n, when p and q are large enough (e.g. 1024 binary digits).

# Mathematical proofs

# Proving the decrypting proccess:

How do we prove that you can really find the original message through the algorithm above:

$$c^d \equiv m \pmod n \tag{1}$$$$m^e \equiv c \pmod n$$$$c=m^e - kn$$$$(m^e - kn)^d \equiv m\pmod n$$$$m^{ed} \equiv m \pmod n \tag{2}$$

(note: see above: Modular Arithmetic rule 4 and 6)

$$ed\equiv 1 \pmod {\varphi(n)}$$$$ed = h\varphi(n) + 1 \tag{3}$$$$m^{h\varphi(n) + 1} \equiv m \pmod n \tag{4}$$

There are 2 situations:

Situation I. m and n are relatively prime:

$$m^{\varphi(n)} \equiv 1 \pmod n$$$$m^{h\varphi(n)} \equiv 1 \pmod n$$$$m^{h\varphi(n) + 1} = m^{h\varphi(n)} \times m \equiv m \pmod n $$

(4) is proved.

Situation II. m and n are not relatively prime

Since $m<n$ and $n=p\times q$, $m$ must be $k$ times $p$ or $k$ times $q$.

$$(kp)^{\varphi(q)} = (kp)^{q-1} \equiv 1 \pmod q$$$$ [(kp)^{q-1}]^{h(p-1)} \equiv 1 \pmod q$$$$ [(kp)^{q-1}]^{h(p-1) } \times kp \equiv kp \pmod q$$$$ (kp)^{h\varphi(n)} \times kp = (kp)^{h\varphi(n)+1} \equiv kp \pmod q$$$$(kp)^{ed} \equiv kp \pmod q$$$$(kp)^{ed} = kp + tq$$$$ k^{ed}p^{ed-1} = k + \frac{tq}{p} $$

Left hand side and $k$ are all integers, so ${tq}/{p}$ must be integer too.So $t$ must be divisible by $p$ (since $q$ is not).

Let $t=t’p$ then we have:

$$(kp)^{ed} = m^{ed} = t'pq + kp = t'n +m$$$$m^{ed} \equiv m \pmod n$$

(1),(2),(3) are proven!

ref:

What is RSA encryption and how does it work

阮一峰的博客

the comment system on this blog works via email. The button
below will generate a mailto: link based on this page's url 
and invoke your email client - please edit the comment there!

[optional] even better, encrypt the email with my public key

- don't modify the subject field
- specify a nickname, otherwise your comment will be shown as   
  anonymous
- your email address will not be disclosed
- you agree that the comment is to be made public.
- to take down a comment, send the request via email.