Course contentsShow
← Security
Lesson 141 of 3,0524. Asymmetric Cryptography and PKIFree lesson

RSA Mathematical Foundation: Primes and Modular Arithmetic

Understanding the number theory behind RSA: prime factorization, modular exponentiation, and why these operations are asymmetric.

RSA Mathematical Foundation: Primes and Modular Arithmetic

What You'll Learn

You'll understand the mathematical concepts that make RSA asymmetric encryption possible: prime numbers, modular arithmetic, and why these operations work in one direction but are nearly impossible to reverse.

The Core Mathematical Ideas

Prime Numbers as Building Blocks RSA begins with two large prime numbers (let's call them p and q). Think of primes as special locks—they only divide evenly by 1 and themselves. RSA multiplies these primes together to create n = p × q. This is the "public" part of your key.

Here's the asymmetry: multiplying is easy, but factoring is hard. Given n = 221, finding that p = 13 and q = 17 requires trial and error. With 2048-bit primes (hundreds of digits long), factoring becomes computationally infeasible with current technology.

Modular Arithmetic: The Clock Mathematics Modular arithmetic is like a clock that wraps around. 17 mod 12 = 5 (17 hours on a 12-hour clock shows 5).

In RSA, we use modular exponentiation: raising numbers to powers and then taking the remainder. For example: 7³ mod 15 = 343 mod 15 = 13.

The Asymmetric Magic RSA creates two special exponents: e (public) and d (private). The relationship works like this:

  • Encrypting: (message^e) mod n = ciphertext
  • Decrypting: (ciphertext^d) mod n = message

Computing d requires knowing the prime factors p and q. Without them, finding d from e and n is mathematically intractable.

Key Takeaway: RSA's security relies on the asymmetry between easy multiplication (creating the public key) and hard factorization (breaking it)—combined with modular exponentiation that creates mathematically linked but computationally separate encryption and decryption operations.