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

415 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.