RSA Cryptography

RSA (Rivest-Shamir-Adleman) is one of the first public-key cryptosystems, based on the mathematical difficulty of factoring the product of two large prime numbers. It's used for both encryption and digital signatures.

Key Generation

1. Choose two large random primes p and q
2. Compute n = p × q (modulus)
3. Compute φ(n) = (p-1)(q-1)
4. Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1
5. Compute d = e⁻¹ mod φ(n)

Public key: (n, e)   // Can be shared
Private key: (n, d)  // Must be secret

Operations

// Encryption (with public key)
ciphertext = plaintext^e mod n

// Decryption (with private key)
plaintext = ciphertext^d mod n

// Signing (with private key)
signature = hash(message)^d mod n

// Verification (with public key)
hash(message) == signature^e mod n

Key Sizes

  • 1024-bit: Deprecated, potentially breakable
  • 2048-bit: Minimum recommended
  • 3072-bit: Recommended for long-term security
  • 4096-bit: High security, slower operations

Common Vulnerabilities

  • Small exponent attacks: Using e=3 unsafely
  • Bleichenbacher attack: PKCS#1 v1.5 padding oracle
  • Weak key generation: Shared prime factors
  • Timing attacks: Non-constant-time implementation

Modern Usage

// RSA often used for key exchange, not data encryption
1. Generate random AES key
2. Encrypt AES key with RSA public key
3. Encrypt data with AES
4. Send: RSA_encrypted_key + AES_encrypted_data

See Also