0:00:00.000,0:00:05.381
The next question we're gonna ask is RSA[br]really a one way function. In other words,

0:00:05.381,0:00:10.566
is it really hard to invert RSA without[br]knowing the Trapdoor? So if an attacker

0:00:10.566,0:00:15.685
wanted to invert the RSA function, well[br]what the attacker has is basically the

0:00:15.685,0:00:21.066
public key namely, he has n and e, and now[br]he's given x to the e and his goal is to

0:00:21.066,0:00:26.251
recover x, okay? So the question really[br]is, given x to the e modulo n, how hard is

0:00:26.251,0:00:31.370
it to recover x? So what we're really[br]asking is, how hard is it to compute e-th

0:00:31.370,0:00:36.816
roots modulo composite? If this problem[br]turns out to be hard, then RSA is in fact

0:00:36.816,0:00:41.077
the one way function. If this problem[br]turns out to be easy which is of course we

0:00:41.077,0:00:44.959
don't believe is easy, then RSA would[br]actually be broken. So just at this

0:00:44.959,0:00:49.456
[inaudible] for this problem requires us[br]the first factor, the modulo n, and then

0:00:49.456,0:00:53.841
the ones we factor the modulus we've[br]already seen last week that it's easy to

0:00:53.841,0:00:58.338
compute the e-th root modulo p, it's easy[br]to compute e-th root modulo q and then

0:00:58.338,0:01:03.117
given both those e-th roots it's actually[br]easy to combine them together using what's

0:01:03.117,0:01:07.839
called the Chinese Remainder Theorem and[br]actually recover the e-th root modulo n.

0:01:07.839,0:01:12.280
So once we're able to factor the modulus[br]computing e-th roots, modulo n becomes

0:01:12.280,0:01:16.890
easy but factoring the modulus as far as[br]we know is a very, very difficult problem.

0:01:16.890,0:01:21.444
But the natural question is, is it true[br]that in order to compute [inaudible] we

0:01:21.444,0:01:26.056
have to factor the modulus n. As far as we[br]know the best algorithm for computing

0:01:26.056,0:01:30.092
[inaudible] modular n requires[br]factorization of n. But who knows, maybe

0:01:30.092,0:01:34.531
there's a short cut that allows us to[br]complete [inaudible] modular n without

0:01:34.531,0:01:38.710
factoring the modulus. To show that that's[br]not possible, we have to show our

0:01:38.710,0:01:43.104
reduction. That is we have to show that if[br]I give you an efficient algorithm for

0:01:43.104,0:01:47.223
computing e-th root modulo m, that[br]efficient algorithm can be turned into a

0:01:47.223,0:01:51.726
factoring algorithm. So this is called the[br]reduction namely given an algorithm for

0:01:51.726,0:01:56.120
e-th root modulo m, we obtain a factoring[br]algorithm and that would show that one

0:01:56.120,0:02:00.736
cannot compute e-th root modulo m faster[br]than factoring the modules. If we had such

0:02:00.736,0:02:04.702
a result, it would show that actually[br]breaking RSA in fact is as hard as

0:02:04.702,0:02:09.109
factoring but unfortunately this is not[br]really known at the moment. In fact this

0:02:09.109,0:02:13.461
is the one of the oldest problems in[br]Public-key crypto and so let me just give

0:02:13.461,0:02:18.089
you a concrete example. I supposed I give[br]you an algorithm what will compute q brute

0:02:18.089,0:02:22.796
modular m. So for any x and zN the[br]algorithm will compute the cube root of x

0:02:22.796,0:02:27.707
modulo m and my question is can you show[br]that using such an algorithm you can

0:02:27.707,0:02:32.808
factor the modulo m? And even that's not[br]known. What is known I'll tell you is for

0:02:32.808,0:02:37.848
example that for e = two. That is if I[br]give you an algorithm for computing square

0:02:37.848,0:02:42.447
roots modulo n, then in fact that does[br]imply factoring the modulus and so

0:02:42.447,0:02:47.551
computing square roots, is in fact as hard[br]as factoring the modulus. Unfortunately,

0:02:47.551,0:02:52.213
if you think back to the definition of[br]RSA, that required that e * d be one

0:02:52.213,0:02:57.505
modulo phi of n and what that means is[br]that e necessarily needs to be relatively

0:02:57.505,0:03:03.277
prime to phi of n. What the first equation[br]says that e is invertible modulo 5n but if

0:03:03.277,0:03:08.884
e is invertible modulo 5n, necessarily[br]that means that e must be relatively prime

0:03:08.884,0:03:14.631
to 5n. But again if you remember that's =[br]p - one * q - one and since p and q are

