0:34

If this problem turns out to be hard, then RSA is in fact an one-way function.

Â If this problem turns out to be easy, which

Â of course we don't believe it's easy, then RSA would actually be broken.

Â So, it turns out the best algorithm for this problem

Â requires us to first factor the modulus N.

Â And then, once we factored the modulus, we have already

Â seen last week, that it's easy to compute the e'th root modulo p,

Â it's easy to compute the 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 are 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 a natural question is, is it true that in

Â order to compute e'th roots modulo N, we have to

Â factor the modulus N? As far as we know, the

Â best algorithm for computing e'th roots

Â modulo N requires factorization of N.

Â But, who knows, maybe there is a short cut

Â that allows us to compute e'th roots modulo N,

Â without factoring the modulus. To show that

Â that's not possible, we have to show a reduction.

Â That is, we have to show that,

Â if I give you an efficient algorithm for

Â computing e'th roots modulo N, that

Â efficient algorithm can be turned into a factoring algorithm.

Â So, this is called a reduction. Namely, given an algorithm for

Â e'th roots modulo N, we obtain a factoring algorithm.

Â That would show that one cannot compute e'th roots modulo N

Â faster than factoring the modulus.

Â 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 one of the oldest problems in public key crypto.

Â So, just let me give you a concrete example.

Â Suppose, I give you an algorithm that will compute cube roots modulo N.

Â 2:19

So, for any x in ZN, the algorithm will compute the cube root of x modulo N.

Â My question is, can you show that using

Â such an algorithm you can factor the modulus N?

Â And, even that is not known. What is known,

Â I'll tell you, is for example that for e equals 2,

Â that is if I give you an algorithm for computing square roots modulo N,

Â then in fact, that does imply factoring the modulus.

Â 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 times d be 1 modulo phi(N).

Â What that means is, that e necessarily needs to be relatively prime to phi(N).

Â Right, this, what the first equation says is that e is invertible modulo phi(N).

Â But, if e is invertible modulo phi(N), necessarily that means that

Â e must be relatively prime to phi(N).

Â But, phi(N), if you remember, that is equal to p minus 1 times q minus 1.

Â And, since p and q are both large primes, p - 1 times q - 1 is always even.

Â And, as a result, the GCD of 2 and phi(N) is equal to 2,

Â because phi(N) is even. And therefore, the public

Â exponent 2 is not relatively prime to phi(N).

Â Which means that, even though we have a reduction

Â from taking square roots to factoring,

Â e equals 2 cannot be used as an RSA exponent.

Â So, really the smallest RSA exponent that is legal is in fact e equals 3.

Â But, for e equal 3, 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 will tell you that there is a little bit of evidence to say

Â that a reduction like that, actually doesn't exist, but it is 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 am not going to explain what that means here.)

Â That is, if given a cube root oracle, you could actually show me an algorithm

Â that would then factor. That reduction, by itself,

Â would actually imply a factoring algorithm.

Â Okay so, that would say that if factoring is hard,

Â a reduction actually doesn't exist.

Â But, as I say this is very weak evidence.

Â Because, who is 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?

Â 4:51

But as I said, as far as we know, RSA is a one way function.

Â In fact, breaking RSA, computing e'th roots that is, actually requires factoring the modulus.

Â We all believe that's true, and that's the state of the art.

Â But, now there 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 has been a number of false starts in this direction.

Â So I want to show you, this wonderful example as a warning.

Â So basically, this is an example of how not to improve the perfomance of RSA.

Â So, you might think that if I wanted to speed up RSA decryption,

Â remember decryption is done by 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 in log of d.

Â So, you might think to yourself, well if I wanted

Â to speed up RSA decryption, why don't I just use a small d.

Â I'll say, I'll say a decryption exponent that's on the order of 2 to the 128.

Â So it's clearly big enough so that exhaustive search against d is not possible.

Â But normally, the decryption exponent d would be as big as the modulus, say 2000 bits.

