I’ve always thought that the RSA and Diffie–Hellman public key encryption algorithm systems are beautiful in their complex simplicity. While there are countless articles out there explaining how to implement them, I have never really found one that I think describes the math behind then in a simple way, so I thought I’d give a crack at it.

Both algorithms are derived from 3 math axioms:

- This is called Modular exponentiation (hereby referred to as modexp). In the following, x is a prime numbers and p is an integer less than x.
**p^(x ) mod x = p** (e.x. 12^(17 ) mod 17 = 12)

**p^(x-1) mod x = 1** (e.x. 12^(17-1) mod 17 = 1 )

- A further derivation from the above formulas shows that we can combine primes and they work in the same manner. In the following, x and y are prime numbers and p is an integer less than x*y.
**p^((x-1)*(y-1) ) mod (x*y) = 1** (e.x. 12^((13-1)*(17-1) ) mod (13*17) = 1 )

Note: This formula is not used in RSA but it helps demonstrate how the formulas from part 1 becomes formula 2b.

Due to how modexp works with primes, values of p that are multiples of x or y do not work with 2a.

**p^((x-1)*(y-1)+1) mod (x*y) = p** (e.x. 12^((13-1)*(17-1)+1) mod (13*17) = 12)

- The final axiom is how modexp can be split apart the same way as in algebra where
**(x^a)^b === x^(a*b)**. For any integers p, x, y, and m:**(p^(x*y) mod m)** === **((p^x mod m)^y mod m)**

With these 3 axioms we have everything we need to explain how RSA works. To execute an RSA exchange, encrypted from Bob and decrypted by Alice, the following things are needed.

The variable | Variable name | Who has it | Who uses it | Description |
---|

Prime Numbers 1 and 2 | **Prime1**, **Prime2** | Alice | Alice | Alice will use these to derive variables **PubKey**, **PrivKey**, and **Modulo**. In our examples we use small numbers, but in reality, very large primes will be used, generally of at least 256 bit size. |

Public key | **PubKey** | Alice, Bob | Bob | Alice sends this to Bob so he can encrypt data to her. Bob uses it as an exponent in a modexp. |

Private key | **PrivKey** | Alice | Alice | Alice uses this to decrypt what Bob sends her. Alice uses it as an exponent in a modexp. |

Modulo | **Modulo** | Bob, Alice | Bob, Alice | Alice sends this to Bob. They both use it as a modulo in a modexp |

Payload Data | **Payload** | The data bob starts with and turns into **EncryptedPayload**. Alice derives **Payload** back from **EncryptedPayload** |

Now, let’s start with axiom 2b:

**Payload^((Prime1-1)*(Prime2-1)+1) mod (Prime1*Prime2) = Payload**

Let’s change this up so the exponent is just 2 multiplications so we can use axiom 3 on it. We need to find 2 integers to become

**PubKey** and

**PrivKey** such that:

**PubKey*PrivKey=(Prime1-1)*(Prime2-1)+1**

And

**Modulo** is

**Prime1*Prime2**.

So we now have:

**Payload^(PubKey*PrivKey) mod Modulo = Payload**

Now, using axiom 3, we can turn it into this:

**(Payload^PubKey mod Modulo)^PrivKey mod Modulo = Payload**

__Now, we can split this up into:__Bob calculates and sends to Alice:

**Payload^PubKey mod Modulo=EncryptedPayload**Alice uses the received

**EncryptedPayload** and performs:

**EncryptedPayload^PrivKey mod Modulo = Payload**And the process is complete!

However, there is 1 caveat that I didn’t cover which makes the encryption that what we currently have weak. The calculation of **PubKey** and **PrivKey** from **Prime1** and **Prime2** needs to follow some rather specific complex rules to make the keys strong. Without this, an attacker may be able to figure out **Prime1** and **Prime2** from the **Modulo** and **PubKey**, and could then easily derive **PrivKey** from it. I generally see the **PubKey** as 65535, or another power of 2 minus 1.