This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

Loading...

From the course by University of Maryland, College Park

Cryptography

423 ratings

This course will introduce you to the foundations of modern cryptography, with an eye toward practical applications.

- Jonathan KatzProfessor, University of Maryland, and Director, Maryland Cybersecurity Center

Maryland Cybersecurity Center

[SOUND] We're going to look here at cyclic groups which

give rise to another class of assumptions on

which public key cryptography can be based.

Let's begin by defining a cyclic group.

So let G be a finite group of order m, and

here we're going to write G using multiplicative notation.

Let little g be an element of the group G.

We can then consider the set of all powers of g, that is,

g to the 0 which is simply the identity element 1, g to the 1,

which is g itself, g squared, g cubed, et cetera.

Now we know from Fermat's little theorem that g to the m is equal to 1,

which is equal to g to the 0.

So that means that this set of elements will start to cycle.

And in particular, the set can have at most m elements.

And of course that has to be the case because we know that the group g itself

only has m elements.

Now if the set of powers of g has exactly m elements, then it must be all of g.

And in that case, we'll call g a generator of the group.

And if the group G has any element which is a generator,

then it will say that the group G is cyclic.

Let's see a simple example.

Let's consider the additive group, ZN.

So, here, we're switching notation to additive notation.

I claim that this group is cyclic for any value of N, and the reason for

that is that the element 1 is always a generator.

To see that, let's consider the powers of one,

which in this case are going to correspond to multiples of 1.

So 0 times 1 is 0, the identity in ZN, 1 times 1 is 1,

2 times 1 is 2, all the way up to N minus 1.

And you see that we've enumerated exactly all the elements of ZN.

And so 1 is always a generator, and ZN is always cyclic.

To see a concrete example,

let's consider an equal of eight, and look at the item group the eight.

We know this group is cyclic, as we just said.

But let's look at whether particular elements of this group are generators.

Consider the element 3, is 3 a generator?

Well, we can look at all multiples of 3, and we have 0, 3, 6,

3 times 3 is 9, which is one modulo 8.

We then get 4, 7, 2, and 5.

And what you can see is that indeed every element of

Z8 appears somewhere on this list.

Of course the elements don't appear in order, but

we never said that they had to appear in order.

All we cared about is that every element of the group is eventually generated

as a power of three.

So 3 is indeed a generator of the Z8.

But not every element is a generator.

For example, consider the element 2.

If we look at multiples of 2, we get 0, 2, 4, 6.

And then if 4 times 2 is 8, which is 0 mod 8.

So in fact 2 does not generate Z8, and 2 is not a generator.

So the fact that a group is cyclic means that it has a generator, but

it need not be the case that every element of the group is a generator.

And in general, it will not be the case.

Two important examples of cyclic groups are given by the following theorems.

Which we're not going to prove here, we're just going to state them.

The first theorem is that any group of prime order is cyclic, and

moreover in a cyclic group of prime order

every element except the identity is a generator.

This is a very useful theorem because it tells you that you don't care about any

details of what the underlying group is if it's prime, if it's order is prime,

then it's cyclic.

Another example of a cyclic group is given by Zp star for p prime.

Important examples * Theorem: Any group of prime order is cyclic, and

every non-identity element is a generator * Theorem: If p is prime,

then Z*p is cyclic (of order p-1).

So remember that Zp star is the multiplicative group, modular p.

And if P is prime, then this contains every element from 1 to p-1.

So this gives an example of a cyclic group.

Now it's easy to be confused here because p is prime, but

the order of the group Zp star is not prime, it's in fact, it's p-1 which for

p greater than 3 will not be a prime.

So this case is not covered by the previous theorem.

Now, one point I want to make is that if we have a group which is cyclic of or,

of order m, and it has to generate a g,

then it's easy to sample a uniform element in the group.

And the way you do that is by sampling a uniform exponent and

then computing g to the, to that exponent.

And the reason this gives you a uniform element of the group G is because there's

a one to one correspondent, correspondence between the exponents from

zero to m minus 1 and the elements of the group.

And this is very useful when we want to sample an elephant,

an element uniformly from the group.

And we'll rely on this implicitly whenever we use such uniform sampling in

the algorithms that we construct.

We're now ready to define the discrete-logarithm problem,

at least informally.

Fix some cyclic group G of order m, and generator g.

So we know, therefore, that the powers of g, that is, the set g to the 0,

g to the 1, up to g to the m minus 1, is exactly the group G itself.

That is, every element of the group appears somewhere on that list.

What this means is that for every h in the group, there's a unique exponent x in Zm,

that is the range of zero to m minus 1 such that g to the x is equal to h.

And we'll define the discrete logarithm of h with respect to g to be this value x.

And we'll write that as log h sub g.

So this is the discrete-logarithm of h with respect to G in the given group.

