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

441 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].

In this lecture, our final lecture on number theory,

I want to just to talk very briefly about appropriate choice of parameters.

Now we've discussed two classes of cryptographic assumptions.

The first, was based on the underlying assumption that factoring was hard, and

the problem that we spoke about here was the RSA assumption.

The other set that we considered, was in the setting of cyclic groups, and

we looked there at the discrete logarithm, the confrontational diffie hunnam and

the dicisional diffie hunnam assumptions.

And we talked very briefly about two classes of

groups in which those assumptions could be studied.

Now all of these problems are indeed believed to be hard in the sense that we

don't believe that they have any polynomial time algorithms for

solving these problems.

But this is not enough for using cryptography in practice.

In practice, it's not sufficient to know that there's no poly-time algorithm for

solving some problem.

In practice, we need to set some concrete value for the parameter.

For example, for the length of the modulus.

And to properly set that, we need to have a more fine grain understanding of how

hard these problems are.

And it's useful here to review what we saw for

the case of symmetric-key cryptography.

So for symmetric-key cryptography,

we said that we could hope for a block cipher with an n-bit key

being secure against an attacker running in time roughly two to the n.

And so if we want to achieve security against an attacker running for

a particular amount of time, we can easily set the length of our key appropriately,

to ensure security against such an attacker.

And, similarly, for the case of hash functions, we said that if

we have a hash function with an n-bit output, then we could hope for

security against an attacker running in time two to the n over two.

So here the security is worse than it is for the case of block ciphers.

But nevertheless, because we can characterize the security very

exactly we know how to set the length of

the output in order to achieve some desired level of security.

And to do analogous calculations for

the public key setting, we need there too to have a better understanding of

the exact difficulty of factoring in computing discrete logarithms.

So, for example, is it the case that factoring a modulus of

length n requires two to the n time or maybe two to the n over two time?

What is it?

And similarly, does computing discreet logarithms in a group with on the order of

two to the n elements?

Take two to the n time, two to the n over two time, something else?

Or does it depend on the group in which we're working?

These are the questions we're going to look at here.

Now I do want to give a little bit of a disclaimer.

And just say that the goal of this lecture is not to actually give you

parameters that you can then use in practice,

although you could do that from the slide I give you at the end.

But the goal instead is to give you an idea as to how these

parameters can be calculated.

And if you're serious about this, then there are many other

important considerations that you need to consider before setting a value for

the parameters you're going to use in your scheme.

And this is really just meant as an introduction.

And just to give you a broad brush, brush strokes.

An idea of how of the parameters are calculated.

Rather than to prescribe any particular setting of the parameters.

So with that in mind lets forge ahead.

In terms of factoring it turns out that there do

exist factoring algorithms that run in much less than two to the n time.

If I let n say denote the length of modulus that we're factoring.

In fact, there are algorithms that run much better than exponential time.

And the best known algorithm asymptotically, is the the general number

field sieve with a heuristic running time of approximately two to the, length

of n to the one third times some lower outer parameters, which are very important

in practice, but not relevant to the high level discussion that I want to have here.

So the point is that we might expect or we might hope for

exponential security which would be two to the n, where I

mean here again the length of the modulus, or maybe two the constant times n.

But instead we get something lower we get actually something a running time which is

sub exponential in the length of the modulus.

And this means in turn that the problem is much easier than say attacking

a symmetric key algorithm whose key length is equal to the modulith length, right?

So if you have a, a 128 bit modulith, that's trivial to factor.

Whereas the 128 bit key is sufficient enough to give good security in practice.

Now as far as the discrete logarithm problem goes

it's kind of interesting here because we have two classes of algorithms and

they both need to be taken into account.

The first class of algorithms are those that work for

arbitrary groups they're sometimes called generic group algorithms.

They work regardless of the group,

they don't care the details of the group you're working in.

All they actually care about, is the order of the group.

The other class of algorithms,

are those that target the discrete logarithm problem in specific groups.

As far as generic algorithms go, the best generic algorithms we have run in

time two to the n over two in a group who's order is about two to the n.

Or to say it differently if we have a group of several order q and the length of

q, the bit length of q is n bits then we get about two to the n over two security.

And it's kind of interesting because in this setting we know that

