RSA Encryption: A Public-Key Cryptography Algorithm Explained

Learn about RSA encryption, a widely used public-key cryptography algorithm for secure data transmission. This guide explains the principles behind RSA, its use of public and private keys, and how it leverages the difficulty of factoring large numbers to ensure data security.

RSA Encryption in Discrete Mathematics

What is RSA Encryption?

RSA is a widely used method for encrypting (making unreadable) information so it can be securely sent over the internet. It's named after its inventors: Rivest, Shamir, and Adleman. The core idea behind RSA is that multiplying large numbers is easy, but figuring out which numbers were multiplied to get that result (factoring) is extremely difficult. This difficulty is what makes RSA secure.

Public-Key Cryptography

RSA is a type of public-key cryptography. This means it uses two keys: a public key and a private key.

  • Public Key: This key is shared publicly; anyone can use it to encrypt a message.
  • Private Key: This key is kept secret; only the owner knows it, and it's used to decrypt the message.

This is like having a mailbox with a slot: anyone can drop a message in (encrypt), but only you have the key to open it (decrypt).

How RSA Works (Simplified)

To understand RSA, imagine a student (Alice) wants to send a secret message to their professor (Bob) through a public channel (like Piazza), without other students seeing it. Bob creates a public key and a private key.

  • Bob makes his public key available to everyone.
  • Alice uses Bob's public key to encrypt her message.
  • Bob uses his private key to decrypt the message.

Even if someone intercepts the encrypted message, they can't read it without Bob's private key. This is analogous to online banking: anyone can send a transaction to the bank (encrypt using the bank's public key), but only the bank and the sender know the transaction details (decrypt using the private key).

Generating RSA Keys

Creating RSA keys involves these steps:

  1. Choose two large prime numbers, p and q.
  2. Calculate n = p * q (n is part of both the public and private keys).
  3. Choose a public exponent e that's relatively prime to (p-1)(q-1) (meaning they share no common factors other than 1).
  4. Calculate the private exponent d (this is a complex mathematical calculation).

The public key is (n, e), and the private key is (n, d).

Key Generation Questions & Answers

Question 1: How to find e such that 1 < e < φ(n) and gcd(φ(n), e) = 1? (φ(n) is a mathematical function related to n)

Answer: Try prime numbers for e, ensuring they don't divide φ(n).

Question 2: How to find d such that d * e ≡ 1 (mod φ(n))?

Answer: Use the Extended Euclidean Algorithm.

RSA Encryption in Action

Let's say Alice wants to send the message "gcd" to Bob, who has a public key (n, e) = (3233, 17) and a private key (n, d) = (3233, 2753).

  1. Alice converts "gcd" into numbers (e.g., using alphabetical order: g=7, c=3, d=4). She might split this into blocks: 73 and 4.
  2. She encrypts each block using the formula: c = me mod n
  3. Alice sends the encrypted message (ciphertext) to Bob.
  4. Bob decrypts using his private key.

Example of RSA Encryption

Encrypt "STOP" using p=43, q=59, and e=13:

  1. Calculate n = p * q = 2537
  2. Convert "STOP" to numbers: S=18, T=19, O=14, P=15. Make blocks: 1819 and 1415
  3. Encrypt each block using c = m13 mod 2537.

Conclusion

RSA is a powerful and widely used encryption method. Its security relies on the difficulty of factoring large numbers. While the mathematics behind it is complex, the basic concept of public and private keys makes it relatively easy to understand its function.