RSA Algorithm- Understanding Public Key Encryption

What Is RSA and Why Should You Care?

RSA is one of the first public-key cryptosystems still in use today. It lets you encrypt data with a public key that anyone can have, while decryption requires a completely separate private key that only you hold.

The algorithm got its name from its inventors: Rivest, Shamir, and Adleman. They published it in 1977, and it became the backbone of internet security.

You use RSA every day without knowing it. It's in your browser's HTTPS connection, your email encryption, digital signatures, and most authentication systems. If you've ever seen a padlock icon in your address bar, RSA or something like it was involved.

How RSA Works: The Basic Idea

RSA relies on a simple mathematical fact: multiplying two large prime numbers is easy, but factoring the result back into those primes is practically impossible for large enough numbers.

Here's the flow:

The Math Behind It

You need Euler's totient function for this. φ(N) = (p-1)(q-1) for primes p and q.

The public key is (e, N) where e and φ(N) are coprime. The private key is (d, N) where d satisfies: e × d ≡ 1 (mod φ(N)).

For encryption: C = Me mod N

For decryption: M = Cd mod N

That's it. The security comes from the fact that calculating d from e and N requires knowing p and q, which means factoring N.

Key Generation Step by Step

Here's exactly how you generate an RSA key pair:

  1. Pick two large primes — typically 2048 bits each for modern security. These must be random and kept secret.
  2. Calculate N — Multiply your primes: N = p × q. N is typically 4096 bits long.
  3. Compute φ(N) — φ(N) = (p-1)(q-1)
  4. Choose public exponent e — Most systems use 65537. It's a balance between efficiency and security.
  5. Calculate private exponent d — Find d where e × d ≡ 1 (mod φ(N)). Use the extended Euclidean algorithm.
  6. Share the public key — (e, N) goes to anyone who needs to send you encrypted data.
  7. Keep the private key safe — (d, N) is your secret. Anyone with this can decrypt everything.

Encryption and Decryption in Practice

Encrypting a Message

Sender gets your public key (e, N). They convert their message M into a number less than N. Then they compute:

C = Me mod N

C gets sent to you. Without your private key, intercepting C is useless.

Decrypting a Message

You receive C. Using your private key (d, N):

M = Cd mod N

You recover the original message. The math guarantees this works as long as d is the correct private exponent.

RSA vs Other Encryption Methods

RSA isn't the only game in town. Here's how it compares:

Algorithm Type Key Size Speed Common Use
RSA Asymmetric 2048-4096 bits Slow Key exchange, digital signatures
AES Symmetric 128-256 bits Fast Bulk data encryption
ECC Asymmetric 256-512 bits Moderate Mobile devices, constrained environments
Diffie-Hellman Asymmetric 2048-4096 bits Slow Key exchange only

RSA is slow compared to symmetric algorithms like AES. That's why most systems use RSA for key exchange — encrypting a symmetric key — then switch to AES for the actual data. This hybrid approach gets you the convenience of public-key crypto with the speed of symmetric encryption.

Real-World Applications

RSA shows up everywhere:

Security Considerations

RSA is secure when implemented correctly, but "correctly" has a lot of moving parts.

Key Size Matters

1024-bit RSA is broken. Don't use it. 2048-bit minimum for most applications. 4096-bit if you're paranoid or have regulatory requirements. The computational cost increases, but hardware is fast enough that 2048-bit works for most real-world scenarios.

Random Number Generation Is Critical

If your primes are predictable, attackers can recreate your keys. Use a cryptographically secure random number generator. This isn't optional — it's the entire foundation of your security.

Padding Is Not Optional

Raw RSA encryption (Me mod N) has mathematical weaknesses. Always use RSA-OAEP for encryption or RSA-PSS for signatures. These padding schemes add randomization and prevent attacks.

Quantum Computing Threat

Shor's algorithm can factor large numbers in polynomial time on a quantum computer. This breaks RSA. The threat isn't immediate — current quantum computers can't do this at scale — but if you're planning long-term security (10+ years), consider post-quantum algorithms.

Getting Started: Using RSA in Code

Most languages have libraries that handle the math. You don't need to implement RSA from scratch.

Python with PyCryptodome

from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP
from Crypto.Signature import pkcs1_15
from Crypto.Hash import SHA256

# Generate key pair
key = RSA.generate(2048)

# Encrypt
cipher = PKCS1_OAEP.new(key.publickey())
ciphertext = cipher.encrypt(b"Your message here")

# Decrypt
cipher = PKCS1_OAEP.new(key)
message = cipher.decrypt(ciphertext)

# Sign
h = SHA256.new(b"Document to sign")
signature = pkcs1_15.new(key).sign(h)

# Verify
try:
    pkcs1_15.new(key.publickey()).verify(h, signature)
    print("Signature valid")
except ValueError:
    print("Signature invalid")

Node.js with Node's Crypto Module

const crypto = require('crypto');

// Generate key pair
const { publicKey, privateKey } = crypto.generateKeyPairSync('rsa', {
  modulusLength: 2048,
});

// Encrypt
const encrypted = crypto.publicEncrypt(
  { key: publicKey, padding: crypto.constants.RSA_PKCS1_OAEP_PADDING },
  Buffer.from('Your message here')
);

// Decrypt
const decrypted = crypto.privateDecrypt(
  { key: privateKey, padding: crypto.constants.RSA_PKCA1_OAEP_PADDING },
  encrypted
);

// Sign
const sign = crypto.createSign('SHA256');
sign.update('Document to sign');
sign.end();
const signature = sign.sign(privateKey);

// Verify
const verify = crypto.createVerify('SHA256');
verify.update('Document to sign');
verify.end();
console.log(verify.verify(publicKey, signature));

Common RSA Mistakes to Avoid

When to Use RSA (And When Not To)

Use RSA when:

Don't use RSA when: