The idea: one table gives the gcd, the inverse and the RSA key
RSA needs a private exponent d with e·d ≡ 1 (mod φ(n)).
Finding it is a job for the extended Euclidean algorithm. Run it on the pair
(a, b) = (φ(n), e). Each row of the table holds a remainder r and two
numbers s and t with r = s·a + t·b. The row with the last non-zero r says
gcd = s·a + t·b. When that gcd is 1, t is the inverse of b, so t gives d.
Then d decrypts what e encrypts.
The table: r = s·a + t·b on every row
Start with two rows that are true by definition: row 0 is a = 1·a + 0·b and row 1 is b = 0·a + 1·b. Then repeat:
q = ⌊ r(i−2) / r(i−1) ⌋
row i = row(i−2) − q · row(i−1) (for r, s and t alike)The r column is plain Euclid: r(i) is the remainder of r(i−2) divided by r(i−1). The s and t columns follow the same subtraction. If two rows satisfy r = s·a + t·b, their difference does too, so every row stays true. The last column of the canvas checks it. The remainders shrink, so r reaches 0. The row above that holds the gcd and its Bézout coefficients. Demo: extended Euclid on (3120, 17):
| i | q | r | s | t | check s·a + t·b |
|---|---|---|---|---|---|
| 0 | 3120 | 1 | 0 | 3120 | |
| 1 | 17 | 0 | 1 | 17 | |
| 2 | 183 | 9 | 1 | −183 | 3120 − 3111 = 9 |
| 3 | 1 | 8 | −1 | 184 | −3120 + 3128 = 8 |
| 4 | 1 | 1 | 2 | −367 | 6240 − 6239 = 1 |
| 5 | 8 | 0 | −17 | 3120 | 0 (stop) |
Euclidean Algorithm gets the same s and t the other way: it divides down the table first, then substitutes back up. This forward form is what code usually does, because it needs only the last two rows in memory.
From Bézout to the modular inverse
The modular inverse of b modulo a is a number x with b·x ≡ 1 (mod a). If the gcd row says s·a + t·b = 1, then t·b = 1 − s·a, which is 1 more than a multiple of a. So t is an inverse. It is often negative: add a once to move it into 0 … a−1. Demo: d = 17⁻¹ mod 3120 gives t = −367 and d = −367 + 3120 = 2753. Check: 17·2753 = 46801 = 15·3120 + 1.
When there is no inverse
If the gcd g is bigger than 1, a and b are both multiples of g. Then every s·a + t·b is a multiple of g too, so t·b mod a is never 1. Demo: no inverse, e = 1001: 1001 = 7·11·13 and 3120 = 2⁴·3·5·13 share the factor 13, the table ends with gcd 13, and there is no d. That is why RSA requires gcd(e, φ(n)) = 1. An even e never works, because φ(n) = (p−1)(q−1) is even. Demo: plain pair (240, 46) shows the same thing for a pair with gcd 2: 240·(−9) + 46·47 = 2, and 46 has no inverse mod 240.
| input | gcd row | result |
|---|---|---|
| p = 61, q = 53, e = 17 | 2·3120 + (−367)·17 = 1 | d = 2753 ✓ |
| p = 11, q = 13, e = 7 | 1·120 + (−17)·7 = 1 | d = 103 ✓ |
| p = 17, q = 11, e = 7 | (−1)·160 + 23·7 = 1 | d = 23 ✓ |
| p = 61, q = 53, e = 1001 | gcd = 13 | no d ✗ |
Toy RSA end to end
- Pick primes p = 61 and q = 53. Then n = p·q = 3233 and φ(n) = 60·52 = 3120.
- Pick e = 17, coprime to 3120. The public key is (e, n) = (17, 3233).
- Run the table on (3120, 17): d = 2753. Only someone who knows p and q can do this, because the table needs φ(n).
- Encrypt a number m < n: c = me mod n. Decrypt: m = cd mod n.
Both powers use square-and-multiply: write the exponent in binary, then for each bit square r, and multiply by the base when the bit is 1, reducing mod n every time. The canvas shows one bit per step. Demo: RSA encrypt and decrypt m = 65: 65¹⁷ mod 3233 = 2790 in 5 multiplications, and 2790²⁷⁵³ mod 3233 = 65 in 15 instead of 2752. The step-by-step version with the exponent growing bit by bit is on Modular Exponentiation.
Why decryption gives m back
e·d = 17·2753 = 1 + 15·3120, that is 1 + k·φ(n). Euler's theorem says mφ(n) ≡ 1 (mod n) when gcd(m, n) = 1, so cd = med = m·(mφ(n))k ≡ m (mod n). It also holds for the few m that share a factor with n (the Chinese Remainder Theorem shows it mod p and mod q separately), so every m from 0 to n−1 comes back. Demo: small key n = 143, m = 42 runs the whole chain on a key small enough to check by hand: d = 103, and 42 comes back. Signing with the same keys is on Digital Signatures.
What the page leaves out
Real keys use primes of 1024 bits or more and e = 65537, and many libraries use λ(n) = lcm(p−1, q−1) instead of φ(n), which gives a smaller d that works the same. Textbook RSA as shown is insecure: the same m always gives the same c, so real systems add random padding (OAEP). Decryption is sped up with the Chinese remainder theorem, and big-number code runs the extended Euclidean algorithm on multi-word integers, often in its binary form. Plain pairs on this page are limited to 2000 so the table fits.