The next question we're gonna ask is RSA really a one way function. In other words, is it really hard to invert RSA without knowing the Trapdoor? So if an attacker wanted to invert the RSA function, well what the attacker has is basically the public key namely, he has n and e, and now he's given x to the e and his goal is to recover x, okay? So the question really is, given x to the e modulo n, how hard is it to recover x? So what we're really asking is, how hard is it to compute e-th roots modulo composite? If this problem turns out to be hard, then RSA is in fact the one way function. If this problem turns out to be easy which is of course we don't believe is easy, then RSA would actually be broken. So just at this [inaudible] for this problem requires us the first factor, the modulo n, and then the ones we factor the modulus we've already seen last week that it's easy to compute the e-th root modulo p, it's easy to compute e-th root modulo q and then given both those e-th roots it's actually easy to combine them together using what's called the Chinese Remainder Theorem and actually recover the e-th root modulo n. So once we're able to factor the modulus computing e-th roots, modulo n becomes easy but factoring the modulus as far as we know is a very, very difficult problem. But the natural question is, is it true that in order to compute [inaudible] we have to factor the modulus n. As far as we know the best algorithm for computing [inaudible] modular n requires factorization of n. But who knows, maybe there's a short cut that allows us to complete [inaudible] modular n without factoring the modulus. To show that that's not possible, we have to show our reduction. That is we have to show that if I give you an efficient algorithm for computing e-th root modulo m, that efficient algorithm can be turned into a factoring algorithm. So this is called the reduction namely given an algorithm for e-th root modulo m, we obtain a factoring algorithm and that would show that one cannot compute e-th root modulo m faster than factoring the modules. If we had such a result, it would show that actually breaking RSA in fact is as hard as factoring but unfortunately this is not really known at the moment. In fact this is the one of the oldest problems in Public-key crypto and so let me just give you a concrete example. I supposed I give you an algorithm what will compute q brute modular m. So for any x and zN the algorithm will compute the cube root of x modulo m and my question is can you show that using such an algorithm you can factor the modulo m? And even that's not known. What is known I'll tell you is for example that for e = two. That is if I give you an algorithm for computing square roots modulo n, then in fact that does imply factoring the modulus and so computing square roots, is in fact as hard as factoring the modulus. Unfortunately, if you think back to the definition of RSA, that required that e * d be one modulo phi of n and what that means is that e necessarily needs to be relatively prime to phi of n. What the first equation says that e is invertible modulo 5n but if e is invertible modulo 5n, necessarily that means that e must be relatively prime to 5n. But again if you remember that's = p - one * q - one and since p and q are both primes, p - one * q - one is always even. And as a result, the GCD of two and phi of n is = two because phi of n is even and therefore, the public exponent two is not relatively prime to phi of n which means that even though we have a reduction from taking square roots to factoring, e = two cannot be use as an RSA exponent. So really the smallest RSA exponent that's legal is in fact e = three but for e = three the question of whether computing cube roots is as hard as factoring is an open problem. It's actually a lot of fun to think about this question. So, I would encourage you to think about it just a little bit that is if I give you an efficient algorithm for computing cube roots modulo n, can you use that algorithm to actually factor the modulus n? I'll tell you that is a little b it of evidence to say that a reduction like that actually doesn't exist but it's very, very weak evidence. What this evidence says is basically if you give me a reduction of a very particular form, in other words if your reduction is what's called algebraic, I'm not gonna explain what that means here, that is if given a cube root, oracle, you could actually show me in algorithm that within factor, that reduction by itself would actually imply a factoring algorithm. Okay so that would say, that a factoring is hard, a reduction actually doesn't exist. But as I say, this is very weak evidence 'cause who's to say that the reduction needs to be algebraic maybe there are some other types of reductions that we haven't really considered. So, I would encourage you to think a little bit about this question, it's actually quite interesting how would you use a cube root algorithm to factor the modulus. But as I said as far as we know RSA is a one way function and in fact breaking RSA, computing e-th root status actually requires factoring the modules. We all believe that's true. That's state of the art. But now there's has been a lot of work on trying to improve the performance of RSA. Either RSA encryption or improve the performance of RSA decryption. And it turns out there's been a number of false start in this direction so I wanna show you this wonderful example as a warning and so this basically is an example on how not to improve the performance of RSA. So you might think that if I wanted to speed up RSA decryption, remember decryption is done but raising the ciphertext to the power of d and you remember that the exponentiation algorithm ran in linear time in the size of d Linear time and log of d. So you might think to yourself well, if I wanted to speed up RSA decryption, why don't I just use d of a, decryption exponent that's on the order of two to the 128th. So it's clearly big enough to that exhaust a search against d is not possible, but normally the decryption exponent d would be as big as the modulus say 2,000 bits. By using d that's only 128th bits, I basically speed up the decryption by a factor twenty. Then I went down from 2,000 bits to 100 bits so exponentiation would run twenty times as fast. It turns out this is a terrible idea, terrible, terrible idea in the following sense there's an attack by Michael [inaudible] that shows that in fact as soon as the private exponent d is less than the fourth root of the modulus, let's see, if the modulus is around twenty to 48 bits, that means that if d is less than two to the 512th. Then RSA is completely, completely insecure. And this is, it's insecure and the worse possible way namely just given a public key and an e, you can very quickly recover the private key d. Well some folks said well this attack works out to 512 bits so why don't we make the modulo say you know 530 bits then this attack actually wouldn't apply but still we get to speed up RSA decryption by a factor of four because we shrunk the exponent from 2000 bits To say 530 bits. Well, it turns out even that that's not secure. In fact, there's an extension to [inaudible] attack that's actually much more complicated that shows that if d is less than n to the .292, then also RSA isn't secure and in fact the conjuncture is that this is true up to n to the .5 so even if d is like n to the .4999, RSA is still, be insecure although this is an open problem. So again, a wonderful open problem, It's been open for like, you know? Its fourteen years now and no one can progress beyond this .292 Somehow Seems kind of strange. Why would .292 be the right answer and yet no one can go beyond .292? So just to be precised when I say that RSA is insecure, what I mean is just giving them the Public-key in n e; your goal is to recover the secret key d. If you're curious where .292 comes from I'll tell you that what it is, it's basically one - one over square root of two. Now how could this possibly be the right answer? The problem is much more natural than the answer is n to the .5 but this is still an open problem. Again, if you wanna think about that it's kind of a fun problem to work on. So the lesson in this is that one should not enforce any structure on d for improving the performance of RSA and in fact now there's a slew of results like this that show, that basically any kind of tricks like this to try and improve RSA's performance is gonna end up in disaster. So this is not the right way to improve RSAs performance. Initially I wasn't going to cover the details of Wiener's Attack but given the discussions in the class I think some of your would enjoy seeing the details. All it involves is just manipulating so many qualities. If you're not comfortable with that, feel free to skip over the slide although I think many of you would actually enjoy seeing the details. So let me remind you in Wiener's Attack basically would given the modulus and the RSA exponent and an e and our goal is to recover d, the private exponent d and all we know is that d is basically less than fourth root of n. In fact, I'm gonna assume that d is less than four root of n divided by three and thus three doesn't really matter but the dominating term here is d is less than the fourth root of n. So let's see how to do it. So first of all, recall that because e and d are RSA public and private exponents, we know that e * d is one modulo phi of n. Well what does that mean, that means that you're exist some integer k such that e * d is = k * phi of n + one. Basically that's what it means for e * d to be one modulo phi of n Basically, some integer multiple phi of n + one. So now let's stare at this equation a little bit, and in fact this equation is the key equation on the attack. And what we're gonna do is first of all divide both sides by d * phi (N). And in fact, I'm gonna move this term here to the left. So after I divide by d * phi (n), what I get is that e / phi(n) - k / d = one / d * phi(n). Okay. So all I did is I just divide it by d * 5n and moved the k * 5n and turn to the left hand side. Now just for the heck of it, I'm going to add absolute values here. This will become useful in just a minute but of course they don't change this equality at all. Now 5n of course is almost n. 5n is very, very close to n as we said earlier and all I'm gonna need then for this fraction is just to say that it's less than one over square root of n. It's actually much, much smaller than one over square root of n. It's actually in the order of one over n or even more than that. But for our purposes, all we need is that this fraction is less than one over square root of n. Now let's stare at this fraction for just a minute. You realize that this fraction on the left here Is a fraction that we don't actually know. We know e but we don't know phi of n and as a result we don't know e over phi of n. But we have a good approximation to e over phi of n namely we know the phi of n is very close to n, therefore e over phi of n is very close to e over n. So we have a good approximation to this left hand side fraction we have ran. What we really want is the right hand fraction because once we get the right hand side fractions basically you guys wanna involve d and then we'll able to recover d, okay. So let's see if we replace e over 5n by e over n. Let's see what kind of error we're gonna get. So to analyze that what we'll do is first of all remind ourselves that 5n is basically n - p - q +one. Which means that n - phi (n) is gonna be less than p + q. Actually I should, to be precise, I should really write p + q + one. But, you know, who cares about this one. It's not, it doesn't really affect anything so I'm just gonna ignore it for simplicity. Okay? So n - phi (n) is less than p + q. Both p and q are roughly half the length of n so, you know, they kind of both on the order of square root of n. So basically, p + q we'll say is less than three * square root of n. Okay. So we're going to use this inequality in just a minute but now we're gonna start using the fact that we know something about [inaudible] so if we look at this inequality here, d is less than the fourth root of n / three, it's act ually fairly easy to see if I square both sides and I just manipulate these a little bit, it's difficult to see that this directly implies the following relation basically one / two d squared - one / square root of n is greater than three / square root of n. As I said this basically follows by square in both sides then taking the inverse of both sides and then I guess multiplying one side by half. Okay. So you can easily derive this relation and we'll need this relation in just a minute. So now let's see, what do we like to do is bound the difference of e / n and k / d. Well, what do we know? By the triangular and equality we know that this is equal to the distance between e / n and e / phi (n) plus the distance from e/ phi (N). 2k / d, okay? This is just what's called the triangular and equality. This is just the property of absolute values. Now this absolute value here we already know how to bound if you think about it as basically the bound that we've already derived so we know that this absolute value here is basically less than one / square root of n. Now what do we know about this absolute value here? What is e / n - e / 5n? Well, let's do common denominators and see what we get so the common denominator is gonna be n * 5n. And the numerator in this case is going to be e * 5n - n. Which we know from this expression here is less than three * square root of n. So really what this numerator is gonna be is e * three square root of n. The numerator is gonna be less than e * three square root of n. So now I know that e is less than phi (N). So I know that e over phi (n) is less than one. In other words, if I erased e and I erased phi (n), I've only made the fraction larger. Okay? So this initial absolute value is not gonna be smaller than three square root of n over n which is simply, three square root of n over n is simply three over square root of n. Okay. But what do we know about three / square root of n, we know that it's less than one. Over 2d squared - one / square root of n. Okay, so that's the end of ou r derivation. So now we know that the first absolute value is less than one over two d square - square root of n. The second absolute value is less than one over square root of n and therefore the sum is less than one over two d squared. And this is the expression that I want you to stare at, so here let me circle it a little bit. So, let me circle this part And this part. Now so let's stir a little bit of a distraction here and what we see is first of all as before. Now we know the value of e / n and what we'd like to find out is the value k / d. But what do we know about this fraction k over d? We know somehow that the difference of these two fractions is really small, it's less than one over two d squared. Now this turns out to happen very and frequently that k over d. Approximate e over n so well That the distance between the two is less than the square of the denominator of k over d. It turns out that, that can happen very often. It turns out there are very few fractions of the form k / d than approximate another fraction so well that their difference is less than one of the 2d squared. And in fact the number of such factions is gonna be most logarithmic in n. So now there's a continued fraction of algorithm. It's a very famous fraction that basically what it would do Si from the fraction e / n it would recover and possible candidate for k / d so we just try them all one by one until we find the direct k / over d. And then we're done. We're done because we know that well e * d is one [inaudible] k, therefore, d is relatively prime to k. So if we just represent k over d as a rational fraction, you know? Numerator by denominator, then denominator must be d. And so we've just recovered, you know? We've tried all possible log in fractions that approximate e over n so well that the difference is less than one over 2d squared and then we just look at the denominator of all of those fractions and one of those denominators must be d and then we're done, we're just recovered the private key. So this is a pretty huge attack and it shows basically how if the private exponent is small, smaller than the fourth root of n, then we can recover d completely and quite easily. Okay. So, I'll stop here.