Â By using d that's only 128 bits, I basically speed up RSA decryption by a factor of 20.

Â Right, I went down from 2000 bits to 100 bits.

Â So, exponentiation would run 20 times as fast.

Â It turns out this is a terrible idea. Terrible, terrible idea, in the following sense.

Â There is an attack by Michael Wiener 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 2048 bits

Â that means that if d is less that 2 to the 512, then RSA is completely, completely insecure.

Â And, this is, it's insecure in the worst possible way.

Â Namely, just given a public key and an e, you can very quickly recover the private key d.

Â 6:44

Well, so some folks said: well this attack works up to 512 bits.

Â So, why donÂ´t we make the modulus, 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 4,

Â because we shrunk the exponent from 2000 bits to, say, 530 bits.

Â Well it turns out, even that is not secure. In fact,

Â there is an extension to Wiener's attack, that's actually much

Â more complicated, that shows that if d

Â is less than N to the 0.292, then also RSA is insecure.

Â And in fact, the conjecture that this is true up to N to the 0.5.

Â So even if d is like N to the 0.4999, RSA should still be insecure,

Â although this is an open problem. It's again, a wonderful open problem,

Â It's been open for like, what is it, 14 years now.

Â And, nobody can progress beyond this 0.292.

Â Somehow, it seems kind of strange, why would 0.292

Â be the right answer and yet no one can go beyond 0.292.

Â 7:49

If you are curious where 0.292 comes from,

Â I'll tell you that what it is, it's basically 1 minus 1 over square root of 2.

Â Now how could this possibly be the right answer to this problem?

Â It's much more natural that the answer is N to the 0.5.

Â But this is still an open problem. Again if you want to 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 going to end up in disaster. So this is not the right way to improve RSA's 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 you would enjoy seeing the details.

Â All it involves is just manipulating some inequalities.

Â If you're not comfortable with that, feel free to skip over this slide,

Â although I think many of you would actually enjoy seeing the details.

Â So let me remind you in Wiener's attack basically

Â we're given the modulus and the RSA exponent N and e,

Â and our goal is to recover d, the private exponent d,

Â and all we know is that d is basically less than the fourth root of N.

Â In fact, I'm going to assume that d is less than the fourth root of N divided by 3.

Â This 3 doesn't really matter, but the dominating term here is that d is less than the 4th 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 times d is 1 modulo phi(N). Well what does that mean?

Â That means that there exists some integer k such that e times d is equal to k times phi(N) plus 1.

Â Basically that's what it means for e times d to be 1 modulo phi(N).

Â Basically some integer multiple of phi(N) plus 1.

Â So now let's stare at this equation a little bit.

Â And in fact this equation is the key equation in the attack.

Â And what we're going to do is first of all divide both sides by d times phi(N).

Â And in fact I'm going to move this term here to the left.

Â So after I divide by d times phi(N), what I get is that

Â e divided by phi(N) minus k divided by d is equal to 1 over d times phi(N).

Â 9:59

Okay, so all I did is I just divided by d times phi(N)

Â and I moved the k times phi(N) term to the left-hand side.

Â Now, just for the heck of it I'm going to add absolute values here.

Â These will become useful in just a minute, but of course they don't change this equality at all.

Â Now, phi(N) of course is almost N; phi(N) is very, very close to N, as we said earlier.

Â And all I'm going to need then for this fraction is just to say that

Â it's less than 1 over square root of N. It's actually much, much smaller

Â than 1 over square root of N, it's actually on the order of 1 over N or even more than that,

Â but for our purposes all we need is that this fraction is less than 1 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(N), and as a result we don't know e over phi(N).

Â But we have a good approximation to e over phi(N). Namely we know that phi(N)

Â is very close to N. Therefore e over phi(N) is very close to e over N.

Â So we have a good approximation to this left-hand side fraction, namely e over N.

Â What we really want is the right-hand side fraction,

Â because once we get the right-hand side fraction,

Â basically that's going to involve d, and then we'll be able to recover d. Okay, so let's see

