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.