How RSA works?

RSA is a public key system that uses a key pair: one public, one private. The public key can encrypt data or verify signatures. The private key decrypts or signs.

The core idea

RSA relies on the fact that multiplying two large primes is easy, while factoring the product back into primes is hard. That one-way gap is what keeps the private key safe.

Key generation in short

1. Pick two large primes p and q.
2. Multiply them to get n = p * q. This is part of the public key.
3. Compute Euler's totient phi(n) = (p - 1)(q - 1).
4. Pick a public exponent e that is coprime with phi(n).
5. Compute d such that e * d ≡ 1 (mod phi(n)). This is the private exponent.

Encryption and decryption

• Encrypt: cipher = message^e mod n
• Decrypt: message = cipher^d mod n

Only the private key has d, so only the owner can decrypt the message.

Signatures

Signing flips the direction:

• Sign: signature = hash(message)^d mod n
• Verify: hash(message) ?= signature^e mod n

If the check passes, the message came from the holder of the private key.

Why we do not encrypt large payloads with RSA

RSA is slow and has size limits. In real systems, RSA encrypts a symmetric key and the payload is encrypted with a fast cipher like AES.

Practical takeaways

• Use modern libraries and defaults (RSA-OAEP, RSA-PSS).
• Rotate keys and set clear expiration.
• Prefer elliptic curve algorithms for new systems when possible.