[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:05.38,Default,,0000,0000,0000,,The next question we're gonna ask is RSA\Nreally a one way function. In other words,
Dialogue: 0,0:00:05.38,0:00:10.57,Default,,0000,0000,0000,,is it really hard to invert RSA without\Nknowing the Trapdoor? So if an attacker
Dialogue: 0,0:00:10.57,0:00:15.68,Default,,0000,0000,0000,,wanted to invert the RSA function, well\Nwhat the attacker has is basically the
Dialogue: 0,0:00:15.68,0:00:21.07,Default,,0000,0000,0000,,public key namely, he has n and e, and now\Nhe's given x to the e and his goal is to
Dialogue: 0,0:00:21.07,0:00:26.25,Default,,0000,0000,0000,,recover x, okay? So the question really\Nis, given x to the e modulo n, how hard is
Dialogue: 0,0:00:26.25,0:00:31.37,Default,,0000,0000,0000,,it to recover x? So what we're really\Nasking is, how hard is it to compute e-th
Dialogue: 0,0:00:31.37,0:00:36.82,Default,,0000,0000,0000,,roots modulo composite? If this problem\Nturns out to be hard, then RSA is in fact
Dialogue: 0,0:00:36.82,0:00:41.08,Default,,0000,0000,0000,,the one way function. If this problem\Nturns out to be easy which is of course we
Dialogue: 0,0:00:41.08,0:00:44.96,Default,,0000,0000,0000,,don't believe is easy, then RSA would\Nactually be broken. So just at this
Dialogue: 0,0:00:44.96,0:00:49.46,Default,,0000,0000,0000,,[inaudible] for this problem requires us\Nthe first factor, the modulo n, and then
Dialogue: 0,0:00:49.46,0:00:53.84,Default,,0000,0000,0000,,the ones we factor the modulus we've\Nalready seen last week that it's easy to
Dialogue: 0,0:00:53.84,0:00:58.34,Default,,0000,0000,0000,,compute the e-th root modulo p, it's easy\Nto compute e-th root modulo q and then
Dialogue: 0,0:00:58.34,0:01:03.12,Default,,0000,0000,0000,,given both those e-th roots it's actually\Neasy to combine them together using what's
Dialogue: 0,0:01:03.12,0:01:07.84,Default,,0000,0000,0000,,called the Chinese Remainder Theorem and\Nactually recover the e-th root modulo n.
Dialogue: 0,0:01:07.84,0:01:12.28,Default,,0000,0000,0000,,So once we're able to factor the modulus\Ncomputing e-th roots, modulo n becomes
Dialogue: 0,0:01:12.28,0:01:16.89,Default,,0000,0000,0000,,easy but factoring the modulus as far as\Nwe know is a very, very difficult problem.
Dialogue: 0,0:01:16.89,0:01:21.44,Default,,0000,0000,0000,,But the natural question is, is it true\Nthat in order to compute [inaudible] we
Dialogue: 0,0:01:21.44,0:01:26.06,Default,,0000,0000,0000,,have to factor the modulus n. As far as we\Nknow the best algorithm for computing
Dialogue: 0,0:01:26.06,0:01:30.09,Default,,0000,0000,0000,,[inaudible] modular n requires\Nfactorization of n. But who knows, maybe
Dialogue: 0,0:01:30.09,0:01:34.53,Default,,0000,0000,0000,,there's a short cut that allows us to\Ncomplete [inaudible] modular n without
Dialogue: 0,0:01:34.53,0:01:38.71,Default,,0000,0000,0000,,factoring the modulus. To show that that's\Nnot possible, we have to show our
Dialogue: 0,0:01:38.71,0:01:43.10,Default,,0000,0000,0000,,reduction. That is we have to show that if\NI give you an efficient algorithm for
Dialogue: 0,0:01:43.10,0:01:47.22,Default,,0000,0000,0000,,computing e-th root modulo m, that\Nefficient algorithm can be turned into a
Dialogue: 0,0:01:47.22,0:01:51.73,Default,,0000,0000,0000,,factoring algorithm. So this is called the\Nreduction namely given an algorithm for
Dialogue: 0,0:01:51.73,0:01:56.12,Default,,0000,0000,0000,,e-th root modulo m, we obtain a factoring\Nalgorithm and that would show that one
Dialogue: 0,0:01:56.12,0:02:00.74,Default,,0000,0000,0000,,cannot compute e-th root modulo m faster\Nthan factoring the modules. If we had such
Dialogue: 0,0:02:00.74,0:02:04.70,Default,,0000,0000,0000,,a result, it would show that actually\Nbreaking RSA in fact is as hard as
Dialogue: 0,0:02:04.70,0:02:09.11,Default,,0000,0000,0000,,factoring but unfortunately this is not\Nreally known at the moment. In fact this
Dialogue: 0,0:02:09.11,0:02:13.46,Default,,0000,0000,0000,,is the one of the oldest problems in\NPublic-key crypto and so let me just give
Dialogue: 0,0:02:13.46,0:02:18.09,Default,,0000,0000,0000,,you a concrete example. I supposed I give\Nyou an algorithm what will compute q brute
Dialogue: 0,0:02:18.09,0:02:22.80,Default,,0000,0000,0000,,modular m. So for any x and zN the\Nalgorithm will compute the cube root of x
Dialogue: 0,0:02:22.80,0:02:27.71,Default,,0000,0000,0000,,modulo m and my question is can you show\Nthat using such an algorithm you can
Dialogue: 0,0:02:27.71,0:02:32.81,Default,,0000,0000,0000,,factor the modulo m? And even that's not\Nknown. What is known I'll tell you is for
Dialogue: 0,0:02:32.81,0:02:37.85,Default,,0000,0000,0000,,example that for e = two. That is if I\Ngive you an algorithm for computing square
Dialogue: 0,0:02:37.85,0:02:42.45,Default,,0000,0000,0000,,roots modulo n, then in fact that does\Nimply factoring the modulus and so
Dialogue: 0,0:02:42.45,0:02:47.55,Default,,0000,0000,0000,,computing square roots, is in fact as hard\Nas factoring the modulus. Unfortunately,
Dialogue: 0,0:02:47.55,0:02:52.21,Default,,0000,0000,0000,,if you think back to the definition of\NRSA, that required that e * d be one
Dialogue: 0,0:02:52.21,0:02:57.50,Default,,0000,0000,0000,,modulo phi of n and what that means is\Nthat e necessarily needs to be relatively
Dialogue: 0,0:02:57.50,0:03:03.28,Default,,0000,0000,0000,,prime to phi of n. What the first equation\Nsays that e is invertible modulo 5n but if
Dialogue: 0,0:03:03.28,0:03:08.88,Default,,0000,0000,0000,,e is invertible modulo 5n, necessarily\Nthat means that e must be relatively prime
Dialogue: 0,0:03:08.88,0:03:14.63,Default,,0000,0000,0000,,to 5n. But again if you remember that's =\Np - one * q - one and since p and q are
Dialogue: 0,0:03:14.63,0:03:20.41,Default,,0000,0000,0000,,both primes, p - one * q - one is always\Neven. And as a result, the GCD of two and
Dialogue: 0,0:03:20.41,0:03:26.64,Default,,0000,0000,0000,,phi of n is = two because phi of n is even\Nand therefore, the public exponent two is
Dialogue: 0,0:03:26.64,0:03:32.80,Default,,0000,0000,0000,,not relatively prime to phi of n which\Nmeans that even though we have a reduction
Dialogue: 0,0:03:32.80,0:03:38.82,Default,,0000,0000,0000,,from taking square roots to factoring, e =\Ntwo cannot be use as an RSA exponent. So
Dialogue: 0,0:03:38.82,0:03:43.04,Default,,0000,0000,0000,,really the smallest RSA exponent that's\Nlegal is in fact e = three but for e =
Dialogue: 0,0:03:43.04,0:03:47.48,Default,,0000,0000,0000,,three the question of whether computing\Ncube roots is as hard as factoring is an
Dialogue: 0,0:03:47.48,0:03:51.86,Default,,0000,0000,0000,,open problem. It's actually a lot of fun\Nto think about this question. So, I would
Dialogue: 0,0:03:51.86,0:03:55.97,Default,,0000,0000,0000,,encourage you to think about it just a\Nlittle bit that is if I give you an
Dialogue: 0,0:03:55.97,0:04:00.41,Default,,0000,0000,0000,,efficient algorithm for computing cube\Nroots modulo n, can you use that algorithm
Dialogue: 0,0:04:00.41,0:04:04.71,Default,,0000,0000,0000,,to actually factor the modulus n? I'll\Ntell you that is a little b it of evidence
Dialogue: 0,0:04:04.71,0:04:09.01,Default,,0000,0000,0000,,to say that a reduction like that actually\Ndoesn't exist but it's very, very weak
Dialogue: 0,0:04:09.01,0:04:13.16,Default,,0000,0000,0000,,evidence. What this evidence says is\Nbasically if you give me a reduction of a
Dialogue: 0,0:04:13.16,0:04:17.45,Default,,0000,0000,0000,,very particular form, in other words if\Nyour reduction is what's called algebraic,
Dialogue: 0,0:04:17.45,0:04:21.28,Default,,0000,0000,0000,,I'm not gonna explain what that means\Nhere, that is if given a cube root,
Dialogue: 0,0:04:21.28,0:04:25.04,Default,,0000,0000,0000,,oracle, you could actually show me in\Nalgorithm that within factor, that
Dialogue: 0,0:04:25.04,0:04:29.37,Default,,0000,0000,0000,,reduction by itself would actually imply a\Nfactoring algorithm. Okay so that would
Dialogue: 0,0:04:29.37,0:04:33.62,Default,,0000,0000,0000,,say, that a factoring is hard, a reduction\Nactually doesn't exist. But as I say, this
Dialogue: 0,0:04:33.62,0:04:37.87,Default,,0000,0000,0000,,is very weak evidence 'cause who's to say\Nthat the reduction needs to be algebraic
Dialogue: 0,0:04:37.87,0:04:41.65,Default,,0000,0000,0000,,maybe there are some other types of\Nreductions that we haven't really
Dialogue: 0,0:04:41.65,0:04:45.69,Default,,0000,0000,0000,,considered. So, I would encourage you to\Nthink a little bit about this question,
Dialogue: 0,0:04:45.69,0:04:50.10,Default,,0000,0000,0000,,it's actually quite interesting how would\Nyou use a cube root algorithm to factor
Dialogue: 0,0:04:50.10,0:04:54.91,Default,,0000,0000,0000,,the modulus. But as I said as far as we\Nknow RSA is a one way function and in fact
Dialogue: 0,0:04:54.91,0:04:59.69,Default,,0000,0000,0000,,breaking RSA, computing e-th root status\Nactually requires factoring the modules.
Dialogue: 0,0:04:59.69,0:05:04.50,Default,,0000,0000,0000,,We all believe that's true. That's state\Nof the art. But now there's has been a lot
Dialogue: 0,0:05:04.50,0:05:08.72,Default,,0000,0000,0000,,of work on trying to improve the\Nperformance of RSA. Either RSA encryption
Dialogue: 0,0:05:08.72,0:05:12.99,Default,,0000,0000,0000,,or improve the performance of RSA\Ndecryption. And it turns out there's been
Dialogue: 0,0:05:12.99,0:05:17.82,Default,,0000,0000,0000,,a number of false start in this direction\Nso I wanna show you this wonderful example
Dialogue: 0,0:05:17.82,0:05:22.09,Default,,0000,0000,0000,,as a warning and so this basically is an\Nexample on how not to improve the
Dialogue: 0,0:05:22.09,0:05:26.14,Default,,0000,0000,0000,,performance of RSA. So you might think\Nthat if I wanted to speed up RSA
Dialogue: 0,0:05:26.14,0:05:30.80,Default,,0000,0000,0000,,decryption, remember decryption is done\Nbut raising the ciphertext to the power of
Dialogue: 0,0:05:30.80,0:05:35.58,Default,,0000,0000,0000,,d and you remember that the exponentiation\Nalgorithm ran in linear time in the size
Dialogue: 0,0:05:35.58,0:05:40.37,Default,,0000,0000,0000,,of d Linear time and log of d. So you\Nmight think to yourself well, if I wanted
Dialogue: 0,0:05:40.37,0:05:44.99,Default,,0000,0000,0000,,to speed up RSA decryption, why don't I\Njust use d of a, decryption exponent
Dialogue: 0,0:05:44.99,0:05:50.10,Default,,0000,0000,0000,,that's on the order of two to the 128th.\NSo it's clearly big enough to that exhaust
Dialogue: 0,0:05:50.10,0:05:55.04,Default,,0000,0000,0000,,a search against d is not possible, but\Nnormally the decryption exponent d would
Dialogue: 0,0:05:55.04,0:06:00.07,Default,,0000,0000,0000,,be as big as the modulus say 2,000 bits.\NBy using d that's only 128th bits, I
Dialogue: 0,0:06:00.07,0:06:05.40,Default,,0000,0000,0000,,basically speed up the decryption by a\Nfactor twenty. Then I went down from 2,000
Dialogue: 0,0:06:05.40,0:06:10.60,Default,,0000,0000,0000,,bits to 100 bits so exponentiation would\Nrun twenty times as fast. It turns out
Dialogue: 0,0:06:10.60,0:06:15.21,Default,,0000,0000,0000,,this is a terrible idea, terrible,\Nterrible idea in the following sense
Dialogue: 0,0:06:15.21,0:06:20.48,Default,,0000,0000,0000,,there's an attack by Michael [inaudible]\Nthat shows that in fact as soon as the
Dialogue: 0,0:06:20.48,0:06:25.75,Default,,0000,0000,0000,,private exponent d is less than the fourth\Nroot of the modulus, let's see, if the
Dialogue: 0,0:06:25.75,0:06:31.08,Default,,0000,0000,0000,,modulus is around twenty to 48 bits, that\Nmeans that if d is less than two to the
Dialogue: 0,0:06:31.08,0:06:36.20,Default,,0000,0000,0000,,512th. Then RSA is completely, completely\Ninsecure. And this is, it's insecure and
Dialogue: 0,0:06:36.20,0:06:41.64,Default,,0000,0000,0000,,the worse possible way namely just given a\Npublic key and an e, you can very quickly
Dialogue: 0,0:06:41.64,0:06:47.36,Default,,0000,0000,0000,,recover the private key d. Well some folks\Nsaid well this attack works out to 512
Dialogue: 0,0:06:47.36,0:06:51.93,Default,,0000,0000,0000,,bits so why don't we make the modulo say\Nyou know 530 bits then this attack
Dialogue: 0,0:06:51.93,0:06:56.92,Default,,0000,0000,0000,,actually wouldn't apply but still we get\Nto speed up RSA decryption by a factor of
Dialogue: 0,0:06:56.92,0:07:01.82,Default,,0000,0000,0000,,four because we shrunk the exponent from\N2000 bits To say 530 bits. Well, it turns
Dialogue: 0,0:07:01.82,0:07:06.89,Default,,0000,0000,0000,,out even that that's not secure. In fact,\Nthere's an extension to [inaudible] attack
Dialogue: 0,0:07:06.89,0:07:11.85,Default,,0000,0000,0000,,that's actually much more complicated that\Nshows that if d is less than n to the
Dialogue: 0,0:07:11.85,0:07:16.80,Default,,0000,0000,0000,,.292, then also RSA isn't secure and in\Nfact the conjuncture is that this is true
Dialogue: 0,0:07:16.80,0:07:21.64,Default,,0000,0000,0000,,up to n to the .5 so even if d is like n\Nto the .4999, RSA is still, be insecure
Dialogue: 0,0:07:21.64,0:07:26.35,Default,,0000,0000,0000,,although this is an open problem. So\Nagain, a wonderful open problem, It's been
Dialogue: 0,0:07:26.35,0:07:31.12,Default,,0000,0000,0000,,open for like, you know? Its fourteen\Nyears now and no one can progress beyond
Dialogue: 0,0:07:31.12,0:07:36.36,Default,,0000,0000,0000,,this .292 Somehow Seems kind of strange.\NWhy would .292 be the right answer and yet
Dialogue: 0,0:07:36.36,0:07:42.17,Default,,0000,0000,0000,,no one can go beyond .292? So just to be\Nprecised when I say that RSA is insecure,
Dialogue: 0,0:07:42.17,0:07:47.38,Default,,0000,0000,0000,,what I mean is just giving them the\NPublic-key in n e; your goal is to recover
Dialogue: 0,0:07:47.38,0:07:52.07,Default,,0000,0000,0000,,the secret key d. If you're curious where\N.292 comes from I'll tell you that what it
Dialogue: 0,0:07:52.07,0:07:56.25,Default,,0000,0000,0000,,is, it's basically one - one over square\Nroot of two. Now how could this possibly
Dialogue: 0,0:07:56.25,0:08:00.54,Default,,0000,0000,0000,,be the right answer? The problem is much\Nmore natural than the answer is n to the
Dialogue: 0,0:08:00.54,0:08:04.68,Default,,0000,0000,0000,,.5 but this is still an open problem.\NAgain, if you wanna think about that it's
Dialogue: 0,0:08:04.68,0:08:08.81,Default,,0000,0000,0000,,kind of a fun problem to work on. So the\Nlesson in this is that one should not
Dialogue: 0,0:08:08.81,0:08:13.05,Default,,0000,0000,0000,,enforce any structure on d for improving\Nthe performance of RSA and in fact now
Dialogue: 0,0:08:13.05,0:08:17.29,Default,,0000,0000,0000,,there's a slew of results like this that\Nshow, that basically any kind of tricks
Dialogue: 0,0:08:17.29,0:08:21.26,Default,,0000,0000,0000,,like this to try and improve RSA's\Nperformance is gonna end up in disaster.
Dialogue: 0,0:08:21.26,0:08:25.79,Default,,0000,0000,0000,,So this is not the right way to improve\NRSAs performance. Initially I wasn't going
Dialogue: 0,0:08:25.79,0:08:29.56,Default,,0000,0000,0000,,to cover the details of Wiener's Attack\Nbut given the discussions in the class I
Dialogue: 0,0:08:29.56,0:08:33.00,Default,,0000,0000,0000,,think some of your would enjoy seeing the\Ndetails. All it involves is just
Dialogue: 0,0:08:33.00,0:08:36.72,Default,,0000,0000,0000,,manipulating so many qualities. If you're\Nnot comfortable with that, feel free to
Dialogue: 0,0:08:36.72,0:08:40.49,Default,,0000,0000,0000,,skip over the slide although I think many\Nof you would actually enjoy seeing the
Dialogue: 0,0:08:40.49,0:08:44.85,Default,,0000,0000,0000,,details. So let me remind you in Wiener's\NAttack basically would given the modulus
Dialogue: 0,0:08:44.85,0:08:49.28,Default,,0000,0000,0000,,and the RSA exponent and an e and our goal\Nis to recover d, the private exponent d
Dialogue: 0,0:08:49.28,0:08:53.49,Default,,0000,0000,0000,,and all we know is that d is basically\Nless than fourth root of n. In fact, I'm
Dialogue: 0,0:08:53.49,0:08:57.80,Default,,0000,0000,0000,,gonna assume that d is less than four root\Nof n divided by three and thus three
Dialogue: 0,0:08:57.80,0:09:02.12,Default,,0000,0000,0000,,doesn't really matter but the dominating\Nterm here is d is less than the fourth
Dialogue: 0,0:09:02.12,0:09:08.06,Default,,0000,0000,0000,,root of n. So let's see how to do it. So\Nfirst of all, recall that because e and d
Dialogue: 0,0:09:08.06,0:09:14.26,Default,,0000,0000,0000,,are RSA public and private exponents, we\Nknow that e * d is one modulo phi of n.
Dialogue: 0,0:09:14.26,0:09:20.77,Default,,0000,0000,0000,,Well what does that mean, that means that\Nyou're exist some integer k such that e *
Dialogue: 0,0:09:20.77,0:09:25.54,Default,,0000,0000,0000,,d is = k * phi of n + one. Basically\Nthat's what it means for e * d to be one
Dialogue: 0,0:09:25.54,0:09:29.96,Default,,0000,0000,0000,,modulo phi of n Basically, some integer\Nmultiple phi of n + one. So now let's
Dialogue: 0,0:09:29.96,0:09:34.80,Default,,0000,0000,0000,,stare at this equation a little bit, and\Nin fact this equation is the key equation
Dialogue: 0,0:09:34.80,0:09:43.41,Default,,0000,0000,0000,,on the attack. And what we're gonna do is\Nfirst of all divide both sides by d * phi
Dialogue: 0,0:09:43.41,0:09:52.34,Default,,0000,0000,0000,,(N). And in fact, I'm gonna move this term\Nhere to the left. So after I divide by d *
Dialogue: 0,0:09:52.34,0:09:59.91,Default,,0000,0000,0000,,phi (n), what I get is that e / phi(n) - k\N/ d = one / d * phi(n). Okay. So all I did
Dialogue: 0,0:09:59.91,0:10:04.39,Default,,0000,0000,0000,,is I just divide it by d * 5n and moved\Nthe k * 5n and turn to the left hand side.
Dialogue: 0,0:10:04.39,0:10:09.04,Default,,0000,0000,0000,,Now just for the heck of it, I'm going to\Nadd absolute values here. This will become
Dialogue: 0,0:10:09.04,0:10:13.75,Default,,0000,0000,0000,,useful in just a minute but of course they\Ndon't change this equality at all. Now 5n
Dialogue: 0,0:10:13.75,0:10:18.23,Default,,0000,0000,0000,,of course is almost n. 5n is very, very\Nclose to n as we said earlier and all I'm
Dialogue: 0,0:10:18.23,0:10:22.99,Default,,0000,0000,0000,,gonna need then for this fraction is just\Nto say that it's less than one over square
Dialogue: 0,0:10:22.99,0:10:27.08,Default,,0000,0000,0000,,root of n. It's actually much, much\Nsmaller than one over square root of n.
Dialogue: 0,0:10:27.08,0:10:31.54,Default,,0000,0000,0000,,It's actually in the order of one over n\Nor even more than that. But for our
Dialogue: 0,0:10:31.54,0:10:35.98,Default,,0000,0000,0000,,purposes, all we need is that this\Nfraction is less than one over square root
Dialogue: 0,0:10:35.98,0:10:40.48,Default,,0000,0000,0000,,of n. Now let's stare at this fraction for\Njust a minute. You realize that this
Dialogue: 0,0:10:40.48,0:10:45.79,Default,,0000,0000,0000,,fraction on the left here Is a fraction\Nthat we don't actually know. We know e but
Dialogue: 0,0:10:45.79,0:10:50.90,Default,,0000,0000,0000,,we don't know phi of n and as a result we\Ndon't know e over phi of n. But we have a
Dialogue: 0,0:10:50.90,0:10:55.83,Default,,0000,0000,0000,,good approximation to e over phi of n\Nnamely we know the phi of n is very close
Dialogue: 0,0:10:55.83,0:11:00.42,Default,,0000,0000,0000,,to n, therefore e over phi of n is very\Nclose to e over n. So we have a good
Dialogue: 0,0:11:00.42,0:11:05.08,Default,,0000,0000,0000,,approximation to this left hand side\Nfraction we have ran. What we really want
Dialogue: 0,0:11:05.08,0:11:09.68,Default,,0000,0000,0000,,is the right hand fraction because once we\Nget the right hand side fractions
Dialogue: 0,0:11:09.68,0:11:14.22,Default,,0000,0000,0000,,basically you guys wanna involve d and\Nthen we'll able to recover d, okay. So
Dialogue: 0,0:11:14.22,0:11:19.29,Default,,0000,0000,0000,,let's see if we replace e over 5n by e\Nover n. Let's see what kind of error we're
Dialogue: 0,0:11:19.29,0:11:24.65,Default,,0000,0000,0000,,gonna get. So to analyze that what we'll\Ndo is first of all remind ourselves that
Dialogue: 0,0:11:24.65,0:11:29.02,Default,,0000,0000,0000,,5n is basically n - p - q +one. Which\Nmeans that n - phi (n) is gonna be less
Dialogue: 0,0:11:29.02,0:11:33.33,Default,,0000,0000,0000,,than p + q. Actually I should, to be\Nprecise, I should really write p + q +
Dialogue: 0,0:11:33.33,0:11:38.01,Default,,0000,0000,0000,,one. But, you know, who cares about this\None. It's not, it doesn't really affect
Dialogue: 0,0:11:38.01,0:11:42.62,Default,,0000,0000,0000,,anything so I'm just gonna ignore it for\Nsimplicity. Okay? So n - phi (n) is less
Dialogue: 0,0:11:42.62,0:11:47.61,Default,,0000,0000,0000,,than p + q. Both p and q are roughly half\Nthe length of n so, you know, they kind of
Dialogue: 0,0:11:47.61,0:11:52.47,Default,,0000,0000,0000,,both on the order of square root of n. So\Nbasically, p + q we'll say is less than
Dialogue: 0,0:11:52.47,0:11:57.25,Default,,0000,0000,0000,,three * square root of n. Okay. So we're\Ngoing to use this inequality in just a
Dialogue: 0,0:11:57.25,0:12:02.04,Default,,0000,0000,0000,,minute but now we're gonna start using the\Nfact that we know something about
Dialogue: 0,0:12:02.04,0:12:06.76,Default,,0000,0000,0000,,[inaudible] so if we look at this\Ninequality here, d is less than the fourth
Dialogue: 0,0:12:06.76,0:12:11.74,Default,,0000,0000,0000,,root of n / three, it's act ually fairly\Neasy to see if I square both sides and I
Dialogue: 0,0:12:11.74,0:12:16.46,Default,,0000,0000,0000,,just manipulate these a little bit, it's\Ndifficult to see that this directly
Dialogue: 0,0:12:16.46,0:12:21.62,Default,,0000,0000,0000,,implies the following relation basically\None / two d squared - one / square root of
Dialogue: 0,0:12:21.62,0:12:26.52,Default,,0000,0000,0000,,n is greater than three / square root of\Nn. As I said this basically follows by
Dialogue: 0,0:12:26.52,0:12:31.22,Default,,0000,0000,0000,,square in both sides then taking the\Ninverse of both sides and then I guess
Dialogue: 0,0:12:31.22,0:12:36.74,Default,,0000,0000,0000,,multiplying one side by half. Okay. So you\Ncan easily derive this relation and we'll
Dialogue: 0,0:12:36.74,0:12:42.12,Default,,0000,0000,0000,,need this relation in just a minute. So\Nnow let's see, what do we like to do is
Dialogue: 0,0:12:42.12,0:12:47.57,Default,,0000,0000,0000,,bound the difference of e / n and k / d.\NWell, what do we know? By the triangular
Dialogue: 0,0:12:47.57,0:12:53.23,Default,,0000,0000,0000,,and equality we know that this is equal to\Nthe distance between e / n and e / phi (n)
Dialogue: 0,0:12:53.23,0:12:57.90,Default,,0000,0000,0000,,plus the distance from e/ phi (N). 2k / d,\Nokay? This is just what's called the
Dialogue: 0,0:12:57.90,0:13:02.62,Default,,0000,0000,0000,,triangular and equality. This is just the\Nproperty of absolute values. Now this
Dialogue: 0,0:13:02.62,0:13:07.70,Default,,0000,0000,0000,,absolute value here we already know how to\Nbound if you think about it as basically
Dialogue: 0,0:13:07.70,0:13:12.60,Default,,0000,0000,0000,,the bound that we've already derived so we\Nknow that this absolute value here is
Dialogue: 0,0:13:12.60,0:13:17.62,Default,,0000,0000,0000,,basically less than one / square root of\Nn. Now what do we know about this absolute
Dialogue: 0,0:13:17.62,0:13:22.46,Default,,0000,0000,0000,,value here? What is e / n - e / 5n? Well,\Nlet's do common denominators and see what
Dialogue: 0,0:13:22.46,0:13:28.88,Default,,0000,0000,0000,,we get so the common denominator is gonna\Nbe n * 5n. And the numerator in this case
Dialogue: 0,0:13:28.88,0:13:34.61,Default,,0000,0000,0000,,is going to be e * 5n - n. Which we know\Nfrom this expression here is less than
Dialogue: 0,0:13:34.61,0:13:39.24,Default,,0000,0000,0000,,three * square root of n. So really what\Nthis numerator is gonna be is e * three
Dialogue: 0,0:13:39.24,0:13:43.94,Default,,0000,0000,0000,,square root of n. The numerator is gonna\Nbe less than e * three square root of n.
Dialogue: 0,0:13:43.94,0:13:49.58,Default,,0000,0000,0000,,So now I know that e is less than phi (N).\NSo I know that e over phi (n) is less than
Dialogue: 0,0:13:49.58,0:13:54.63,Default,,0000,0000,0000,,one. In other words, if I erased e and I\Nerased phi (n), I've only made the
Dialogue: 0,0:13:54.63,0:14:00.20,Default,,0000,0000,0000,,fraction larger. Okay? So this initial\Nabsolute value is not gonna be smaller
Dialogue: 0,0:14:00.20,0:14:06.13,Default,,0000,0000,0000,,than three square root of n over n which\Nis simply, three square root of n over n
Dialogue: 0,0:14:06.13,0:14:11.02,Default,,0000,0000,0000,,is simply three over square root of n.\NOkay. But what do we know about three /
Dialogue: 0,0:14:11.02,0:14:16.94,Default,,0000,0000,0000,,square root of n, we know that it's less\Nthan one. Over 2d squared - one / square
Dialogue: 0,0:14:16.94,0:14:22.29,Default,,0000,0000,0000,,root of n. Okay, so that's the end of ou r\Nderivation. So now we know that the first
Dialogue: 0,0:14:22.29,0:14:27.02,Default,,0000,0000,0000,,absolute value is less than one over two d\Nsquare - square root of n. The second
Dialogue: 0,0:14:27.02,0:14:31.76,Default,,0000,0000,0000,,absolute value is less than one over\Nsquare root of n and therefore the sum is
Dialogue: 0,0:14:31.76,0:14:36.85,Default,,0000,0000,0000,,less than one over two d squared. And this\Nis the expression that I want you to stare
Dialogue: 0,0:14:36.85,0:14:42.19,Default,,0000,0000,0000,,at, so here let me circle it a little bit.\NSo, let me circle this part And this part.
Dialogue: 0,0:14:42.19,0:14:47.74,Default,,0000,0000,0000,,Now so let's stir a little bit of a\Ndistraction here and what we see is first
Dialogue: 0,0:14:47.74,0:14:53.56,Default,,0000,0000,0000,,of all as before. Now we know the value of\Ne / n and what we'd like to find out is
Dialogue: 0,0:14:53.56,0:14:58.37,Default,,0000,0000,0000,,the value k / d. But what do we know about\Nthis fraction k over d? We know somehow
Dialogue: 0,0:14:58.37,0:15:03.05,Default,,0000,0000,0000,,that the difference of these two fractions\Nis really small, it's less than one over
Dialogue: 0,0:15:03.05,0:15:07.40,Default,,0000,0000,0000,,two d squared. Now this turns out to\Nhappen very and frequently that k over d.
Dialogue: 0,0:15:07.40,0:15:13.17,Default,,0000,0000,0000,,Approximate e over n so well That the\Ndistance between the two is less than the
Dialogue: 0,0:15:13.17,0:15:17.59,Default,,0000,0000,0000,,square of the denominator of k over d. It\Nturns out that, that can happen very
Dialogue: 0,0:15:17.59,0:15:21.88,Default,,0000,0000,0000,,often. It turns out there are very few\Nfractions of the form k / d than
Dialogue: 0,0:15:21.88,0:15:26.90,Default,,0000,0000,0000,,approximate another fraction so well that\Ntheir difference is less than one of the
Dialogue: 0,0:15:26.90,0:15:31.92,Default,,0000,0000,0000,,2d squared. And in fact the number of such\Nfactions is gonna be most logarithmic in
Dialogue: 0,0:15:31.92,0:15:36.70,Default,,0000,0000,0000,,n. So now there's a continued fraction of\Nalgorithm. It's a very famous fraction
Dialogue: 0,0:15:36.70,0:15:41.54,Default,,0000,0000,0000,,that basically what it would do Si from\Nthe fraction e / n it would recover and
Dialogue: 0,0:15:41.54,0:15:46.56,Default,,0000,0000,0000,,possible candidate for k / d so we just\Ntry them all one by one until we find the
Dialogue: 0,0:15:46.56,0:15:51.85,Default,,0000,0000,0000,,direct k / over d. And then we're done.\NWe're done because we know that well e * d
Dialogue: 0,0:15:51.85,0:15:56.73,Default,,0000,0000,0000,,is one [inaudible] k, therefore, d is\Nrelatively prime to k. So if we just
Dialogue: 0,0:15:56.73,0:16:02.22,Default,,0000,0000,0000,,represent k over d as a rational fraction,\Nyou know? Numerator by denominator, then
Dialogue: 0,0:16:02.22,0:16:06.71,Default,,0000,0000,0000,,denominator must be d. And so we've just\Nrecovered, you know? We've tried all
Dialogue: 0,0:16:06.71,0:16:11.40,Default,,0000,0000,0000,,possible log in fractions that approximate\Ne over n so well that the difference is
Dialogue: 0,0:16:11.40,0:16:15.98,Default,,0000,0000,0000,,less than one over 2d squared and then we\Njust look at the denominator of all of
Dialogue: 0,0:16:15.98,0:16:19.100,Default,,0000,0000,0000,,those fractions and one of those\Ndenominators must be d and then we're
Dialogue: 0,0:16:19.100,0:16:24.86,Default,,0000,0000,0000,,done, we're just recovered the private\Nkey. So this is a pretty huge attack and
Dialogue: 0,0:16:24.86,0:16:30.00,Default,,0000,0000,0000,,it shows basically how if the private\Nexponent is small, smaller than the fourth
Dialogue: 0,0:16:30.00,0:16:34.38,Default,,0000,0000,0000,,root of n, then we can recover d\Ncompletely and quite easily. Okay. So,
Dialogue: 0,0:16:34.38,0:16:35.34,Default,,0000,0000,0000,,I'll stop here.