0:03:14.631,0:03:20.413
both primes, p - one * q - one is always[br]even. And as a result, the GCD of two and

0:03:20.413,0:03:26.645
phi of n is = two because phi of n is even[br]and therefore, the public exponent two is

0:03:26.645,0:03:32.803
not relatively prime to phi of n which[br]means that even though we have a reduction

0:03:32.803,0:03:38.824
from taking square roots to factoring, e =[br]two cannot be use as an RSA exponent. So

0:03:38.824,0:03:43.043
really the smallest RSA exponent that's[br]legal is in fact e = three but for e =

0:03:43.043,0:03:47.481
three the question of whether computing[br]cube roots is as hard as factoring is an

0:03:47.481,0:03:51.864
open problem. It's actually a lot of fun[br]to think about this question. So, I would

0:03:51.864,0:03:55.973
encourage you to think about it just a[br]little bit that is if I give you an

0:03:55.973,0:04:00.411
efficient algorithm for computing cube[br]roots modulo n, can you use that algorithm

0:04:00.411,0:04:04.714
to actually factor the modulus n? I'll[br]tell you that is a little b it of evidence

0:04:04.714,0:04:09.014
to say that a reduction like that actually[br]doesn't exist but it's very, very weak

0:04:09.014,0:04:13.155
evidence. What this evidence says is[br]basically if you give me a reduction of a

0:04:13.155,0:04:17.454
very particular form, in other words if[br]your reduction is what's called algebraic,

0:04:17.454,0:04:21.276
I'm not gonna explain what that means[br]here, that is if given a cube root,

0:04:21.276,0:04:25.045
oracle, you could actually show me in[br]algorithm that within factor, that

0:04:25.045,0:04:29.374
reduction by itself would actually imply a[br]factoring algorithm. Okay so that would

0:04:29.374,0:04:33.622
say, that a factoring is hard, a reduction[br]actually doesn't exist. But as I say, this

0:04:33.622,0:04:37.871
is very weak evidence 'cause who's to say[br]that the reduction needs to be algebraic

0:04:37.871,0:04:41.653
maybe there are some other types of[br]reductions that we haven't really

0:04:41.653,0:04:45.694
considered. So, I would encourage you to[br]think a little bit about this question,

0:04:45.694,0:04:50.098
it's actually quite interesting how would[br]you use a cube root algorithm to factor

0:04:50.098,0:04:54.906
the modulus. But as I said as far as we[br]know RSA is a one way function and in fact

0:04:54.906,0:04:59.690
breaking RSA, computing e-th root status[br]actually requires factoring the modules.

0:04:59.690,0:05:04.504
We all believe that's true. That's state[br]of the art. But now there's has been a lot

0:05:04.504,0:05:08.717
of work on trying to improve the[br]performance of RSA. Either RSA encryption

0:05:08.717,0:05:12.986
or improve the performance of RSA[br]decryption. And it turns out there's been

0:05:12.986,0:05:17.824
a number of false start in this direction[br]so I wanna show you this wonderful example

0:05:17.824,0:05:22.094
as a warning and so this basically is an[br]example on how not to improve the

0:05:22.094,0:05:26.135
performance of RSA. So you might think[br]that if I wanted to speed up RSA

0:05:26.135,0:05:30.803
decryption, remember decryption is done[br]but raising the ciphertext to the power of

0:05:30.803,0:05:35.585
d and you remember that the exponentiation[br]algorithm ran in linear time in the size

0:05:35.585,0:05:40.368
of d Linear time and log of d. So you[br]might think to yourself well, if I wanted

0:05:40.368,0:05:44.990
to speed up RSA decryption, why don't I[br]just use d of a, decryption exponent

0:05:44.990,0:05:50.105
that's on the order of two to the 128th.[br]So it's clearly big enough to that exhaust

0:05:50.105,0:05:55.035
a search against d is not possible, but[br]normally the decryption exponent d would

0:05:55.035,0:06:00.068
be as big as the modulus say 2,000 bits.[br]By using d that's only 128th bits, I

0:06:00.068,0:06:05.402
basically speed up the decryption by a[br]factor twenty. Then I went down from 2,000

0:06:05.402,0:06:10.604
bits to 100 bits so exponentiation would[br]run twenty times as fast. It turns out

0:06:10.604,0:06:15.214
this is a terrible idea, terrible,[br]terrible idea in the following sense

0:06:15.214,0:06:20.482
there's an attack by Michael [inaudible][br]that shows that in fact as soon as the

0:06:20.482,0:06:25.750
private exponent d is less than the fourth[br]root of the modulus, let's see, if the

