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.