Breaking RSA - Computerphile

Key Takeaways

so let's talk a bit more about RSA now we've covered RSA a few times on this channel um it's extremely prevalent and important public key um algorithm and it's used a lot in digital signatures and things like this we're going to skip a bit over how RSA Works in you know in all the mathematical detail but you have two keys right you have a public key and a private key and what typically RSA is used for is you sign something using the private key and then you verify something you verify that signature with the public key now the public key is going to be some value e and a very large number n and the private key is going to be d e and N are not Secrets this are public and D is the private key e is usually 65537 which I mentioned before best number ever and then N is a very large some somewhat random number right and it's going to be somewhere like 2,000 bits maybe even 4,000 bits long so how do we calculate n well when we generated this key the person who has the secret key they generated n by calculating P Times by Q these are two prime numbers so they use some kind of primality tests some kind of random number generation to generate two random values p and Q multiply them together used this n this e and various other bits of maths to calculate the private key and then and then essentially for the sake of this conversation delete all this intermediate information and then just publish enn on the web somewhere or on a certificate now I was reading an article day today um by researcher called hobok uh and what he'd found was that there are various um systems that are using a library that generates a weak value for p andq right values for p andq where we can break the RSA key and essentially recalculate d right which is absolutely not what you want to happen right if you have a server that's signing things with a private key and you can work out what that private key is you can then sign things as that server and so essentially pretend to be that server right that's a huge problem because you can basically convince someone's browser that you are an online shop and it would be really good idea if they gave you their credit card details right so that's not that's not what we want to break RSA what we actually have to do if you imagine you've just been given n right we have to split it into p and Q right now why is that let's talk a bit about that process right so you've got enn as an attacker you've just been given enn and what what our goal is to do is to calculate D so let's imagine that you can Factor n into p and Q so you can say okay I've worked out what p is and I've worked out what Q is then you can calculate something called the oiler tent of n which is actually in this case equal to P -1 Times by Q -1 right now we're going to skip over what that is and why right but the point is that as an attacker that's all we're interested in doing as an attacker we Factor n into p and Q we use this formula to calculate the to of n right and then we can use this equation e multiplied by D is congruent to one mod totient of n i shouldn't have put an extra bracket in there I don't know why I did that right so what does this mean well it means that basically what we want to do is we've got e because it's public e is 65537 right we want to find some number that when we multiply by E we get an intermediate value which when we reduce mod detent of n we get one again right and if we do that we've calculated our p key D because that's the actual formula for calculating D now normally you wouldn't be able to as an attacker compute this because you wouldn't have a toen of n you don't know what p and Q are because you're just given n you're not given the factorization p and Q so you can't use this formula so you can't calculate to of n which means you can't do this right that's essentially the how it works the key here is that P and Q are a secret right so could we calculate the to of n in some other way yes right you could use brute force um it would take you longer than lifetime in the universe or some unrealistic amount of time the fastest way really to calculate the to of N and hence to calculate the private key is just to factor n into p and Q now factoring n which means finding its prime factors is not difficult if n is small right so if n is 30 well one of the factors is two right two that gives us 15 three and five that that was it right not a genius it just wasn't very difficult now if n is 4,000 bits long or 2,000 bits long and you don't have one of the factors as two so you can make your problem instantly double as easy this is very very much more difficult right it's so difficult that there aren't very many good algorithms to do it unless you choose p and Q badly so imagine that P and Q are the same right in which case p is the square root of n right there are algorithms for that that's not so difficult so my suggestion would be if you're picking random primes p and Q you don't use the same Prime twice right that would be the first one but the other thing is what you might accidentally do is generate two prime numbers quite close together right so you know you can imagine that if this is the square root of n one of them might be a little bit bigger and one of them will be a bit smaller but they'll they'll multiply together to get n um if they're only very very close together you might imagine intuitively it's a little bit easier to find what the factorization is and then once you factored it you can just do these steps to completely Rec calculate the private key so a really good method for doing this when p and Q are thought maybe not to be that far apart is fats Factor on ation algorithm right and that's what this researcher Hano was using to do his attack right and the way it works is basically like this so we know that n is p and Q right now there's also another neat trick that we know which is that some composite number n is the difference of two square numbers right so it's going to be some some a squ that we don't know minus some b^ squ that we don't know now we can also rewrite this as a + b Times by a minus B right now we're not going to De in too much much detail right but this is basically the core of the algorithm now that's p and that's Q or vice versa it doesn't really matter which one if we could work out what these intermediate values A and B are then we can use this little formula here to work out what p and Q are what I've done is Rewritten a formula I haven't actually shown that we can do it any more easily but we can rewrite this to be b^ 2 is equal to a 2 minus n what we do for the firmat factorization algorithm is we say okay what's a good guess for a well a let's say the square root of n is about roughly where we want to start and we want to start moving up through the A's to try and find plausible solutions to this equation so we say that our initial guess for a is going to be the square root of N and then the integer immediately above that that's the ceiling function so if the square root of n is you know 7 we just go up to the next integer above right now we do that so we pick our a we calculate a s minus our original n and we see what we get out and what we get out has to be a square number it has to be a number that has an integer square root because if it doesn't this doesn't work right and it didn't so what we do is we add one to a and we try it again we square a we subtract the original value and we find if we've got a square number right now this is not trivial to do in terms of the the amount of computation to calculate these large square roots and things but it's not that bad and the the interesting thing about firmat factorization method is if p and Q are fairly close to each other this will give you a solution for p and Q extremely quickly you'll do a few iterations you'll get an A where you square it you minus n and you've got a square number then you know what A and B are and then you can do a plus b a minus B to get p and Q and you've broken RSA right so let's have a quick look and I'll show you so we're going to use Sage Maths for this right now I love sage math essentially think of it like it's python but with a bunch more maths in it um you know if you use mat lab or octave or some other mathematical library or Mathematica or something it's it's one of those kind of things I like it because it's um it's got a lot of sort of helpful stuff for cryptography but also um because I know python quite well and so you know it's easy now it it's a command prompt that says Sage on it but actually it's basically python right so I can write normal python now what I've done is I've got a week n right so what I did was I picked two random primes that were not that different and I multiplied them together and got an n and I forgotten what the primes are and deleted them right so n equal rules and I'm going to paste it in and it's a very very large number I don't know how many digits it is but some number of digits is quite big I can go n do n Bits is 246 so it's actually marginally smaller than 2048 but it's not bad now so n is my n is my very large part of the public key let's say my other component is 65537 as an attacker what we want to do is break n into p and Q we can calculate to of n we can calculate the private key D and then we can wak all kinds of havoc on the web web um but don't by the way um now because I haven't chosen pnq properly at random they are actually quite similar so the first half of p and the first half of they were 1,000 bit numbers the first half the first roughly 500 bits were identical for both and then they're random on the tail end like the second half um and that means that they've got still got 512 bits that are different they're not the same number at all and if you were counting up from to the other it would take you many thousands of years to do but this factorization method breaks in very very quickly so let's code it up let's first calculate our initial guess for a right so a is going to be the integer square root which is essentially the integer down from the square root of n + one so that's for ceiling right I could could have just used the seiling function we won't dwell on it so a is some implausibly large number and what we're going to do is we're going to calculate a^ 2us n and see if that's a square number and then we're going to increment a just keep going until we get one and then we can calculate p and Q so um I'm going to write uh a little bit of code to do this while true don't use while true most of the time I'm I'm cheating while true let's calculate b^ 2 is equal to a to the^ 2 minus n all right hope this will work and then if is square as an inside the thing I like about Sage mass is they've already implemented things like is square so I don't have to bother implementing by myself sounds like a lot of work I don't like doing a lot of work for my attx so if B2 is a square we've already solved the algorithm right so we're going to do then we're going to calculate B is equal to the Square < t of B2 otherwi and then we're going to break and out of our Loop if not we're going to do AAL a + one right and it's already finished right I think it was about 10 iterations of this before we hit on the correct day it's is ridiculous how quickly this works so I can say a is that number B is this number and so we can now say p is equal to a plus b and Q is equal to a minus B and then we can just do a check so p is this is p a prime P do is prime thinking about it primality test witness numbers yes it is right and I could do the same for Q so it's looking good and then the last test is to see if P * Q is equal to n so n is equal to p P * Q true right so we factored n into p and Q now actually I could now calculate the um the private key so let's suppose e is 655 37 right then what I do is I calculate the to of n so 5 n is equal to P -1 * Q -1 and then we have to calculate the multiplicative inverse which is d d is equal to inverse mod it might be mod inverse let's find out of E and F of n d oops that's not true D there we go so e is that and D is that so I've already calculated the private key not a lot of work incidentally the algorithm you use to calculate the M multiplicative inverse is the extended ukan algorithm so that's implemented in here as well I know you said that this is for kind of like weak numbers yeah potentially could it work for any RSA number so this will eventually return the answer but eventually is is IR relative um when the numbers are very close to the square root of n then this will return within you know 10 20 30 maybe a maxim of 100 iterations will return the number right for any you know so for example for thousand bit numbers if the if the last 500 bits are the same they are way too close together if you were actually generating values for p and Q properly you wouldn't want to generate values that almost even had the same number of bits you know they they want to be somewhere around 1024 bits but you don't want to enforce it and maybe um and maybe you need to make some effort to generate them properly so one way that they generate which is not entirely uniform but it's not bad is you pick a random number and then you just increment it and find the next prime up from that number so what you would not want to do is pick a number and find an X Prime up and an X Prime down or something like that because they're only going to be maybe a th000 or 100 apart that's not going to work they're going to be very close to the square root so what you do is you pick some random number you find the X Prime you pick an entirely different random number maybe not even the same length find the X Prime and then they are going to be sufficiently different if the numbers are very very far apart the factorization method becomes you know impossibly slow because you're doing all this extra Square rooting and things that you don't need to do right and there are better factorization methods out there so you wouldn't ever use it apart from in the really easy cases it didn't take me long to prove whether or not this was a weak a weak number right so what you could do and in fact what this researcher did was look at some publicly available keys and just find out whe they're weak by just simply whether this returned within 100 iterations so it's extremely easy to find out if this n is has got weak a weak p andq and so you have to be extremely careful generating these random values right a lot of thought goes into generating random primes than I am going into just doing the justice of in this video right um it it's not simply a case of calling math. random and then is it a prime right there's a lot there's a lot to it idea it's called psych it's out it's after Doctor Who isn't it right so it's been a while since I've watched Doctor Who but the idea is that do uh who keeps showing people this blank piece of paper and it's psychic paper which means that they see some identification that means so multiply it with itself 29 times on the clock and the number I end up with is 18