This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Number Theory One
Loading...
Del curso dictado por University of Maryland, College Park
Cryptography
423 calificaciones
Conoce a los instructores
Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center
Maryland Cybersecurity Center
[SOUND] In this lecture we're going to begin our treatment of number theory.
Now you might actually be surprised that until this point in the class we
haven't had to rely on or to learn any number theory.
And the reason you might find that surprising is because my impression is
that when people think about cryptography popularly,
the first thing that comes to their mind is exactly the number theory.
That's kind of the quote, un-quote sexy part of cryptography.
However as we've seen in this class so far number theory is not really needed for
a lot of important cryptographic applications.
And in particular, all of practical private key cryptography is based on
things like stream ciphers, block ciphers, and hash functions, that can be
constructed analyzed, and reasoned about, without any mention of any number theory.
And so I think the point here is that number theory, is, of course, going to be
needed, for public key cryptography, but it's not needed for all of cryptography.
There's a lot of interesting things you can do without any number theory at all.
Having said that of course, it turns out that some kind of
number theory does seem to be inherent for any sort of public cryptography.
Now we haven't talked about public-key world cryptography yet.
We won't talk about it until next week, but this is just sort of a primer for
what we're going to need in that setting.
The point of this week is to really cover the basics of number theory, very quickly.
That is, the goal here is not to give a survey of number theory.
It's certainly not to give a comprehensive course on number theory.
But only to present the bare minimum that we need for
the applications that we're going to study.
And for that reason I'm not going to focus particularly on the proofs of a lot of
un-underlying concepts and results unless I
think that the proof sheds some insight on understanding what's going on.
For those that were interested I can recommend several textbooks that can be
used to supplement the material and
in particular a lot of what we cover here with appropriate proofs.
And also some additional details is available in the Cat Lyndel text book.
What we're going to talk about in this lecture is algorithmic number theory.
And this is actually interesting because very often from a mathematical point of
view or from a mathematician's point of view I should say,
they're interested in the existence of numbers with certain properties, or
in proving that some number has a particular property.
But there are very often less interested in the algorithmic efficiency of
determining whether or not some number has a given property.
In our setting, the computer scientist setting where we're
going to ultimately be interested in implementing cryptography.
We do have to also take care to think about the algorithmic
complexity of determining various properties of numbers, and
of computing various interesting things about those numbers.
And ultimately, if you're interested in particular in implementing very
fast cryptography, a good understanding of
these kind of algorithmic considerations is very important.
Now one thing that's important to stress,
is that when we talk about the efficiency of number theoretic operations,
we're always going to be interested in asymptotic complexity, of course.
But the asymptotic complexity will be measured in
terms of the length of the input.
That's always true throughout computer science but
it's important to stress it here because it's very often easy to
get confused between the magnitude of an input and it's length.
And in particular if we have some input integer A then
the magnitude of A is itself.
If A is equal to 1000 then the magnitude of A is 1000.
But the length of that input,
the length of A, is the length of the binary representation of A.
And I'm going to denote that by these two vertical bars surrounding the integers.
So, it's sort of like an extended absolute value sign.
So we have these the length of A.
The binary representation of a, and
the binary representation of an integer is the log of the magnitude of the integer.
Right, the number of bits that you need in order to represent some number,
is the logarithm of that number's magnitude, and conversely,
the magnitude of a number is exponential in its length.
And again it's very easy to get these concepts confused when thinking about
algorithms but we're going to try very carefully to keep them separate.
Now in terms of our study of algorithmic number theory, we're not going to
dwell extensively on different algorithms for different computational problems.
There's a lot of interesting things to be done there, and as I said it is
very important when it comes to efficient implementation of cryptography.
But for our purposes what we only want to do, is to
be able to distinguish between problems that are easy and problems that are hard.
Where for us, easy means that it can be solved in polynomial time.
And hard, at least for
now, is going to mean that it can't be solved in polynomial time.
And so beyond making that kind of a very gross distinction we're not going to
be extremely interested in fine tuning the, algorithms that we give or
that we discuss, or, the problems we consider.
And again, there are several textbooks you can use to supplement the material.
Several references you can use if you're ever implementing cryptography and
want to find out about the most efficient algorithms for some problem.
Before I jump in, I want to just review some notation,
regarding modular arithmetic, some of which is a bit idiosyncratic.
By a bracket a mod N,
I'm going to mean the remainder of the integer a when divided by the integer N.
So this means you just take, a divided by N.
You compute some quotient, which here we don't care about.
And you take the remainder.
And note, of course, that bracket A mod N,
has to lie strictly between 0 and N minus 1.
I want to contrast that with the more standard notation that you might be
familiar with, namely that A ie equal to B mod N.
So A being equal to B mod N means exactly that A and
B have the same remainder modulo N.
But, the point is that the notation on the left,
A equals B mod N, is different from the notation a mod N inside the brackets.
Because again, A equals B mod N is expressing something about
the relationship between two integers.
And A mod N inside the brackets refers to a specific integer in the range of
0 to N minus1, which is the remainder of A when divided by N.
Okay. [SOUND] So
let's jump in with a our discussion of algori, algorithmic number
theory by just briefly noting some basic facts about what can be done efficiently.
So if we look at different standard arithmetic operations,
we can see that their's actually can be done efficiently.
So integer addition for
example, can be done efficiently using the standard grade school algorithm.
And if you think about how that works, you'll see that it runs in time,
essentially linear, in the length of the inputs and the same for subtraction.
Multiplication can also be done using a grade school algorithm.
The running time now is quadratic rather than liner.
And I'll mention that better algorithms are known, but, again, for
our purposes, we're just going to be happy with the grade school algorithm because it
does run in polynomial time.
A little bit more difficult to see, but perhaps not very surprising,
is that division with remainder, can be done efficiently.
And this in particular means that we can compute bracket A mod N
efficiently by just performing the divisions and taking the remainder.
For that reason similarly, we can do modular addition,
subtraction, multiplication, and reduction efficiently as well.
So for example, modular multiplication, would just mean that we have two integers.
We want to compute their product, modulus if any N, modulus N if any.
[COUGH] And what we can do there is to simply perform the multiplication over
the integers and then reduce mod N.
And because of those component operations can be
done efficiently we know that the entire computation can be done efficiently.
What about a more complicated operation, in particular, modular exponentiation?
And I focus here on modular exponentiation really for two reasons.
First is that it's an important computation that's going to be
used all the time in cryptography, and second,
because I think it gives a very good illustration of a non trivial algorithm.
That is one where the naive algorithm as we'll see does not run in polynomial time,
but with a little bit of cleverness you can come up with an algorithm that
does run in polynomial time.
So lets look at the problem of exponentiation.
First of all think about exponentiation over the integers.
So here's there's no modular reduction.
Let's say we want to compute A to the B, all right, the integer A to the Bth power.
Well, let's first consider the size of the result.
So the number of bits that we need to specify the result,
A to the B, is going to be the order of the logarithm of that,
which is the order of the magnitude of B, times the length of A.
And what you can see, here, is just writing down the answer
can require exponential time, exponential in B, that is.
Because the running time, sorry the, the number of bits we need to specify
the answer, is going to be linear in the magnitude of B, rather than length of B.
So we don't really have any hope of computing integer exponentiation in
polynomial time.
Fortunately in cryptography we never need to compute integer exponentiation,
what we do need instead is modular exponentiation, where we're interested in
computing the result of A to the B modulo sum, given modulus N.
And note here we don't run into the problem we had before,
because the size of the answer here is going to have to be at most the size of N,
because the answer has to lie in the interval 0 to N minus 1.
So how do we do it?
Well the first thing to observe is that a strategy that will not work.
If the compute a to the b over the integers.
And then reduce the result mod N.
That won't work because as we just noted, the the length of the intermediate result,
A to the B over the integers cannot even be written down in polynomial space.
So, that's not the approach we're going to want to use.
Let's consider a, maybe a naive algorithm that we would want to use for
computing modular exponentiation.
So here, I'm just writing a simple function that takes three arguments, A, B,
and N and is meant to compute the result, A to the B, mod N.
And we'll assume that B is greater than or equal to 0.
We won't worry about negative exponents, for now.
They can be handled but it's not important for our purposes.
So one natural approach is to just start off with a variable called ans that's
going to hold the answer, initialize that to 1.
And then for I ranging from 1 to B, what we'll do is we'll simply multiply
the current value of the answer by A and then reduce mod N.
So this of course is not valid C code.
This is meant to just be pseudo code.
But what I've indicated here is that we just multiply a into the current answer
and then increment B.
And we're going to avoid the problem that we had on the previous slide.
Of first computing A to the B and then reducing modular N.
Because you'll notice here that we're reducing modular N at every step.
So every time we multiply, we're going to then reduce.
And so the value of Ns at any point during the computation,
is going to be strictly in the range of 0 to N minus 1.
So we do this for a total of B iterations of the loop, and
then we return the answer.
This will indeed give the right result, but
what's the running time of the algorithm?
Well, it's easy to see here that the inner loop is going to be running for
a total of B times.
And that is not, efficient.
That is not polynomial time.
Because we would like an algorithm that runs in time polynomial in the length of B
not in the magnitude of B.
And again here we have a loop running for a number of steps linear in
the magnitude of B, so this is not going to qualify as an efficient algorithm.
What kind of approach could we use to get a more efficient algorithm,
to get in particular a polynomial kind of algorithm?
Well it's easiest to think about the problem if we assume for
simplicity that B is a power of 2.
So let's say that B equals 2 to the K for some integer K.
If you kind of unwrap the proceeding algorithm or
maybe just view it in a different way.
You can see that the preceding algorithm roughly corresponds to
performing B multiplications of A.
That is, to computing A times A, times A again, times A again, et cetera, for
A total of 2 to the K minus 1 multiplications.
But a better way to do the computation.
Would be to first square A, right to just compute A times A,
take that result and square it again.
Take that and square that, and keep going until you've done a total of K squarings.
Or K minus 1 squarings I guess.
So, that would give a much better algorithm.
Then the former one because we have k
squarings versus two to the k minus one multiplications.
And again, the important thing to note here is that k is order of log of B,
which means that K is order of the length of B.
So what we have here in the second case is an algorithm that's running in
time linear, in the length of B.
So of course this only works when B is a power of two.
But as we'll see in the next slide we can modify this approach even when B
is not a power of 2.
So here is the algorithm.
So again we're going to have an algorithm taking as input A, B, and N.
And we're going to again assume that B is greater than or equal to 0.
What we'll do here is to initialize two variables.
One called X and one called T.
We'll initialize X to a and T to 1.
And then while B is greater than 0 we do the following.
So first of all we check if B is odd.
If B is odd we then compute a within a set T equal to T times X mod N.
And we reduce B by 1.
Then we compute X equals X squared And B is equal to B divided by 2.
So note that in this point the algorithm must be even because if it
were odd at the beginning of the loop then in the previous step we checked that it
was odd and so we subtracted 1.
We keep doing this as long as B is greater than 0, and then finally return t.
Now it's a bit difficult, perhaps, to be convinced that this is working.
But you can prove that the algorithm works by looking at, or
by showing that the algorithm satisfies the following invariant.
And the invariant is, that the answer, the correct answer that you're looking for
is always equal to T times X to the B amount N.
And that's certainly true at the beginning of the algorithm when we
initialized the variables because then X is equal to A and T is equal to 1.
And indeed A to the B amount N is exactly the answer we're looking for.
And then you can check throughout the loop.
That if B is even for example,
then what we end up doing is squaring the value of X and reducing B in half.
And so X to the b mod N, or t times x to the b mod N,
is of course equal to T to the X squared, to the B over 2 mod N.
Just algebra.
And similarly, if B is odd, we then shift a factor of X into T, and reduce B by 1.
And you can write down on paper and easily verify that the invariant is satisfied.
At the end of the algorithm, B is equal to 0, and
so the correct answer is given by exactly T.
And T is a value that we return.
What's the running time here?
Well the important thing to note is that in every execution of the inner loop.
The value of B is decreased by at least half.
And that means that the number of iterations of the inner loop is going to
be 0 of log B, which is linear in the length of B.
In each iteration of the inner loop,
we perform some computation that can be done in time polynomial, in, A, B and N.
And so without getting into too much of a fine grained analysis we can see that
the overall running time of the algorithm is indeed polynomial in the length
of it's three inputs.
In the next lecture we'll spend some more time on modular arithmetic.
And we'll also introduce the very important notion of an abstract group
that will allow us to think in a more clean away about various of
the manipulations that we're going to be doing and
that we're going to use for crypt, for cryptography.
See you next time.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
