ASYMMETRIC ENCRYPTION & RSA

What Makes It Asymmetric?

• In symmetric encryption, the same key is used to both encrypt and decrypt.
  • For instance, in the Ceaser Ciphers covered earlier, we use the same key to encrypt (shift forwards) and decrypt (shift backwards).
• In asymmetric encryption, there are two different keys:
  • Public key: used to lock (encrypt) the message 🔓
  • Private key: used to unlock (decrypt) the message 🔑

We call it asymmetric since the keys are not the same for encrypting and decrypting.

This means you can safely share your public key with the world, while keeping your private key secret.

Why Do We Need RSA?

• Symmetric ciphers (like Substitution or Caesar) need both people to share the same secret key.
• But how do we share that key securely over the internet?
• This is a big problem for symmetric encryption schemes.
• RSA solves this by letting you publish your public key so anyone can encrypt messages to you.
• Only your secret private key can decrypt it.

How Does RSA Work? (Simplified)

1. Pick two prime numbers (For this example we will use 5 and 11)
2. Multiply them together (n = 5 × 11 = 55).
3. Choose a public exponent (we will choose e = 3).
4. Work out a private exponent (this is quite difficult to do but in this case, d = 27 will work).
5. We will chose 9, as our message.
6. To encrypt: Raise message to the public exponent, then mod by 55. c = (9^3 mod 55) = 14
7. To decrypt: Raise ciphertext to the private exponent, mod by 55. m = (14^27 mod 55) = 9 which was our message!

Practice Task

Task 1: Encryption

Bob’s RSA public key, n = 55 and public exponent, e = 3. Alice wants to send him the message, m = 4. What is the ciphertext? (encrypted message)

Try to solve before opening the answer!

Task 2: Decryption

Bob’s private key, d = 27 and public exponent, n = 55. He receives ciphertext, c = 9. What is the hidden message, m? Hint (use this calculator for large values: https://www.wolframalpha.com)

Try to solve before opening the answer!