0:06:25.750,0:06:31.084
modulus is around twenty to 48 bits, that[br]means that if d is less than two to the

0:06:31.084,0:06:36.203
512th. Then RSA is completely, completely[br]insecure. And this is, it's insecure and

0:06:36.203,0:06:41.637
the worse possible way namely just given a[br]public key and an e, you can very quickly

0:06:41.637,0:06:47.364
recover the private key d. Well some folks[br]said well this attack works out to 512

0:06:47.364,0:06:51.929
bits so why don't we make the modulo say[br]you know 530 bits then this attack

0:06:51.929,0:06:56.916
actually wouldn't apply but still we get[br]to speed up RSA decryption by a factor of

0:06:56.916,0:07:01.815
four because we shrunk the exponent from[br]2000 bits To say 530 bits. Well, it turns

0:07:01.815,0:07:06.892
out even that that's not secure. In fact,[br]there's an extension to [inaudible] attack

0:07:06.892,0:07:11.848
that's actually much more complicated that[br]shows that if d is less than n to the

0:07:11.848,0:07:16.803
.292, then also RSA isn't secure and in[br]fact the conjuncture is that this is true

0:07:16.803,0:07:21.636
up to n to the .5 so even if d is like n[br]to the .4999, RSA is still, be insecure

0:07:21.636,0:07:26.347
although this is an open problem. So[br]again, a wonderful open problem, It's been

0:07:26.347,0:07:31.118
open for like, you know? Its fourteen[br]years now and no one can progress beyond

0:07:31.118,0:07:36.362
this .292 Somehow Seems kind of strange.[br]Why would .292 be the right answer and yet

0:07:36.362,0:07:42.174
no one can go beyond .292? So just to be[br]precised when I say that RSA is insecure,

0:07:42.174,0:07:47.384
what I mean is just giving them the[br]Public-key in n e; your goal is to recover

0:07:47.384,0:07:52.069
the secret key d. If you're curious where[br].292 comes from I'll tell you that what it

0:07:52.069,0:07:56.254
is, it's basically one - one over square[br]root of two. Now how could this possibly

0:07:56.254,0:08:00.545
be the right answer? The problem is much[br]more natural than the answer is n to the

0:08:00.545,0:08:04.678
.5 but this is still an open problem.[br]Again, if you wanna think about that it's

0:08:04.678,0:08:08.810
kind of a fun problem to work on. So the[br]lesson in this is that one should not

0:08:08.810,0:08:13.048
enforce any structure on d for improving[br]the performance of RSA and in fact now

0:08:13.048,0:08:17.286
there's a slew of results like this that[br]show, that basically any kind of tricks

0:08:17.286,0:08:21.260
like this to try and improve RSA's[br]performance is gonna end up in disaster.

0:08:21.260,0:08:25.792
So this is not the right way to improve[br]RSAs performance. Initially I wasn't going

0:08:25.792,0:08:29.559
to cover the details of Wiener's Attack[br]but given the discussions in the class I

0:08:29.559,0:08:33.000
think some of your would enjoy seeing the[br]details. All it involves is just

0:08:33.000,0:08:36.721
manipulating so many qualities. If you're[br]not comfortable with that, feel free to

0:08:36.721,0:08:40.487
skip over the slide although I think many[br]of you would actually enjoy seeing the

0:08:40.487,0:08:44.853
details. So let me remind you in Wiener's[br]Attack basically would given the modulus

0:08:44.853,0:08:49.277
and the RSA exponent and an e and our goal[br]is to recover d, the private exponent d

0:08:49.277,0:08:53.486
and all we know is that d is basically[br]less than fourth root of n. In fact, I'm

0:08:53.486,0:08:57.803
gonna assume that d is less than four root[br]of n divided by three and thus three

0:08:57.803,0:09:02.120
doesn't really matter but the dominating[br]term here is d is less than the fourth

0:09:02.120,0:09:08.056
root of n. So let's see how to do it. So[br]first of all, recall that because e and d

0:09:08.056,0:09:14.255
are RSA public and private exponents, we[br]know that e * d is one modulo phi of n.

0:09:14.255,0:09:20.772
Well what does that mean, that means that[br]you're exist some integer k such that e *

0:09:20.772,0:09:25.545
d is = k * phi of n + one. Basically[br]that's what it means for e * d to be one

0:09:25.545,0:09:29.964
modulo phi of n Basically, some integer[br]multiple phi of n + one. So now let's

0:09:29.964,0:09:34.795
stare at this equation a little bit, and[br]in fact this equation is the key equation

0:09:34.795,0:09:43.409
on the attack. And what we're gonna do is[br]first of all divide both sides by d * phi

