RSA algorithm step by step example

hi in this video we're going to talk about rsa encryption and how it works [Music] so rsa encryption is a brilliant mathematical problem that makes the internet work today the inventors are pictured here on the screen so we have r which is revest s which is shamir and a which is edelman three brilliant people that don't get enough credit i believe in their work so rsa relies on a concept of public and private keys so i'm going to briefly talk about this but i have a full video on the differences and you can see that link here so if you were working in a program like gpg which is the open source version of pretty good privacy you would have a command that looks like this you would have a gen key command and gen key allows you to create your private and your public key when you run the program you would get something that looks like this this is an example of a public key it's a long text it's a key that is not it's not the encryption of a document but it is used to do the encryption so really it's the result of a very difficult math problem which i promise we'll get to eventually when you send an encrypted message to a friend they receive the encrypted message and they also need your public key to decrypt it and so you can see the command here we're going to encrypt a document and we are going to send it specifically to bill gates and so we used his email address and we have an output file that comes suggest to him so he's the only one that should be able to see this so when you send an encrypted message you can put it right into your text of your email so as as you should probably know email is very insecure it's clear text that people can intercept but if you send this package here obviously you can't read it and that's where the encryption is going to make it secure so you can see here that i'm running the decrypt command here so the gpg utility and then the hyphen d is the decrypt so rsa relies on the idea of factoring large numbers so what is factoring well you remember in math class they taught you how to factor things like what are the factors of 12 well 1 times 12 is a factor 2 times six are factors three times four those are all factors of twelve well let's get a little harder what are the factors of thirty-five thirty-five is a unique number we can get one and thirty-five and we can get five and seven so what's unique about this is that five and seven are prime numbers and so that's the secret to making encryption work here's a quote from an economist from years ago william stanley evans he wrote in a book in 1874 he said can the readers say what two numbers multiplied together will produce the number eight million eight billion something i think it unlikely that anyone but myself will ever know and we know today it is the product of two prime numbers of 89681 and 96.079 the reason why it is possible for him to make such a claim is because it is difficult to find the factors of a large number and that's where the key works today in encryption so rsa encryption relies on factors and large prime numbers let's take an example 31 and 37 they're both prime numbers what are they when you multiply them together that's 11 that's 1147. that's that's quite easy to solve but then we can ask what are the factors of 1147 how would you solve that well you would take your calculator and you would start to divide you divide by 2 divide by 3 divide by 5 just to see if these are factors of the number so you go through all the prime numbers so with you and your pencil and paper that would take a long time with a computer it doesn't take so long how about this example what are the factors of 414 thousand 836 now that is a little bit more difficult how about this one what are the factors of this enormous number and now we are beyond the reach of what your computer can calculate in a short amount of time and we have reached a point where we have a difficult math problem to solve and that is going to help us with encryption so let's take a simple example of how to create what's called an rsa key we're going to choose two very large prime numbers and we are going to call them p and q then we're going to find the product of those numbers and we'll call that n so n is p times q now we're going to also use an interesting number that is called the euler toitian and we are going to say that p minus 1 times q minus 1 is going to give us this number t and we'll see what happens with that in a minute now we're going to take two numbers e and d e stands for encryption d stands for decryption and we are going to find these two numbers such that that when you multiply them together and you take the mod t it's going to come out to be one now that's not real hard to do and we'll show you example here and you'll understand what that means that's that's kind of the fuzzy part of where most people get lost but hang on you'll see it's not that bad now we're going to publish two numbers we're going to say hey i have n and i have e and that becomes my public key and then i'm going to keep the other one secret d is the decryption key and n and we will not share that so that is really the essence find a really difficult prime number uh factoring problem and keep half of it secret okay so now let's work out a solution using a simple example for a public and a private key so the first thing is i'm going to choose two prime numbers now i have the right to choose any two primes i want but i'm going to pick simple ones because they're easy to work with my with my calculator and maybe with pencils and paper so 2 and 6 or 2 and 7 sounds like a good one p and q now the second is what's the product well that's pretty easy 2 times 7 is 14 so that's my big number n in the function now this letter t that we're going to calculate is the formula that says take p minus one and q minus one multiply them so two minus one is one seven minus one is six so their product is six so this t number is six that's my boundary of some upper limit that i'm going to use here in a minute okay continue to work with the problem now i need to work out d and e so d is the decryption number and e is the encryption number so it's like two halves to a factoring problem how am i gonna choose these two numbers so that if i multiply them together and i do a mod six i get a one so the mod six part comes from the previous line where did six come from t is six and now i want to get the numbers to have just a one off from a mod six okay so what does that look like all right to help me out i'm going to go in to do some work with a spreadsheet because it helps me do a lot of math so i want to choose e and i want to choose d so i could switch those d and e now the rule for the first guy is going to be he must be less than six so we need to put first of all a list here of who my choices are so i'm just going to type in the possibilities for the first number so the second rule i'm going to apply here is that the number i choose must be co-prime with 6 and 14. so first of all i'm going to ignore the 1 and look at the rest of these actually the number 6 doesn't count either because it has to be less than 6. so i'm left with 2 3 4 5. co co-prime with six and fourteen well what's co prime so two is a factor of both six and fourteen and so is four because even numbers aren't going to work here so let's let's turn those red we're gonna say no deal we've got ourselves three and five for candidates well let's see three is a factor of six so he is out and the only one left we're going to call our factor is five okay so we know that the first number that we're going to pick is 5. so the next item that i'm going to consider is d i'm going to put in a rule here that says we have to choose e times d mod 6 or mod n and that will give us one so let's see if we can find one a good candidate that will work here so the first thing i'm going to do is create just a counter list so i'm going to call this thing multiples multiples of 5 and i want to count from 1 onward so let's do 1 to 20. so the next column i'm going to calculate the number of multiples here so i'll just say that the column here is going to be equal to the previous column times 5 and then we'll fill it down and we'll get 5 10 15 20 25 30. so so far so good not too hard so the next column we're going to calculate is the mod 6 value so excel has a mod function built into it so we'll say equals mod and you can see that it wants two inputs it wants the number so that will be the previous column so we'll do d8 and then it wants the divisor so 6 is what we're talking about here so what's the 5 mod 6 that's five what's ten mod six remainder is four and fifteen mod six the remainder is three and so we'll just do a fill down and you can see that the mod is cycling through here so five four three two one 0 all the way down so now we have candidates for our second number d so remember our rule up here it says we want to choose e times d mod 6 so that we get the answer of 1. well here's an answer of 1 so i'm going to highlight that guy as a possibility we could choose this one that one also has a mod one and so any number where we have the product that as mod 6 to come up with a 1 we could use this so i could use my two numbers i could say i could say this i could say e equals 5. and the next one i could say d equals and i could use 5 we could use 11 or 17. so i don't want the same key to be used in both places so i'm just going to choose 11 for now the larger number you pick apparently it's more complex so 11 is a good choice let's so let's do 11 and 5. so let's return to the powerpoint slide here and you can see that my choice is i want to choose e times d mod 6 equals 1 and i'm going to use the 5 and 11 as the choices that i computed here on my spreadsheet all right so now i've got these two numbers what am i going to do with them so i'm going to publish my public key 5 comma 14. those two numbers together are half of the problem that i'm solving and everyone can see it so it's public the private key though let's retain and we're going to call that 11 14. so that is your public and private key so now let's put them into practice how would we run an encryption with rsa so we would know first of all the 514 is our public key let's let a message be the letter b that's my my secret message very short example one letter b now we are going to work with numbers here instead of letters and that's really how you do it in a computer anyway so instead of using ascii symbols like a is65 b is 66 as you might know we're going to let b be the number two and we'll just have a sequence to say a would be 1 b is 2 c is 3 etc so now the next result is we are going to come up with this equation it's the encryption value this is the function that is rsa this is how it's based so the encryption value equals this strange equation 2 to the 5th mod 14. now let's see where did we come up with those numbers so first of all the base 2. 2 is the encryption or this is the secret message this is the thing that's going to be encrypted the letter b so b is 2 remember and now where's the 5 come from well you can see that 5 is the first part of the public key so take your encrypted message or the part to be encrypted take it to the power of the public key the first value the public key the second then is mod 14. all right so we could do this with a calculator it's not too hard we could even do it in your head almost two to the fifth so two to the fifth is 2 4 8 16 32 so that is our first part if you take 32 and divide it by 14. let's see you can take multiples of 14. you got 14 28 and then it gets bigger it so 28 is the largest number that can go into 32 mod it and you get 4. so that's the remainder 4. all right so 4 is our magic number this is the this is the result the encrypted message so since it is the number four we want to translate it back into english you might say or into letters and so we'll call that the letter d so there's our encryption so if i were to send you the letter d we have different message now now just change that for every single letter in your message and you've got a random cipher okay so now you got the letter now you want to decrypt the message what does d mean well we first of all have to have the public key so 5 14 it was already calculated so now i also know the private key since uh of course that's private the 11 part so can i take 11 and run it through a formula to get back to my original message the answer is i can so the secret message is the number 4 or the letter d instead of d let's translate it into 4 as i mentioned now here's how you do the decryption so the decryption value is the same kind of equation but with a different uh different placeholder so 4 is the letter d 11 the exponent 11 comes from the first part of my private key the mod of course is 14 is the same was it was before so what does this come compute to i had to use a calculator but i come up with this it's 4 million in something now that is 4 to the 11th power if i do a mod again i get four so how do you calculate that so if you want to find out what the mod of third of this big number is you can take the the big number divided by 14 and you get this long thing how do you how do you get the mod out of that well you just ignore the first the integer part and then focus in on the decimal part what happens when you that's the remainder right so what happens you take the remainder times 14 that gives you the number two so the two part is our mod so we we got this whole thing and the answer now comes out to two two does that sound familiar two is the encrypted message and two translates that back into the letter b so we decrypted from d to b now once again take this and not just use a single letter but think of large primes now we worked with two very small numbers what are the results in the real life so if you think of two really large prime numbers and then see if the computers can calculate them let's see what happens so wikipedia of course to the rescue to find out what are the largest numbers that have been cracked here so here's here's a challenge that was produced by the rsa corporation and they said hey here's here's a large number and find the two factors go and people with their computers and hacking skills tried to come up with these with parallel processing and with high-end mainframes and here's the results so back way back in 1991 there was this 100 decimal digit number that was provided so here it is they said here is a hundred digit number and i promise you that there are only two factors in this number they are prime numbers and go go go calculate so guess and check and here's the results they found these two numbers if you can pronounce them you can win a prize i suppose too these two numbers are multiplied together to get this rsa100 so here's the results it says it took a few days using some kind of a special algorithm and a parallel computer so back in 91 that was a crackable number so it took what did they say four hours to repeat this factorization so not bad okay so we scroll through a little bit and we see that the problems get more difficult as they go here's here's an example of of a difficult problem a 200 digit number so they said hey i've got this 200 digit number find the two prime factors and 2005 they cracked it and it says here the cpu time spent on finding these factors approximately 75 years will work for a single processor so that's a lot of work so the security of rsa is that computing the two factors takes a lot of looping through guessing and checking and as you come down to the end i think they start to say that some numbers that were put into the challenge have never been factored so far here we go so there's one says and so far nobody knows nobody knows the two factors for these but they promise that there are two prime numbers so as long as our computers never catch up to the magnitude of the math problem our security is secure the encryption still works now it's interesting to see that there's developments in cracking technology so in 2019 google made some waves when they announced that they have a quantum computer what is a quantum computer so it's a computer that runs on a completely different technology rather than silicon it is looking at the spin of atoms to be able to hold data so as you know an electronics a one and a zero are the two types of data in a quantum computer if they look at an atom a single atom in an electronic formation the electron formation can have a pattern that they can observe and use as a computing device so very cutting edge here so the promise of a quantum computer is not so much that computers will all of a sudden be faster at everything they do but there's really one purpose that they seem to know that a quantum computer can do and that's factoring numbers in parallel so that way these difficult factoring problems that are the foundation of encryption will just be an easy problem to solve in linear time rather than exponential difficulty and so if the nation or company that develops this gets there first then all communications sent by agencies such as the cia the nsa any government secure thing will no longer be secure and so that means that existing encrypted messages can be seen so it's not just to worry about future encryption and so that we'll have to change our encryption but the existing things that are still locked up will all of a sudden be visible so we'll know what china said last year and the year before so there's still some debate to say did google really accomplish this they have this tiny in relative terms a tiny little computer to what we'll need but they're saying we're on the right track ibm's kind of mad because they they wanted to be there first and of course the government's got their own programs so this is a big race who's going to crack all of the codes and see the encrypted messages online rsa is the foundation now and you understand a little bit about why this is a big deal in the mathematical and computer science world so thanks for watching now check out the channel i've got other videos that are related to computer security encryption working with not only app development but with it systems as well so hang around and learn something new today you

Channel: Programming Professor

Views: 60,090

Keywords: RSA algorithm example step by step, rsa, rsa encryption, rsa algorithm, rsa step by step, rsa public key encryption algorithm, rsa public key encryption, rsa and aes, rsa prime numbers, rsa math explained, rsa math example, rsa discrete math, rsa encryption discrete mathematics, encryption discrete math, rsa explained, rsa example p=7 q=11, rsa algorithm example in cryptography, rsa algorithm example, rsa step by step example, rsa encryption example, rsa keys explained

Id: j2NBya6ADSY

Length: 20min 41sec (1241 seconds)

Published: Thu Sep 03 2020