The Mathematics of Cryptography: How RSA Works

Every time you see a padlock in your browser, make a mobile payment, or log in to a banking app, public-key cryptography is protecting you. RSA, one of the first and most famous public-key systems, rests on a surprisingly small amount of mathematics: prime numbers, modular arithmetic and one theorem from the eighteenth century. In this article we build RSA from scratch and run it by hand on real numbers.

The Problem RSA Solves

Traditional ciphers use one secret key for both locking and unlocking. That raises a chicken-and-egg problem: how do two strangers on the internet agree on a secret key without an eavesdropper hearing it? Public-key cryptography solves this by using two keys:

• A public key, which anyone may know and use to encrypt a message to you.
• A private key, which only you hold and which decrypts those messages.

The trick is to make the public key easy to compute from the private key, but practically impossible to reverse. RSA achieves this using the difficulty of factoring large numbers.

RSA is named after Ron Rivest, Adi Shamir and Leonard Adleman, who published it at MIT in 1977. Remarkably, Clifford Cocks at the British intelligence agency GCHQ had found an equivalent system in 1973, but it remained classified until 1997.

The Mathematical Ingredients

Euler's totient function

For a positive integer \(n\), \(\varphi(n)\) counts the integers from 1 to \(n\) that share no common factor with \(n\). For a prime \(p\), \(\varphi(p) = p - 1\). For a product of two different primes,

$$ \varphi(pq) = (p - 1)(q - 1) $$

Euler's theorem

If \(\gcd(m, n) = 1\), then

$$ m^{\varphi(n)} \equiv 1 \pmod{n} $$

This generalises Fermat's little theorem and is the reason RSA decryption works.

Modular inverses

The private key is the inverse of the public exponent modulo \(\varphi(n)\), found with the extended Euclidean algorithm.

The RSA Algorithm

Key generation

1. Choose two large distinct primes \(p\) and \(q\).
2. Compute the modulus \(n = pq\).
3. Compute \(\varphi(n) = (p - 1)(q - 1)\).
4. Choose a public exponent \(e\) with \(1 < e < \varphi(n)\) and \(\gcd(e, \varphi(n)) = 1\).
5. Compute the private exponent \(d\) so that \(ed \equiv 1 \pmod{\varphi(n)}\).

The public key is \((n, e)\). The private key is \(d\) (and \(p\), \(q\), \(\varphi(n)\) must also be kept secret).

Encryption of a message number \(m\) with \(0 \leq m < n\):

$$ c = m^e \bmod n $$

Decryption:

$$ m = c^d \bmod n $$

Why decryption recovers the message

Since \(ed \equiv 1 \pmod{\varphi(n)}\), we can write \(ed = 1 + k\varphi(n)\) for some integer \(k\). Then

$$ c^d \equiv (m^e)^d = m^{1 + k\varphi(n)} = m \cdot \left(m^{\varphi(n)}\right)^k \equiv m \cdot 1^k = m \pmod n $$

using Euler's theorem. (The rare case where \(m\) shares a factor with \(n\) also works, which can be shown with the Chinese remainder theorem.)

Worked Example 1: A Tiny RSA System by Hand

Key generation

• Choose \(p = 5\) and \(q = 11\).
• Then \(n = 5 \times 11 = 55\).
• And \(\varphi(55) = 4 \times 10 = 40\).
• Choose \(e = 3\). Since 3 does not divide 40, \(\gcd(3, 40) = 1\).
• Find \(d\) with \(3d \equiv 1 \pmod{40}\). Trying multiples of 40 plus 1: 41 is not divisible by 3, but \(81 = 3 \times 27\). So \(d = 27\).

Check: \(3 \times 27 = 81 = 2 \times 40 + 1\). Correct.

Encryption of \(m = 7\):

$$ c = 7^3 \bmod 55 = 343 \bmod 55 $$

Since \(6 \times 55 = 330\), we get \(c = 343 - 330 = 13\).

Decryption: compute \(13^{27} \bmod 55\) by square-and-multiply. Write \(27 = 16 + 8 + 2 + 1\).

