Tools / RSA Calculator
RSA Calculator
Three modes in one tool. Decrypt a ciphertext when you already know p, q, e, and c. Factor from sum when the challenge leaks p + q alongside n. Generate keys from arbitrary primes to verify your understanding. All arithmetic uses JavaScript BigInt - no size limits.
Optional - computed from p×q if omitted
Common values: 65537, 3, 17
How RSA works
1. Choose two large primes p and q. Compute n = p × q.
2. Compute φ(n) = (p-1)(q-1) (Euler's totient).
3. Choose public exponent e coprime to φ(n). Common: 65537.
4. Compute private key d = e⁻¹ mod φ(n) (modular inverse).
5. Encrypt: c = mᵉ mod n. Decrypt: m = cᵈ mod n.
CTF attacks exploit weak key generation: small primes, shared factors, smooth p-1 (Pollard), sum/product leaks.
Common RSA CTF attack patterns
Most RSA CTF challenges exploit weak key generation rather than breaking the underlying math:
- Sum/product leak - if you know
p + qandp * q, solve the quadraticx² - (p+q)x + pq = 0(use "Factor from sum" mode). - Smooth p-1 (Pollard) - if
p - 1has only small prime factors, Pollard's p-1 algorithm factorsnin seconds. - Small e with small m - if
e = 3and the message is small,m³ < n, so computing the integer cube root ofcgivesmdirectly. - Shared factor - if two public keys share a prime, GCD(n₁, n₂) reveals it.
Challenges solved with this tool: picoCTF 2022 - Sum-O-Primes, Very Smooth, picoCTF 2023 - SRA, picoCTF 2024 - rsa_oracle.
The core of RSA rests on the difficulty of factoring the modulus n = p * q. The private key exponent d is computed as the modular inverse of e modulo Euler's totient φ(n) = (p - 1)(q - 1). Decryption then computes m = cd mod n. All of this arithmetic is performed on very large integers - typically thousands of bits in real-world RSA, but only hundreds of bits in CTF problems to keep solving feasible.
A useful first step when you receive an RSA challenge is to check whether n can be factored online. Sites like FactorDB maintain a database of factored integers. If the challenge author reused or generated weak primes, the factorization may already be known. Paste n there before spending time on algebraic attacks - it often saves hours.
After recovering p and q by any method, paste them into the Decrypt mode of this calculator along with e and the ciphertext c. The tool computes φ(n), finds the modular inverse d via the extended Euclidean algorithm, and raises c to the dth power mod n to produce the plaintext integer. Convert the result to bytes (big-endian) and you typically have the flag.
For a deeper understanding of the attacks behind these challenges - small public exponent, weak modulus factoring, common modulus, Wiener's attack, and RSA oracle blinding - see the RSA Attacks for CTF guide.