Skip to content

RSA Algorithm (Rivest-Shamir-Adleman)

The RSA algorithm is a widely used asymmetric encryption technique, meaning it uses a public key for encryption and a private key for decryption. It was developed in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman and is based on the difficulty of prime factorization in number theory.

1. Characteristics of RSA

  • Type: Asymmetric-key cryptographic algorithm
  • Key Length: Typically 1024, 2048, or 4096 bits (longer keys provide stronger security)
  • Security Basis: Relies on the difficulty of factoring large prime numbers
  • Usage: Used for encryption, digital signatures, and secure key exchange

2. Steps of the RSA Algorithm

A. Key Generation

  1. Select Two Large Prime Numbers (p & q)
    • Choose two distinct large prime numbers, p and q.
  2. Compute n (the modulus)
    • n = p × q
    • The value n is used as part of both the public and private keys.
  3. Calculate Euler’s Totient Function (φ(n))
    • φ(n) = (p - 1) × (q - 1)
    • This is the count of numbers less than n that are relatively prime to n.
  4. Choose the Public Key Exponent (e)
    • Select an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (i.e., e and φ(n) are coprime).
    • Common choices for e: 3, 17, 65537 (because they are prime and optimize performance).
  5. Compute the Private Key Exponent (d)
    • Compute d as the modular inverse of e under φ(n), meaning:
      • d ≡ e⁻¹ (mod φ(n))
    • This means that (d × e) mod φ(n) = 1.
    • The private key (d, n) must be kept secret.

B. Encryption Process

  • The sender encrypts a message M using the receiver’s public key (e, n): C=Memod  nC = M^e \mod nC=Memodn
  • The ciphertext C is then sent to the receiver.

C. Decryption Process

  • The receiver decrypts the ciphertext C using their private key (d, n): M=Cdmod  nM = C^d \mod nM=Cdmodn
  • This recovers the original message M.

3. Example of RSA Encryption & Decryption

A. Key Generation Example

  1. Select two prime numbers:
    • p = 61, q = 53
  2. Compute n:
    • n = 61 × 53 = 3233
  3. Compute Euler’s Totient:
    • φ(n) = (61-1) × (53-1) = 60 × 52 = 3120
  4. Choose e such that gcd(e, 3120) = 1 (let’s choose e = 17).
  5. Compute d such that (d × 17) mod 3120 = 1:
    • d = 2753 (found using modular inverse).
  6. Public Key: (e, n) = (17, 3233)
  7. Private Key: (d, n) = (2753, 3233).

B. Encryption Example

  • Suppose we want to encrypt M = 65.
  • Using the public key (17, 3233): C=6517mod  3233=2790C = 65^{17} \mod 3233 = 2790C=6517mod3233=2790
  • The ciphertext sent is C = 2790.

C. Decryption Example

  • Using the private key (2753, 3233): M=27902753mod  3233=65M = 2790^{2753} \mod 3233 = 65M=27902753mod3233=65
  • The original message M = 65 is successfully recovered.

4. Security of RSA

✅ Based on Prime Factorization Problem:

  • Factoring n = p × q for large p and q is computationally infeasible.

✅ Large Key Size Increases Security:

  • RSA-2048 and RSA-4096 are considered secure today.

✅ Public Key Sharing is Safe:

  • Only the private key should be kept secret.

5. Weaknesses of RSA

❌ Slow Performance:

  • RSA is computationally expensive compared to AES (symmetric encryption).

❌ Vulnerability to Quantum Computing:

  • Shor’s Algorithm (for quantum computers) can factor large numbers efficiently.

❌ Poor Key Management Can Lead to Attacks:

  • Small e values like 3 can lead to attacks if improper padding is used.

❌ Padding Attacks:

  • RSA without padding (textbook RSA) is insecure.
  • Secure implementations use PKCS#1 or OAEP padding.

6. Applications of RSA

🔹 Secure Web Browsing (HTTPS/TLS):

  • Used in SSL/TLS certificates to establish secure connections.
    🔹 Digital Signatures:
  • Verifies message authenticity and integrity.
    🔹 Email Encryption (PGP, S/MIME):
  • Used to encrypt sensitive email communications.
    🔹 Cryptocurrency Wallets:
  • RSA is used in Bitcoin and Ethereum wallets for secure key exchange.

7. Alternatives to RSA

🔸 Elliptic Curve Cryptography (ECC):

  • More secure with smaller key sizes (e.g., ECC-256 is equivalent to RSA-3072).
    🔸 Post-Quantum Cryptography:
  • Algorithms like Lattice-based cryptography are being developed to resist quantum attacks.

8. Conclusion

The RSA algorithm is a cornerstone of modern cryptography, providing secure communication and authentication. While RSA is still widely used, newer algorithms like ECC and quantum-resistant cryptography are being explored due to security concerns in the future.