RSA Algorithm Explained: How to Select d, e, n, p, q, and φ (phi)

[00:00:00]welcome in this video I'll explain how to use the RSA algorithm to encrypt and decrypt information first of all RSA has a lot of meanings in the security world first of all it's the name of this algorithm which is probably the most widely used encryption algorithm in the world secondly it's also the name of a company RSA which was founded to market products that used RSA back when it had a patent and as sense uh developed many products including two Factor authentication key fobs like these and it's also the name of a annual conference that's held every February in San Francisco but originally RSA came from the names of these three MIT professors Ron rivest Addie Shamir and Leonard Adelman and their last names formed the acronym RSA so the algorithm itself was invented in 1977 and was published the following year in the communications of the a M this is the paper and it was a groundbreaking piece of research and what was so groundbreaking about it was that for the first time in history we had a system to encrypt with one key and to decrypt with another so in this case we have one public key to encrypt and then the private key would decrypt and the inverse was also true so a private key could be used to encrypt and the public key would be then used to decrypt so to remind you about inverse functions the inverse of any number times itself is one and this is useful for encryption for example let's say we have a secret message 7 and I want to encrypt this secret message by multiplying it by another number in this case 328 so the result of this is a larger number and it's not clear that that seven is a part of this number so it's it's it's obfuscated it's encrypted Let's Pretend in the number 2296 but if I multiply 2296 by the inverse of 328 I get back to the secret number 7 so this is the RSA algorithm the one used for encryption you take a message M raised to the eth power and then you take the modulus of that result for the number n and the result is is your Cipher text and this is the decryption function you take the cipher text raise it to the power D mod n and that results in your plain text message so if you look at both of these together you see that one is undoing the effect of the other now all of these different variables here two of these e and N form the public key the key that's shared with the world that could be published on the web or anywhere and the exponent D is the private key the number that must be kept secret for this scheme to work so rsa's been is called a oneway trapdoor function and what this means is there's no way to undo the encryption function unless you know the trap door and in this case the the number n is the trapo so the question is why is it difficult to find n or the trapo in in since it's published to the world and the answer is prime factorization and this gets back to the fundamental theorem of arithmetic which holds that Any number greater than one can be written in exactly one way as the product of prime numbers so for example the number 15 can be written as the product of the prime numbers three and five or or the number 255 can be written as the product of three primes namely 35 and 17 so for example it's easy to find the product of two large prime numbers but it's very hard to take a very large product and Factor it to find the two primes that compose it now let me show you a real world application of this this number here is my pgp public key or in other words the variable n it is a 4,096 bit number and here is expressed in decimal form and you can see that is huge now the question is what two prime numbers multiply together result in this large number n and this is a problem which is supposed to be impossible for the world's Computing resources to solve for many many decades in fact 50 years is probably a low estimate so knowing the factors of n is the trapo in this trapo function if you know the factors of n you can decrypt a message that's been encrypted with the public key now you try so here is the algorithm for encryption and decryption and here's the message for you to encrypt in this case the secret is the answer to the ultimate question of life the universe and everything or in other words the number 42 and I'm giving you two primes 61 and 53 represented by P and Q I'm also giving you e which is 17 and n 3,233 and D which is 2753 so I'll explain how to calculate these constants later but for now you can use them to encrypt the message and decrypt so try that out put this video on pause okay let's check your work so to encrypt we have 42 raised to the 17th power this is the variable e mod n or 3,233 and that gives us our Cipher text result if we were to type all of this into wolfrom Alpha and calculate it it tells us the result is 257 so there we are this is our Cipher text now for decryption so we take the cipher text 2557 raised to D which is 2753 mod n which is 3233 and this should give us back to our plain text message again typing this into wolf from alpha we get this result the plain text 42 so the question is how do you choose your own values of n e and D so in the previous example I gave you these variables but how do you calculate these for yourself so you can use RSA in your own system well first you choose two very large primes second you calculate a constant fi which I'll explain and you choose two exponents e and D in a very specific way which I'll also explain so first choose two very large Primes so these primes represented by P and Q when multiplied together give us n so the question is how large should p and Q be well again back to my example of my public pgp key this is 4,096 bits which means that P and Q are each 248 bits and multipli together these two very large prime numbers resultant in it's important that N is a very large number the conservative recommendation currently is that it be at least 4,096 bits long so the second step is to calculate fi so fi is a mathematical constant which stands for the oiler totient function which is named after one of the great mathematicians of all time Leon har Oiler as commemorated on this this Swiss Fran bill so we need to find a number five so that almost any X raised to F mod n will result in one this is important because it will allow us to derive the inverse of e f is calculated as the product of p minus1 and Q minus one it also has the limitation that five must not share a factor with e so you just have to check this before you continue using the algorithm so the final step is to choose exponents e and D so first you can choose a small e it just has to be greater than two and very commonly e is three it's a constant in many systems or five or 17 the difficult part is finding the inverse of e which is d and specifically it has to be the inverse of e mod f this is the algorithm for this e * D mod 5 gives us one if this is true then we have found the inverse of e now to do this we're going to use an ancient algorithm created by the mathematician uid another one of the The Luminaries of mathematics this particular algorith which he designed well over 2,000 years ago is called the extended greatest common divisor algorithm or the extended ukian algorithm and I'll explain how this works so we start off with our very large primes five and 11 and we set e to the value seven and now our task is to find its inverse so first we find n which is the product of p and Q so 5 * 11 is 55 so so n is 55 now we find F so f is p -1 * Q minus one and in our case this gives us 40 so f is 40 now the task is to find D and this is where we use the extended ukian algorithm we have to find D so that e * D mod 5 is 1 there are formal ways of expressing this algorithm but I'll show you a shorthand way of doing this which you can use to calculate D using fi and E first rewrite a table consisting of two columns and two rows in the top row we write the number five in our case 40 in both columns and then in the second row we have the variable e and in the second column we have the number one so we always start off this way with five e and 1 so you start off by dividing five by e or in our case divide 40 by 7 and this gives us the number five now we multiply this result five by seven and by 1 to give us 35 and 5 now we take these two results and we write them below seven and one in each column now we subtract these results from five in both columns this case 40 minus 35 for colum 1 and 40 - 5 in column 2 and the result of this we write Below in each of the columns and now with this third row we can remove the first row so that now we have a new row one and a new row two and we start over again we divide 5 into 7 which goes in one time and now we multiply 1 by five and 1 by 35 we subtract 5 from seven and we subtract 35 from 1 and this gives us 2 and - 34 now with this negative result we have to do one additional step which is to take its modulus so - 34 mod 40 or mod 5 and to do this we simply add these two numbers together - 34 and 40 to give us a positive number in this case six so we write six in column two and once again now we have three rows and we can eliminate the first row and we do this one more time so two goes into five two times and we take this result multiply it by the numbers in the second row row and this gives us 4 and 12 and we subtract so we have 1 and 23 now this number one is a special result when we get one in the third column of column one that tells us that we have arrived at our result which means that 23 is the value for d and we can check our work so here is the Formula E * D mod 5 results in one so in our case here are our values 7 * 23 our derived D value mod 40 results in one so it checks so here are all the variables we need to use the RSA algorithm our public key is e and n or 755 and our private key is D or 23 now you try use these primes 89 and 107 and e as your exponent Now find fi and using fi derive D you can pause this video and then we'll go over the solution okay let's check your work so n is p * Q or in our case 89 * 107 and this is 9523 so now that we have n let's calculate F so P -1 * Q -1 so f is 9,328 and now we find D so again here's our Formula E * D mod 5 = 1 so again using the extended ukian algorithm we write five in the first row in both columns 1 and two and in the second row column one you write the variable e and in the second column row two we write the number one we see how many times three goes into 9328 and we get this result 3,19 now we multiply 3,19 by three and also by one which gives us these results we subtract our numbers from Row one and get this result now this is much faster because we arrived at one at in the first step which means that D is 6,219 so again checking our work e * D mod 5 is 1 so 3 * 6,219 mod 9,328 equal 1 so a checks so now let's talk about RSA as used in real life so RSA is about a thousand times slower than symmetric crypto systems like AES and for this reason RSA has been used from the very beginning in hybrid crypto systems or systems that use a symmetric key or Secret algorithm and an asymmetric or public key algorithm probably the most common hybrid crypto system is your web browser if you visit amazon.com using SSL and click on the padlock in the top left you will see this connection information in this case the connection is encrypted using rc4 a symmetric encryption algorithm using a 128bit key and it uses RSA as the key exchange mechanism which means all RSA is used for in this case is to encrypt the symmetric key the rc4 key and send it to the recipient once this key is received the SSL session switches over to using rc4 but RSA is used for more than just key exchange if we click on the link for certificate information we see this in this case the class 3 certificate Authority at the top signs the verisign G5 ceric certificate and the verisign G5 certificate Authority signs the verisign class 3 G3 certificate if we scroll down for details we can see amazon.com's RSA public key which we can see is 248 bits or as represented here as 256 bytes and those are the steps to use the RSA algorithm hope you found this useful