The Magic of RSA Cryptosystems

all right thank you to the brave souls who are enduring another talk of cryptography this early in the morning doesn't quite seem fair but you're doing great troopers um the the keynote was great talk about some some uh some history with the with cryptography and today I want to talk about we're gonna discuss very briefly asymmetric versus symmetric encryption we're gonna talk about it from a math standpoint it's a little bit different Mike stop smiling at me you said you're gonna make faces and then we're gonna walk through an actual example of how asymmetric encryption works for this illustration we're gonna use RSA and then we're gonna step through we're gonna step through the algorithm one step at a time so you can

understand the theory behind it and then to finish off I'll talk about some of the subtle differences between the way that we are calculating this manually encrypting and decrypting it manually versus how your computer actually does it so if you think back to algebra you have to keep things balanced on the same side so if I say minus five on one side I'm gonna have to do the same thing on the other side and then if I want to reverse that process I add or I subtracted five and then I'm gonna have to add five to get back to I was you can see how data with numbers we can use the inverse to come back full circle and we

can do this same thing with text when you represent text as numerical values and this picture that kind of illustrates that so if you guys were like me in middle school you're you're writing messages to your friends but if it's secret you have to encode it some sort of way and so if you ever did like Caesar cipher or things like that you tell your friend the key or you come up with other little secret languages so you can see that there are many kinds of ways you can permutate data to change it here are some complementary functions so if you add another example earlier if you if you add five or subtract five you can do the

inverse to get back to where you were same with division to multiplication if you send you repent matrix multiplication doesn't actually there's no such thing as matrix division so it's called inverse matrix multiplication and that will bring it back to where you were so it works for simple functions it works for trigonometric trigonometric functions and symmetric encryption is really great and all but it gets messy because it doesn't scale well because if if the person in the middle wants to send encrypted messages with symmetric encryption to each of the people here they're gonna have to distribute keys but then they got to keep track of a key per person that they're communicating that so you can see how it can quickly

get really ugly by contrast with asymmetric encryption it's more like handing out locks so you hand out your public key and that's what's represented by the lock and then the the key in this picture is represents the private key so they basically lock up the message send it to you and then you just have just that one key that you can use to decrypt all those messages it's the benefits are that it's much simpler the downside is it's a lot more it's a lot slower it's more computationally expensive but you can justify that difficulty because it is based on more complex theoretical results so asymmetric encryption is used all over the place you can see this is

something we use every day and we'll talk about that a little bit more later a brief introduction into the RSA cryptosystem the acronym RSA comes from the last names of its of its three inventors who were studying at MIT in doing research actually there was a guy named Clifford Cox he worked for a British intelligence agency and he came up with the same idea in 1973 but no one knew about it because it was kept secret until I'm gonna say like 10 or 15 years later so I kind of cool all these people were coming up with some brilliant ideas on how to make asymmetric encryption work where you've got different keys and yet you're able to still do that inverse

function process that we talked about to get your data back to where it was and be able to transmit it securely so we're gonna go through an example and this is gonna be very simple so back to middle school the message I'm sending to my friend is B I don't know if I'm cheating for a test or something don't cheat kids but B is the message we're gonna keep it really simple and we're gonna represent it with the number two if you say a is 1 B is 2 C is 3 we're gonna say B is 2 because once it's numerical we can start doing mathematical functions on it so here's our message it's going to be

represented by M and this formula C equals M ^ e mod n is the RSA formula to encrypt when we treat plaintext as our message as a large binary number if the M if our message is actually bigger than our n they you have to break it up into smaller pieces into smaller chunks to encrypt and then send piecemeal the suggestion is to break it up by the largest power of 2 that's still smaller than n if you want a fancy term to add your vocabulary we call that modular exponentiation so that's cute all right so we're gonna plug in 2 for a message there and then here's our public key so 5 and 14 are

the two values that comprise our public key and this is the public key that gets its was represented by the lock in the picture earlier so the 14 is our n value and E stands for like our encryption key is 5 so we're gonna plug those numbers into our formula there we have 2 to the 5 mod 14 to the five is 32 and 14 modulus is basically the remainder if you remember doing math and fourth grade you divide a number however many time it goes evenly and then you have some leftover numbers that become the decimal or your remainder so 14 goes into 32 cleanly twice gives us 28 the leftover is 4 so

