RSA Algorithm Explained

 

The Mathematics Behind the RSA Algorithm

RSA is one of the classic public-key cryptographic algorithms. Its mathematics comes primarily from number theory, especially prime numbers, modular arithmetic, Euler's theorem, and modular inverses.

1. The Big Picture

RSA has two keys:

• Public key — anyone can know it.
• Private key — must be kept secret.

Message   →   Encryption using public key   →   Ciphertext

Ciphertext   →   Decryption using private key   →   Original Message

The fascinating part is that encryption and decryption are based on exponentiation modulo a large number.

Encryption: c = m^e mod n

Decryption: m = c^d mod n

2. First: What Does "mod" Mean?

The word mod means "remainder after division."

Example 1

17 divided by 5 gives:

17 = 5 × 3 + 2

Therefore:

17 mod 5 = 2

Another example

25 mod 7 = 4

because:

25 = 7 × 3 + 4

Modular arithmetic is extremely important in RSA.

3. Why Prime Numbers?

RSA begins by selecting two large prime numbers:

p = prime number
q = prime number

For learning, we will use small numbers:

p = 61
q = 53

In real RSA, these numbers are enormously larger.

4. Calculate n

Multiply the two primes:

n = p × q

With our example:

n = 61 × 53
n = 3233

This number n becomes part of both the public and private keys.

Important: The security of RSA relies heavily on the difficulty of taking a huge number such as n and discovering the two prime factors p and q.

5. Euler's Totient Function

The next mathematical concept is Euler's totient function, written as:

φ(n)

It counts how many positive integers less than or equal to n are relatively prime to n.

A small example

Consider:

n = 8

Numbers from 1 through 8 that are relatively prime to 8 are:

1, 3, 5, 7

Therefore:

φ(8) = 4

For RSA

Because p and q are prime:

n = p × q

We can calculate:

φ(n) = (p - 1)(q - 1)

For our example:

φ(3233)
= (61 - 1)(53 - 1)
= 60 × 52
= 3120

6. Choosing the Public Exponent e

We now choose a number e.

It must satisfy:

1 < e < φ(n)

and:

gcd(e, φ(n)) = 1

In other words, e and φ(n) must have no common factor other than 1.

Our example

φ(n) = 3120
e = 17

Since:

gcd(17, 3120) = 1

17 is a valid choice.

Our public key is now:

Public Key = (e, n)
= (17, 3233)

7. What Does gcd Mean?

gcd means greatest common divisor.

Example

Consider:

gcd(12, 18)

Factors of 12:

1, 2, 3, 4, 6, 12

Factors of 18:

1, 2, 3, 6, 9, 18

The largest common factor is 6:

gcd(12, 18) = 6

But:

gcd(17, 3120) = 1

So 17 and 3120 are relatively prime.

8. Finding the Private Key d

Now we need a number d satisfying:

e × d ≡ 1 mod φ(n)

With our values:

17d ≡ 1 mod 3120

The solution is:

d = 2753

Let's verify it

17 × 2753 = 46801

Divide 46801 by 3120:

46801 = 3120 × 15 + 1

Therefore:

46801 mod 3120 = 1

So:

17 × 2753 ≡ 1 mod 3120

Therefore:

Private Key = (d, n)
= (2753, 3233)

9. How Do We Find d?

We use the Extended Euclidean Algorithm.

We want:

17d + 3120k = 1

The Extended Euclidean Algorithm finds integers d and k that satisfy this equation.

In real cryptographic software, this calculation is performed automatically.

Key idea: Finding d from e and φ(n) is easy when φ(n) is known. The challenge for an attacker is obtaining φ(n), because that requires factoring n.

10. RSA Encryption

Suppose our message is represented by:

m = 65

Encryption is:

c = m^e mod n

Substitute our values:

c = 65¹⁷ mod 3233

The result is:

c = 2790

So 65 has been transformed into 2790.

65
↓
Encryption using (17, 3233)
↓
2790

11. RSA Decryption

The recipient has the private key:

(2753, 3233)

Decryption is:

m = c^d mod n

Therefore:

m = 2790²⁷⁵³ mod 3233

The result is:

m = 65

The original message has been recovered.

12. Why Does RSA Actually Work?

This is the most important mathematical part.

We choose e and d such that:

ed ≡ 1 mod φ(n)

This means there is some integer k such that:

ed = 1 + kφ(n)

