RSA encryption and decryption process step by step in 10 mins

We all know that RSA is used for encryption. As a serious developer, it’s important to know how does it work and why is it hard to break? In this article, I will walk you through the process of RSA and the Math behind it.

Let’s start.

# Definition

**RSA** (**Rivest–Shamir–Adleman**) is a public-key cryptosystem widely used for secure data transmission.

# Prime

RSA is all about playing with Prime numbers. A prime number n means can not be factored by any number between [2, n-1]. e.g. 2,3,5,7,11,13,17,19…

Let’s dive in a little bit deeper.

# Coprime

In mathematics, two integers *a* and *b* are **coprime**, **relatively prime,** or **mutually prime** if the only positive integer that is a divisor of both of them is 1. Wiki

So examples 2, and 5 are coprime because they share no common divisor except 1. same for 2 and 7, 3 and 11 ….

# Totient

If ask yourself this question: how many coprime (or relative prime) (x, N), x≤N? This is called the Totient function.

A brute force solution could be looped through every number between [1, N] and check if gcd(x, N) == 1, where gcd is the famous greatest common divisor function, however, which seems to be too slow (for an encryption function).

# A bit of math & Sample

What if given N = p*q, p and q are both prime numbers, to find out all coprime(x, N) where 1<x<N,

so let p=5, q=7, and N=p*q=35

#1 think about the number p, how many primes 1≤x≤5? that’s easy, by definition of prime, all of them, {1, 2, 3, 4, 5} = array1

#2 think about the number q, how many primes are 1≤y≤7? all of them, {1, 2, 3, 4, 5, 6, 7} = array2

#3 let array1**array2 .so how many pairs? p**q=35.

#4 we already know, N=p**q, which means N could only be only factored by p or q.*

*let’s list out those numbers 1≤k≤35, k %5=0 or k%7 =0.**we have {5,10, 15, 20, 25, 30, 35} (count=7) and {7, 14, 21, 28, 35} (count=5).**so, we only need to exclude these numbers from the p**q combos…