we've successfully encrypted our message of B into 4 which will represent the letter D because it's the fourth letter so that is the message that will be sent across the wire my friend gets it you can be my friends today so you get it and letters D you're gonna change that into 4 so you can start running your calculations on it here's the formula for decryption C ^ D mod n it is different than the encryption formula you so that's why we call it a symmetric so we're gonna plug in our numbers C stands for a ciphertext so that's 4 and here's our private key the N the 14 is the same and that was represented in the

public key and then the D is the decrypt decryption key so we're gonna plug those numbers in for the power of 11 mod 14 and obviously everyone knows for the power of 11 is 4 million 194 304 so then we're gonna mod 14 on that longhand of course because that's most fun and you get to you can check me on the math it does work out so we get get it back to B which was our original message so we can see that's how it works maybe you're thinking that was really cute and fun Shelby but how how did that work so how did you know to use the key 11 right so let's let's talk about how

how to actually generate those keys and know that those numbers are going to work out so to start off you're gonna pick two prime numbers these are represented by P and Q and they're randomly chosen obviously I'm using very small numbers here but in the actual implementation your your numbers are gonna be a lot larger and these prime numbers I believe can also be pseudo prime because computationally speaking it's going to be very difficult to brute force it even using pseudo Prime's so we've got our P and our Q on our next step is we have to calculate n this is the end that was published with the public key as well as used for the

private key so our value is going to be 14 this the N is called the modulus it's also called a trapdoor because it's a one-way function not that not in the sense that it can't be undone but it's not feasible to brute-force it once you start getting into really big numbers I mean these ends are usually what is it the 2048 key so these ends are usually a lot bigger than what you can just brute force so for that reason we call it the trapdoor because it's easy to do our P times R cubed but it's very difficult to come back and because of this this is the magic of the RSA cryptosystem because of prime factorization it's

going to be easy to calculate it in one direction but nearly impossible to break the encryption by reversing it also another fun vocabulary word for you is semi prime and is considered a semi prime number because it's made of two primes so that's fun okay our next step for figuring out a system is we have to get 5 n and so we're gonna start by listing our numbers 1 through N n was 14 so here are all our numbers and then we're gonna cross out every number that has a factor in common with n so n is divisible by 2 by 7 by itself and by 1 we're actually going to give one a special pass because it makes the

math work out ones and zeros are usually just kind of special when it comes to math so except for one we're gonna cross out to all of the numbers that have a factor in common with N and so you see we're left with 1 3 5 9 11 and 13 so Phi and is the the Phi function is actually a count of the number of Co primes which is the numbers that are not crossed out so we've got 6 in this case 1 3 5 9 11 and 13 so Phi is gonna be Phi n is 6 and I didn't define co-prime co-prime means that they don't share any common factors so if you don't want to actually write

down every single number all the way up to N which is going to be a very large number there's actually a quicker way to do this this is called the euler totient function and it makes it a lot quicker for us there we get the same result so we'll go back to our where we were in the process and our next step is to choose an e so e is a little bit finicky so e you have to it has a couple conditions that's going to tell you what you can use for e the first is that it has to be between 1 and Phi n in this case Phi n was 6 so our options are 2 3

4 and 5 the next condition is that e needs to be co-prime with N and Phi n so I wrote down all the Co primes we already figured out the KO Prime's of n from our previous slide where we cross out the numbers then ko Prime's of 6 are just gonna be 1 in 5 so the e the only option we have that confits all three of these are all these conditions is 5 that's the only one common here see it's listed with all the chevron points so our E is 5 ok so I don't have any questions this is boring good ok cool our last step is to find a D and D can actually have several options and

we're gonna have to we're gonna solve this one backwards so if you look at this formula de modify n has to equal one so we're gonna solve backwards for D we're gonna plug in our numbers that we have so 5 D mod 6 has to equal 1 so what are our options well if you've got if d if d is gonna be multiplied by 5 we only have options that are multiples of 5 so our options are 5 10 15 20 25 and so on and so you have to if we run a mod 6 on each of these we're gonna keep going through that until we get one that is mod 4 mod 6 equals 1 so if you start with those

