4 ms·
For a slightly less mathematical introduction: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://blog.c
by jgrahamc 12y ago
For a slightly less mathematical introduction: https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/ https://blog.cloudflare.com/a-relatively-easy-to-understand-...
- j2kun 12y agoBut the mathematical ones are the best ones :)
- YAYERKA 12y agoFor a slightly more mathematical introduction: https://www.youtube.com/watch?v=t3JzdKE-Fhs https://www.youtube.com/watch?v=t3JzdKE-Fhs along with accompanying slides http://crypto.biu.ac.il/sites/default/files/3rd_BIU_Winter_School/NigelSmart-BIU2013.pdf 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".
- j2kun 12y agoWhat I didn't say is that I wrote one :) So I don't think I need one.
- ColinWright 12y agoBy 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: 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". I know the article is trying to be informal, but that seems a simple thing to get right, and quite important. If I'm wrong I'd welcome being corrected. [0] http://en.wikipedia.org/wiki/Trapdoor_function http://en.wikipedia.org/wiki/Trapdoor_function
- Retr0spectrum 12y agoWouldn't the "special information" be the private key in this case?
- ColinWright 12y agoIt's more complicated than that. Consider RSA. 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. Now multiplying the numbers p and q is a one-way function, because there is no effective way to factor n (if p and q are chosen suitably.) The exponentiation M^e is a trap-door function because normally you can't undo it, but with any of the extra knowledge p, q, or d, then you can undo it. 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.)
- nightcracker 12y agoPerhaps 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.
- agwa 12y agoNo, 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.
- markburns 12y agoI'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 https://www.youtube.com/channel/UCgo7FCCPuylVk4luP3JAgVw
- markc 12y agoThe 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.
- markc 12y agoThe 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.