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

$x$ is a modular multiplicative inverse of an integer $a$, such that $ax$ is congruent to 1 with respect to the modulus n Noted as: $$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

Given that $a$ and $n$ are relatively prime, then $$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.

Encryption Find the code $c$ by calculating the Remainder of $m^e \div n$ $$m^e \equiv c \pmod n$$

Decryption Find the original text $m$ by calculating the Remainder $c^d \div 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:

We need to prove: $$c^d \equiv m \pmod n \tag{1}$$

From the encryption algorithm, we have: $$m^e \equiv c \pmod n$$

Which can be written as: $$c=m^e - kn$$

Substituting c into (1): $$(m^e - kn)^d \equiv m\pmod n$$

Which is equivalent to: $$m^{ed} \equiv m \pmod n \tag{2}$$ (note: see above: Modular Arithmetic rule 4 and 6)

From the key generating algorithm, we have: $$ed\equiv 1 \pmod {\varphi(n)}$$

Which can be written as: $$ed = h\varphi(n) + 1 \tag{3}$$

Substituting (3) into (2), now we need to prove: $$m^{h\varphi(n) + 1} \equiv m \pmod n \tag{4}$$

There are 2 situations:

Situation I. m and n are relatively prime:

According to Euler’s theorem: $$m^{\varphi(n)} \equiv 1 \pmod n$$

Then (modular arithmetic rule): $$m^{h\varphi(n)} \equiv 1 \pmod n$$

Apparently: $m \equiv m \pmod n$, then: $$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$.

Let’s say $m=kp$. Because $m=kp<n=pq$, $k$ must be smaller than $q$, then $k$ and $q$ are relatively prime($q$ is prime). So that we have: $$(kp)^{\varphi(q)} = (kp)^{q-1} \equiv 1 \pmod q$$

With modular arithmetic rule we have $$ [(kp)^{q-1}]^{h(p-1)} \equiv 1 \pmod q$$

And $$ [(kp)^{q-1}]^{h(p-1) } \times kp \equiv kp \pmod q$$

Which is: $$ (kp)^{h\varphi(n)} \times kp = (kp)^{h\varphi(n)+1} \equiv kp \pmod q$$

Substituting with (3), we get: $$(kp)^{ed} \equiv kp \pmod q$$

Which can be written as: $$(kp)^{ed} = kp + tq$$

Both side devided by $p$: $$ 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$$

So: $$m^{ed} \equiv m \pmod n$$

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

ref:

What is RSA encryption and how does it work

阮一峰的博客