kind of a walk through this mental process with me if you start with 5 so say D is 1 if you mod 6 on that it equals 5 5 doesn't equal 1 if you go up to the next increment if you say D is 2 which means that we have 5 times 2 so 10 mod 6 we're gonna get for the next one if you move to 15 it's going to be 3 if you move to 20 it's 2 and then it goes on so actually you get this repeating pattern so every in this case its mod 6 so every 6 in integer is going to be an option that you can choose for D and

they're all gonna actually work out in this case I chose D equals 11 and there there are later on I'll show you in real world's implementations there are there are limits on what kind of a D you should choose because you have all these options and you shouldn't pick one that's too big because it's just kind of messy so we have all the pieces of our crypto system we figured out our public key and our private key and the amazing thing about RSA is that the public key is published and it includes it includes the N it includes the the encryption key and the entire algorithm the whole crypto system for RSA is publicly known and yet it still works as

long as you keep your D PQ and your Phi n secret so does that make sense how that works because little prime factorization awesome okay so there are a couple differences between the way that we calculated it and the way your computer is actually going to do it so when we were talking about the the lengths of P and Q these are these should be chosen at random and as we know when it comes to security finding at true randomness is difficult but we were not going to get into that today for finding prime integers the more efficient way to do this is using a prime ality test and your P and your Q should be different lengths of number of

bits but pretty similar like close to each other and then we know about the n we've talked about that when we talk about the key lengths it's actually the length of n so nist recommends at least 2048 bits although you can increase it if you want keep in mind that increasing it is going to lower the speed of your implementation okay number three is pretty different this is we actually didn't even talk about lambda functions when we did our walkthrough but this this function that I wrote out on step three that's called carmichael's totient function and LCM stands for least common multiple this works out because it does boil down essentially to euler's totient function which is what

we used which is the p minus 1 times Q minus 1 the reason it works is because Phi n is always going to be bit divisible by lambda n so if you want to get more into this which you probably don't but it's there's a there's a theory that kind of proves this it's called Lagrange is theorem you can apply it to the multiplicative group of integers modulo P key oh so basically a simpler way of doing it in the original paper published by the RSA inventors they did use the euler totient function but with the lambda function it's going to be more efficient to calculate and there are there's a Chinese remainder theorem that also goes

to prove that and helps solidify that as well when let's see we talked about choosing e and there all these different rules that apply it the same similar rules we used our rules for e based on v n but the same rules apply with lambda n as well the last step is the modular multiplicative inverse so your d when the original writers made RSA if they actually published it with steps four and five flipped so the way I have it written has how we do it now they actually reversed it and their original proposal the reason we switched it to this to do first and then D is because of it's just more efficient he is gonna

be smaller and so it's going to have a short bit length and a small Hamming weight which is the number of non-zeros in a stream so somehow that makes it better and more efficient and then how do we use RSA in real life it's actually really slow so you're not going to be sending user data with RSA it's too much overhead too much effort and des is a symmetric encryption so I mentioned that when you increase the key size the the implementation is slower it's not even it's not even linear so if you double the key size if you go from 2048 to 50 96 it's actually slowing it down by 6 to 7 times every time you double that key

and then we also use RSA to pass encrypted shared keys so this is where it really shines and so you want to do symmetric for speeds sake but in order to get that to work you have to be able to share those keys in a secure way where they're not going to be intercepted and that's what you use RSA for so you're going to encrypt your your symmetric key and then send that so that you can then do bulk encryption decryption operations much quicker so that's used whenever you're doing SSL sessions for authentication and sending the key so that you can prove that you are the sender is who they say they are because they're the

only one who has their private key with their also used for digital certs which are used to prove authenticity so you can sign your messages or the file even better it's best to sign the cryptographic hash of the message because then you're just doing on a small piece instead of the entire file and that basically makes it almost impossible to for non-repudiation we also use RSA for authenticating with SSH with your login keys and so RSA is a very good part of our lives and that's all I have does anybody have questions [Applause] was it fun knowing through anything so thanks enjoy that's the con