these algorithms are in fact optimal in some sense.

However, we have this other class of algorithms to consider which looks at

the particular group in which we're performing the discreet log

calculation and tries to tailor the algorithm for that group.

The best algorithm, that's known for the case of discreet logarithms in z,

p star or in subgroups of z, p star, is the so called number field sieve.

This algorithm has running time which is heuristically about two to the bit

length of p, to the one third.

So again, as in the case of factoring, this,

the running time of this algorithm is sub exponential in the length of p.

Which again means that the discrete logarithm problem in z p

star is easier than the corresponding, then

attacking a corresponding symmetric key algorithm with an equivalent key length.

Now what's particularly interesting in what makes elliptic curve cryptography

so exciting.

Is that if you choose your elliptic curve groups appropriately,

then there's no algorithms known that are better than the generic algorithms.

So this means that in some sense, elliptic curves are currently,

elliptic curve groups are currently optimal with respect to what we

could hope for as far as security is concerned.

Now, there is this caveat that I did put in parenthesis appropriately chosen.

Some care does need to be taken you can't just willy nilly pick any elliptical curve

group you want, there's some that's specifically need to be avoided.

However because we didn't go into any detail about ecliptic curve I'm not

going to go into detail about that either.

But you can find suitable references online.

Now this, in turn has a big impact on the efficiency of cryptographic algorithms.

So just as an example, NIST has recommended different security levels, or

rather, different parameters corresponding to different security levels.

And I've listed, here, the recommendations of NIST.

If you want to achieve 112 bit security, that is,

roughly speaking, security against attacks running in time two to the 1/12th, or

maybe a better way to put it would be security equivalent to

what you would get with a 112 bit, for, for a 112 bit symmetric key cypher.

For factoring the recommendation is to use a 2048 bit modulus.

So of course this is about a factor of 20 larger than the 112-bit key that

you would need to obtain equivalent security for a blog cypher.

And this reflects the fact that we do know sub exponential time

algorithm for factoring.

For the discreet logarithm problem,

if we look at the discreet log problem in order q sub group of z p star.

Then remember we have to be concerned both about the generic algorithms,

as well as for the specific algorithm tailored to z p star.

So to ensure 112 bit security against a generic algorithm, we need to make sure

that the order of the group is on the order, is roughly two to the 224.

Right? Because a group of order,

roughly two to the n, gives you about two to the n over two security.

So that means that the bit length of q,

if q is the order of the group, should be, should be 224.

But to protect against the Taylor algorithm,

that specifically targets the discrete log problem in z p star.

We need to set p much larger.

Because we have sub exponential time algorithms working in z p star.

And in particular, NIST recommends taking the bit length of p equal to 2048.

So, it's a little bit difficult to think about what this means exactly.

But wh, what it means is that you take your prime p of length 2048.

But then you're working in a much, much smaller subgroup of that larger group,

and this balances the security that you get against generic algorithms on

the one hand and against tailored algorithms on the other hand.

If we come to the case of elliptic curve groups or

elliptic curve subgroups, well as we said a moment ago for elliptic curve groups.

No algorithms known no, no algorithms are known which are better than what you get

by using generic algorithms.

And this means that it's sufficient here to take the group order equal to something

that would give you the requisite security against a generic algorithm.

Meaning that you could take the order to be something approximately two to

the 224 or equivalently you set your group order q, such that q has bit length 224.

And again this is why elliptic curves are so exciting because you can use

smaller parameters, I really haven't defined what elliptic curve groups are so

it's a little bit hard for me to say what those parameters are, but

you can use smaller smaller integer calculations and get equivalent security

to what you would get in using a much larger p in the case of z p star.

So, roughly speaking, elliptic-curve,

using elliptic curve groups will give you the same security at better efficiency.

In any case, one takeaway point here is that these parameters are much

larger than what you have for symmetric-key algorithms.

Perhaps with the exception of hash functions.

And this explains in part why public ecryto in a particular factoring based

crypto or crypto based on discreet log in some groups of z p star is so

much less, so much less efficient than symmetric ecryto.

This concludes our discussion of number theory.

And in the following weeks we're going to see some application of

all the number theory we learned to public-key cryptography.

And I look forward to seeing you all there.

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