Â if we replace e over phi(N) by e over N, let's see what kind of error we're going to get.

Â So to analyze that, what we'll do is first of all remind ourselves

Â that phi(N) is basically N - p - q + 1,

Â which means that N minus phi(N) is going to be less than p + q.

Â Actually I should, to be precise I should really write p + q + 1, but you know,

Â who cares about this 1, it's not, it doesn't really affect anything.

Â So I'm just going to 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're both kind of on the order of square root of N,

Â so basically p + q we'll say is less than 3 times square root of N.

Â Okay, so we're going to use this inequality in just a minute.

Â But now we're going to start using the fact that we know something about d,

Â namely that d is small. So if we look at this inequality here,

Â d is less than the fourth root of N divided by 3.

Â It's actually fairly easy to see that if I square both sides

Â and I just manipulate things a little bit, it's [not] difficult to see that

Â this directly implies the following relation,

Â basically 1 over 2 d squared minus 1 over square root of N is greater than 3 over square root of N.

Â As I said, this basically follows by squaring both sides, then taking the

Â inverse of both sides, and then I guess multiplying one side by a 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 we'd like to do is bound

Â the difference of e over N and k over d. Well what do we know?

Â By the triangular inequality, we know that this is equal to

Â the distance between e over N and e over phi(N) plus

Â the distance from e over phi(N) to k over d.

Â This is just what's called a triangular inequality; this is just a property of absolute values.

Â Now this absolute value here, we already know how to bound.

Â If you think about it it's basically the bound that we've already derived.

Â So we know that this absolute value here is basically less than 1 over square root of N.

Â Now what do we know about this absolute value here? What is e over N minus e over phi(N)?

Â Well let's do common denominators and see what we get.

Â So the common denominator is going to be N times phi(N),

Â and the numerator in this case is going to be e times phi(N) minus N.

Â Which we know from this expression here is less than 3 times square root of N.

Â So really what this numerator is going to be is e times 3 square root of N.

Â The numerator is going to be less than e times 3 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 1.

Â In other words, if I erase e and I erase phi(N) I've only made the fraction larger.

Â Okay, so this initial absolute value is now going to be

Â smaller than 3 square root of N over N, which is simply,

Â 3 square root of N over N is simply 3 over square root of N.

Â Okay, but what do we know about 3 over square root of N?

Â We know that it's less than 1 over 2 d squared minus 1 over square root of N.

Â Okay, so that's the end of our derivation.

Â So now we know that the first absolute value is less than 1 over 2 d squared minus square root of N.

Â The second absolute value is less than 1 over square root of N.

Â And therefore their sum is less than 1 over 2 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.

Â 14:43

Now, so let's stare a little bit at this fraction here.

Â And what we see is first of all, as before, now we know the value of e over N,

Â and what we'd like to find out is the value k over 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 1 over 2 d squared. Now this turns out to happen very infrequently,

Â that k over d approximates e over N so well that

Â the difference between the two is less than the square of the denominator of k over d.

Â It turns out that that can't happen very often.

Â It turns out that there are very few fractions of the form k over d that approximate another fraction

Â so well that their difference is less than 1 over 2 d squared.

Â And in fact the number of such fractions is going to be at most logarithmic in N.

Â So now there's a continued fraction algorithm. It's a very famous fraction

Â that basically what it will do is, from the fraction e over N,

Â it will recover log(N) possible candidates for k over d.

Â So we just try them all one by one until we find the correct k over d.

Â And then we're done. We're done, because we know that,

Â well e times d is 1 mod 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,

Â the denominator must be d. And so we've just recovered, you know,

Â we've tried all possible log(N) fractions that approximate e over N so well

Â that the difference is less than 1 over 2 d squared.

Â And then we just look at the denominator of all those fractions, and one of those denominators must be d.

Â And then we're done; we've just recovered the private key.

Â So this is a pretty cute 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, quite easily. Okay, so I'll stop here.

Â