0:09:43.409,0:09:52.343
(N). And in fact, I'm gonna move this term[br]here to the left. So after I divide by d *

0:09:52.343,0:09:59.908
phi (n), what I get is that e / phi(n) - k[br]/ d = one / d * phi(n). Okay. So all I did

0:09:59.908,0:10:04.391
is I just divide it by d * 5n and moved[br]the k * 5n and turn to the left hand side.

0:10:04.391,0:10:09.041
Now just for the heck of it, I'm going to[br]add absolute values here. This will become

0:10:09.041,0:10:13.748
useful in just a minute but of course they[br]don't change this equality at all. Now 5n

0:10:13.748,0:10:18.230
of course is almost n. 5n is very, very[br]close to n as we said earlier and all I'm

0:10:18.230,0:10:22.993
gonna need then for this fraction is just[br]to say that it's less than one over square

0:10:22.993,0:10:27.083
root of n. It's actually much, much[br]smaller than one over square root of n.

0:10:27.083,0:10:31.535
It's actually in the order of one over n[br]or even more than that. But for our

0:10:31.535,0:10:35.978
purposes, all we need is that this[br]fraction is less than one over square root

0:10:35.978,0:10:40.479
of n. Now let's stare at this fraction for[br]just a minute. You realize that this

0:10:40.479,0:10:45.789
fraction on the left here Is a fraction[br]that we don't actually know. We know e but

0:10:45.789,0:10:50.901
we don't know phi of n and as a result we[br]don't know e over phi of n. But we have a

0:10:50.901,0:10:55.829
good approximation to e over phi of n[br]namely we know the phi of n is very close

0:10:55.829,0:11:00.415
to n, therefore e over phi of n is very[br]close to e over n. So we have a good

0:11:00.415,0:11:05.077
approximation to this left hand side[br]fraction we have ran. What we really want

0:11:05.077,0:11:09.678
is the right hand fraction because once we[br]get the right hand side fractions

0:11:09.678,0:11:14.220
basically you guys wanna involve d and[br]then we'll able to recover d, okay. So

0:11:14.220,0:11:19.286
let's see if we replace e over 5n by e[br]over n. Let's see what kind of error we're

0:11:19.286,0:11:24.646
gonna get. So to analyze that what we'll[br]do is first of all remind ourselves that

0:11:24.646,0:11:29.023
5n is basically n - p - q +one. Which[br]means that n - phi (n) is gonna be less

0:11:29.023,0:11:33.331
than p + q. Actually I should, to be[br]precise, I should really write p + q +

0:11:33.331,0:11:38.009
one. But, you know, who cares about this[br]one. It's not, it doesn't really affect

0:11:38.009,0:11:42.625
anything so I'm just gonna ignore it for[br]simplicity. Okay? So n - phi (n) is less

0:11:42.625,0:11:47.610
than p + q. Both p and q are roughly half[br]the length of n so, you know, they kind of

0:11:47.610,0:11:52.472
both on the order of square root of n. So[br]basically, p + q we'll say is less than

0:11:52.472,0:11:57.246
three * square root of n. Okay. So we're[br]going to use this inequality in just a

0:11:57.246,0:12:02.035
minute but now we're gonna start using the[br]fact that we know something about

0:12:02.035,0:12:06.761
[inaudible] so if we look at this[br]inequality here, d is less than the fourth

0:12:06.761,0:12:11.737
root of n / three, it's act ually fairly[br]easy to see if I square both sides and I

0:12:11.737,0:12:16.463
just manipulate these a little bit, it's[br]difficult to see that this directly

0:12:16.463,0:12:21.625
implies the following relation basically[br]one / two d squared - one / square root of

0:12:21.625,0:12:26.523
n is greater than three / square root of[br]n. As I said this basically follows by

0:12:26.523,0:12:31.218
square in both sides then taking the[br]inverse of both sides and then I guess

0:12:31.218,0:12:36.736
multiplying one side by half. Okay. So you[br]can easily derive this relation and we'll

0:12:36.736,0:12:42.119
need this relation in just a minute. So[br]now let's see, what do we like to do is

0:12:42.119,0:12:47.570
bound the difference of e / n and k / d.[br]Well, what do we know? By the triangular

0:12:47.570,0:12:53.229
and equality we know that this is equal to[br]the distance between e / n and e / phi (n)

0:12:53.229,0:12:57.901
plus the distance from e/ phi (N). 2k / d,[br]okay? This is just what's called the

0:12:57.901,0:13:02.620
triangular and equality. This is just the[br]property of absolute values. Now this

