Is RSA a one-way function? (17 min)

The next question, we're going to ask:

is RSA really an 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 is given x to the e

and his goal is to recover x. OK, 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 a composite?

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.

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?

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.

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.

So, just to be precise, when I say that RSA is insecure,

what I mean is just given the public key N and e,

your goal is to recover the secret key d.

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).

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.

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.