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