[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.15,0:00:01.70,Default,,0000,0000,0000,,The next question, we're going to ask:
Dialogue: 0,0:00:01.70,0:00:03.64,Default,,0000,0000,0000,,is RSA really an one-way function?
Dialogue: 0,0:00:03.64,0:00:05.79,Default,,0000,0000,0000,,In other words, is it really hard to
Dialogue: 0,0:00:05.79,0:00:08.10,Default,,0000,0000,0000,,invert RSA without knowing the trapdoor?
Dialogue: 0,0:00:09.01,0:00:11.100,Default,,0000,0000,0000,,So, if an attacker wanted to invert the RSA function,
Dialogue: 0,0:00:11.100,0:00:15.00,Default,,0000,0000,0000,,well, what the attacker has, is basically the public key,
Dialogue: 0,0:00:15.00,0:00:19.05,Default,,0000,0000,0000,,namely he has N and e. And now, he is given x to the e
Dialogue: 0,0:00:19.05,0:00:23.29,Default,,0000,0000,0000,,and his goal is to recover x. OK, so the question really is:
Dialogue: 0,0:00:23.29,0:00:26.13,Default,,0000,0000,0000,,given x to the e modulo N, how hard is it to
Dialogue: 0,0:00:26.13,0:00:28.93,Default,,0000,0000,0000,,recover x? So, what we're really asking is,
Dialogue: 0,0:00:28.93,0:00:33.11,Default,,0000,0000,0000,,how hard is it to compute e'th roots modulo a composite?
Dialogue: 0,0:00:34.18,0:00:38.54,Default,,0000,0000,0000,,If this problem turns out to be hard, then RSA is in fact an one-way function.
Dialogue: 0,0:00:38.54,0:00:39.97,Default,,0000,0000,0000,,If this problem turns out to be easy, which
Dialogue: 0,0:00:39.97,0:00:44.56,Default,,0000,0000,0000,,of course we don't believe it's easy, then RSA would actually be broken.
Dialogue: 0,0:00:44.56,0:00:46.83,Default,,0000,0000,0000,,So, it turns out the best algorithm for this problem
Dialogue: 0,0:00:46.83,0:00:49.56,Default,,0000,0000,0000,,requires us to first factor the modulus N.
Dialogue: 0,0:00:50.05,0:00:52.24,Default,,0000,0000,0000,,And then, once we factored the modulus, we have already
Dialogue: 0,0:00:52.24,0:00:55.89,Default,,0000,0000,0000,,seen last week, that it's easy to compute the e'th root modulo p,
Dialogue: 0,0:00:55.89,0:00:58.48,Default,,0000,0000,0000,,it's easy to compute the e'th root modulo q.
Dialogue: 0,0:00:58.48,0:01:02.11,Default,,0000,0000,0000,,And, then given both those e'th roots, it's actually easy to combine them together,
Dialogue: 0,0:01:02.11,0:01:04.70,Default,,0000,0000,0000,,using what's called the Chinese remainder theorem
Dialogue: 0,0:01:04.70,0:01:07.67,Default,,0000,0000,0000,,and actually recover the e'th root modulo N.
Dialogue: 0,0:01:07.67,0:01:09.95,Default,,0000,0000,0000,,So, once we are able to factor the modulus,
Dialogue: 0,0:01:09.95,0:01:12.85,Default,,0000,0000,0000,,computing e'th roots modulo N becomes easy.
Dialogue: 0,0:01:12.85,0:01:14.64,Default,,0000,0000,0000,,But, factoring the modulus, as far as
Dialogue: 0,0:01:14.64,0:01:16.76,Default,,0000,0000,0000,,we know, is a very, very difficult problem.
Dialogue: 0,0:01:16.76,0:01:19.86,Default,,0000,0000,0000,,But a natural question is, is it true that in
Dialogue: 0,0:01:19.86,0:01:22.57,Default,,0000,0000,0000,,order to compute e'th roots modulo N, we have to
Dialogue: 0,0:01:22.57,0:01:25.71,Default,,0000,0000,0000,,factor the modulus N? As far as we know, the
Dialogue: 0,0:01:25.71,0:01:27.37,Default,,0000,0000,0000,,best algorithm for computing e'th roots
Dialogue: 0,0:01:27.37,0:01:30.00,Default,,0000,0000,0000,,modulo N requires factorization of N.
Dialogue: 0,0:01:30.00,0:01:31.63,Default,,0000,0000,0000,,But, who knows, maybe there is a short cut
Dialogue: 0,0:01:31.63,0:01:33.77,Default,,0000,0000,0000,,that allows us to compute e'th roots modulo N,
Dialogue: 0,0:01:33.77,0:01:36.70,Default,,0000,0000,0000,,without factoring the modulus. To show that
Dialogue: 0,0:01:36.70,0:01:38.81,Default,,0000,0000,0000,,that's not possible, we have to show a reduction.
Dialogue: 0,0:01:38.81,0:01:40.31,Default,,0000,0000,0000,,That is, we have to show that,
Dialogue: 0,0:01:40.31,0:01:42.00,Default,,0000,0000,0000,,if I give you an efficient algorithm for
Dialogue: 0,0:01:42.00,0:01:43.87,Default,,0000,0000,0000,,computing e'th roots modulo N, that
Dialogue: 0,0:01:43.87,0:01:48.13,Default,,0000,0000,0000,,efficient algorithm can be turned into a factoring algorithm.
Dialogue: 0,0:01:48.13,0:01:51.02,Default,,0000,0000,0000,,So, this is called a reduction. Namely, given an algorithm for
Dialogue: 0,0:01:51.02,0:01:53.14,Default,,0000,0000,0000,,e'th roots modulo N, we obtain a factoring algorithm.
Dialogue: 0,0:01:53.14,0:01:57.31,Default,,0000,0000,0000,,That would show that one cannot compute e'th roots modulo N
Dialogue: 0,0:01:57.31,0:02:00.10,Default,,0000,0000,0000,,faster than factoring the modulus.
Dialogue: 0,0:02:00.10,0:02:02.28,Default,,0000,0000,0000,,If we had such a result, it would show that
Dialogue: 0,0:02:02.28,0:02:05.72,Default,,0000,0000,0000,,actually breaking RSA, in fact is as hard as factoring.
Dialogue: 0,0:02:05.72,0:02:08.11,Default,,0000,0000,0000,,But, unfortunately, this is not really known at the moment.
Dialogue: 0,0:02:08.11,0:02:11.97,Default,,0000,0000,0000,,In fact, this is one of the oldest problems in public key crypto.
Dialogue: 0,0:02:11.97,0:02:14.42,Default,,0000,0000,0000,,So, just let me give you a concrete example.
Dialogue: 0,0:02:14.42,0:02:18.52,Default,,0000,0000,0000,,Suppose, I give you an algorithm that will compute cube roots modulo N.
Dialogue: 0,0:02:19.04,0:02:23.69,Default,,0000,0000,0000,,So, for any x in ZN, the algorithm will compute the cube root of x modulo N.
Dialogue: 0,0:02:23.69,0:02:25.97,Default,,0000,0000,0000,,My question is, can you show that using
Dialogue: 0,0:02:25.97,0:02:29.07,Default,,0000,0000,0000,,such an algorithm you can factor the modulus N?
Dialogue: 0,0:02:29.07,0:02:31.24,Default,,0000,0000,0000,,And, even that is not known. What is known,
Dialogue: 0,0:02:31.24,0:02:33.92,Default,,0000,0000,0000,,I'll tell you, is for example that for e equals 2,
Dialogue: 0,0:02:34.38,0:02:37.71,Default,,0000,0000,0000,,that is if I give you an algorithm for computing square roots modulo N,
Dialogue: 0,0:02:37.71,0:02:40.70,Default,,0000,0000,0000,,then in fact, that does imply factoring the modulus.
Dialogue: 0,0:02:40.70,0:02:44.70,Default,,0000,0000,0000,,So, computing square roots is in fact as hard as factoring the modulus.
Dialogue: 0,0:02:44.71,0:02:47.78,Default,,0000,0000,0000,,Unfortunately, if you think back to the definition of RSA,
Dialogue: 0,0:02:47.78,0:02:52.91,Default,,0000,0000,0000,,that required that e times d be 1 modulo phi(N).
Dialogue: 0,0:02:52.91,0:02:58.61,Default,,0000,0000,0000,,What that means is, that e necessarily needs to be relatively prime to phi(N).
Dialogue: 0,0:02:58.61,0:03:03.13,Default,,0000,0000,0000,,Right, this, what the first equation says is that e is invertible modulo phi(N).
Dialogue: 0,0:03:03.13,0:03:06.12,Default,,0000,0000,0000,,But, if e is invertible modulo phi(N), necessarily that means that
Dialogue: 0,0:03:06.12,0:03:09.11,Default,,0000,0000,0000,,e must be relatively prime to phi(N).
Dialogue: 0,0:03:09.11,0:03:13.93,Default,,0000,0000,0000,,But, phi(N), if you remember, that is equal to p minus 1 times q minus 1.
Dialogue: 0,0:03:13.93,0:03:19.38,Default,,0000,0000,0000,,And, since p and q are both large primes, p - 1 times q - 1 is always even.
Dialogue: 0,0:03:19.38,0:03:25.50,Default,,0000,0000,0000,,And, as a result, the GCD of 2 and phi(N) is equal to 2,
Dialogue: 0,0:03:25.50,0:03:28.22,Default,,0000,0000,0000,,because phi(N) is even. And therefore, the public
Dialogue: 0,0:03:28.22,0:03:30.86,Default,,0000,0000,0000,,exponent 2 is not relatively prime to phi(N).
Dialogue: 0,0:03:30.86,0:03:33.17,Default,,0000,0000,0000,,Which means that, even though we have a reduction\N
Dialogue: 0,0:03:33.17,0:03:35.26,Default,,0000,0000,0000,,from taking square roots to factoring,
Dialogue: 0,0:03:35.26,0:03:38.76,Default,,0000,0000,0000,,e equals 2 cannot be used as an RSA exponent.
Dialogue: 0,0:03:38.76,0:03:43.64,Default,,0000,0000,0000,,So, really the smallest RSA exponent that is legal is in fact e equals 3.
Dialogue: 0,0:03:43.64,0:03:46.91,Default,,0000,0000,0000,,But, for e equal 3, the question of whether computing cube roots
Dialogue: 0,0:03:46.91,0:03:48.98,Default,,0000,0000,0000,,is as hard as factoring, is an open problem.
Dialogue: 0,0:03:48.98,0:03:50.98,Default,,0000,0000,0000,,It's actually a lot of fun to think about this question.
Dialogue: 0,0:03:50.98,0:03:53.44,Default,,0000,0000,0000,,So, I would encourage you to think about it just a little bit.
Dialogue: 0,0:03:53.44,0:03:58.35,Default,,0000,0000,0000,,That is, if I give you an efficient algorithm for computing cube roots modulo N,
Dialogue: 0,0:03:58.35,0:04:02.11,Default,,0000,0000,0000,,can you use that algorithm to actually factor the modulus N?
Dialogue: 0,0:04:02.11,0:04:05.30,Default,,0000,0000,0000,,I will tell you that there is a little bit of evidence to say
Dialogue: 0,0:04:05.30,0:04:09.40,Default,,0000,0000,0000,,that a reduction like that, actually doesn't exist, but it is very, very weak evidence.
Dialogue: 0,0:04:09.40,0:04:11.37,Default,,0000,0000,0000,,What this evidence says is basically, if you
Dialogue: 0,0:04:11.37,0:04:13.50,Default,,0000,0000,0000,,give me a reduction of a very particular form.
Dialogue: 0,0:04:13.50,0:04:16.07,Default,,0000,0000,0000,,In other words, if your reduction is what's called algebraic,
Dialogue: 0,0:04:16.07,0:04:18.51,Default,,0000,0000,0000,,(I am not going to explain what that means here.)
Dialogue: 0,0:04:18.51,0:04:23.09,Default,,0000,0000,0000,,That is, if given a cube root oracle, you could actually show me an algorithm
Dialogue: 0,0:04:23.09,0:04:26.06,Default,,0000,0000,0000,,that would then factor. That reduction, by itself,
Dialogue: 0,0:04:26.06,0:04:28.55,Default,,0000,0000,0000,,would actually imply a factoring algorithm.
Dialogue: 0,0:04:28.55,0:04:31.08,Default,,0000,0000,0000,,Okay so, that would say that if factoring is hard,
Dialogue: 0,0:04:31.08,0:04:33.64,Default,,0000,0000,0000,,a reduction actually doesn't exist.
Dialogue: 0,0:04:33.64,0:04:35.54,Default,,0000,0000,0000,,But, as I say this is very weak evidence.
Dialogue: 0,0:04:35.54,0:04:37.62,Default,,0000,0000,0000,,Because, who is to say that the reduction needs to be algebraic.
Dialogue: 0,0:04:37.62,0:04:39.72,Default,,0000,0000,0000,,Maybe, there are some other types of reductions that
Dialogue: 0,0:04:39.72,0:04:42.86,Default,,0000,0000,0000,,we haven't really considered. So, I would
Dialogue: 0,0:04:42.86,0:04:44.34,Default,,0000,0000,0000,,encourage you to think a little bit about this
Dialogue: 0,0:04:44.34,0:04:46.24,Default,,0000,0000,0000,,question. It's actually quite interesting.
Dialogue: 0,0:04:46.24,0:04:50.09,Default,,0000,0000,0000,,How would you use a cube root algorithm to factor the modulus?
Dialogue: 0,0:04:51.31,0:04:54.14,Default,,0000,0000,0000,,But as I said, as far as we know, RSA is a one way function.
Dialogue: 0,0:04:54.14,0:05:00.27,Default,,0000,0000,0000,,In fact, breaking RSA, computing e'th roots that is, actually requires factoring the modulus.
Dialogue: 0,0:05:00.27,0:05:02.92,Default,,0000,0000,0000,,We all believe that's true, and that's the state of the art.
Dialogue: 0,0:05:02.92,0:05:07.64,Default,,0000,0000,0000,,But, now there has been a lot of work on trying to improve the performance of RSA.
Dialogue: 0,0:05:07.64,0:05:12.04,Default,,0000,0000,0000,,Either, RSA encryption or improve the performance of RSA decryption.
Dialogue: 0,0:05:12.04,0:05:14.90,Default,,0000,0000,0000,,And it turns out, there has been a number of false starts in this direction.
Dialogue: 0,0:05:14.90,0:05:18.80,Default,,0000,0000,0000,,So I want to show you, this wonderful example as a warning.
Dialogue: 0,0:05:18.80,0:05:23.23,Default,,0000,0000,0000,,So basically, this is an example of how not to improve the perfomance of RSA.
Dialogue: 0,0:05:23.23,0:05:26.77,Default,,0000,0000,0000,,So, you might think that if I wanted to speed up RSA decryption,
Dialogue: 0,0:05:26.77,0:05:28.58,Default,,0000,0000,0000,,remember decryption is done by raising the
Dialogue: 0,0:05:28.58,0:05:30.90,Default,,0000,0000,0000,,ciphertext to the power of d. And, you remember
Dialogue: 0,0:05:30.90,0:05:34.26,Default,,0000,0000,0000,,that the exponentiation algorithm ran in linear
Dialogue: 0,0:05:34.26,0:05:37.77,Default,,0000,0000,0000,,time in the size of d. Linear time in log of d.
Dialogue: 0,0:05:37.77,0:05:39.76,Default,,0000,0000,0000,,So, you might think to yourself, well if I wanted
Dialogue: 0,0:05:39.76,0:05:43.52,Default,,0000,0000,0000,,to speed up RSA decryption, why don't I just use a small d.
Dialogue: 0,0:05:43.52,0:05:48.26,Default,,0000,0000,0000,,I'll say, I'll say a decryption exponent that's on the order of 2 to the 128.
Dialogue: 0,0:05:48.42,0:05:52.35,Default,,0000,0000,0000,,So it's clearly big enough so that exhaustive search against d is not possible.
Dialogue: 0,0:05:52.35,0:05:57.42,Default,,0000,0000,0000,,But normally, the decryption exponent d would be as big as the modulus, say 2000 bits.
Dialogue: 0,0:05:57.42,0:06:04.67,Default,,0000,0000,0000,,By using d that's only 128 bits, I basically speed up RSA decryption by a factor of 20.
Dialogue: 0,0:06:04.67,0:06:07.53,Default,,0000,0000,0000,,Right, I went down from 2000 bits to 100 bits.
Dialogue: 0,0:06:07.53,0:06:10.92,Default,,0000,0000,0000,,So, exponentiation would run 20 times as fast.
Dialogue: 0,0:06:10.92,0:06:15.44,Default,,0000,0000,0000,,It turns out this is a terrible idea. Terrible, terrible idea, in the following sense.
Dialogue: 0,0:06:15.44,0:06:18.64,Default,,0000,0000,0000,,There is an attack by Michael Wiener that shows that, in fact,
Dialogue: 0,0:06:18.64,0:06:23.42,Default,,0000,0000,0000,,as soon as the private exponent d is less than the fourth root of the modulus.
Dialogue: 0,0:06:23.42,0:06:27.53,Default,,0000,0000,0000,,Let's see, if the modulus is around 2048 bits
Dialogue: 0,0:06:27.53,0:06:34.58,Default,,0000,0000,0000,,that means that if d is less that 2 to the 512, then RSA is completely, completely insecure.
Dialogue: 0,0:06:34.58,0:06:37.51,Default,,0000,0000,0000,,And, this is, it's insecure in the worst possible way.
Dialogue: 0,0:06:37.51,0:06:43.13,Default,,0000,0000,0000,,Namely, just given a public key and an e, you can very quickly recover the private key d.
Dialogue: 0,0:06:44.23,0:06:48.49,Default,,0000,0000,0000,,Well, so some folks said: well this attack works up to 512 bits.
Dialogue: 0,0:06:48.49,0:06:52.38,Default,,0000,0000,0000,,So, why don´t we make the modulus, say, you know 530 bits.
Dialogue: 0,0:06:52.38,0:06:54.23,Default,,0000,0000,0000,,Then, this attack actually wouldn't apply.
Dialogue: 0,0:06:54.23,0:06:57.54,Default,,0000,0000,0000,,But still, we get to speed up RSA decryption by a factor of 4,
Dialogue: 0,0:06:57.54,0:07:01.100,Default,,0000,0000,0000,,because we shrunk the exponent from 2000 bits to, say, 530 bits.
Dialogue: 0,0:07:01.100,0:07:03.98,Default,,0000,0000,0000,,Well it turns out, even that is not secure. In fact,
Dialogue: 0,0:07:03.98,0:07:06.24,Default,,0000,0000,0000,,there is an extension to Wiener's attack, that's actually much
Dialogue: 0,0:07:06.24,0:07:08.18,Default,,0000,0000,0000,,more complicated, that shows that if d
Dialogue: 0,0:07:08.18,0:07:13.23,Default,,0000,0000,0000,,is less than N to the 0.292, then also RSA is insecure.
Dialogue: 0,0:07:13.23,0:07:16.67,Default,,0000,0000,0000,,And in fact, the conjecture that this is true up to N to the 0.5.
Dialogue: 0,0:07:16.67,0:07:21.98,Default,,0000,0000,0000,,So even if d is like N to the 0.4999, RSA should still be insecure,
Dialogue: 0,0:07:21.98,0:07:25.78,Default,,0000,0000,0000,,although this is an open problem. It's again, a wonderful open problem,
Dialogue: 0,0:07:25.78,0:07:28.39,Default,,0000,0000,0000,,It's been open for like, what is it, 14 years now.
Dialogue: 0,0:07:28.39,0:07:31.56,Default,,0000,0000,0000,,And, nobody can progress beyond this 0.292.
Dialogue: 0,0:07:31.56,0:07:34.33,Default,,0000,0000,0000,,Somehow, it seems kind of strange, why would 0.292
Dialogue: 0,0:07:34.33,0:07:38.22,Default,,0000,0000,0000,,be the right answer and yet no one can go beyond 0.292.
Dialogue: 0,0:07:38.80,0:07:41.67,Default,,0000,0000,0000,,So, just to be precise, when I say that RSA is insecure,
Dialogue: 0,0:07:41.67,0:07:45.22,Default,,0000,0000,0000,,what I mean is just given the public key N and e,
Dialogue: 0,0:07:45.22,0:07:48.08,Default,,0000,0000,0000,,your goal is to recover the secret key d.
Dialogue: 0,0:07:49.10,0:07:52.26,Default,,0000,0000,0000,,If you are curious where 0.292 comes from,
Dialogue: 0,0:07:52.26,0:07:56.31,Default,,0000,0000,0000,,I'll tell you that what it is, it's basically 1 minus 1 over square root of 2.
Dialogue: 0,0:07:56.31,0:07:58.50,Default,,0000,0000,0000,,Now how could this possibly be the right answer to this problem?
Dialogue: 0,0:07:58.50,0:08:01.30,Default,,0000,0000,0000,,It's much more natural that the answer is N to the 0.5.
Dialogue: 0,0:08:01.30,0:08:04.34,Default,,0000,0000,0000,,But this is still an open problem. Again if you want to think about that,
Dialogue: 0,0:08:04.34,0:08:06.16,Default,,0000,0000,0000,,it's kind of a fun problem to work on.
Dialogue: 0,0:08:06.16,0:08:10.10,Default,,0000,0000,0000,,So the lesson in this is that one should not enforce any structure on d
Dialogue: 0,0:08:10.10,0:08:12.48,Default,,0000,0000,0000,,for improving the performance of RSA, and in fact
Dialogue: 0,0:08:12.48,0:08:15.28,Default,,0000,0000,0000,,now there's a slew of results like this that show
Dialogue: 0,0:08:15.28,0:08:19.71,Default,,0000,0000,0000,,that basically, any kind of tricks like this to try and improve RSA's performance
Dialogue: 0,0:08:19.71,0:08:24.28,Default,,0000,0000,0000,,is going to end up in disaster. So this is not the right way to improve RSA's performance.
Dialogue: 0,0:08:24.28,0:08:27.99,Default,,0000,0000,0000,,Initially I wasn't going to cover the details of Wiener's attack.
Dialogue: 0,0:08:27.99,0:08:31.58,Default,,0000,0000,0000,,But given the discussions in the class, I think some of you would enjoy seeing the details.
Dialogue: 0,0:08:31.58,0:08:35.23,Default,,0000,0000,0000,,All it involves is just manipulating some inequalities.
Dialogue: 0,0:08:35.23,0:08:37.74,Default,,0000,0000,0000,,If you're not comfortable with that, feel free to skip over this slide,
Dialogue: 0,0:08:37.74,0:08:40.98,Default,,0000,0000,0000,,although I think many of you would actually enjoy seeing the details.
Dialogue: 0,0:08:40.98,0:08:43.36,Default,,0000,0000,0000,,So let me remind you in Wiener's attack basically
Dialogue: 0,0:08:43.36,0:08:46.89,Default,,0000,0000,0000,,we're given the modulus and the RSA exponent N and e,
Dialogue: 0,0:08:46.89,0:08:50.51,Default,,0000,0000,0000,,and our goal is to recover d, the private exponent d,
Dialogue: 0,0:08:50.51,0:08:54.17,Default,,0000,0000,0000,,and all we know is that d is basically less than the fourth root of N.
Dialogue: 0,0:08:54.17,0:08:57.71,Default,,0000,0000,0000,,In fact, I'm going to assume that d is less than the fourth root of N divided by 3.
Dialogue: 0,0:08:57.71,0:09:02.37,Default,,0000,0000,0000,,This 3 doesn't really matter, but the dominating term here is that d is less than the 4th root of N.
Dialogue: 0,0:09:02.37,0:09:05.94,Default,,0000,0000,0000,,So let's see how to do it. So first of all, recall that
Dialogue: 0,0:09:05.94,0:09:09.14,Default,,0000,0000,0000,,because e and d are RSA public and private exponents,
Dialogue: 0,0:09:09.14,0:09:14.14,Default,,0000,0000,0000,,we know that e times d is 1 modulo phi(N). Well what does that mean?
Dialogue: 0,0:09:14.14,0:09:22.25,Default,,0000,0000,0000,,That means that there exists some integer k such that e times d is equal to k times phi(N) plus 1.
Dialogue: 0,0:09:22.25,0:09:26.28,Default,,0000,0000,0000,,Basically that's what it means for e times d to be 1 modulo phi(N).
Dialogue: 0,0:09:26.28,0:09:29.83,Default,,0000,0000,0000,,Basically some integer multiple of phi(N) plus 1.
Dialogue: 0,0:09:29.83,0:09:32.59,Default,,0000,0000,0000,,So now let's stare at this equation a little bit.
Dialogue: 0,0:09:32.59,0:09:35.83,Default,,0000,0000,0000,,And in fact this equation is the key equation in the attack.
Dialogue: 0,0:09:35.83,0:09:40.35,Default,,0000,0000,0000,,And what we're going to do is first of all divide both sides by d times phi(N).
Dialogue: 0,0:09:40.35,0:09:43.70,Default,,0000,0000,0000,,And in fact I'm going to move this term here to the left.
Dialogue: 0,0:09:43.70,0:09:47.45,Default,,0000,0000,0000,,So after I divide by d times phi(N), what I get is that
Dialogue: 0,0:09:47.45,0:09:58.50,Default,,0000,0000,0000,,e divided by phi(N) minus k divided by d is equal to 1 over d times phi(N).
Dialogue: 0,0:09:59.47,0:10:02.90,Default,,0000,0000,0000,,Okay, so all I did is I just divided by d times phi(N)
Dialogue: 0,0:10:02.90,0:10:05.85,Default,,0000,0000,0000,,and I moved the k times phi(N) term to the left-hand side.
Dialogue: 0,0:10:05.85,0:10:09.12,Default,,0000,0000,0000,,Now, just for the heck of it I'm going to add absolute values here.
Dialogue: 0,0:10:09.12,0:10:13.48,Default,,0000,0000,0000,,These will become useful in just a minute, but of course they don't change this equality at all.
Dialogue: 0,0:10:13.48,0:10:20.18,Default,,0000,0000,0000,,Now, phi(N) of course is almost N; phi(N) is very, very close to N, as we said earlier.
Dialogue: 0,0:10:20.18,0:10:23.37,Default,,0000,0000,0000,,And all I'm going to need then for this fraction is just to say that
Dialogue: 0,0:10:23.37,0:10:26.64,Default,,0000,0000,0000,,it's less than 1 over square root of N. It's actually much, much smaller
Dialogue: 0,0:10:26.64,0:10:30.57,Default,,0000,0000,0000,,than 1 over square root of N, it's actually on the order of 1 over N or even more than that,
Dialogue: 0,0:10:30.57,0:10:35.64,Default,,0000,0000,0000,,but for our purposes all we need is that this fraction is less than 1 over square root of N.
Dialogue: 0,0:10:35.64,0:10:37.94,Default,,0000,0000,0000,,Now let's stare at this fraction for just a minute.
Dialogue: 0,0:10:37.94,0:10:44.51,Default,,0000,0000,0000,,You realize that this fraction on the left here is a fraction that we don't actually know.
Dialogue: 0,0:10:44.51,0:10:49.04,Default,,0000,0000,0000,,We know e, but we don't know phi(N), and as a result we don't know e over phi(N).
Dialogue: 0,0:10:49.04,0:10:53.63,Default,,0000,0000,0000,,But we have a good approximation to e over phi(N). Namely we know that phi(N)
Dialogue: 0,0:10:53.63,0:10:59.24,Default,,0000,0000,0000,,is very close to N. Therefore e over phi(N) is very close to e over N.
Dialogue: 0,0:10:59.24,0:11:03.44,Default,,0000,0000,0000,,So we have a good approximation to this left-hand side fraction, namely e over N.
Dialogue: 0,0:11:03.44,0:11:06.03,Default,,0000,0000,0000,,What we really want is the right-hand side fraction,
Dialogue: 0,0:11:06.03,0:11:07.65,Default,,0000,0000,0000,,because once we get the right-hand side fraction,
Dialogue: 0,0:11:07.65,0:11:12.96,Default,,0000,0000,0000,,basically that's going to involve d, and then we'll be able to recover d. Okay, so let's see
Dialogue: 0,0:11:12.96,0:11:19.04,Default,,0000,0000,0000,,if we replace e over phi(N) by e over N, let's see what kind of error we're going to get.
Dialogue: 0,0:11:19.04,0:11:22.51,Default,,0000,0000,0000,,So to analyze that, what we'll do is first of all remind ourselves
Dialogue: 0,0:11:22.51,0:11:26.20,Default,,0000,0000,0000,,that phi(N) is basically N - p - q + 1,
Dialogue: 0,0:11:26.20,0:11:30.80,Default,,0000,0000,0000,,which means that N minus phi(N) is going to be less than p + q.
Dialogue: 0,0:11:30.80,0:11:34.75,Default,,0000,0000,0000,,Actually I should, to be precise I should really write p + q + 1, but you know,
Dialogue: 0,0:11:34.75,0:11:37.84,Default,,0000,0000,0000,,who cares about this 1, it's not, it doesn't really affect anything.
Dialogue: 0,0:11:37.84,0:11:40.24,Default,,0000,0000,0000,,So I'm just going to ignore it for simplicity.
Dialogue: 0,0:11:40.24,0:11:45.51,Default,,0000,0000,0000,,Okay, so N - phi(N) is less than p + q. Both p and q are roughly half the length of N,
Dialogue: 0,0:11:45.51,0:11:48.92,Default,,0000,0000,0000,,so you know, they're both kind of on the order of square root of N,
Dialogue: 0,0:11:48.92,0:11:53.88,Default,,0000,0000,0000,,so basically p + q we'll say is less than 3 times square root of N.
Dialogue: 0,0:11:53.88,0:11:56.84,Default,,0000,0000,0000,,Okay, so we're going to use this inequality in just a minute.
Dialogue: 0,0:11:56.84,0:12:00.24,Default,,0000,0000,0000,,But now we're going to start using the fact that we know something about d,
Dialogue: 0,0:12:00.24,0:12:02.96,Default,,0000,0000,0000,,namely that d is small. So if we look at this inequality here,
Dialogue: 0,0:12:02.96,0:12:05.54,Default,,0000,0000,0000,,d is less than the fourth root of N divided by 3.
Dialogue: 0,0:12:05.54,0:12:08.60,Default,,0000,0000,0000,,It's actually fairly easy to see that if I square both sides
Dialogue: 0,0:12:08.60,0:12:12.12,Default,,0000,0000,0000,,and I just manipulate things a little bit, it's [not] difficult to see that
Dialogue: 0,0:12:12.12,0:12:15.51,Default,,0000,0000,0000,,this directly implies the following relation,
Dialogue: 0,0:12:15.51,0:12:24.26,Default,,0000,0000,0000,,basically 1 over 2 d squared minus 1 over square root of N is greater than 3 over square root of N.
Dialogue: 0,0:12:24.26,0:12:28.54,Default,,0000,0000,0000,,As I said, this basically follows by squaring both sides, then taking the
Dialogue: 0,0:12:28.54,0:12:33.33,Default,,0000,0000,0000,,inverse of both sides, and then I guess multiplying one side by a half.
Dialogue: 0,0:12:33.33,0:12:37.91,Default,,0000,0000,0000,,Okay, so you can easily derive this relation, and we'll need this relation in just a minute.
Dialogue: 0,0:12:37.91,0:12:40.17,Default,,0000,0000,0000,,So now let's see, what we'd like to do is bound
Dialogue: 0,0:12:40.17,0:12:45.06,Default,,0000,0000,0000,,the difference of e over N and k over d. Well what do we know?
Dialogue: 0,0:12:45.06,0:12:47.87,Default,,0000,0000,0000,,By the triangular inequality, we know that this is equal to
Dialogue: 0,0:12:47.87,0:12:52.12,Default,,0000,0000,0000,,the distance between e over N and e over phi(N) plus
Dialogue: 0,0:12:52.12,0:12:56.57,Default,,0000,0000,0000,,the distance from e over phi(N) to k over d.
Dialogue: 0,0:12:56.57,0:13:01.81,Default,,0000,0000,0000,,This is just what's called a triangular inequality; this is just a property of absolute values.
Dialogue: 0,0:13:01.81,0:13:04.70,Default,,0000,0000,0000,,Now this absolute value here, we already know how to bound.
Dialogue: 0,0:13:04.70,0:13:07.12,Default,,0000,0000,0000,,If you think about it it's basically the bound that we've already derived.
Dialogue: 0,0:13:07.12,0:13:11.98,Default,,0000,0000,0000,,So we know that this absolute value here is basically less than 1 over square root of N.
Dialogue: 0,0:13:11.98,0:13:17.74,Default,,0000,0000,0000,,Now what do we know about this absolute value here? What is e over N minus e over phi(N)?
Dialogue: 0,0:13:17.74,0:13:20.49,Default,,0000,0000,0000,,Well let's do common denominators and see what we get.
Dialogue: 0,0:13:20.49,0:13:25.24,Default,,0000,0000,0000,,So the common denominator is going to be N times phi(N),
Dialogue: 0,0:13:25.24,0:13:31.25,Default,,0000,0000,0000,,and the numerator in this case is going to be e times phi(N) minus N.
Dialogue: 0,0:13:31.25,0:13:35.76,Default,,0000,0000,0000,,Which we know from this expression here is less than 3 times square root of N.
Dialogue: 0,0:13:35.76,0:13:40.84,Default,,0000,0000,0000,,So really what this numerator is going to be is e times 3 square root of N.
Dialogue: 0,0:13:40.84,0:13:44.33,Default,,0000,0000,0000,,The numerator is going to be less than e times 3 square root of N.
Dialogue: 0,0:13:44.33,0:13:51.25,Default,,0000,0000,0000,,So now I know that e is less than phi(N), so I know that e over phi(N) is less than 1.
Dialogue: 0,0:13:51.25,0:13:57.31,Default,,0000,0000,0000,,In other words, if I erase e and I erase phi(N) I've only made the fraction larger.
Dialogue: 0,0:13:57.31,0:14:00.02,Default,,0000,0000,0000,,Okay, so this initial absolute value is now going to be
Dialogue: 0,0:14:00.02,0:14:03.66,Default,,0000,0000,0000,,smaller than 3 square root of N over N, which is simply,
Dialogue: 0,0:14:03.66,0:14:09.24,Default,,0000,0000,0000,,3 square root of N over N is simply 3 over square root of N.
Dialogue: 0,0:14:09.24,0:14:11.27,Default,,0000,0000,0000,,Okay, but what do we know about 3 over square root of N?
Dialogue: 0,0:14:11.27,0:14:17.71,Default,,0000,0000,0000,,We know that it's less than 1 over 2 d squared minus 1 over square root of N.
Dialogue: 0,0:14:17.71,0:14:20.47,Default,,0000,0000,0000,,Okay, so that's the end of our derivation.
Dialogue: 0,0:14:20.47,0:14:26.44,Default,,0000,0000,0000,,So now we know that the first absolute value is less than 1 over 2 d squared minus square root of N.
Dialogue: 0,0:14:26.44,0:14:29.51,Default,,0000,0000,0000,,The second absolute value is less than 1 over square root of N.
Dialogue: 0,0:14:29.51,0:14:34.37,Default,,0000,0000,0000,,And therefore their sum is less than 1 over 2 d squared.
Dialogue: 0,0:14:34.37,0:14:36.58,Default,,0000,0000,0000,,And this is the expression that I want you to stare at.
Dialogue: 0,0:14:36.58,0:14:42.95,Default,,0000,0000,0000,,So here, let me circle it a little bit. So let me circle this part and this part.
Dialogue: 0,0:14:43.58,0:14:46.44,Default,,0000,0000,0000,,Now, so let's stare a little bit at this fraction here.
Dialogue: 0,0:14:46.44,0:14:51.44,Default,,0000,0000,0000,,And what we see is first of all, as before, now we know the value of e over N,
Dialogue: 0,0:14:51.44,0:14:54.82,Default,,0000,0000,0000,,and what we'd like to find out is the value k over d.
Dialogue: 0,0:14:54.82,0:14:56.86,Default,,0000,0000,0000,,But what do we know about this fraction k over d?
Dialogue: 0,0:14:56.86,0:15:00.72,Default,,0000,0000,0000,,We know somehow that the difference of these two fractions is really small;
Dialogue: 0,0:15:00.72,0:15:05.38,Default,,0000,0000,0000,,it's less than 1 over 2 d squared. Now this turns out to happen very infrequently,
Dialogue: 0,0:15:05.38,0:15:10.59,Default,,0000,0000,0000,,that k over d approximates e over N so well that
Dialogue: 0,0:15:10.59,0:15:15.31,Default,,0000,0000,0000,,the difference between the two is less than the square of the denominator of k over d.
Dialogue: 0,0:15:15.31,0:15:17.32,Default,,0000,0000,0000,,It turns out that that can't happen very often.
Dialogue: 0,0:15:17.32,0:15:22.34,Default,,0000,0000,0000,,It turns out that there are very few fractions of the form k over d that approximate another fraction
Dialogue: 0,0:15:22.34,0:15:26.42,Default,,0000,0000,0000,,so well that their difference is less than 1 over 2 d squared.
Dialogue: 0,0:15:26.42,0:15:30.31,Default,,0000,0000,0000,,And in fact the number of such fractions is going to be at most logarithmic in N.
Dialogue: 0,0:15:30.31,0:15:33.95,Default,,0000,0000,0000,,So now there's a continued fraction algorithm. It's a very famous fraction
Dialogue: 0,0:15:33.95,0:15:38.88,Default,,0000,0000,0000,,that basically what it will do is, from the fraction e over N,
Dialogue: 0,0:15:38.88,0:15:42.98,Default,,0000,0000,0000,,it will recover log(N) possible candidates for k over d.
Dialogue: 0,0:15:42.98,0:15:47.15,Default,,0000,0000,0000,,So we just try them all one by one until we find the correct k over d.
Dialogue: 0,0:15:47.15,0:15:51.64,Default,,0000,0000,0000,,And then we're done. We're done, because we know that,
Dialogue: 0,0:15:51.64,0:15:55.38,Default,,0000,0000,0000,,well e times d is 1 mod k, therefore d is relatively prime to k,
Dialogue: 0,0:15:55.38,0:16:00.85,Default,,0000,0000,0000,,so if we just represent k over d as a rational fraction, you know, numerator by denominator,
Dialogue: 0,0:16:00.85,0:16:05.27,Default,,0000,0000,0000,,the denominator must be d. And so we've just recovered, you know,
Dialogue: 0,0:16:05.27,0:16:10.36,Default,,0000,0000,0000,,we've tried all possible log(N) fractions that approximate e over N so well
Dialogue: 0,0:16:10.36,0:16:13.69,Default,,0000,0000,0000,,that the difference is less than 1 over 2 d squared.
Dialogue: 0,0:16:13.69,0:16:19.34,Default,,0000,0000,0000,,And then we just look at the denominator of all those fractions, and one of those denominators must be d.
Dialogue: 0,0:16:19.34,0:16:22.84,Default,,0000,0000,0000,,And then we're done; we've just recovered the private key.
Dialogue: 0,0:16:22.84,0:16:26.34,Default,,0000,0000,0000,,So this is a pretty cute attack. And it shows basically how,
Dialogue: 0,0:16:26.34,0:16:31.27,Default,,0000,0000,0000,,if the private exponent is small, smaller than the fourth root of N,
Dialogue: 0,0:16:31.27,0:16:35.35,Default,,0000,0000,0000,,then we can recover d completely, quite easily. Okay, so I'll stop here.