RSA Encryption Step-by-Step Simulator

What is RSA Encryption?

RSA (Rivest-Shamir-Adleman) is one of the first public-key cryptosystems, published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. Unlike symmetric encryption (where the same key encrypts and decrypts), RSA uses a key pair: a public key anyone can use to encrypt data, and a private key only the owner can use to decrypt it.

The mathematical security of RSA rests on the integer factorization problem: multiplying two large primes is trivial, but factoring their product back into primes is computationally infeasible for sufficiently large numbers.

How RSA Key Generation Works

The RSA key generation process involves five fundamental steps:

• Step 1 – Choose Primes: Select two distinct, large prime numbers p and q. The larger these primes, the more secure the keys.
• Step 2 – Compute Modulus: Calculate n = p × q. The bit length of n determines the key size (e.g., 2048 bits).
• Step 3 – Euler's Totient: Compute φ(n) = (p−1)(q−1). This value is critical for selecting e and computing d.
• Step 4 – Public Exponent: Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1. The standard choice is 65537.
• Step 5 – Private Exponent: Compute d using the Extended Euclidean Algorithm so that d × e ≡ 1 (mod φ(n)).

The Extended Euclidean Algorithm

Computing the private exponent d requires finding the modular multiplicative inverse of e modulo φ(n). The Extended Euclidean Algorithm efficiently solves this by extending the standard GCD algorithm to also find coefficients x and y such that a·x + b·y = gcd(a, b).

When gcd(e, φ(n)) = 1, the algorithm yields x such that e·x ≡ 1 (mod φ(n)), giving us d = x mod φ(n).

RSA Security Considerations

• Key Size: Modern RSA uses 2048 or 4096-bit keys. The small primes in this simulator are for educational purposes only and can be factored instantly.
• Padding Schemes: Real-world RSA implementations use padding (OAEP, PKCS#1) to prevent mathematical attacks on raw RSA.
• Performance: RSA is much slower than symmetric encryption. In practice, RSA encrypts a random symmetric key, which then encrypts the actual data (hybrid encryption).
• Quantum Threat: Shor's algorithm on a sufficiently powerful quantum computer could factor large numbers efficiently, threatening RSA. Post-quantum cryptography is being developed as a countermeasure.

Practical Applications of RSA

• TLS/SSL (HTTPS): RSA is used during the handshake to exchange symmetric session keys securely.
• Digital Signatures: RSA signs documents by encrypting a hash with the private key, verifiable with the public key.
• Email Encryption: PGP and S/MIME use RSA for encrypting email communications.
• SSH Authentication: RSA key pairs provide password-less authentication for remote server access.
• Code Signing: Software publishers sign executables with RSA to prove authenticity and integrity.

Frequently Asked Questions