RSA Cryptography

RSA Cryptography: The Secret Lockbox of the Internet

The Story of the Magic Mailbox

Imagine you want to send a secret letter to your best friend. But there’s a problem - lots of people can see your mailbox! How do you keep your message safe?

Here’s a brilliant idea: What if your friend gave you a special lock that only they have the key for?

• You put your letter in a box
• You snap the lock shut
• Now ONLY your friend can open it!

This is exactly how RSA works! It’s like a magic mailbox system that keeps secrets safe on the internet.

What is RSA?

RSA stands for Rivest, Shamir, and Adleman - three clever people who invented this system in 1977.

graph TD
    A["You want to send&lt;br&gt;a secret message"] --> B[Get friend's<br>PUBLIC key]
    B --> C["Lock message&lt;br&gt;with public key"]
    C --> D["Send locked&lt;br&gt;message"]
    D --> E["Friend uses&lt;br&gt;PRIVATE key"]
    E --> F["Message unlocked!"]

The Two Keys

Think of it like this:

Real Example:

• Your public key is like your home address - anyone can know it
• Your private key is like your house key - only you have it

How RSA Uses Prime Numbers

Remember prime numbers? Numbers like 2, 3, 5, 7, 11, 13… that can only be divided by 1 and themselves?

RSA uses a clever trick with primes!

The Magic Recipe

Step 1: Pick Two Prime Numbers

Let’s use small ones to understand:

• First prime (p) = 3
• Second prime (q) = 11

Step 2: Multiply Them

n = 3 × 11 = 33

This number 33 becomes part of both keys!

Step 3: The Secret Sauce

Here’s the genius part:

• It’s EASY to multiply: 3 × 11 = 33
• It’s HARD to figure out: What two primes make 33?

For small numbers, it’s easy. But imagine:

Real RSA uses numbers with
300+ digits!

That's like trying to guess
which two HUGE prime numbers
multiply to make another
GIGANTIC number.

Even supercomputers would take
millions of years!

The RSA Process Step by Step

Creating Your Keys

graph TD
    A["Pick prime p"] --> B["Pick prime q"]
    B --> C["Multiply: n = p × q"]
    C --> D["Calculate special<br>number φ"]
    D --> E["Choose number e"]
    E --> F["Calculate number d"]
    F --> G["PUBLIC KEY<br>n and e"]
    F --> H["PRIVATE KEY<br>n and d"]

Let’s see a simple example!

Step 1: Choose p = 5 and q = 11

Step 2: Calculate n = 5 × 11 = 55

Step 3: Calculate φ (phi) = (p-1) × (q-1)

• φ = (5-1) × (11-1) = 4 × 10 = 40

Step 4: Choose e (must be coprime with φ)

• e = 3 (works because 3 and 40 share no common factors except 1)

Step 5: Find d (the inverse of e)

• d × e ≡ 1 (mod φ)
• d = 27 (because 27 × 3 = 81 = 2×40 + 1)

Your Keys:

• Public Key: (n=55, e=3)
• Private Key: (n=55, d=27)

Encrypting a Message

Let’s send the secret number 7 to our friend!

The Encryption Formula

Encrypted = Message^e mod n

Our Example:

• Message = 7
• e = 3
• n = 55

Encrypted = 7³ mod 55
         = 343 mod 55
         = 13

We send 13 (not 7!) through the internet. Anyone who sees 13 has no idea it means 7!

Decrypting a Message

Your friend receives 13. Now they use their private key!

The Decryption Formula

Original = Encrypted^d mod n

Our Example:

• Encrypted = 13
• d = 27
• n = 55

Original = 13²⁷ mod 55
        = 7

The secret number 7 is recovered!

Why Is This Secure?

The Factoring Problem

Here’s why RSA is like an unbreakable safe:

To find d, you MUST find p and q first!

With small numbers: Easy peasy!

• 55 = 5 × 11 (figured it out in seconds)

With REAL RSA numbers:

• n has 617 digits
• No computer can factor it!

graph TD
    A["Attacker sees n"] --> B{Try to factor n}
    B --> C["Check if 2 divides n?"]
    C --> D["Check if 3 divides n?"]
    D --> E["Check if 5 divides n?"]
    E --> F["..."]
    F --> G["Would take<br>trillions of years!"]

RSA in Real Life

Every time you see the little lock icon in your browser, RSA (or similar systems) are protecting you!

When You Shop Online

graph TD
    A["You type credit&lt;br&gt;card number"] --> B[Your browser encrypts<br>with shop's PUBLIC key]
    B --> C["Encrypted data travels&lt;br&gt;through internet"]
    C --> D["Shop decrypts with&lt;br&gt;their PRIVATE key"]
    D --> E["Purchase complete!"]

Digital Signatures

RSA can also prove WHO sent a message!

The Trick: Use keys in reverse!

• Sign with YOUR private key
• Anyone can verify with YOUR public key

graph TD
    A["You write message"] --> B["Sign with YOUR<br>private key"]
    B --> C["Send message<br>+ signature"]
    C --> D["Friend verifies with<br>YOUR public key"]
    D --> E[Confirmed it's<br>really from you!]

Summary: RSA in a Nutshell

The Key Ideas

1. Two Keys Work Together

   • Public key = Lock (share with everyone)
   • Private key = Key (keep secret forever)

2. Prime Numbers Are the Magic

   • Easy to multiply primes
   • Nearly impossible to factor back

3. Math Does the Heavy Lifting

   • Encryption: Message^e mod n
   • Decryption: Encrypted^d mod n

4. Security = Factoring Difficulty

   • Bigger primes = safer secrets
   • Real RSA uses 2048+ bit keys

The Beautiful Simplicity

RSA is like a box with two keyholes:

• One keyhole only locks (public key)
• One keyhole only unlocks (private key)

And that’s it! This simple idea protects:

• Your bank account
• Your emails
• Your messages
• Your passwords
• The entire internet!

Quick Reference

You now understand the same encryption that protects the world’s secrets!

From secret agents to online shopping, RSA keeps our digital world safe - all thanks to the beautiful poetry of prime numbers.