RSA Encryption Learning

Key Components of RSA

Step 2 of 9

Understanding the fundamental building blocks that make RSA encryption work.

Prime Numbers: The Foundation

RSA encryption begins with two large prime numbers. These numbers are the foundation of the entire cryptosystem's security.

Key Insight: The larger the prime numbers, the more secure the encryption. Modern RSA implementations typically use primes that are hundreds of digits long.

What makes prime numbers special?

A prime number is only divisible by 1 and itself

2
3
5
7
11
13
17
19
23
29

RSA uses two prime numbers

p

First prime

×
q

Second prime

=
n

Modulus

Finding prime factors of n is computationally difficult for large numbers

The Modulus (n) and Totient Function φ(n)

The modulus n is the product of the two prime numbers p and q. The totient function φ(n) counts the positive integers up to n that are relatively prime to n.

Calculating the Modulus

n = p × q

Example: If p = 3 and q = 11, then n = 3 × 11 = 33

The modulus n is used in both the public and private keys, and is publicly shared.

Calculating the Totient

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

Example: If p = 3 and q = 11, then φ(n) = (3-1) × (11-1) = 2 × 10 = 20

The totient φ(n) is kept secret and used to generate the private key.

Visual Example: Finding Totient φ(9)

Step 1: List Numbers

Numbers from 1 to 9:

1
2
3
4
5
6
7
8
9
Step 2: Find Factors

9 = 3 × 3

Numbers divisible by 3:
3
6
9
Step 3: Result

Numbers coprime with 9:

1
2
4
5
7
8
φ(9) = 6

Key Insight: The totient φ(n) represents the count of numbers that share no common factors with n (except 1). For a prime number p, φ(p) = p-1 because all numbers less than p are coprime with it.

Public Exponent (e) and Private Exponent (d)

The public exponent e and private exponent d are the core components that enable encryption and decryption in RSA.

Public Exponent (e)

  • Must be between 1 and φ(n)
  • Must be coprime with φ(n) (share no common factors)
  • Typically chosen as 65537 (216+1) for efficiency

The public key consists of the pair (n, e) and is shared openly.

Private Exponent (d)

  • Calculated as the modular multiplicative inverse of e modulo φ(n)
  • Satisfies the equation: (d × e) mod φ(n) = 1
  • Calculated using the Extended Euclidean Algorithm

The private key consists of the pair (n, d) and must be kept secret.

How These Components Work Together

Encryption

C = Me mod n

Uses public key (n, e)

Decryption

M = Cd mod n

Uses private key (n, d)

Mathematical Relationship

The security of RSA relies on the fact that:

  • It's easy to calculate n = p × q when you know p and q
  • It's computationally difficult to find p and q when you only know n (for large primes)
  • The relationship between e and d ensures that (Me)d ≡ M (mod n) for any message M

Test Your Understanding

1. Which of the following is NOT a component of RSA encryption?

2. How is the modulus (n) calculated in RSA?

3. What is the relationship between e and d in RSA?

Back