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

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 7 times 11 so Phi of 77 is 6 times 10 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 the 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 two numbers such that they 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 will always be left with 1 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 1 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 1 by any number say M it always equals M in the same way we can multiply the left side by n to get M on the right hand side and this can be simplified as M to the power of K times Phi n plus 1 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 N 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 3127 then she calculates Phi of n easily since she knows the factorization of n which turns out to three thousand and sixteen next she picked 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 two thousand and eleven 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 ^ e mod n call this see 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 ^ 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 rediscovered in 1977 by Ron Rivest Adi Shamir and len Adelman 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 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