So the group here is going to be left implicit typically,

although when you talk about the discrete logarithm of some element,

you need to be clear what group you're working in.

The discrete logarithm problem in G roughly speaking is the following.

Given a generator g and

an element h, compute the discreet logarithm of h with respect to g.

And the discreet logarithm assumption is that solving the discreet

logarithm problem in g is hard.

That is, cannot be done in polynomial time.

More formally, let's, let script g here be a group generation algorithm.

By which I mean that on input the security parameter,

it will output the description of some cyclic group g along with

its order that I'm here going to denote by q, and a generator g of that group.

And we're going to require that the order of the group the,

the bit length of the order of the group should n, the security parameter.

For any such group generation algorithm and

any algorithm A, we can define the following discrete log experiment.

What we do is we first run this group generation algorithm on

the security parameter to generate our group G, or the description of the group,

it's order queue, and the generator G.

We then choose a uniform element h from that group.

And as we said a few slides ago, this is always easy to do efficiently.

We then provide to the algorithm A, the description of the group, the order q,

the generator, g, and it's element, h.

And we ask it to output for us the discrete log of h with respect to g.

So h wise, and, and outputs some value, x.

And the experiment evaluates to 1, or A succeeds, if that's the correct answer.

I.e.,

if g to the x is equal to h.

And we'll say that the discrete logarithm problem is hard relative to

this group generation algorithm G.

If for all probabilistic polynomial time algorithm is A, the probability with

which A can successfully compute this discrete logarithm, that is,

a discrete logarithm of a uniform element of the group, is negligible.

Now, it's very useful to define problems that are based on, but

not known to be equivalent to, the discrete logarithm problem.

And these are the so-called Diffie-Hellman problems.

Named after Diffie and Hellman, who first introduced the problems.

Although implicitly, in their paper from 1978.

So fix as usual a group G with a generator little g.

And within I'm going to define a bit of notation.

We're going to define DH sub G of h1 and h2, where h1 and

h2 are just elements of the group G.

We're going to define that as g to the xy.

Where x is the discrete log of h1 with respect to g, and

y is the discrete log of h2 with respect to g.

That is, to evaluate the function DH sub g on h1 and h2,

we first evaluate or we compute the discrete log of x the discreet log,

sorry the discreet log of h1 which is x, the discreet log of h2 which is y.

And then compute g to the xy.

The computational Diffie-Hellman problem asks to compute DH sub g of h1, h2.

That is given a generator g and

two elements h1, h2, compute the Diffie-Hellman of h1, h2.

Now, we said a moment ago that this could be computed by

computing the discreet logarithms of h1 and h2.

But of course if the discrete logarithm problem is hard, then it's not

going to give an efficient way to solve the computational Diffie-Hellman problem.

The decisional Diffie-Hellman problem, roughly speaking, asks for

something stronger.

It requires a given g, h1, and h2.

It's even hard to distinguish the correct answer DH of h1,

h2 from a completely uniform and independent element of G.

And we're going to define this more formally on the following slide.

We won't define formally the computational Diffie-Hellman problem, although I trust

that by now you would be able to come up with a formal definition on your own.

So it's a formally defined the decisional Diffie-Helman or DDH problem.

We'll gain let script g be a group generation algorithm.

And we'll say that the DDH problem is hard relative to this group generation

algorithm G, and for all probabilistic polynomial times, time algorithm A.

The difference in the following two probabilities is negligible.

And those probabilities are, in the first case, we run our

group generation algorithm to obtain a group g, it's order q and a generator g.

And then, give it, give to a, those parameters, along with g to the x,

g to the y, and g to the z.

Where all those values are chosen uniformly at random.

And in the second case, we do the same experiment,

although now rather than giving a three uncorrelated elements, g to the x,

g to the y, g to the z, we give it instead g to the x,

g to the y, and then the correct solution g to the x y.

And I see here that there's a typo on the slide,

which I'll correct when I post them online.

So intuitively, this this notion corresponds exactly to

what we said on the previous slide.

Namely, that it's hard for any algorithm A to distinguish the correct solution,

g to the xy, from a completely uniform element, g to the z.

If Z is uniform, then G to the Z is also uniform, and

as we said it's completely uncorrelated with G to the X and G to the Y.

[SOUND] Now it's useful to think about how the Diffie-Hellman problems relate to

each other as well as the to the discrete logarithm problem.

So if we fix some group generation algorithm, G.

Then as we said a moment ago if the discrete-logarithm problem is easy,

with respect to this group generation algorithm, then so

is the computational Diffie-Hellman problem.

And again, that's because if we can solve the discreet logarithm problem,

then given H1 and H2 we can compute the discreet logarithm of one of them.

And then compute the required solution g to the xy.

