I want to talk about NSA surveillance that's been in the news lately; but most people don't know how they do it, how they actually do it - how can they read our emails? How can they sort of eavesdrop? Well it turns out it's based on very sophisticated math and some super long and super big numbers; and I'm going to show you some of those numbers. That sound good?
- (Brady: Yeah, we love numbers!) Well I have to set it up a little bit. I want to talk a little bit about something, you know, which we use in our everyday life - the clock. So let's say you start you start working
at 9:00 in the morning, okay, and you work
for five hours - when do you finish?
(You finish at 2.) Okay, but if you- you know if you were to calculate 9 plus 5 you get 14. Why do we say 2:00 p.m. and not 14? That's because 14 is 12 plus 2. So when we get a result like 14, which is larger than 12, then we sort of just take the remainder. This is called clock arithmetic, and also in mathematics we call it modular arithmetic because we say that 9 plus 5 is 2 modulo 12. Modulo just means that we retain the remainder. So likewise we can imagine a clock which doesn't have 12 hours but has any other whole number as the number of hours. For example could be 10 hours, could be 5 hours, could be you know 5368 hours. But actually in mathematics the best clocks are the ones in which the number of hours is a prime number. It turns out that actually there are some really sophisticated things about this arithmetic. But of course the sophistication you can can only feel when that number of hours becomes larger. If it's all modulo 7, modulo 12, there isn't so much room to create something complicated that we could use in encryption say; but if that number is zillions of zillions of zillions you know then that that opens up the opportunity to do something that other people cannot crack. For example when we send our credit card number online or we send an email it gets scrambled and then gets unscrambled at the endpoint; that is based on this kind of arithmetic, arithmetic with some very large prime number of hours. And I'll show you what the actual numbers involved in a bit. But let me explain a little bit more about what these algorithms are based on. So first well they're based on this clock arithmetic as we already- we already understand that, and there is one more layer which is that we also look at equations, at an equation with two variables. The kind of equations that go into the algorithms that NSA was able to crack have to do with what mathematicians call elliptic curves. So an elliptic curve is something which is defined by an equation like this: y squared equals x cubed minus 3x plus 5. So that's an equation with two variables, x and y. To solve this equation means to find two numbers x and y such that the left-hand side is equal to the right hand side. But there is a crucial element - where exactly do we look for solutions? There are many options. Of course the obvious choice would be to look for solutions say in real numbers. And then this will actually give us a curve which will look something like this. You know, every point here will have two coordinates x and y and if you plug them into this equation left hand side will equal to the right hand side. So that's the most obvious way to think of solutions being armed with this new arithmetic, the clock arithmetic. We can also look for solutions modulo some prime number right? Nothing can stop us from doing that. So for example we can choose x and y to be elements of this set of possible hours on this seven hour clock and we can try to look for pairs x and y such that the left-hand side is equal to the right hand side. So this way we get something like- think of this as sort of like a sub- so maybe some points on this kind of curve.
- (So there are less solutions?) There are fewer solutions for sure because- well to begin with x and y can only take values from 1 to 7. We can sort of think of them as some special points on this curve. And of course if you take a very large prime number then there will be more many more solutions that if you take a small one like 7. And there is a whole industry in mathematics which is called elliptic curve cryptography. And elliptic curve cryptography has to do with using these solutions to scramble and unscramble messages when when they are transmitted. There are some standards in this area which were set by by National Institute of Standards and
Technology which is a body in the United States which is responsible for these kind of things, it came up with the standards. And in fact you can you can read this, it's all public knowledge this was not classified. Here is the algorithm which is called this dual- dual elliptic curve deterministic random bits generator. So you see the elliptic curve is prominently featured here and this is the equation! It's exactly the equation that I wrote-
- (It's a very simple equation.) It's a very simple equation but you have to pick a prime number.
In this document they actually give you details, they provide you this number p; so see this is the first large number. It gives you the largest clock that you've ever seen - look how many digits there are.
- (So that's the- that's the clock) (they're using in on their curve?)
- That's right, so on their curve, on this- on their equation they're using this many hours. Okay so so in the- their day has many more hours than we're used to in some sense right? And then then there are some additional is some additional data that have to be used in this algorithm. And so you use this data and as a result you create something which produces numbers that look totally random. Those numbers themselves do not live on the curve but the curve is used to produce them. It's actually very important problem in mathematics to produce numbers that look completely random. So this by itself is not an encryption algorithm, it's not used to encrypt a specific email or a specific credit card number, but rather it produces something based on which other algorithms which would actually be encrypting your emails or your credit card numbers, it'll be based on that. That's a flowchart which generates random numbers. You start with something and there's sort of like a loop which creates more and more and more numbers and then they get scrambled and then the output is some number from which you just extract bits. And the way it's set up it should be so that they are completely random. In other words if somebody reads those numbers they cannot predict what's the next numbers coming out. So in addition to this equation itself, in addition to the prime number which is given, what makes this work is a pair of solutions.
- (You need this to) (kickstart things do you?)
- That's right, to kickstart and then to keep going. P is used to run the cycle, to produce the next one and next one the next one and Q is used to kind of scramble the output of that cycle; so that in theory nobody would be able to predict what's what's- you know the next one. Think of these solutions as being some points on a curve. And this, by the way, it's very difficult to find those solutions because the numbers involved are huge so it's not an easy task at all. But this government agency is sort of simplifying our life and they're saying 'look, you don't have to look for solutions yourself we'll give you the solutions, we'll give you those two points.' Okay? So here's P, maybe he's here, and Q is here; they just give you this. So these are the numbers actually there, you can see them here.
- (Oh this is our big money shot!) This is our big money shot: Px, Py, Qx, Qy. These are the numbers which the government says, these are the solutions and actually anybody can, this is public information, this public knowledge anybody can take this numbers and substitute into the equation and see that indeed the equation's satisfied. But they found this for you, okay, so now you- they suggest to use these two numbers to run the to run this number- random number generator.
- (If all of these companies used) (the same equation and the same numbers) (provided by the government and then) (started their
flowchart machine - weren't) (they all generating the exact same) (numbers?)
Good point - there is a seed, also you have to start with something, and that you can choose yourself and of course that's what will distinguish your sequence from other people's sequence. But they give you P and Q which are kind of like the the two steps which provide the information to run the steps of the procedure right? It's a multi- it's a multi-step procedure, it's a flowchart really. And to implement those steps you need those two points. And what is implicit here is a suggestion that these two are kind of random, P and Q are kind of random, that they are not- they don't bear any relation with each other. So it's almost like they give you two random villages in Australia and they say- and you're like you've never been to Australia so you you don't know you know where they are, what the distance between- between them is and you expect that no one else would know. It may not be such a good analogy because of course in case of villages in Australia you can easily find out what the distance is; but imagine something where actually it would be incredibly hard to find the relation between two numbers. But imagine that somebody actually knows what the relation is; and as now we find out, actually NSA apparently did know a relation. And then the point is that in that case there is a backdoor. That you can use that information, sort of the distance between the two villages in Australia you can use it to be able to predict the outcome of the algorithm. Once you know, you can observe it for some period of time and see what numbers are coming out, then you can actually find out what the next ones are going to be. And that sort of throws a whole sort of a monkey wrench in the whole procedure because then it gives you a way to peek into these other encryption algorithms which rely on this random number generator. And that's what happened.
- (What has the NSA got? What did) (they do that meant they were able to) (find the relation but spies from other) (countries or mathematicians like you) (can't do it? Or did they reverse-engineer) (it? Did they make the equation?)
- They reverse-engineered it, yes,
that's the point. And the the thing is it's very hard to find that relation if you don't already know it. And this is actually the basis of this whole- this whole idea of encryption based on clock arithmetic; that there are certain problems which when you do in clock arithmetic which are intractable, it would take years on even on a network of supercomputers to be able to find a solution.
- So in the video description is going to be a bunch of links you should have a look at. That's going to include documents that we discussed in this video, they're all public documents, a continuation of the discussion I had with the professor that didn't make it into this video and that covers a whole range of interesting topics like the people who actually foresaw that maybe this was a problem; why companies were spoon-fed this information; and also the importance of mathematics in the world these days - it's worth a look. And I'll also include a link to Professor Frenkel's book - this is it here, it's called 'Love and Math', it's really good, it's worth a look if you're into mathematics books - and you should be because you're watching Numberphile. And lastly thank you to everyone for your support through 2013 and watching Numberphile, it's been great fun making videos like this and hopefully there's going to be a lot more in 2014, cheers.
This is quite interesting. Can anyone recommend some good introductory level resources to learn cryptography?
Nice Vdeo - easy to understand even without any knowledge of mathematics!
I had this guy as a professor for Multivariable Calculus. Check out his "arthouse" movie, The Rites of Love and Math.
http://www.youtube.com/watch?v=MOzevd3XbAI
Ha! Who knew all that stuff we did on polynomial rings last semester had any real world applications.
The scariest thing..? It was all planned from the beginning.
Could we theoretically just use a different elliptic curve equation, find our own solutions for P and Q, use our own algorithm for generating pseudorandom numbers, and encrypt data in our own way that doesn't allow the NSA access to it?
I understand that this is a simplified version of what actually goes on, but it seems like enough study on elliptic curves might give a similar encryption technique that is completely shut off from NSA surveillance.
How many companies actually use these P and Q, thereby allowing NSA to spy on their clients? Do email providers like google and yahoo choose to use them? Or are they using it for the sake of compatibility with other... clients? I'm confused... It seems like they are capable of creating their P and Q. Or do they get incentive from the government to use what is provided by NIST.
so how does knowing the relationship with P,Q allow for a backdoor? Does the video imply that NSA only knows the relationship with P,Q that is given. Can't we just find another P,Q?
Jesus. How do we know the NSA hasn't got a backdoor to SHA-2?