Why Does RSA Work?

This post was written by Jake on January 6, 2008
Posted Under: Computer Science, Math

To skip to the math, scroll down or click here.

adleman_r_s.jpg

The Algorithm

The algorithm is divided into three stages: precalculation, encryption, and decryption. Precalculation is performed a single time for each person with a public/private key pair, and encryption/decryption is performed for each message.

Precalculation

  1. Pick primes: Find two arbitrarily large prime numbers, p and q.
  1. Determine the modulus: Multiply p and q to get n. This will be your modulus for all equations.
  1. Calculate phi(n): Using Euler’s totient function, calculate $\phi(n) = (p-1) * (q-1)$ . This number is a secret number, so don’t give it away. The strength of the algorithm depends on $\phi(n)$ being hard to calculate when given a sufficiently large n = p * q
  1. Determine an encryption exponent: Take any number, e, such that GCD($\phi(n)$, e) = 1. This means that they are relatively prime, and share no common factors. This number is considered your public key (when combined with n), and you can give this number to whoever you like.
  1. Compute the decryption exponent: Solve the Extended Euclidean Algorithm of GCD($\phi(n)$, e) to find e^{-1}. This is your private key.

We have a private decryption key pair: {n, d}, and a public encryption key pair: {n, e}.

Encryption

$m_{1} \equiv m^{e} (mod\ n)$

$m_{1}$ is the encrypted message, and it can safely be sent publicly.

Decryption

$m_{2} \equiv m_{1}^d (mod\ n)$

$m_{2}$ is the decrypted message. The person with the private key for the message will be able to read it, and theoretically, nobody else.

Is the message preserved?

$m_{2} \equiv m_{1}^{d} (mod\ n) \equiv m^{ed} (mod\ n)

Applying the Corollary to Euler’s Theorem to $m^{ed} (mod\ n)$, we get $m^{1} (mod\ n) \equiv m$.

We also notice that $m^{ed} \equiv m^{ee^{-1}} \equiv m (mod\ n)$

Why is it hard for an attacker to crack?

In a perfect world, the attacker needs to solve some equivalent of the Integer Factorization Problem to factor n, which is suspected to be outside of complexity class P using classical computation. If we have access to quantum computers, we have access to an algorithm, Shor’s Algorithm, to crack integer factorization efficiently, but probabilistically.

The essential problem that the attacker faces is as follows: they have the encryption exponent and the modulus. They know what n is, but they currently have no method of calculating what $\phi(n)$ is without first factoring n. They need to find the decryption exponent, d = $e^{-1}$,, but can’t find the exponent without being able to solve the Extended Euclidean Algorithm, where they need to know the value of $\phi(n)$. So long as n is hard to factor, RSA will remain difficult to break.

We don’t live in a perfect world, and there are plenty of examples of attacks that take advantage of weak implementations of RSA. See RFC 3447 for some best practices.

The Math


Extended Euclidean Algorithm

The Euclidean Algorithm finds the Greatest Common Divisor (GCD) of two integers, a and b. The Extended Euclidean Algorithm finds integers m and n in the following equation:

$GCD(a,\ b) = m * a + n * b

Euclidean Algorithm

To see how it does this, we will look at an example. Let a = 200, b = 37. Please note that 200 = \phi(101 * 3). Since (200, 37) = 1, this is the equivalent of trying to find 37-1 (mod 200). For previous writings on the material, click here.

  1. $200 = 37 * 5 + 15$
  2. $37 = 15 * 2 + 7$
  3. $15 = 7 * 2 + 1$
  4. $7 = 1 * 7 + 0$

Line 3 is considered the “final” line of the algorithm because it is the last line where the remainder is nonzero. The remainder of that line, 1, is also GCD(200, 37).

Extended Euclidean Algorithm

We start by rewriting every equation so that the remainder is on the RHS.

  1. $15 = 200 – 5 * 37$
  2. $7 = 37 – 2 * 15$
  3. $1 = 15 – 2 * 7$

From here, we start at line 3, and substitute in line 2. Don’t simplify any multiplications, just the additions.

$1 = 15 – 2 * 7 = 15 – 2 * (37 – 2 * 15)$
$1 = 5 * 15 – 2 * 37$

Substitute line 1 into the resulting equation.

[Unparseable or potentially dangerous latex formula. Error 5 : 533x369]

$1 = 5 * 200 – 27 * 37$

We now have everything that we need for the inverse of 37. It turns out that $1 = 5 * 200 – 27 * 37$ is equivalent to saying:

$-27 * 37 \equiv 173 * 37 \equiv 1 (mod\ 200)

so 173 is the multiplicative inverse of 37 (mod 200). Neat, huh?

Fermat’s Little Theorem + Euler’s Theorem

pierre_de_fermat.png
In a letter written in 1640, Fermat (of Pythagorean fame) offhandedly mentioned that he had noticed and proved the following relation:

Fermat’s Little Theorem

For a any integer, and p prime,

$a^{p-1} \equiv 1 (mod\ p)$

As he is occasionally noted for doing, he did not bother to write down the proof. Leibniz is said to have proved it, but didn’t get around to publishing it. He was an inventor of calculus, so we’ll cut him some slack.

leonhard_euler.jpg

Enter Leonhard Euler. Euler was 18 feet tall, shot laser beams from his eyes, and proved Mathematics every second he was awake. In 1736, he took 23 minutes off from a conquest of Mars to prove Fermat’s Little Theorem.

This wasn’t enough, though. He attempted to find a way to generalize it for any number, n, instead of just for primes, p, but couldn’t. The problem tortured him for 24 years, when in 1760* he was finally able to produce his proof.

His proof makes use of a function he defines, phi(x).

Euler’s Totient Function

For any positive integer, n, $\phi(n)$ is equal to the number of positive integers where GCD(a, n) = 1, for a < n.

Most germane to this discussion, for any prime, p, $\phi(n)$ = p-1. This makes perfect sense, of course, as a prime is indivisible, and therefore all numbers less than p don’t share factors with p, or else p could be divided!

The formula ends up being:

Euler’s Theorem

For any positive integers a, n:

$a^{\phi(n)} \equiv 1 (mod\ n)$

* Wikipedia says 1736, my number theory book says 1760, tie goes to the book.

Corollary to Euler’s Theorem

Because $a^{\phi(n)} \equiv 1 (mod\ n)$, we can reduce the multiplication needed for any power of a > n.

$a^{b} \equiv a^{b (mod\ \phi(n))} (mod\ n)$

Edit: added link to Wikipedia’s article on Integer Factorization, and a better explanation of why the attack is hard

Popularity: 31% [?]

Reader Comments

I was so incredibly disappointed when I missed the day of class my professor explained how this technique worked in my number theory class. I spent all semester thinking to myself how boring number theory next to more modern mathematics, and then I went ahead and missed what is perhaps coolest practical result of the entire subject!

Thank you so much for presenting it so clearly here. I will definitely take time to consume everything on this page.

#1 
Written By tac-tics on January 7th, 2008 @ 11:56 am

Add a Comment

required, use real name
required, will not be published
optional, your blog address

Next Post:
Previose Post: