Explore RSA encryption with small primes — generate keys, encrypt and decrypt messages, see modular exponentiation step by step.
RSA (Rivest–Shamir–Adleman, 1977) is the foundational public-key cryptosystem that secures most of the internet. Its security rests on the practical difficulty of factoring the product of two large primes. The algorithm is elegant: choose two primes p and q, compute n = pq and φ(n) = (p−1)(q−1), pick a public exponent e coprime to φ(n), and derive the private exponent d = e⁻¹ mod φ(n). Encryption is c = mᵉ mod n; decryption is m = cᵈ mod n.
This educational tool lets you experiment with RSA using small primes so every step is transparent. Enter your own primes (or use presets), and the calculator generates the full key pair, encrypts a message, decrypts it, and verifies the round trip. Each modular exponentiation is shown step-by-step using the square-and-multiply algorithm, so you can trace exactly how the ciphertext and plaintext are computed.
Whether you are a student learning number theory and cryptography, an instructor building a lecture demo, or a developer wanting to understand the math behind TLS, this tool makes RSA's inner workings visible and interactive.
RSA is one of the most important algorithms in computing, yet its mechanics are often presented as opaque formulas. This demo makes every step visible — from prime selection through key generation to the bit-by-bit square-and-multiply exponentiation. Seeing the math in action builds genuine understanding rather than rote memorization.
It also serves as a sanity-check tool: enter your homework primes, verify the key generation, and trace the encryption/decryption to catch arithmetic errors. For instructors, the step-by-step output can be projected or screenshotted directly into lecture slides.
Key generation: n = p×q, φ(n) = (p−1)(q−1), e: gcd(e,φ)=1, d = e⁻¹ mod φ(n). Encrypt: c = mᵉ mod n. Decrypt: m = cᵈ mod n. Correctness: mᵉᵈ ≡ m (mod n) by Euler's theorem.
Result: n=3233, φ=3120, e=17, d=2753, c=42^17 mod 3233=2557, decrypt=2557^2753 mod 3233=42 ✓
With p=61, q=53: n=3233, φ=3120, e=17 (coprime to 3120), d=2753. Message 42 encrypts to 2557 and decrypts back to 42.
RSA was published in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. An equivalent system had been secretly developed in 1973 by Clifford Cocks at the UK's GCHQ but remained classified until 1997. RSA was the first widely practical public-key cryptosystem and enabled secure internet communication, digital signatures, and key exchange. It remains the foundation of PKI (Public Key Infrastructure) and is used in TLS/SSL, SSH, PGP, and many other protocols.
The core operation in RSA — computing m^e mod n — uses the square-and-multiply algorithm for efficiency. The exponent e is processed bit by bit from LSB to MSB: if the current bit is 1, multiply the accumulator by the current power of the base; then square the base. This reduces O(e) multiplications to O(log e), making RSA practical even with 2048-bit exponents.
RSA relies on three pillars of number theory: Euler's theorem (a^φ(n) ≡ 1 mod n for gcd(a,n)=1), the Chinese Remainder Theorem (used to speed up decryption by working mod p and mod q separately), and the computational difficulty of integer factorization. The security assumption is that factoring n = pq is infeasible for sufficiently large primes, even though no mathematical proof of this difficulty exists — it is an empirical assumption supported by centuries of failed factoring attempts.
RSA's security depends on the difficulty of factoring n = p × q. If an attacker could factor n, they could compute φ(n) and derive the private key d. Understanding this concept helps you apply the calculator correctly and interpret the results with confidence.
e must be coprime to φ(n). The most common choice in practice is 65537 (2¹⁶+1) because it has only two 1-bits, making exponentiation fast.
d is the modular multiplicative inverse of e modulo φ(n), computed via the Extended Euclidean Algorithm. It satisfies e×d ≡ 1 (mod φ(n)).
By Euler's theorem: mᵉᵈ = m^(1 + kφ(n)) = m × (m^φ(n))^k ≡ m × 1^k ≡ m (mod n), provided gcd(m,n) = 1. Understanding this concept helps you apply the calculator correctly and interpret the results with confidence.
Modern RSA uses at least 2048-bit keys (about 617 decimal digits for n). 4096-bit keys are increasingly recommended. This demo uses tiny primes for educational clarity.
Classical RSA with 2048+ bits remains secure against known classical attacks. However, a sufficiently large quantum computer running Shor's algorithm could break it, motivating post-quantum cryptography research.