Similarly if the computational Diffie-Hellman problem is easy then so

is the decisional Diffie-Hellman problem.

And the reason for

this is simply that if we can compute the correct answer DH of h1, h2.

Then in particular we're able to identify the correct answer if it's given to us.

Put differently, this means that the DDH assumption is a stronger assumption

than the computational Diffie-Hellman assumption, and

the CDH assumption is in turn stronger that the discrete logarithm assumption.

So if we want to make the weakest possible assumption here,

then we're looking at the discrete-logarithm assumption.

And if we're willing to make the strongest possible assumption,

that would be the DDH assumption.

Now, for cryptographic applications, we have to discuss what kind of

groups are there for which all these problems are conjectured to be hard.

And the first think I'll note is that,

in general, it's best to use groups of prime order, and this is why it was so

important earlier when I mentioned that prime-order groups are always cyclic.

I don't want to get into the full reasons for this, but one thing I will say is

that if you take a nonprime-order group, then it certainly is possible for

the discrete logarithm problem to be hard in such a group.

However, it turns out that the discrete logarithm problem in non prime-order

groups is somehow easier than the discrete logarithm in prime-order groups.

So again this does not mean the discrete logarithm problem is easy,

it just means that it's easier if the group does not have prime-order.

And again, this relies on some results that I'm not presenting here, and

it's just meant to be an informal statement.

It turns out that in cryptography, there are really only two common classes of

groups that people use when they want to group that satisfies the discreet log or

Diffie-Hellman assumptions.

The first one is really relatively easy to talk about, and

this is prime order subgroups of Zp star for p prime.

So remember that Zp star itself is cyclic.

But because we want to work in a prime order group, we're going to restrict

ourselves to a subset of the group, a subgroup of Zp star which has prime order.

And one way that this can be generated, or

actually the canonical way in which this is generated, is as follows.

If we take p equals to tq plus 1 for q prime and p prime.

So you have to find p and q and, and t with these properties.

Then we can take the subgroup of Zp star, consisting of all t'th powers.

That is, we're going to take, we can consider the group,

G, containing the t'th power of every element of Zp star.

It's not very difficult to show that this is group.

It's not hard to show that it's closed.

And all the other properties actually follow pretty straightforwardly from

the fact that Zp star is a group.

It's a little bit more difficult, but not terribly so, to show that the order of

this group is exactly p minus 1 divided by t, which is equal to q.

And by construction, q is prime.

Since Q is prime,

we can rely on our previous result and say that this group is in fact cyclic.

So if we work in the subgroup of t'th powers modular p,

then we do indeed get a cyclic group of prime order in which the discreet

logarithm problem and Diffie-Hellman problems are conjectured to be hard.

Now, I'll throw in an advanced comment, which I don't expect all of you will know,

but for those of you who do, this may be useful or

may be useful to think about things this way.

A generalization of this is to consider prime-order subgroups

of the multiplicative group of a finite field of large characteristic.

So Zp star is kind of is an example of a finite field of large characteristic.

Zp star is the prime order subgroup rather of the field fp.

And you can generalize this to to other fields as well besides Zp star itself.

If you don't understand that that's fine.

I don't assume that people know fields.

You don't have to know anything about fields to follow anything else

from here on out.

Another example of groups in which the discrete logarithm problem and

Diffie-Hellman problems are conjectured to be hard,

are prime order subgroups of an elliptic curve group.

And if you've ever heard of elliptic curve cryptography,

then this is simply this is exactly what it means.

It means cryptography based on the discreet log rhythm problem, or

Diffie-Hellman problems in such groups.

Now, I'm not going to go into any detail at all about elliptic curves.

And the reason for

that is that the require a bit more group theory than we've developed.

Nevertheless, for our purposes, we're going to generally describe algorithms in

abstract groups where the exact details of the underlying group are irrelevant.

This means two things.

First of all, if you're not interested in implementing it yourself and

you're just interested in understanding it at a high level,

then you can safely ignore the details of the underlying group.

It doesn't really matter from that perspective,

what underlying group you're working in as long as the underlying group is

one in which these computational problems are hard.

Even if you're interested in implementing these algorithms.

What it means is that you can take the algorithm that's des,

that's described abstractly and

instantiate the underlying group with any appropriate group of your choice.

Where by appropriate here, I mean one where the corresponding cryptographic

problem is assumed to be hard.

You can of course plug in any cyclic group you like, but

if the cyclic group you plug in is not one for which the problems are hard,

then you won't get anything that's cryptographically secure.

Now, in the next lecture,

we'll talk a little bit about choosing concrete parameters for

these different groups, as well as for the RSA problem.

And you'll see a little bit about why people are so

excited about elliptic cryptography.

And why it seems to give better efficiency as compared to the other

algorithms we've talked about so far.

Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.