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

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.