Modular Exponentiation Visualization | Square-and-Multiply, Toy RSA

The idea: arithmetic on a clock

Modular arithmetic works with the remainders 0 to n − 1 only. Picture a clock with n hours and 0 at the top. Adding b walks b hops round the clock, and when you pass n − 1 you wrap back to 0. On a 12-hour clock, 9 + 5 lands on 2, because 14 = 1·12 + 2. We write 9 + 5 ≡ 2 (mod 12) (Demo: clock arithmetic, 9 + 5 mod 12).

Adding mod 12 walks round the clock; the wrap past 11 is what "mod 12" means.

Reduce after every step

The remainder of a sum or a product only depends on the remainders of its parts: (a·b) mod n = ((a mod n)·(b mod n)) mod n. So you can take the remainder after every multiplication, and no number ever grows past n². 3¹³ is 1,594,323, but working mod 7 the page never sees a number bigger than 36.

Square-and-multiply

Multiplying the base by itself e − 1 times is far too slow for big exponents. Square-and-multiply (binary exponentiation) reads the bits of e from left to right instead:

Start with r = b for the leading 1 bit.
For every further bit, square: r ← r² mod n. This doubles the exponent reached so far.
If that bit is 1, also multiply: r ← r·b mod n. This adds 1 to the exponent.

For 3¹³ mod 7, 13 = 1101₂ and the exponent grows 1 → 3 → 6 → 13 (Demo: 3^13 mod 7 by square-and-multiply). The table on the canvas shows one row per bit, with the square, the multiply and the exponent so far.

Bits 1, 1, 0, 1 of 13. Bit 1: start r = 3, exponent 1. Bit 1: 3 squared = 9 ≡ 2, times 3 = 6, exponent 3. Bit 0: 6 squared = 36 ≡ 1, exponent 6. Bit 1: 1 squared = 1, times 3 = 3, exponent 13. Total 3 squarings + 2 multiplies = 5, naive 12 — Each bit squares (doubling the exponent); each 1 bit also multiplies by 3 (adding 1).

r = b
for each bit of e after the leading 1:
    r = r * r mod n
    if bit == 1:
        r = r * b mod n
return r

How many multiplications

An exponent with k bits, w of them ones, costs (k − 1) squarings + (w − 1) multiplies, so at most 2(k − 1). The naive way costs e − 1. The fast cost grows with the number of digits of e, the naive cost with e itself (Demo: naive vs fast multiplication count).

exponent	binary	naive: e − 1	square-and-multiply
13	1101	12	3 + 2 = 5
17 (RSA e)	10001	16	4 + 1 = 5
2753 (RSA d)	101011000001	2752	11 + 4 = 15
a 2048-bit d	2048 bits	about 2²⁰⁴⁸ ≈ 10⁶¹⁶	at most 4094

The last row is the whole point: with square-and-multiply, a real RSA decryption takes a few thousand multiplications; the naive way would not finish before the end of the universe.

Toy RSA: making the keys

RSA uses modular exponentiation for both directions. The textbook toy key (Demo: RSA key generation):

Pick two primes p = 61 and q = 53 (see Sieve of Eratosthenes for finding primes).
n = p·q = 3233. It is public.
φ(n) = (p − 1)(q − 1) = 3120. Only someone who knows p and q can compute it.
Pick e = 17 with gcd(17, 3120) = 1.
d = e⁻¹ mod φ(n) = 2753, because 17·2753 = 46801 = 15·3120 + 1. The extended Euclidean algorithm finds d; see Euclid's GCD Algorithm.

The public key is (n, e) = (3233, 17); the private key is d = 2753.

How the extended Euclidean table on (3120, 17) produces d = 2753, and what happens when e shares a factor with φ(n), is animated on Extended Euclid, Modular Inverse and Toy RSA.

Encrypt and decrypt

To encrypt a message number m < n, anyone computes c = m^e mod n. To decrypt, the key owner computes m = c^d mod n. With m = 65 (the letter A in ASCII), 65¹⁷ mod 3233 = 2790 and 2790²⁷⁵³ mod 3233 = 65 (Demo: RSA encrypt and decrypt m = 65).

Key box: p = 61, q = 53, n = 3233, phi(n) = 3120, e = 17, d = 2753, 17·2753 = 15·3120 + 1. It produces the public key (3233, 17) and the private key 2753. Below: m = 65 goes to c = 2790 by c = m to the 17 mod 3233, which anyone can do, then back to m = 65 by m = c to the 2753 mod 3233, which only the owner of d can do — Encryption uses the public e, decryption the secret d; both are one modular power.

It works because e·d = 1 + 15·φ(n), and Euler's theorem says m^φ(n) ≡ 1 (mod n) when gcd(m, n) = 1. So c^d = m^ed = m·(m^φ(n))¹⁵ ≡ m. The scheme is safe only because finding φ(n), or d, from n alone means factoring n, which is hopeless for a 2048-bit n. For how this public/private split is used in practice, see Symmetric vs Asymmetric Encryption.

RSA decryption speeds up by working mod p and mod q separately and combining the results with the Chinese Remainder Theorem.

The same square-and-multiply powers make up Diffie-Hellman key exchange, with p = 23 and g = 5.

Multiplication mod N drawn as chords on a circle, where k = 2 makes a cardioid: see The Times-Table Circle: i → k·i mod N.

What the page leaves out

Real RSA uses primes of 1024 bits or more, found with probabilistic primality tests, and the common public exponent 65537. Textbook RSA as shown here is insecure: the same message always gives the same ciphertext, so real systems add random padding (OAEP for encryption, PSS for signatures). Libraries speed up decryption with the Chinese remainder theorem, use Montgomery multiplication instead of division, and make the exponentiation run in constant time so the bits of d do not leak through timing. Signatures, which run the same powers the other way round, are on Digital Signatures.