We now have a trap door for solving Phi. If you know the factorization for N, then finding Phi(N) is easy.

For example, the prime factorization of 77 is 7x11. So Phi of 77 is 6x10, 60.

Step 3: How to connect the Phi function to modular exponentiation?

For this he turned to Euler's theorem, which is a relationship between Phi function and modular exponentiation as follows:

m to the power of Phi(n) is congruent to 1 mod n.

This means you could pick any 2 numbers, that do not share a common factor, let's call them m and n,

say m equals 5 and n equals 8. Now, when you raise m to the power of Phi(n), or 4, and divide by n, you'll always be left with 1.

Now, we just need to modify this equation using 2 simple rules.

1. If you raise the number 1 to any exponent k, you always get 1.

In the same way, we can multiply the exponent Phi(a) by any number k and the solution is still 1.

2. If you multiply 1 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*Phi(n) plus 1.

This is the breakthrough. We now have an equation for finding e*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 trap door, 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 keys as follows:

First she generates 2 random prime numbers of similar size and multiplies them to get n, 3127.

Then she calculates Phi of n easily, since she knows the factorization of n, which turns out to 3016.

Next she picks some small public exponent e,

with a condition that it must be an odd number, that does not share a factor with Phi(n).

In this case she picks e equals 3.

Finally she finds the value of her private exponent d,

which in this case is 2*Phi(n)+1 divided by 3, or 2011.

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 opened 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 trap door,

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 exponent d,

if they can calculate Phi(n), which requires 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 it's publication.

However, it was independently re-discovered at 1977 by Ron Rivest, Adi Shamir and Leonard Adleman.

Which is why it's now known as RSA encryption.

RSA is the most widely used public key algorithm in the world.

And the most copied software in the history.

Every Internet user on Earth is using RSA or some very in to it whether they realize it or not.

It's strength is relies on a hardness of prime factorization.

Which is a result of deep questions about the distribution of prime numbers.

A question which is remained unsolved for thousands of years.

This is Amazing, I love this course and I learnt each and every topic interestingly. Thank you dude...