🔐 RSA Encryption — Alice to Bob

🔑 Understanding RSA Encryption

RSA (Rivest–Shamir–Adleman) is one of the most widely used asymmetric encryption algorithms. It relies on a pair of mathematically linked keys — a public key to encrypt data, and a private key to decrypt it. RSA is the backbone of many secure communication protocols on the internet.

🔍 Key Features

• Uses two large prime numbers to generate a secure key pair
• Encryption and decryption are based on modular exponentiation
• Public key is shared with anyone; private key is kept secret
• Security relies on the difficulty of factoring large numbers

🎯 Common Use Cases

• Key Exchange: Send AES or session keys securely
• Digital Signatures: Prove authenticity and integrity of documents
• SSL/TLS: Used during HTTPS handshakes
• Email Encryption: (e.g., PGP or S/MIME)

✅ Advantages

• No need to share a secret key before communication begins
• Supports authentication via digital signatures
• Proven and time-tested cryptographic method
• Still widely used for key exchange despite the rise of elliptic curve cryptography (ECC)

Step 1: Key Generation (Bob)

• Choose two primes: p = 1291, q = 1361
• Compute n: n = p × q = 1757051
• Euler's Totient: ϕ(n) = (p−1)(q−1) = 1754400
• Pick public exponent: e = 17 (commonly small prime)
• Compute private key: d ≡ e⁻¹ mod ϕ(n) = 1036945
• Public Key (shared): (17, 1757051)
• Private Key (kept secret): (1036945, 1757051)

Step 2: Encryption (Alice ➜ Bob)

Alice wants to send the number 42 securely to Bob. She uses Bob's public key to encrypt it:

ciphertext = message^e mod n
           = 42^17 mod 1757051
           = 391192

This encrypted number is safe to send even on insecure channels.

Step 3: Decryption (Bob)

Bob receives 391192 and uses his private key to retrieve the original message:

message = ciphertext^d mod n
        = 391192^1036945 mod 1757051
        = 283673

✅ Successfully recovered the original message: 283673

🧠 What Did We Learn?

• Asymmetric encryption: Uses two keys (public & private)
• Public key: Used to encrypt
• Private key: Used to decrypt
• Only the holder of the private key (Bob) can decrypt Alice’s message
• RSA security relies on the difficulty of factoring large primes

📚 Summary

1. Bob creates public/private key pair from two large primes.
2. Alice encrypts her message using Bob’s public key (safe to share).
3. Only Bob can decrypt it using his private key.
4. RSA provides secure communication over insecure networks.