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.