This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.
Number Theory Three
Loading...
來自 University of Maryland, College Park 的課程
Cryptography
458 個評分
與講師見面
Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center
Maryland Cybersecurity Center
[SOUND] Up to now, in our discussion of number theory,
we've only considered number theoretic problems that are easy, i.e.,.
that can be solved in polynomial time.
But what's interesting to cryptographers is
that there are some problems that are conjectured to be hard, that is,
are conjectured to not be solvable in polynomial time.
And maybe the most basic and
the most well-known of these is the problem of factoring.
And we know of course that multiplying two numbers is easy.
We already talked about this in a previous lecture.
However, breaking a product into it's constituent factors appears to be hard.
That is, if we're given two integers x and
y, it's easy to compute their product x times y.
However, given the product, given the result x times y,
it appears to be difficult to find x and y.
Just as a way of comparison,
imagine if I gave you the problem of multiplying these two integers.
You could easily do that or you could find a program to do it for you,
or write a program yourself.
However, if I ask you instead to find the factors of this large number, well,
there's no immediate way to do that.
Of course in this particular case, the number is small enough that you could
find something find a program that would allow you to factor it.
But the point is that it's a much harder problem than multiplication is.
Of course we have to be a little bit careful.
It's not hard to factor all numbers.
If we pick a random number, for example.
Well, half the time that number will be even, and
it's easy to factor even numbers, right?
One of the factors of any even number is two, and we can easily divide by two and
find another factor.
So we can find two integers whose product is the number we're given.
And similarly, if we pick a random number,
then one third of the time the random number will be divisible by three, and
that gives us yet another way to factor a random number.
So what we mean actually is something a little bit different from factoring
random numbers.
And in fact the hardest numbers to factor seem to
be those that are the product of two equal length primes.
So we're interested in the problem of factoring numbers of a specific form.
That is, numbers that are the product of two large primes, and
in particular two equal length primes.
Now it turns out that the factoring problem, no matter how popular and
widespread it is, is not directly useful for much of cryptography.
And for that reason we're not going to spend time formalizing it.
What we're going to do instead is to introduce a problem that has had
more applications to cryptography, which is related to but
not identical to factoring, and this is the RSA problem.
So let me describe a little bit about the setting before we
formally define the problem.
For the rest of this lecture, we're going to only consider numbers and or
rather the, when we talk about an integer N, we're going to
only mean an integer N which is the product of two primes, P and Q.
Where P and Q are distinct and odd.
And their also going, going to in practice, be the same length.
But that won't really affect anything we say here.
So recall that Zn star is the set of
invertible elements under multiplication module n and this gives a group.
We said last that the order of Zn star is exactly phi
of N which is equal to p minus 1 times q minus 1.
And the first thing to note is that for somebody who knows the factors of N,
the group order that is phi of N is easy to compute.
We just take p minus 1 and multiply it by q minus 1.
However, if we just give somebody N, but do not give them the factors p and
q, it turns out that phi of N is hard to compute from N alone.
And in fact you can show that computing phi of N given N
is equivalent to factoring N.
So what we have here is a situation where if we publish N then somebody who knows
the, the factorization of N can compute the group order,
or the order of the of the group Zn star.
But somebody who does not know the factorization of N can still
perform operations in the group Zn star.
They can still multiply elements and reduce the modulo N.
However, they are not able to compute the order of the group they're working in.
And that's a very interesting asymmetry that we'll show how to
exploit in a moment.
Remember, at the end of last lecture, we gave a result that said in
particular that if g is a finite group of order m, then for
any integer e the function by which we raise elements of that group to the eth
power is the permutation, if the gcd of e and m is equal one.
In our setting, we have a group Z, n star of order phi of N.
Whether that order is known or not, it's not relevant here, it has order phi of N.
If we therefore fix an integer e whose greatest common
divisor with phi of N is equal to one, then the previous results tells us that
raising to the eth power is a permutation in this group.
So raising to the eth power permeates the elements of zn star.
Furthermore we said that if d is equal to e inverse mod n.
Then fd, that is,
raising things to the dth power, is the inverse of the function fe.
That is, raising to the dth power undoes, as it were,
the operation of raising to the eth power.
So let's think about what this means.
So we again have our group Zn star of order phi of N.
If we fix e with gcd of e phi of N equal to 1,
then raising to the e-th power is a permutation on Z n star.
And if ed is equal to 1 mod inve of N, that is d is equal to e inverse mod inve
of N, then raising the the d-th power is the inverse of raising the the e-th power.
To the e raised to the dth power will give you back x, and
similarly x to the d raised to the eth power will also give you back x.
Another way to say this is that, the element x to the d, taken modulo N here,
but that's implied, because we're working in the group Z n star.
The element x to the d is the eth root of x modulo N.
So why is it an eth root?
Well it's an eth root because if we take x to the d and
raise it to the eth power we get x.
So it's certainly an eth root.
Moreover it's a unique eth root, it's the unique eth root because of
the fact that raising to the eth power is a permutation.
So again, this means that the element, or, or
the result X to the D is the E-th root of X, where we'd work modular N.
So if p and q are known, right?
If the factorization of the modulus N is known,
then we've seen already that phi of N can be computed.
This implies that d equals e inverse mod phi can then be computed.
We didn't talk specifically about this however it turns out you can compute
inverses modulo any know modulo, so phi (N) is known we can compute the inverse
of e modulo phi(N) and that means that it's possible to compute.
E-th roots modulo N.
Again, for any element X,
if I want to compute it's e-th root, I just compute x to the d mod N.
On the other hand, if p and
q are not known, then computing phi of N is as hard as factoring N.
And since we don't have phi of N,
we certainly can't easily compute e inverse modular phi of N.
It's hard to imagine computing an inverse when we don't even know what modulus we're
working with respect to.
And in fact you can prove this.
You can show that computing e inverse mod phi of N, computing some element d,
such that d times e is equal to 1 mod phi of N, is also as hard as factoring N.
And this is very useful for public key cryptography.
Right, and it seems to be that if we don't have d,
then there's no other way to compute the e-th root of elements modulo N.
Now we unfortunately cannot show that that's equivalent to factoring N, and
we therefore are going to state this as an independence assumption called
the RSA assumption.
So the RSA assumption informally.
Says exactly that given a modulus N and some energy e,
relatively prime to phi of N, it's hard to compute e-th root's modulo N.
Or more specifically it's hard to compute the e-th root of
some uniform element y chosen uniformly as Zn star.
Now, if we wanted to find this assumption formally,
we need to be a little bit more careful and specify how N and e are generated.
So let's, abstractly for now, let GenRSA be some algorithm that on input
1 to the n, right, where little n, if you remember from back previously
security parameter is going to output three elements, N, e and d.
where N is equal to pq, and p and q are two n-bit primes.
And furthermore, with e times d equal to 1 mod phi of N.
So we have such an algorithm.
Well, we can then define an experiment RSA inverse relative to
that GenRSA and relative to any algorithm a.
The experiment is defined in the following way.
What we do is we run GenRSA on the given value of
the security parameter to generate our modulus N and our integers e and d.
We then choose a uniform element, y, in Zn star.
And we give to our algorithm A, N, e and this value y.
And we're essentially asking A to compute an eth root of y modulo N.
So A will output some x, and the experiment evaluates to one or
A is successful if it indeed outputs an e That is,
if it outputs a value x for which x to the e is equal to y modulo N.
And we'll say the RSA problem is hard relative to GenRSA.
So relative to this way of generating the modulus N and the integer e.
If it holds that for all probabilistic polynomial time algorithms A.
The probability with which A can succeed in the previous experiment.
That is the probability with which A can compute and
eth route of a uniform element of VN star is negligible.
Now in practice we have to fix some way of implementing GenRSA, but
there's a very natural way to do that.
And the natural way to do that is to first gen for,
generate uniform n-bit primes, p and q, and then multiply them.
We won't go into the details of how you can generate these n-bit primes, but
it turns out that this can be done.
It's a problem that's been studied quite a bit.
And we do have mechanisms for doing that.
They're not trivial, and they're very interesting.
But we won't have time to go into them here.
But if you grant me that we can do that,
then the rest of the algorithm is straightforward.
We generate our, our uniform n bit primes p and q, we multiply to get the modulus N,
and then we're free to choose e arbitrarily so
long as the gcd of e and phi of N is equal to 1.
Once we've done that we can compute the inverse of modulus phi of N,
we said earlier that this can be done efficiently.
And then we simply output an e and d.
Now, it's a little bit
interesting that we didn't pin down exactly how e can be chosen.
And it turns out that the way e is
chosen does not really seem to effect hardness of the RSA problem.
Or what I should say more carefully is that several different ways of
choosing e seem to give equivalent hardness when it comes to the RSA problem.
In practice, it's very common to set e, e equal to 3.
Or e equal to two to the 16 plus 1.
And the reason for that is to allow efficient exponentiation.
So think about e equals 3 in particular e equals 3 is a small number.
And therefore raising to the eth power is very efficient, can be done very quickly.
Similarly, e equals 2 the 16 plus 1 if you think about the way
that's written in binary.
2 the 16 plus one will be an integer with exactly two ones and the rest zeros.
And if you think about also the way we defined our exponentiation algorithm,
this will also lead to an efficient way an efficient algorithm for
raising things to the eth power.
So if you do things this way,
you just have to be a little bit careful to choose p and q in such a way that phi
of N will be relatively prime to one of these values of e.
Now, if factoring moduli output by GenRSA is easy, that is,
if given some modulus N output by GenRSA.
I could easily factor it.
Then the RSA problem cannot possibly be hard relative to GenRSA.
And the reason for that is that if we can factor the modulus N, we get p and q.
We can then compute phi of N, we can then compute d as e inverse mod phi of N, and
we can then take eth roots like anybody else.
So what this means is that if factoring is easy then the RSA problem is easy.
And so factoring being hard is a necessary condition for
the RSA problem to possibly be hard.
On the other hand, as I mentioned a few minutes ago.
Hardness of the RSA problem is not known to be implied by the hardness of
the factoring problem.
So we don't know that hardness of factoring implies hardness of RSA.
And it's possible though we believe it to be unlikely,
that factoring is hard but RSA, but the RSA problem is easy.
Now, as far as we know, and as far as our current algorithms lead us to believe,
the RSA problem is equally as hard as factoring.
the, the algorithms we know for
solving RSA all work by first factoring the modulus N.
So even though it's true that mathematically speaking and formally
speaking the factoring, hardness of factoring does not imply hardness of RSA.
As far as cryptographic assumptions go, it's as reasonable to assume that the RSA
problem is hard, as it is currently to assume that factoring is hard.
In the next lecture, we'll introduce another class of
cryptographic assumptions that are based on cyclic groups.