Now encryption followed by decryption gives:

(m^e)^d = m^ed

Substitute:

m^ed = m^{1 + kφ(n)}

Therefore:

m^{1 + kφ(n)} = m × (m^φ(n))^k

Euler's theorem tells us:

m^φ(n) ≡ 1 mod n

Therefore:

m × (1)^k ≡ m mod n

Therefore: m^ed ≡ m mod n

That's why decryption gives us the original message.

13. A Tiny RSA Example From Scratch

Let's use extremely small numbers so that we can see the entire process manually.

Step 1: Choose primes

p = 3
q = 11

Step 2: Calculate n

n = 3 × 11 = 33

Step 3: Calculate φ(n)

φ(n) = (3 - 1)(11 - 1)
= 2 × 10
= 20

Step 4: Choose e

Choose:

e = 3

Check:

gcd(3, 20) = 1

Good.

Step 5: Find d

We need:

3d ≡ 1 mod 20

Try d = 7:

3 × 7 = 21
21 mod 20 = 1

Therefore:

d = 7

Keys

Key	Value
Public key	(3, 33)
Private key	(7, 33)

Step 6: Encrypt

Suppose:

m = 4

Encryption:

c = 4³ mod 33
= 64 mod 33
= 31

So:

4 → 31

Step 7: Decrypt

m = 31⁷ mod 33

The result is:

m = 4

So:

Original 4 → Encrypt → 31 → Decrypt → 4

14. Why Can't an Attacker Simply Calculate d?

This is the central security idea.

The attacker knows:

n
e

For our example:

n = 3233
e = 17

But to calculate d, we need:

φ(n)

And to calculate φ(n), we need:

p and q

In other words:

p, q
↓
n = p × q
↓
φ(n) = (p-1)(q-1)
↓
d

Going forward is easy.

Going backward requires factoring n.

15. A Simple Factoring Example

Suppose an attacker sees:

n = 3233

They could try:

3233 ÷ 2
3233 ÷ 3
3233 ÷ 5
...

Eventually they discover:

3233 = 61 × 53

Then they can calculate:

φ(n) = (61 - 1)(53 - 1)
= 3120

Then they can calculate d.

This is why our tiny example is NOT secure.

3233 is trivial to factor. Real RSA uses enormous primes, typically producing RSA moduli such as 2048 bits or larger.

16. The Role of Modular Exponentiation

You may wonder how a computer can calculate something like:

2790²⁷⁵³ mod 3233

without generating a gigantic number containing thousands of digits.

It uses an efficient technique called modular exponentiation, commonly implemented using repeated squaring.

Example

Suppose we want:

3¹³ mod 7

Since:

13 = 8 + 4 + 1

We calculate powers by repeatedly squaring:

3¹ mod 7 = 3
3² mod 7 = 2
3⁴ mod 7 = 4
3⁸ mod 7 = 2

Then:

3¹³ = 3⁸ × 3⁴ × 3

Therefore:

2 × 4 × 3 mod 7
= 24 mod 7
= 3

So:

3¹³ mod 7 = 3

17. Chinese Remainder Theorem

Real RSA implementations often use another important number theory concept: the Chinese Remainder Theorem (CRT).

Instead of doing one huge modular exponentiation modulo:

n = pq

computations can be performed separately modulo p and q and then recombined.

mod p      +      mod q

↓

CRT

↓

mod pq

This can make RSA decryption significantly faster.

18. What Mathematics Is Really Doing the Work?

Mathematical concept	Purpose in RSA
Prime numbers	Used to construct n
Multiplication	n = p × q
Euler's totient	Calculates φ(n)
GCD	Checks whether e is valid
Extended Euclidean Algorithm	Finds d
Modular exponentiation	Encryption and decryption
Euler's theorem	Explains why decryption reverses encryption
Integer factorization	Provides the computational security assumption
Chinese Remainder Theorem	Can speed up private-key operations

19. The Entire RSA Algorithm in One Place

Key Generation

1. Choose two large primes p and q.
2. Calculate:
   n = pq
3. Calculate:
   φ(n) = (p-1)(q-1)
4. Choose e such that:
   gcd(e, φ(n)) = 1
5. Calculate d such that:
   ed ≡ 1 mod φ(n)

Public Key

(e, n)

Private Key

(d, n)

Encryption

c = m^e mod n

Decryption

m = c^d mod n

RSA turns number theory into a one-way computational problem.