If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains ***.kastatic.org** and ***.kasandbox.org** are unblocked.

Main content

Current time:0:00Total duration:4:58

- [Voiceover] We now have
a trapdoor for solving phi. If you know the factorization for N, then finding phi N is easy. For example, the prime factorization of 77 is seven times 11, so phi
of 77, is six times 10, 60 Step three, how to
connect the phi function to modular exponentiation. For this, he turned to Euler's Theorem, which is a relationship
between the phi function and modular exponentiation, as follows: m to the power of phi n, is congruent to one mod n. This means you can pick any two numbers, such that they do not
share a common factor, let's call them "m" and "n". Say m equals five and n equals eight. Now, when you raise m to
the power of phi n, or 4, and divide by n, you will
always be left with one. Now, we just need to modify this equation using two simple rules. First, if you raise the number one to any exponent, k, you always get one. In the same way, we can
multiply the exponent phi n by any number k, and the
solution is still one. Second, if you multiply
one by any number, say m, it always equals m. In the same way, we can
multiply the left side by m, to get m on the right hand side. And this can be simplified as m to the power of k,
times phi n, plus one. This is the breakthrough. We now have an equation
for finding e times d, which depends on phi n. Therefore, it's easy to calculate d, only if the factorization of n is known. Meaning d should be Alice's private key. It's the trapdoor which will allow her to undo the effect of e. Let's do a simple example, to see all of this in action. Say Bob has a message he
converted into a number, using a padding scheme. Let's call this "m". Then, Alice generates her public
and private key as follows: First, she generates
two random prime numbers of similar size and multiplies
them to get n, 3,127. Then she calculates phi of n easily, since she knows the factorization of n, which turns out to 3,016. Next, she picks some
small public exponent, e, with the condition that
it must be an odd number that does not share a factor with phi n. In this case she picks e equals three. Finally, she finds the value
of her private exponent, d, which in this case is two
times phi of n, plus one, divided by three, or 2,011. Now, she hides everything
except the value of n and e, because n and e make up her public key. Think of it as an open lock. She sends this to Bob to
lock his message with. Bob locks his message by calculating m to the power of e, mod n. Call this "c", his encrypted message, which he sends back to Alice. Finally, Alice decrypts his message using her private key, d, accessed through her trapdoor. c to the power of d, mod n, equals Bob's original message, m. Notice that Eve, or anyone else, with c, n, and e, can
only find the exponent d, if they can calculate phi n, which requires that they know
the prime factorization of n. If n is large enough, Alice can be sure that this will take hundreds of years, even with the most powerful
network of computers. This trick was immediately
classified after its publication, however, it was independently redisovered in 1977 by Ron Rivest, Adi
Shamir and Len Adleman, which is why it's now
known as RSA in encryption. RSA is the most widely
used public key algorithm in the world, and the most
copied software in history. Every internet user on earth is using RSA, or some variant of it, whether they realize it or not. Its strength relies on the
hardness of prime factorization. which is a result of deep questions about the distribution of prime numbers. A question which has remained unsolved for thousands of years. (dramatic music)