Elliptic Curve Cryptography: a gentle introduction(andrea.corbellini.name)
andrea.corbellini.name
Elliptic Curve Cryptography: a gentle introduction
http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
11 comments
For a slightly less mathematical introduction: https://blog.cloudflare.com/a-relatively-easy-to-understand-...
The Cloudflare ECC introduction is well written and very accessible - however I notice that it omits a very crucial bit of explanation.
In the billards example it's stated that for a given player starting at point A:
"It is easy for him to hit the ball over and over following the rules described above."
arriving at some point B after some number of hits N. However, regarding some other player who knows point A and B
"they cannot determine the number of times the ball was struck to get there without running through the whole game again"
The question of course, is "Why not? Why can't the second player just start at point A and keep hitting the ball until it gets to point B, and count the hits?
The answer is that the first player does not run through the the sequence one hit at a time! Knowing N, you can take a mathematical shortcut from A to B. The simplest of these is known as "double and add" for elliptic curves. This is similar to the "square and multiply" method for fast exponentiation. The shortcut is the critical advantage, because it's the enormous computational complexity of running through the entire game without the shortcut that is the basis of ECC's security.
In the billards example it's stated that for a given player starting at point A:
"It is easy for him to hit the ball over and over following the rules described above."
arriving at some point B after some number of hits N. However, regarding some other player who knows point A and B
"they cannot determine the number of times the ball was struck to get there without running through the whole game again"
The question of course, is "Why not? Why can't the second player just start at point A and keep hitting the ball until it gets to point B, and count the hits?
The answer is that the first player does not run through the the sequence one hit at a time! Knowing N, you can take a mathematical shortcut from A to B. The simplest of these is known as "double and add" for elliptic curves. This is similar to the "square and multiply" method for fast exponentiation. The shortcut is the critical advantage, because it's the enormous computational complexity of running through the entire game without the shortcut that is the basis of ECC's security.
By my understanding, there's an inaccuracy in that article. It describes a one-way function, but calls it a trapdoor function. I thought that a one-way function is only a trapdoor function if there exists the possibility of reversing it with an extra piece of information. The wikipedia link[0] given seems to confirm that understanding:
[0] http://en.wikipedia.org/wiki/Trapdoor_function
A trapdoor function is a function that is easy
to compute in one direction, yet difficult to
compute in the opposite direction (finding its
inverse) without special information, called the
"trapdoor".
[0] http://en.wikipedia.org/wiki/Trapdoor_function
In a cryptographic context;
>1.12 Definition
>A function f from a set X to a set Y is called a one-way function if f(x) is “easy” to compute for all x \in X but for “essentially all” elements y \in Im(f) it is “computationally infeasible” to find any x \in X such that f(x) = y. [0]
>1.16 Definition
>A trapdoor one-way function is a one-way function f : X -> Y with the additional property that given some extra information (called the trapdoor information) it becomes feasible to find for any given y \in Im(f), an x \in X such that f(x) = y. [0]
[0]; Menezes, A.; Oorschot, P. van; Vanstone, S. (2001). Handbook of Applied Cryptography (5th ed.). CRC Press.
>1.12 Definition
>A function f from a set X to a set Y is called a one-way function if f(x) is “easy” to compute for all x \in X but for “essentially all” elements y \in Im(f) it is “computationally infeasible” to find any x \in X such that f(x) = y. [0]
>1.16 Definition
>A trapdoor one-way function is a one-way function f : X -> Y with the additional property that given some extra information (called the trapdoor information) it becomes feasible to find for any given y \in Im(f), an x \in X such that f(x) = y. [0]
[0]; Menezes, A.; Oorschot, P. van; Vanstone, S. (2001). Handbook of Applied Cryptography (5th ed.). CRC Press.
[deleted]
Wouldn't the "special information" be the private key in this case?
It's more complicated than that. Consider RSA.
There are nuances, and time and time again I meet people who think lots of things are the same when in fact they are different, and the differences matter.
A one-way function is not necessarily a trap-door function.
In this case many things are equivalent in the sense that one can easily be computed given another, but the details actually matter.
The point, though, is that there are on-way functions that do not have trap-doors and hence are not trap-door functions. The definition as given in the blog post seems to conflate the two, when in fact the difference is important. PKCs are often made by starting with a provably one-way function and trying to find a way of inserting a trap-door without weakening it.
(Sorry if this is a little incoherent, it's late here, and I need to do some stuff before going to bed, and I have an early start tomorrow.)
Choose p, q, and let n=pq
Note: phi(n) = (p-1)(q-1)
Choose e
Compute d such that de = 1 (mod phi(n))
The number d is your private key.
Given a message M, E(M) = M^e (mod n)
Given an encrypted message E, D = E^d (mod n).
Magically, D=M.
There are nuances, and time and time again I meet people who think lots of things are the same when in fact they are different, and the differences matter.
A one-way function is not necessarily a trap-door function.
In this case many things are equivalent in the sense that one can easily be computed given another, but the details actually matter.
The point, though, is that there are on-way functions that do not have trap-doors and hence are not trap-door functions. The definition as given in the blog post seems to conflate the two, when in fact the difference is important. PKCs are often made by starting with a provably one-way function and trying to find a way of inserting a trap-door without weakening it.
(Sorry if this is a little incoherent, it's late here, and I need to do some stuff before going to bed, and I have an early start tomorrow.)
Perhaps a better example of a one-way function vs. a trap door is with symmetric cryptography? Let's look at two examples of a 2^128 -> 2^128 function f(n):
- The first 128 bits of SHA2(n). It should be computationally infeasible to find n from the output.
- AES128(n, k). It should be computationally infeasible to find n from the output, unless you know k.
- The first 128 bits of SHA2(n). It should be computationally infeasible to find n from the output.
- AES128(n, k). It should be computationally infeasible to find n from the output, unless you know k.
No, because in elliptic curve Diffie-Hellman, the private key isn't used to invert anything, as opposed to RSA (a true example of a trapdoor), where it is.
Well... it's used to invert the scalar multiplication and compute the discrete logarithm - with a notation similar to other comments:
Easy: given int n, point P -> compute Q = nP
Hard: given points P, Q (known to be nP for some n) -> compute n
While the equivalence between RSA and integer factorization is still an open question, the Rabin (exponent 2) trapdoor permutation is tightly equivalent to factoring.
Furthermore, for most groups the DHP is polynomially equivalent to the DLP. The requirement for this to be true is that there exists an elliptic curve with smooth order modulo the Diffie-Hellman group's order. Such smooth-order curves are hard to actually find for large groups, exponentially so (this is a fine example of the chasm between uniform and nonuniform reductions); but for elliptic curves groups used in practice, it is possible to find them. In other words, an easy way to break the DHP in smallish elliptic curve groups would lead to ECDLP solving with only polynomial overhead.
Furthermore, for most groups the DHP is polynomially equivalent to the DLP. The requirement for this to be true is that there exists an elliptic curve with smooth order modulo the Diffie-Hellman group's order. Such smooth-order curves are hard to actually find for large groups, exponentially so (this is a fine example of the chasm between uniform and nonuniform reductions); but for elliptic curves groups used in practice, it is possible to find them. In other words, an easy way to break the DHP in smallish elliptic curve groups would lead to ECDLP solving with only polynomial overhead.
Thanks for this. I was unclear on this point. So looking at the discrete log problem vs a trapdoor function:
Discrete log: for f(x) = y
- Easy: given f and x find y.
- Hard: given f and y find x.
Trapdoor: for f(x) = y
- Easy: given f and y find x, given a secret, e.g. (p-1)(q-1) in RSA.
- Hard: given f and y find x, without possesion of the secret.
Yes, that's essentially the difference between a one-way function and a trapdoor function.
I'm sure you knew this already, but for completeness, another property of the trapdoor function is:
I'm sure you knew this already, but for completeness, another property of the trapdoor function is:
- Easy: given f and x find y.It is likely that some of the functions are trap door functions. That is basically what is the theory behind the random number generator that the NSA paid to have set as default in BSAFE library. https://en.wikipedia.org/wiki/Dual_EC_DRBG
But the mathematical ones are the best ones :)
For a slightly more mathematical introduction: https://www.youtube.com/watch?v=t3JzdKE-Fhs along with accompanying slides
http://crypto.biu.ac.il/sites/default/files/3rd_BIU_Winter_S... both from ""3rd BIU Winter School on Cryptography: The basics of elliptic curves - Nigel Smart".
What I didn't say is that I wrote one :) So I don't think I need one.
I'd advise anyone trying to learn by implementing ECC to be careful using this article as an introduction. It's written as if you can follow along, but there are some omissions (see the comments section).
James D'Angelo has some good videos that go into some of the detail too
https://www.youtube.com/channel/UCgo7FCCPuylVk4luP3JAgVw
James D'Angelo has some good videos that go into some of the detail too
https://www.youtube.com/channel/UCgo7FCCPuylVk4luP3JAgVw
Also check out https://events.ccc.de/congress/2014/Fahrplan/events/6369.htm...
Video of the talk: http://media.ccc.de/browse/congress/2014/31c3_-_6369_-_en_-_...
Video of the talk: http://media.ccc.de/browse/congress/2014/31c3_-_6369_-_en_-_...
Really liked this version. All the time I was wondering when they would transition from the "toy" clock curve that is easy to understand to the complicated y^3 curves that are mentioned in the OP but it turns out that the easy to understand curve was just as good all along and much easier to implement correctly.
If you want to experiment with the graph try adjusting the a/b parameters here: https://www.desmos.com/calculator/3ugvl6yz4i
There is no design trend more inimical to the function of the web than gray on white text. If only it stopped at gray values of #444444, which is bad enough on old displays or in bright ambient light. The text on this site is #7f8d8c — more white than black — and the strokes on the letters in the equations are quite fine. Yes, it looks nice and clean to have so little black on the page, but the tradeoff is that I have to squint to read it.
I can't help but to point out the irony of a post complaining about grey text, being... in grey text (referring to the downvotes)
It's not gonna be the most constructive comment, but I would like to thank the author for writing this article and the poster for submitting it. I worked a bit during my undergraduate studies on the Elliptic Curve method to factor products of large prime numbers, and found it interesting, and sometimes wish I could learn more about that.
> Those of you who know what public-key cryptography
For those of you that don't, might I suggest my: https://nickdesaulniers.github.io/blog/2015/02/22/public-key...
For those of you that don't, might I suggest my: https://nickdesaulniers.github.io/blog/2015/02/22/public-key...
You are awesome. Thank you!
For those who prefer audio/video, this was also covered in Security Now episode 374: http://twit.tv/show/security-now/374
Can someone help me out here: I'm a bit rusty on my set builder notation... Is the following correct?
The set of natural numbers isn't a group because a group is a set partially defined by { ∀a∃b | a + b = 0 } - or in other words for every element a in the group there exists an element b in the group such that a + b = 0; or to put it yet another way, every element a has an element b that is its arithmetic inverse. As the set of natural numbers are only positive, you can't satisfy this condition.
The set of natural numbers isn't a group because a group is a set partially defined by { ∀a∃b | a + b = 0 } - or in other words for every element a in the group there exists an element b in the group such that a + b = 0; or to put it yet another way, every element a has an element b that is its arithmetic inverse. As the set of natural numbers are only positive, you can't satisfy this condition.
A group is a set equipped with a binary operator that obeys a few rules. One of the rules is the existence of inverses. If the operator is addition, then your description is correct. That is, every element x of the underlying set has an additive inverse x^-1 also in the set such that x + x^-1 = 0. Obviously, zero needs to be in the set as well and in some constructions of the natural numbers it is not.
Thank you!
Needs javascript to read... sigh.
No it doesn't. At least not with Firefox. Just use
And it gets even worse for the light gray text. OS X Accessibility has a setting to "Enhance Contrast". But in this case the gray is closer to white than to black, so all that "enhancing" does is make the text even lighter!
Sigh.
View --> Page Style --> No Style
Preferences --> Content --> Colors --> override ...
And it gets even worse for the light gray text. OS X Accessibility has a setting to "Enhance Contrast". But in this case the gray is closer to white than to black, so all that "enhancing" does is make the text even lighter!
Sigh.
The interactive tool[1] needs javascript. Don't try graphing secp256k1.
[1] https://cdn.rawgit.com/andreacorbellini/ecc/0939921/interact...
[1] https://cdn.rawgit.com/andreacorbellini/ecc/0939921/interact...
I was ready to say "well, the animations and formulas need it" but no, those are static images. Meh...
When I was in college there was a distinct worry about elliptic curves vs rsa. My professors were intuitively worried that discrete logs over elliptic curves may well have a simple solution, unlike factorization which has millenia of research proving that it is hard. They were worried enough that I just assumed that GCHQ had already cracked it. Is that still a worry?
Such worries have mostly faded by now, though you will see some conservative people still preferring RSA. Keep in mind that the computational study of integer factorization only started seriously in the 70s with CFRAC, making the "milennia" argument somewhat moot.
There is a fascinating article by (among others) Neal Koblitz, one of the inventors of elliptic curve cryptography, which describes the history and development of ECC through the 80s, 90s, and 00s, and some of the worries that developed: https://eprint.iacr.org/2008/390.
There is a fascinating article by (among others) Neal Koblitz, one of the inventors of elliptic curve cryptography, which describes the history and development of ECC through the 80s, 90s, and 00s, and some of the worries that developed: https://eprint.iacr.org/2008/390.
I don't like how 0 is used as three different symbols in the beginning: the number, the point of infinity and the identity element. I know 0 is a common symbol for each of the three cases respectively but in the same context it feels rather confusing. Is that a common thing to do?
Yes, it's a very common thing to use the same symbol to mean different things in mathematics.
the number zero is always defined as being an additive identity element, and in these groups 0 is the point at infinity.