3,233
3,120
—
bits
—
3,233
3,120
—
bits
—
RSA (Rivest–Shamir–Adleman) is the most widely deployed public-key cryptosystem in the world, securing everything from HTTPS web traffic to email encryption, digital signatures, and secure key exchange. Invented in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT, RSA was one of the first practical implementations of public-key cryptography—a concept theorized by Whitfield Diffie and Martin Hellman just one year earlier.
The security of RSA rests on a single mathematical assumption: the integer factorization problem. While multiplying two large prime numbers is computationally trivial, factoring their product back into the original primes is believed to be computationally infeasible for sufficiently large numbers. A 2048-bit RSA modulus (the product of two ~1024-bit primes) has approximately 617 decimal digits—factoring such a number would require more computational effort than currently exists on Earth.
The RSA Calculator demonstrates the core mathematical operations of RSA key generation using small prime numbers. You provide two primes p and q and a candidate public exponent e, and the calculator computes the modulus n, Euler's totient φ(n), the key size in bits, and whether your chosen e is valid (coprime to φ(n)). This tool is designed for educational purposes—real RSA implementations use primes of 512–2048 bits each.
Understanding RSA begins with Euler's totient function. For a product of two distinct primes, φ(n) = (p−1)(q−1). This value determines the mathematical structure of the key pair: the public exponent e must be coprime to φ(n) (i.e., gcd(e, φ(n)) = 1), and the private exponent d is the modular multiplicative inverse of e modulo φ(n), satisfying e × d ≡ 1 (mod φ(n)).
The RSA algorithm has three operations: key generation (choosing primes and computing the key pair), encryption (computing c = me mod n for message m), and decryption (computing m = cd mod n). The mathematical elegance lies in Euler's theorem: because ed ≡ 1 (mod φ(n)), raising a message to the e-th power and then to the d-th power (modulo n) returns the original message.
In practice, RSA is rarely used to encrypt data directly. Instead, it encrypts a symmetric key (e.g., AES-256), which then encrypts the actual data. This hybrid approach combines RSA's key exchange capabilities with the speed of symmetric encryption. RSA is also fundamental to digital signatures: signing involves raising a message hash to the d-th power, and verification raises the signature to the e-th power, confirming the signer possesses the private key.
Current NIST guidelines (SP 800-57) recommend a minimum RSA key size of 2048 bits for security through 2030, with 3072 bits recommended for protection beyond 2030. The largest RSA modulus factored to date is RSA-250 (829 bits), accomplished in 2020 using approximately 2,700 CPU core-years of computation.
RSA key generation follows these steps:
Step 1: Compute the modulus.
$$n = p \times q$$
The modulus n is public and forms part of both the public and private keys. Its bit length determines the key size.
Step 2: Compute Euler's totient.
$$\varphi(n) = (p - 1)(q - 1)$$
The totient counts integers less than n that are coprime to n. It is kept secret because knowing φ(n) along with n allows trivial factorization of n.
Step 3: Validate the public exponent.
$$\gcd(e, \varphi(n)) = 1$$
The public exponent e must be coprime to φ(n). The calculator checks the simpler necessary condition: φ(n) mod e ≠ 0. Common choices for e are 3, 17, and 65537. The value 65537 (216+1) is standard because it is prime, provides fast encryption (only 17 multiplications via square-and-multiply), and avoids vulnerabilities associated with small exponents.
Step 4: Key size in bits.
$$\text{bits} = \lceil \log_2(n) \rceil$$
This determines the security level of the RSA key. A 2048-bit key provides approximately 112 bits of symmetric-equivalent security.
The modulus n is the product of your two primes and forms the core of the RSA key pair. In real implementations, n would be a number with 617+ decimal digits (2048 bits). The small values used here are for learning purposes only.
If is_e_valid shows 0 (No), your chosen exponent e shares a common factor with φ(n), making it unsuitable for RSA. Try a different value—common safe choices are 3, 5, 7, 11, 13, 17, or 65537. The most widely used value in practice is 65537.
The key size in bits reflects the security strength. With the small primes used in this educational tool, key sizes will be far below the 2048-bit minimum recommended by NIST. This calculator demonstrates the mathematical principles; never use these small keys for actual cryptographic purposes.
Inputs
Results
This classic example produces n=3233 and φ(n)=3120. Since 3120 mod 17 = 8 ≠ 0, the exponent e=17 is valid. The key size is only 12 bits—purely educational. The private key d would be 2753 (since 17 × 2753 = 46801 = 15 × 3120 + 1).
Inputs
Results
With p=11 and q=13, n=143 and φ(n)=120. Since 120 mod 7 = 1 ≠ 0, e=7 is valid. The private key d=103 (since 7×103=721=6×120+1). An 8-bit key is trivially breakable but illustrates RSA mechanics clearly.
RSA is used for public-key encryption, digital signatures, and key exchange. It secures HTTPS/TLS connections, email (S/MIME, PGP), SSH authentication, code signing, VPNs, and countless other protocols. In practice, RSA typically encrypts a symmetric session key rather than data directly, combining RSA's key management with the speed of symmetric algorithms like AES.
The private exponent d is defined as the modular inverse of e modulo φ(n): ed ≡ 1 (mod φ(n)). This inverse exists if and only if gcd(e, φ(n)) = 1. If e shares a common factor with φ(n), no valid private key exists, and decryption would be impossible. This is a fundamental requirement from modular arithmetic (Bézout's identity).
The value 65537 = 216 + 1 is a Fermat prime that offers an optimal balance: it is large enough to resist certain mathematical attacks against small exponents (like Coppersmith's attack on e=3), yet small enough for fast encryption using the square-and-multiply algorithm (requiring only 17 modular multiplications). It has been the de facto standard since the 1990s.
NIST SP 800-57 recommends: 2048 bits minimum (112-bit security, acceptable through 2030), 3072 bits (128-bit security, recommended for long-term protection), and 4096 bits for maximum security. The largest successfully factored RSA key is 829 bits (RSA-250, factored in 2020). Keys below 1024 bits are considered broken.
Yes. Shor's algorithm on a sufficiently powerful quantum computer can factor large integers in polynomial time, completely breaking RSA regardless of key size. A quantum computer with approximately 4,000 logical qubits could factor a 2048-bit RSA key. NIST has standardized post-quantum alternatives (CRYSTALS-Kyber for encryption, CRYSTALS-Dilithium for signatures) in FIPS 203/204 (2024) to replace RSA before large-scale quantum computers become practical.
Elliptic Curve Cryptography (ECC) provides equivalent security with much smaller key sizes: a 256-bit ECC key offers comparable security to a 3072-bit RSA key. ECC is faster for key generation and signing, uses less memory and bandwidth, and is preferred for modern applications (TLS 1.3 defaults to ECDHE). RSA remains widely used for backward compatibility and in scenarios requiring simple, well-understood mathematics.
Computing the private key d requires the Extended Euclidean Algorithm or modular exponentiation, which involves iterative operations that are difficult to express as a single algebraic formula in the calculator engine. In a full implementation, d = modular_inverse(e, φ(n)), satisfying ed mod φ(n) = 1. The examples in this calculator include the computed d values for reference.
If p or q is composite, the RSA construction fails because Euler's totient formula φ(n) = (p−1)(q−1) is only correct when both factors are prime. Encryption and decryption may appear to work for some messages but will fail for others. Real RSA implementations use probabilistic primality tests (Miller-Rabin) with error probability below 2-128 to ensure both primes are valid.
RSA-OAEP (Optimal Asymmetric Encryption Padding) is the recommended padding scheme for RSA encryption, defined in PKCS#1 v2.2 (RFC 8017). It adds randomized padding to the plaintext before encryption, preventing deterministic encryption vulnerabilities and providing provable security against chosen-ciphertext attacks. Never use raw (textbook) RSA or the older PKCS#1 v1.5 padding for new implementations.
To sign a message, the signer computes a hash h of the message and raises it to the private exponent: s = hd mod n. To verify, anyone can raise the signature to the public exponent: h' = se mod n and check that h' = h. This works because only the holder of d can produce a valid signature, while anyone with the public key (e, n) can verify it. RSA-PSS is the recommended signature padding scheme.
Roboculator Team
The Roboculator Team explains calculations, planning tools, and practical formulas in clear language for real-life situations.
How helpful was this calculator?
Be the first to rate!