0:13:02.620,0:13:07.702
absolute value here we already know how to[br]bound if you think about it as basically

0:13:07.702,0:13:12.603
the bound that we've already derived so we[br]know that this absolute value here is

0:13:12.603,0:13:17.624
basically less than one / square root of[br]n. Now what do we know about this absolute

0:13:17.624,0:13:22.464
value here? What is e / n - e / 5n? Well,[br]let's do common denominators and see what

0:13:22.464,0:13:28.881
we get so the common denominator is gonna[br]be n * 5n. And the numerator in this case

0:13:28.881,0:13:34.609
is going to be e * 5n - n. Which we know[br]from this expression here is less than

0:13:34.609,0:13:39.245
three * square root of n. So really what[br]this numerator is gonna be is e * three

0:13:39.245,0:13:43.940
square root of n. The numerator is gonna[br]be less than e * three square root of n.

0:13:43.940,0:13:49.578
So now I know that e is less than phi (N).[br]So I know that e over phi (n) is less than

0:13:49.578,0:13:54.630
one. In other words, if I erased e and I[br]erased phi (n), I've only made the

0:13:54.630,0:14:00.196
fraction larger. Okay? So this initial[br]absolute value is not gonna be smaller

0:14:00.196,0:14:06.127
than three square root of n over n which[br]is simply, three square root of n over n

0:14:06.127,0:14:11.015
is simply three over square root of n.[br]Okay. But what do we know about three /

0:14:11.015,0:14:16.945
square root of n, we know that it's less[br]than one. Over 2d squared - one / square

0:14:16.945,0:14:22.292
root of n. Okay, so that's the end of ou r[br]derivation. So now we know that the first

0:14:22.292,0:14:27.024
absolute value is less than one over two d[br]square - square root of n. The second

0:14:27.024,0:14:31.756
absolute value is less than one over[br]square root of n and therefore the sum is

0:14:31.756,0:14:36.847
less than one over two d squared. And this[br]is the expression that I want you to stare

0:14:36.847,0:14:42.194
at, so here let me circle it a little bit.[br]So, let me circle this part And this part.

0:14:42.194,0:14:47.736
Now so let's stir a little bit of a[br]distraction here and what we see is first

0:14:47.736,0:14:53.563
of all as before. Now we know the value of[br]e / n and what we'd like to find out is

0:14:53.563,0:14:58.368
the value k / d. But what do we know about[br]this fraction k over d? We know somehow

0:14:58.368,0:15:03.053
that the difference of these two fractions[br]is really small, it's less than one over

0:15:03.053,0:15:07.400
two d squared. Now this turns out to[br]happen very and frequently that k over d.

0:15:07.400,0:15:13.167
Approximate e over n so well That the[br]distance between the two is less than the

0:15:13.167,0:15:17.588
square of the denominator of k over d. It[br]turns out that, that can happen very

0:15:17.588,0:15:21.883
often. It turns out there are very few[br]fractions of the form k / d than

0:15:21.883,0:15:26.903
approximate another fraction so well that[br]their difference is less than one of the

0:15:26.903,0:15:31.923
2d squared. And in fact the number of such[br]factions is gonna be most logarithmic in

0:15:31.923,0:15:36.702
n. So now there's a continued fraction of[br]algorithm. It's a very famous fraction

0:15:36.702,0:15:41.541
that basically what it would do Si from[br]the fraction e / n it would recover and

0:15:41.541,0:15:46.561
possible candidate for k / d so we just[br]try them all one by one until we find the

0:15:46.561,0:15:51.851
direct k / over d. And then we're done.[br]We're done because we know that well e * d

0:15:51.851,0:15:56.730
is one [inaudible] k, therefore, d is[br]relatively prime to k. So if we just

0:15:56.730,0:16:02.219
represent k over d as a rational fraction,[br]you know? Numerator by denominator, then

0:16:02.219,0:16:06.706
denominator must be d. And so we've just[br]recovered, you know? We've tried all

0:16:06.706,0:16:11.400
possible log in fractions that approximate[br]e over n so well that the difference is

0:16:11.400,0:16:15.980
less than one over 2d squared and then we[br]just look at the denominator of all of

0:16:15.980,0:16:19.995
those fractions and one of those[br]denominators must be d and then we're

0:16:19.995,0:16:24.856
done, we're just recovered the private[br]key. So this is a pretty huge attack and

0:16:24.856,0:16:30.003
it shows basically how if the private[br]exponent is small, smaller than the fourth

0:16:30.003,0:16:34.377
root of n, then we can recover d[br]completely and quite easily. Okay. So,

0:16:34.377,0:16:35.343
I'll stop here.