RSA Calculator | Key Generation, Encryption & Decryption Step-by-Step
Explore RSA public-key cryptography step by step. Enter two prime numbers p and q; the calculator derives n, φ(n), public exponent e, and private key d using the extended Euclidean algorithm. Encrypts and decrypts numeric messages with full modular exponentiation working shown at each step.
What Is the RSA Calculator | Key Generation, Encryption & Decryption Step-by-Step?
RSA (Rivest–Shamir–Adleman, 1977) is a public-key cryptosystem based on the mathematical difficulty of factoring the product of two large prime numbers. The public key (n, e) can be shared openly; the private key d is derived from the secret factorization of n. The security relies on the fact that computing d from (n, e) alone requires factoring n, which is computationally intractable for large primes.
Formula
n = p·q; φ(n) = (p−1)(q−1); choose e: gcd(e,φ)=1; d = e⁻¹ mod φ(n) via Extended Euclidean. Encrypt: C = M^e mod n. Decrypt: M = C^d mod n. Verify: e·d ≡ 1 (mod φ(n)).
How to Use
- 1
Enter a prime number p (e.g. 11). A green badge confirms it is prime.
- 2
Enter a distinct prime number q (e.g. 13). It must differ from p.
- 3
Enter the public exponent e, or click Auto-suggest to automatically pick the smallest valid e.
- 4
Enter a numeric message M. It must satisfy 0 < M < n (the calculator will show n after generation).
- 5
Click Generate Keys & Encrypt/Decrypt to run the full RSA algorithm.
- 6
Review the key generation steps: n, φ(n), valid e values, Extended Euclidean working for d, and verification that e·d mod φ(n) = 1.
- 7
Expand the Encryption Steps and Decryption Steps to see the square-and-multiply modular exponentiation working.
Enter two distinct prime numbers p and q, a public exponent e (or click Auto-suggest), and a numeric message M. Click Generate Keys to see the full key generation process, then encrypt and decrypt your message.
Example Calculation
p=11, q=13, n=143, φ(n)=120. Choose e=7 (gcd(7,120)=1). Extended Euclidean: 7d ≡ 1 mod 120 → d=103. Public key: (143,7). Private key: (143,103). Encrypt M=5: C = 5^7 mod 143 = 47. Decrypt: 47^103 mod 143 = 5. Verified.
Understanding RSA | Key Generation, Encryption & Decryption Step-by-Step
RSA Key Generation Steps
| Step | Operation | Formula | Notes |
|---|---|---|---|
| 1 | Choose primes | p, q prime, p ≠ q | Must be distinct; real RSA uses 1024-bit primes each |
| 2 | Compute modulus | n = p × q | Public; anyone can see n; factoring it is computationally hard |
| 3 | Compute totient | φ(n) = (p−1)(q−1) | Secret; reveals p and q if known; kept private |
| 4 | Choose public exponent | 1 < e < φ(n), gcd(e, φ(n)) = 1 | Common choices: 3, 17, 65537 (Fermat primes) |
| 5 | Find private key | d = e⁻¹ mod φ(n) | Extended Euclidean Algorithm; d is the private key |
| 6 | Encrypt | C = M^e mod n | Anyone with public key (n, e) can encrypt M < n |
| 7 | Decrypt | M = C^d mod n | Only private key (n, d) holder can recover M |
RSA Key Size Security Reference
| Key Size (bits) | n Size | Security Level | Status | Use Case |
|---|---|---|---|---|
| < 512 | 155 digits | < 56-bit equiv. | Broken — do not use | Historical/educational only |
| 512 | 155 digits | 56-bit equiv. | Broken (since 1999) | Deprecated; vulnerable to factoring |
| 1024 | 309 digits | 80-bit equiv. | Discouraged (NIST) | Legacy; not recommended after 2010 |
| 2048 | 617 digits | 112-bit equiv. | Secure through 2030 | Minimum for new systems (NIST rec.) |
| 3072 | 925 digits | 128-bit equiv. | Secure through 2040+ | Recommended for long-term security |
| 4096 | 1234 digits | 140-bit equiv. | Highly secure | High-security applications, CA root keys |
Applications of RSA Cryptography
- ▸HTTPS/TLS: RSA key exchange in the TLS handshake protects the initial connection before symmetric keys are established; modern TLS 1.3 prefers ECDHE but RSA certificates remain common for authentication.
- ▸Digital signatures: RSA signing (M^d mod n) allows anyone with the public key to verify authenticity and integrity. Used in code signing, document signing (PDF), and S/MIME email.
- ▸SSH key authentication: RSA key pairs allow passwordless login to servers; the server stores the public key; the client proves possession of the private key via a challenge-response.
- ▸Certificate Authorities (CAs): Root certificates for browsers use RSA-4096 keys that sign intermediate and leaf certificates in the X.509 PKI hierarchy.
- ▸PGP/GPG email encryption: Phil Zimmermann's Pretty Good Privacy uses RSA to encrypt session keys for secure email and file encryption.
- ▸Smart cards and hardware security tokens: RSA private keys stored in tamper-resistant hardware enable two-factor authentication and digital identity.
- ▸Quantum computing threat: RSA is vulnerable to Shor's algorithm on a sufficiently large quantum computer; NIST post-quantum standards (ML-KEM, ML-DSA) are designed as future replacements.
Frequently Asked Questions
Why is RSA secure?
RSA security relies on the integer factorization problem: given n = p·q (a large semiprime), finding p and q is computationally infeasible with known classical algorithms when p and q are each 1000+ bit primes. The best known factoring algorithm (General Number Field Sieve) requires sub-exponential but still astronomical time for 2048-bit n.
What is the Extended Euclidean Algorithm?
It is an extension of Euclid's algorithm that, given a and b, finds integers x and y such that ax + by = gcd(a,b). For RSA, we need d such that e·d ≡ 1 (mod φ(n)), i.e. e·d − φ(n)·k = 1. The Extended Euclidean Algorithm solves this directly, yielding d mod φ(n).
Why is e = 65537 commonly chosen?
65537 = 2¹⁶ + 1 is a Fermat prime with exactly two 1-bits in binary (10000000000000001), making modular exponentiation during encryption very fast (only 17 squarings, 1 multiplication). It is large enough to avoid small-exponent attacks that affect e=3 when RSA padding is not used properly.
Is RSA used directly to encrypt data?
In practice, RSA is used to encrypt a random symmetric key (e.g. AES-256), not the actual data. This is called hybrid encryption. Direct RSA encryption of data is slow (especially with large keys), limited to messages smaller than n, and vulnerable to attacks without proper padding schemes like OAEP (Optimal Asymmetric Encryption Padding).
What is RSA padding and why is it necessary?
Raw (textbook) RSA encryption is deterministic and malleable — the same message always produces the same ciphertext, and attackers can multiply ciphertexts. PKCS#1 v1.5 and OAEP padding add randomness and structure. OAEP (used in modern TLS) makes RSA encryption semantically secure (IND-CPA). Never use textbook RSA in production without padding.
You Might Also Like
Explore 360+ Free Calculators
From math and science to finance and everyday life — all free, no account needed.