• \(13^2 = 169 \equiv 169 - 165 = 4\)
• \(13^4 \equiv 4^2 = 16\)
• \(13^8 \equiv 16^2 = 256 \equiv 256 - 220 = 36\)
• \(13^{16} \equiv 36^2 = 1296 \equiv 1296 - 1265 = 31\)

Now multiply the needed powers, reducing as we go:

$$ 13^{27} \equiv 31 \times 36 \times 4 \times 13 \pmod{55} $$

• \(31 \times 36 = 1116 \equiv 1116 - 1100 = 16\)
• \(16 \times 4 = 64 \equiv 9\)
• \(9 \times 13 = 117 \equiv 117 - 110 = 7\)

We recover \(m = 7\). The system works.

Worked Example 2: The Classic Textbook Key

Now a slightly larger system.

Step 1: Choose \(p = 61\), \(q = 53\). Then \(n = 61 \times 53 = 3233\) and

$$ \varphi(n) = 60 \times 52 = 3120 $$

Step 2: Choose \(e = 17\). Since 17 is prime and does not divide 3120, \(\gcd(17, 3120) = 1\).

Step 3: Find \(d\) with the extended Euclidean algorithm.

$$ 3120 = 183 \times 17 + 9 $$

$$ 17 = 1 \times 9 + 8 $$

$$ 9 = 1 \times 8 + 1 $$

Working backwards:

$$ 1 = 9 - 8 = 9 - (17 - 9) = 2 \times 9 - 17 $$

$$ 1 = 2(3120 - 183 \times 17) - 17 = 2 \times 3120 - 367 \times 17 $$

So \(17 \times (-367) \equiv 1 \pmod{3120}\), giving \(d = -367 + 3120 = 2753\).

Check: \(17 \times 2753 = 46{,}801 = 15 \times 3120 + 1\). Correct.

Step 4: Encrypt \(m = 65\) (the ASCII code for the letter A):

$$ c = 65^{17} \bmod 3233 = 2790 $$

Step 5: Decrypt:

$$ 2790^{2753} \bmod 3233 = 65 $$

Both powers are computed with square-and-multiply in about a dozen squarings each, and the original letter A comes back. An attacker who knows only \(n = 3233\) and \(e = 17\) must find \(d\), which requires \(\varphi(n)\), which in turn requires factoring 3233 into \(61 \times 53\). For a four-digit number that is easy; for real keys it is not.

Why RSA Is Secure in Practice

Real RSA moduli are 2048 or 3072 bits long, that is, around 617 or 925 decimal digits. Multiplying two 1024-bit primes takes a computer microseconds, but the best known classical factoring algorithm, the general number field sieve, would need an infeasible amount of computation to factor such a product. The largest RSA challenge number factored publicly so far, RSA-250 in 2020, had 829 bits and took about 2,700 core-years of computing.

In practice, RSA is combined with careful padding schemes such as OAEP, because "textbook" RSA, as in our examples, leaks patterns: encrypting the same message always gives the same ciphertext. RSA is also usually used to exchange or sign a short key, while faster symmetric ciphers like AES encrypt the bulk data.

Did You Know?

• Shor's algorithm, published in 1994, could factor large numbers quickly on a big enough quantum computer, which is why researchers are developing "post-quantum" cryptography.
• The common public exponent \(e = 65537 = 2^{16} + 1\) is chosen because its binary form has only two 1s, making encryption fast.
• In 1977, Martin Gardner's Scientific American column challenged readers to break an RSA-129 message. It was cracked in 1994 and read "The Magic Words are Squeamish Ossifrage".

Key Takeaways

• RSA uses a public key \((n, e)\) for encryption and a private key \(d\) for decryption.
• Key generation needs \(n = pq\), \(\varphi(n) = (p-1)(q-1)\) and \(d = e^{-1} \bmod \varphi(n)\).
• Euler's theorem guarantees that \((m^e)^d \equiv m \pmod n\).
• Square-and-multiply makes huge modular powers fast to compute.
• Security rests on the difficulty of factoring large \(n\).

If cryptography or number theory assignments are giving you trouble, Amathify's experts and PhD scholars provide step-by-step solutions through WhatsApp or the Ask a Question form.