Public Key Cryptography: RSA Encryption Algorithm

up until the 1970s cryptography had been based on symmetric keys that is the sender encrypts their message using a specific key and the receiver decrypts using an identical key as you may recall encryption is a mapping from some message using a specific key to a cipher text message to decrypt the cipher text you use the same key to reverse the mapping so for Alice and Bob to communicate securely they must first share identical keys however establishing a shared key is often impossible if Alice and Bob can't physically meet or requires extra communications overhead when using the diffie-hellman key exchange plus if Alice needs to communicate with multiple people perhaps she's a bank then she's going to have to exchange distinct keys with each person now she'll have to manage all of these keys and send thousands of messages just to establish them could there be a simpler way in 1970 James Ellis a British engineer and mathematician was working on an idea for non-secret encryption it's based on a simple yet clever concept lock and unlock are inverse operations Alice could buy a lock keep the key and send the open lock to Bob Bob then locks his message and sends it back to Alice no keys are exchanged this means she could publish the lock widely and let anyone in the world use it to send her a message and she now only needs to keep track of a single key Alice never arrived at a mathematical solution though he had an intuitive sense of how it should work the idea is based on splitting a key into two parts an encryption key and a decryption key the decryption key performs the inverse or undo operation which was applied by the encryption key to see how inverse keys could work let's do a simplified example with colors how could Bob send Alice a specific color without Eve who is always listening intercepting it the inverse of some color is called a complementary color which when added to it produces white undoing the effect of the first color in this example we assume that mixing colors is a one-way function because it's fast to mix colors and output 1/3 and it's much slower to undo Alice first generates her private key by randomly selecting a color say red next assume Alice uses a secret color machine to find the exact complement of her red and nobody else has access to this this results in cyan which she sends to Bob as her public key let's say Bob wants to send a secret yellow to Alice he mixes this with her public color and sends the resulting mixture back to Alice now Alice adds her private color to Bob's mixture this undoes the effect of her public color leaving her with Bob's secret color notice Eve has no easy way to find Bob's yellow since she needs Alice's private red to do so this is how it should work however a mathematical solution was needed to make this work in practice the solution was found by another British mathematician in cryptographer Clifford Cox needed to construct a special kind of one-way function called a trapdoor one-way function this is a function that is easy to compute in one direction yet difficult to reverse unless you have special information called the trapdoor for this he turned to modular exponentiation which we introduced as clock arithmetic in the diffie-hellman key exchange as follows take a number raise it to some exponent divided by the modulus and output the remainder this can be used to encrypt a message as follows imagine Bob has a message which is converted into a number M he then multiplies his number by itself e times where E is a public exponent then he divides the result by a random number n and outputs the remainder of the division this results in some numbers see this calculation is easy to perform however given only C E and n it is much more difficult to determine which M was used because we'd have to resort to some form of trial and error so this is our one-way function that we can apply to M easy to perform but difficult to reverse it is our mathematical lock now what about the key the key is the trapdoor some piece of information that makes it easy to reverse the encryption we need to raise C to some other exponent say D which will undo the initial operation applied to M and return the original message M so both operations together is the same as M to the power of e all raised to the power of D which is the same as M to the power of e times D e is the encryption D is the decryption therefore we need a way for Alice to construct e and D which makes it difficult for anyone else to find D this requires a second one-way function which is used for generating D and for this he looked back to Euclid over 2,000 years ago Euclid showed every number has exactly one prime factorization which we can think of as a secret key it turns out that prime factorization is a fundamentally hard problem let's clarify what we mean by easy and hard by introducing what's called time complexity we have all multiplied numbers before and each of us has our own rules for doing so in order to speed things up if we program a computer to multiply numbers it can do so much faster than any human can here is a graph that shows the time required for a computer to multiply two numbers and of course the time required to find the answer increases as the numbers get larger notice that the computation time stays well under one second even with fairly large numbers therefore it is easy to perform now compare this the prime factorization if someone told you to find the prime factorization of 589 you will notice the problem feels harder no matter what your strategy it will require some trial and error until you find a number which evenly divides 589 after some struggle you will find 19 times 31 is the prime factorization if you were told to find the prime factorization of 437,000 to 131 you probably give up and get a computer to help you this works fine for small numbers though if we try to get a computer to factor of larger and larger numbers there is a runaway effect the time needed to perform the calculations increases rapidly as there are more steps involved as the numbers grow the computer needs minutes then hours and eventually will require hundreds or thousands of years to factor huge numbers we therefore say it is a hard problem due to this growth rate of time needed to solve it so factorization is what Cox used to build the trapdoor solution step 1 imagine Alice randomly generated a prime number over 150 digits long call this p1 then a second random prime number roughly the same size call this p2 she then multiplies these two Prime's together to get a composite number n which is over 300 digits long this multiplication step would take less than a second we could even do it in a web browser then she takes the factorization of n p1 times p2 and hides it now if she gave n2 anyone else they would have to have a computer running for years to find the solution step 2 Cox needed to find a function which depends on knowing the factorization of n for this he looked back to work done in 1760 by Swiss mathematician Leonardo Euler Euler continue to investigate properties of numbers specifically the distribution of prime numbers one important function he defined is called the Phi function it measures the break ability of a number so given a number say n it outputs how many integers are less than or equal to n that do not share any common factor with n for example if we want to find the Phi of 8 we look at all values from 1 to 8 then we count how many integers 8 does not share a factor greater than 1 with notice 6 is not counted because it shares a factor of 2 well 1 3 5 and 7 are all counted because they only share factor of 1 therefore Phi of 8 equals 4 what's interesting is that calculating the Phi function is hard except in one case look at this graph it is a plot of values of Phi over integers from 1 to a thousand now notice any predictable pattern the straight line of points along the top represent all the prime numbers since prime numbers have no factors greater than 1 the Phi of any prime number P is simply P minus 1 to calculate Phi of 7 a prime number we count all integers except 7 since none of them share a factor with 7 Phi of 7 equals 6 so if you're asked to find Phi of 20 1377 a prime number you would only need to subtract 1 to get the solution 20 1376 Phi of any prime is easy to compute this leads to an interesting result based on the fact that the Phi function is also multiplicative that is Phi a times B equals Phi a times Phi B if we know some number n is the product of two primes P 1 and P 2 then Phi of n is just the value of Phi for each prime multiplied together or P 1 minus 1 times P 2 minus 1 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 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 1 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 em on the right-hand side and this can be simplified as m ^ 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 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 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 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

Channel: Art of the Problem

Views: 779,318

Rating: 4.9435463 out of 5

Keywords: rsa, rsa encryption, rsa public key encryption, rsa algorithm, euler's theorem, euler's phi function, time complexity, cryptography

Id: wXB-V_Keiu8

Length: 16min 30sec (990 seconds)

Published: Mon Jul 30 2012

Reddit Comments

[u/QAOP_Space]

Interesting, and well explained. I think most online commerce systems use a cryptographic algorithm stronger than RSA nowadays (AES, SHA-256 etc)