7 ms·

Elliptic Curve Cryptography for Beginners

328 points by deafcalculus 9y ago

landmark3 9y ago
Well written and even I understood it - recommended!
gewoonkris 9y ago
The article gives a nice intuition about how encryption works using elliptic curves without going too deep into the math. I'm curious for a similar explanation for how decryption would work though; a trapdoor function is nice and all, but it's only half of the story if there is no 'way out'.
- dsacco 9y ago
  Your question (if I interpret correctly) is about how trapdoor functions work in asymmetric cryptography, which is broader than elliptic curves in particular. I can give a basic overview; in essence, you use a trapdoor function because you want something to be very difficult to compute but comparatively easy to verify. Mathematically speaking, a good trapdoor function should be such that anyone without the solution will spend a great deal of time trying to calculate it, while anyone with the solution will spend almost no time verifying that the solution is correct. If we use RSA as an example, we can see how this works in practice: 1. Let n be the product of two large primes, p and q. Large means 512 bits or greater in this context. Then n is the RSA modulus. 2. Select a special number e such that 1 < e < (p - 1)(q - 1), and such that e is coprime with (p - 1)(q - 1) (meaning no numbers divide evenly into both). 3. Your RSA public key is now (n, e) - you can share this publicly with anyone you want to securely communicate with. Conversely, p and q must not be public. This is where your one-way function comes in to separate what can be public from what must be private: n is part of the public key, but was generated by p and q, and multiplication of two primes is a one-way function. 4. Your RSA private key d is computed from q and e, such that for any pair (n, e) there can only be a unique d. d is the inverse of e modulo (p - 1)(q - 1) - in other words, d is a unique number such that, when multiplied by e, is equal to 1 modulo (p - 1)(q - 1). This can be expressed simply as ed = 1 mod (p - 1)(q - 1). 5. Assuming you chose e correctly, d is unique and very difficult to find without having p, q and e. However, while it's very difficult to find without those inputs, it's very easy to find if you have them, because you can use what's called the Extended Euclidean Algorithm to compute d in polynomial time given p and q. 6. So now you want to encrypt something with RSA. Your peer has your public key, (n, e). The encryption process to compute the ciphertext C from the plaintext P is simple: C = P^e mod n (C is equal to the plaintext P multiplied by itself e times and reduced modulo n). Exponentiation has polynomial complexity. 7. To decrypt the ciphertext C in order to compute the plaintext P, all the holder of the private key needs to do is this: P = C^d mod n. In other words, they raise the ciphertext C to the power of their private key. So, returning to trapdoor functions in general: why does this work? It works because the solution is easy to compute with all inputs, easy to verify with a reduced (public) set of inputs, and extremely difficult to compute with only the reduced set of inputs (and the secret inputs are themselves difficult to find from the public ones). Hope that helps a bit and I understood your question's context correctly! Trapdoor functions do not necessarily mean that there's "no way out", what they mean is that a set of values have a relation such that one of the values requires only a few of the values to compute a ciphertext and all or most of the values to compute a plaintext for that ciphertext. When we talk about functions being irreversible, we're specifically talking about one-way functions, and those are used in the context of hash functions. Trapdoor functions are "merely" difficult to reverse. One of the things I'm actively researching at the moment is whether or not (and how) it would be possible to construct a post-quantum secure public-key cryptosystem based on a hardness assumption derived from problems in Ramsey Theoretic graph problems (coincidentally, this problem had a recent treatment after being quietly raised over a decade ago: https://pdfs.semanticscholar.org/1599/62064634fe10897aea300cddb3a909affe6e.pdf https://pdfs.semanticscholar.org/1599/62064634fe10897aea300c...).
  - T_D_K 9y ago
    This is a great response! But I think the person you replied to understands all this, and is wondering about the exact method (or a layman's explanation) of the same process in terms of elliptic curve crypto rather than the traditional RSA (I'm wondering the same thing).
- ecesena 9y ago
  As far as I can see there's no mention to encryption, the OP describes how scalar multiplication works on elliptic curves. To encrypt/decrypt, for example, you can use the ElGamal scheme: https://en.wikipedia.org/wiki/ElGamal_encryption https://en.wikipedia.org/wiki/ElGamal_encryption (note that wikipedia uses the multiplicative notation, while in ECC typically additive notation is preferred, so you'll have to translate every A^x into xA -- but it's a good exercise.)
jlgaddis 9y ago
I'm not aure if this page uses MathML or something like that but it does not render correctly on the iPad.
enedil 9y ago
As nice as it is, integers are not a field (i.e. most of them don't have multiplicative inverses, or 1/n usually isn't integral). Another good writeup: http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryp...
- widdma 9y ago
  True, perhaps the author meant rationals.
  - ecesena 9y ago
    It's usually integers modulo p (p prime), which is a field. Edit: but yes, the OP writes "integers (Z) are a field", which is wrong. Integers form a ring.
- sixbrx 9y ago
  Came here to see if anyone noticed this. You can actually make a field of Z using a bijection to the rationals Q, which do exist. But then you aren't using the standard operations, but using the ones inherited from the particular mapping to Q.
- internetman55 9y ago
  I think integers mod p (p prime) is a field
dsacco 9y ago
This is pretty good! The arithmetic of elliptic curves gets very complex, but I like how you arrived at points on an elliptic curve just by defining groups and fields. It might be a slight improvement to give a short, Rudin-style explanation of the difference between a set and a field. You could do this from first principles of set theory without being so terse as to be incomprehensible or diving into the axioms; I think the stated goal of little math is fine for the audience, but at the same time such an audience might not immediately understand what “field = set with addition and multiplication defined on it” means. I think a small expansion of the treatment on why the ECDLP is hard would also be good. It's intuitively easy to follow that hard problems can exist, but maybe continue on in showing why this particular hardness assumption works for cryptography (because there are many that do not). Places to go from here if you enjoyed reading this and want to learn more about elliptic curves and cryptography related to them: 1. http://blog.bjrn.se/2015/07/lets-construct-elliptic-curve.html?m=1 http://blog.bjrn.se/2015/07/lets-construct-elliptic-curve.ht... More on an elliptic curve and constructing a hypothetical one. 2. https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627 https://medium.com/@VitalikButerin/exploring-elliptic-curve-... Elliptic curve pairings. 3. https://www.lvh.io/posts/supersingular-isogeny-diffie-hellman-101.html https://www.lvh.io/posts/supersingular-isogeny-diffie-hellma... An intro to supersingular isogeny cryptography, which has a basis in elliptic curves as a mathematical structure, but is fundamentally different from elliptic curve cryptography.
mlevental 9y ago
more in depth and just as gentle: https://jeremykun.com/2014/02/08/introducing-elliptic-curves/ https://jeremykun.com/2014/02/08/introducing-elliptic-curves...
wyc 9y ago
If you want to see a "from scratch" implementation using existing algorithms, here's short working snippet of elliptic curve cryptography (specifically Bitcoin's) without 3rd party libraries: https://github.com/wyc/haschain/blob/master/Secp256K1.hs https://github.com/wyc/haschain/blob/master/Secp256K1.hs The implementation doesn't concern itself with groups or fields, but they're still very useful to make sense of the code at all. Actually, I should add some types and implement an instance of Data.Group when I have more time. Of course, it's for fun and not production use. I didn't give the slightest thought to timing attacks, optimized performance, etc.
fallingfrog 9y ago
In the image for A+A=C (multiply by 2) I see the intersection point C, but what if you wanted to multiply by 3? That would be A+C=D and I don't see any point on the curve that the line through A and C intersects. In fact it looks like for any A you choose, adding A+A gives a C which has that property (in other words A*3=0 for any A). This is just by visual inspection. What am I missing?
- CarolineW 9y ago
  Seems to have labelled "C" and "-C" in a very misleading manner. Take point A. Draw a tangent, that cuts the curve at point C. That's not the point 2A. That's the point C. Reflect C across the X axis, and that's point 2A. So you're not missing anything, the article is misleading at best. In short, to take the sum of two points A and B, draw a line through them both to find a third point on the curve, reflect that point across the X-axis, and the result (which will also be on the curve) is A+B. If A and B coincide then use the tangent at A. The point at (vertical) infinity plays the role of the zero.
  - fallingfrog 9y ago
    Ohh OK! Thank you. Makes more sense now.
drcode 9y ago
In case anyone here is interested in Cryptography as it pertains to Cryptocurrency specifically, here's a talk I gave recently that might be interesting to you: https://www.youtube.com/watch?v=Fyqtl7eGQZY&t=1062s https://www.youtube.com/watch?v=Fyqtl7eGQZY&t=1062s
- kanzure 9y ago
  here are some videos from dan boneh on cryptography, https://www.youtube.com/playlist?list=PL9oqNDMzcMClAPkwrn5dm7IndYjjWiSYJ https://www.youtube.com/playlist?list=PL9oqNDMzcMClAPkwrn5dm...
jrubinovitz 9y ago
Well done, loved the use of interactive graphics. Curious if you will continue this approach, but for more advanced cryptography, or move on to other things. Would love a more in depth guide to cryptography in this format.
red_admiral 9y ago
I always get a bit annoyed when someone tries to explain ECC with an image of an elliptic curve over the reals. The whole point of ECs over finite fields in cryptography is that they don't have any regular structure like that!
- xyzzyz 9y ago
  What do you mean? Elliptic curves over finite fields have tons of structure themselves, and to my knowledge, the discrete logarithm problem for ECs over reals is just as hard as for finite fields.
  - red_admiral 9y ago
    I'm not sure what your level of understanding is, so I'll write this reply in a way I hope the average reader can follow, though I assume you'll know most of this already - I hope I don't come across as condescending. TL;DR: the topology of these curves is quite different over finite fields. I first encountered what I consider cryptographically unhelpful drawings/intuition when I studied lattice-based cryptography. There's a whole field where a fundamental hard problem is finding the closest vector to a point not on the lattice. If you try and explain this by drawing a 2 or 3-dimensional example over the reals, anyone who's paying attention and proficient in Linear Algebra will ask themselves, why don't you just transpose the whole thing and then take the orthonormal projection? The problem is that in a finite field, unlike over the reals or complex numbers, orthogonal projection doesn't get you any closer to your target, so the intuition over R^2 is in my opinion very unhelpful to understand exactly why SVP/CVP are supposed to be hard, and indeed had me confused for a while until my professor pointed out I should forget "the silly drawing over R^2" which he didn't like either. For Elliptic Curve Cryptography, I find the example of a curve over the reals again misses the point of why exactly problems like DLOG are hard - for discrete-log based crypto at the 256-bit security level over finite fields, you need an about 15k bit modulus depending on which site you look at (NIST 2016 at keylength.com is a good place to start) due to speedups from Number Field Sieving etc. THis is the kind of structure that I mean you don't get. On EC, to get 256 bit security you need exactly 2 * 256 = 512 bits of key (slightly oversimplifying, the factor 2 is because you get the "sign of the y value" for free). The number 512 pretty much stands for the conjecture "there is no other cryptographically exploitable structure to take DLOGs over these Elliptic Curves". In fact it's not just "we haven't found any such structure" but there's an argument about heights of points (Miller '85 I think - though I'm pretty sure I've also read something by Koblitz on this) why on certain kinds of curves such structure is unlikely to exist. (Of course, other kinds of curves for fancy bilinear group stuff exist and do have more structure. And supersingular curves are another topic altogether.) The structure you obviously do get is a group, which you can extend to a vector space over the finite field so that (x \mapsto xP) is a linear function. The security property you want is roughly "you get this group, but only this group" (and the "sign", so add 1 extra bit to your keylength) and there is no useful concept of anything like points being close to each other, continuous maps in the usual sense etc. Plot the points on an EC over a small finite field and it looks like a random scatterplot rather than a neat and elegant curve - which is the whole point of using ECs over finite fields for DLOG-based crypto.
deleted 9y ago
[deleted]
tptacek 9y ago
So far, the best single-page elliptic curve primer for generalist programmers I know of is Adam Langley's: https://www.imperialviolet.org/2010/12/04/ecc.html https://www.imperialviolet.org/2010/12/04/ecc.html I understand the urge to try to get a high-level grok of curves without much math, but I spent years bouncing off the outermost surface of curve understanding by trying to start with the curve picture and the intuitive geometry of curve shape, and what finally made curves click for me (and quickly) was to simply take the curve equation --- which is itself high school math! --- and play with it a bit. So if you're a programmer and you want a baseline understanding how curves work, do what you'd do with any other subject you're trying to understand: pop open an editor, take the Weierstrass curve equation, pick a y, solve for x; then do it in a finite field (ie, mod a prime). Then write an "add", then a "scalar mult". It's a couple hours of noodling, tops. As always, but particularly with curves, remember that the basic understanding of what's going on is nowhere nearly enough to ever use them safely!
- palisade 9y ago
  The common advice of, "You'll never know enough to use them safely so don't bother trying, just trust us." that has been going around has been proven itself to weaken encryption. Just recently, an amateur programmer with very little background in cryptography discovered a flaw in libsodium in the Argon2 implementation and also in the reference implementation that everyone in the world was trusting without question. My advice is if you're an engineer, don't be afraid to write your own implementation of tried and trusted ciphers. This is how we find bugs and improve. This isn't the only trusted library or algorithm that has been shown flawed in recent times. The strength of your cipher implementation can be tested and proven. We need to stop telling everyone these algorithms are absolutely trustworthy so don't try understanding them or implementing them. Nothing ever advances or improves that way. Buck the trends, create competing libraries, try new things. The ancient ones were not all knowing, they were doing everything wrong. Their designs are full of flaws. Deny them. We need to code ourselves out of the coming cryptographic apocalypse. Do not hide your heads in the sand and hope the world doesn't come crashing down around you. Edit: I found the blog/website of the man I mentioned in this comment who discovered the Argon2 flaw. http://loup-vaillant.fr/articles/implemented-my-own-crypto http://loup-vaillant.fr/articles/implemented-my-own-crypto In his own words, "There's something worrying about this bug: I was the first to discover it, in January 2017. According to Khovratovich himself, it was two years old. Now I understand why the authors themselves didn't find it: unlike me, they didn't have a reference implementation to compare to. What I don't understand is, how come nobody else discovered this bug? If you implement Argon2 from spec, you cannot miss it. Test vectors won't match, and searching for the cause will naturally lead to this bug. I can draw only one conclusion from this: I'm the first to independently re-implement Argon2. This 'never implement your own crypto' business went a little too far."
wildchild 9y ago
Also good reading https://steemit.com/monero/@luigi1111/understanding-monero-cryptography-privacy-introduction https://steemit.com/monero/@luigi1111/understanding-monero-c...

328 points by deafcalculus 9y ago

Well written and even I understood it - recommended!

The article gives a nice intuition about how encryption works using elliptic curves without going too deep into the math. I'm curious for a similar explanation for how decryption would work though; a trapdoor function is nice and all, but it's only half of the story if there is no 'way out'.

dsacco 9y ago
Your question (if I interpret correctly) is about how trapdoor functions work in asymmetric cryptography, which is broader than elliptic curves in particular. I can give a basic overview; in essence, you use a trapdoor function because you want something to be very difficult to compute but comparatively easy to verify. Mathematically speaking, a good trapdoor function should be such that anyone without the solution will spend a great deal of time trying to calculate it, while anyone with the solution will spend almost no time verifying that the solution is correct. If we use RSA as an example, we can see how this works in practice: 1. Let n be the product of two large primes, p and q. Large means 512 bits or greater in this context. Then n is the RSA modulus. 2. Select a special number e such that 1 < e < (p - 1)(q - 1), and such that e is coprime with (p - 1)(q - 1) (meaning no numbers divide evenly into both). 3. Your RSA public key is now (n, e) - you can share this publicly with anyone you want to securely communicate with. Conversely, p and q must not be public. This is where your one-way function comes in to separate what can be public from what must be private: n is part of the public key, but was generated by p and q, and multiplication of two primes is a one-way function. 4. Your RSA private key d is computed from q and e, such that for any pair (n, e) there can only be a unique d. d is the inverse of e modulo (p - 1)(q - 1) - in other words, d is a unique number such that, when multiplied by e, is equal to 1 modulo (p - 1)(q - 1). This can be expressed simply as ed = 1 mod (p - 1)(q - 1). 5. Assuming you chose e correctly, d is unique and very difficult to find without having p, q and e. However, while it's very difficult to find without those inputs, it's very easy to find if you have them, because you can use what's called the Extended Euclidean Algorithm to compute d in polynomial time given p and q. 6. So now you want to encrypt something with RSA. Your peer has your public key, (n, e). The encryption process to compute the ciphertext C from the plaintext P is simple: C = P^e mod n (C is equal to the plaintext P multiplied by itself e times and reduced modulo n). Exponentiation has polynomial complexity. 7. To decrypt the ciphertext C in order to compute the plaintext P, all the holder of the private key needs to do is this: P = C^d mod n. In other words, they raise the ciphertext C to the power of their private key. So, returning to trapdoor functions in general: why does this work? It works because the solution is easy to compute with all inputs, easy to verify with a reduced (public) set of inputs, and extremely difficult to compute with only the reduced set of inputs (and the secret inputs are themselves difficult to find from the public ones). Hope that helps a bit and I understood your question's context correctly! Trapdoor functions do not necessarily mean that there's "no way out", what they mean is that a set of values have a relation such that one of the values requires only a few of the values to compute a ciphertext and all or most of the values to compute a plaintext for that ciphertext. When we talk about functions being irreversible, we're specifically talking about one-way functions, and those are used in the context of hash functions. Trapdoor functions are "merely" difficult to reverse. One of the things I'm actively researching at the moment is whether or not (and how) it would be possible to construct a post-quantum secure public-key cryptosystem based on a hardness assumption derived from problems in Ramsey Theoretic graph problems (coincidentally, this problem had a recent treatment after being quietly raised over a decade ago: https://pdfs.semanticscholar.org/1599/62064634fe10897aea300cddb3a909affe6e.pdf https://pdfs.semanticscholar.org/1599/62064634fe10897aea300c...).
- T_D_K 9y ago
  This is a great response! But I think the person you replied to understands all this, and is wondering about the exact method (or a layman's explanation) of the same process in terms of elliptic curve crypto rather than the traditional RSA (I'm wondering the same thing).
ecesena 9y ago
As far as I can see there's no mention to encryption, the OP describes how scalar multiplication works on elliptic curves. To encrypt/decrypt, for example, you can use the ElGamal scheme: https://en.wikipedia.org/wiki/ElGamal_encryption https://en.wikipedia.org/wiki/ElGamal_encryption (note that wikipedia uses the multiplicative notation, while in ECC typically additive notation is preferred, so you'll have to translate every A^x into xA -- but it's a good exercise.)

jlgaddis 9y ago

I'm not aure if this page uses MathML or something like that but it does not render correctly on the iPad.

enedil 9y ago

As nice as it is, integers are not a field (i.e. most of them don't have multiplicative inverses, or 1/n usually isn't integral). Another good writeup: http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/ http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryp...

widdma 9y ago
True, perhaps the author meant rationals.
- ecesena 9y ago
  It's usually integers modulo p (p prime), which is a field. Edit: but yes, the OP writes "integers (Z) are a field", which is wrong. Integers form a ring.
sixbrx 9y ago
Came here to see if anyone noticed this. You can actually make a field of Z using a bijection to the rationals Q, which do exist. But then you aren't using the standard operations, but using the ones inherited from the particular mapping to Q.
internetman55 9y ago
I think integers mod p (p prime) is a field

dsacco 9y ago

This is pretty good! The arithmetic of elliptic curves gets very complex, but I like how you arrived at points on an elliptic curve just by defining groups and fields. It might be a slight improvement to give a short, Rudin-style explanation of the difference between a set and a field. You could do this from first principles of set theory without being so terse as to be incomprehensible or diving into the axioms; I think the stated goal of little math is fine for the audience, but at the same time such an audience might not immediately understand what “field = set with addition and multiplication defined on it” means. I think a small expansion of the treatment on why the ECDLP is hard would also be good. It's intuitively easy to follow that hard problems can exist, but maybe continue on in showing why this particular hardness assumption works for cryptography (because there are many that do not). Places to go from here if you enjoyed reading this and want to learn more about elliptic curves and cryptography related to them: 1. http://blog.bjrn.se/2015/07/lets-construct-elliptic-curve.html?m=1 http://blog.bjrn.se/2015/07/lets-construct-elliptic-curve.ht... More on an elliptic curve and constructing a hypothetical one. 2. https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627 https://medium.com/@VitalikButerin/exploring-elliptic-curve-... Elliptic curve pairings. 3. https://www.lvh.io/posts/supersingular-isogeny-diffie-hellman-101.html https://www.lvh.io/posts/supersingular-isogeny-diffie-hellma... An intro to supersingular isogeny cryptography, which has a basis in elliptic curves as a mathematical structure, but is fundamentally different from elliptic curve cryptography.

mlevental 9y ago

more in depth and just as gentle: https://jeremykun.com/2014/02/08/introducing-elliptic-curves/ https://jeremykun.com/2014/02/08/introducing-elliptic-curves...

wyc 9y ago

If you want to see a "from scratch" implementation using existing algorithms, here's short working snippet of elliptic curve cryptography (specifically Bitcoin's) without 3rd party libraries: https://github.com/wyc/haschain/blob/master/Secp256K1.hs https://github.com/wyc/haschain/blob/master/Secp256K1.hs The implementation doesn't concern itself with groups or fields, but they're still very useful to make sense of the code at all. Actually, I should add some types and implement an instance of Data.Group when I have more time. Of course, it's for fun and not production use. I didn't give the slightest thought to timing attacks, optimized performance, etc.

fallingfrog 9y ago

In the image for A+A=C (multiply by 2) I see the intersection point C, but what if you wanted to multiply by 3? That would be A+C=D and I don't see any point on the curve that the line through A and C intersects. In fact it looks like for any A you choose, adding A+A gives a C which has that property (in other words A*3=0 for any A). This is just by visual inspection. What am I missing?

CarolineW 9y ago
Seems to have labelled "C" and "-C" in a very misleading manner. Take point A. Draw a tangent, that cuts the curve at point C. That's not the point 2A. That's the point C. Reflect C across the X axis, and that's point 2A. So you're not missing anything, the article is misleading at best. In short, to take the sum of two points A and B, draw a line through them both to find a third point on the curve, reflect that point across the X-axis, and the result (which will also be on the curve) is A+B. If A and B coincide then use the tangent at A. The point at (vertical) infinity plays the role of the zero.
- fallingfrog 9y ago
  Ohh OK! Thank you. Makes more sense now.

drcode 9y ago

In case anyone here is interested in Cryptography as it pertains to Cryptocurrency specifically, here's a talk I gave recently that might be interesting to you: https://www.youtube.com/watch?v=Fyqtl7eGQZY&t=1062s https://www.youtube.com/watch?v=Fyqtl7eGQZY&t=1062s

kanzure 9y ago
here are some videos from dan boneh on cryptography, https://www.youtube.com/playlist?list=PL9oqNDMzcMClAPkwrn5dm7IndYjjWiSYJ https://www.youtube.com/playlist?list=PL9oqNDMzcMClAPkwrn5dm...

jrubinovitz 9y ago

Well done, loved the use of interactive graphics. Curious if you will continue this approach, but for more advanced cryptography, or move on to other things. Would love a more in depth guide to cryptography in this format.

red_admiral 9y ago

I always get a bit annoyed when someone tries to explain ECC with an image of an elliptic curve over the reals. The whole point of ECs over finite fields in cryptography is that they don't have any regular structure like that!

xyzzyz 9y ago
What do you mean? Elliptic curves over finite fields have tons of structure themselves, and to my knowledge, the discrete logarithm problem for ECs over reals is just as hard as for finite fields.
- red_admiral 9y ago
  I'm not sure what your level of understanding is, so I'll write this reply in a way I hope the average reader can follow, though I assume you'll know most of this already - I hope I don't come across as condescending. TL;DR: the topology of these curves is quite different over finite fields. I first encountered what I consider cryptographically unhelpful drawings/intuition when I studied lattice-based cryptography. There's a whole field where a fundamental hard problem is finding the closest vector to a point not on the lattice. If you try and explain this by drawing a 2 or 3-dimensional example over the reals, anyone who's paying attention and proficient in Linear Algebra will ask themselves, why don't you just transpose the whole thing and then take the orthonormal projection? The problem is that in a finite field, unlike over the reals or complex numbers, orthogonal projection doesn't get you any closer to your target, so the intuition over R^2 is in my opinion very unhelpful to understand exactly why SVP/CVP are supposed to be hard, and indeed had me confused for a while until my professor pointed out I should forget "the silly drawing over R^2" which he didn't like either. For Elliptic Curve Cryptography, I find the example of a curve over the reals again misses the point of why exactly problems like DLOG are hard - for discrete-log based crypto at the 256-bit security level over finite fields, you need an about 15k bit modulus depending on which site you look at (NIST 2016 at keylength.com is a good place to start) due to speedups from Number Field Sieving etc. THis is the kind of structure that I mean you don't get. On EC, to get 256 bit security you need exactly 2 * 256 = 512 bits of key (slightly oversimplifying, the factor 2 is because you get the "sign of the y value" for free). The number 512 pretty much stands for the conjecture "there is no other cryptographically exploitable structure to take DLOGs over these Elliptic Curves". In fact it's not just "we haven't found any such structure" but there's an argument about heights of points (Miller '85 I think - though I'm pretty sure I've also read something by Koblitz on this) why on certain kinds of curves such structure is unlikely to exist. (Of course, other kinds of curves for fancy bilinear group stuff exist and do have more structure. And supersingular curves are another topic altogether.) The structure you obviously do get is a group, which you can extend to a vector space over the finite field so that (x \mapsto xP) is a linear function. The security property you want is roughly "you get this group, but only this group" (and the "sign", so add 1 extra bit to your keylength) and there is no useful concept of anything like points being close to each other, continuous maps in the usual sense etc. Plot the points on an EC over a small finite field and it looks like a random scatterplot rather than a neat and elegant curve - which is the whole point of using ECs over finite fields for DLOG-based crypto.

deleted 9y ago

[deleted]

tptacek 9y ago

So far, the best single-page elliptic curve primer for generalist programmers I know of is Adam Langley's: https://www.imperialviolet.org/2010/12/04/ecc.html https://www.imperialviolet.org/2010/12/04/ecc.html I understand the urge to try to get a high-level grok of curves without much math, but I spent years bouncing off the outermost surface of curve understanding by trying to start with the curve picture and the intuitive geometry of curve shape, and what finally made curves click for me (and quickly) was to simply take the curve equation --- which is itself high school math! --- and play with it a bit. So if you're a programmer and you want a baseline understanding how curves work, do what you'd do with any other subject you're trying to understand: pop open an editor, take the Weierstrass curve equation, pick a y, solve for x; then do it in a finite field (ie, mod a prime). Then write an "add", then a "scalar mult". It's a couple hours of noodling, tops. As always, but particularly with curves, remember that the basic understanding of what's going on is nowhere nearly enough to ever use them safely!

palisade 9y ago
The common advice of, "You'll never know enough to use them safely so don't bother trying, just trust us." that has been going around has been proven itself to weaken encryption. Just recently, an amateur programmer with very little background in cryptography discovered a flaw in libsodium in the Argon2 implementation and also in the reference implementation that everyone in the world was trusting without question. My advice is if you're an engineer, don't be afraid to write your own implementation of tried and trusted ciphers. This is how we find bugs and improve. This isn't the only trusted library or algorithm that has been shown flawed in recent times. The strength of your cipher implementation can be tested and proven. We need to stop telling everyone these algorithms are absolutely trustworthy so don't try understanding them or implementing them. Nothing ever advances or improves that way. Buck the trends, create competing libraries, try new things. The ancient ones were not all knowing, they were doing everything wrong. Their designs are full of flaws. Deny them. We need to code ourselves out of the coming cryptographic apocalypse. Do not hide your heads in the sand and hope the world doesn't come crashing down around you. Edit: I found the blog/website of the man I mentioned in this comment who discovered the Argon2 flaw. http://loup-vaillant.fr/articles/implemented-my-own-crypto http://loup-vaillant.fr/articles/implemented-my-own-crypto In his own words, "There's something worrying about this bug: I was the first to discover it, in January 2017. According to Khovratovich himself, it was two years old. Now I understand why the authors themselves didn't find it: unlike me, they didn't have a reference implementation to compare to. What I don't understand is, how come nobody else discovered this bug? If you implement Argon2 from spec, you cannot miss it. Test vectors won't match, and searching for the cause will naturally lead to this bug. I can draw only one conclusion from this: I'm the first to independently re-implement Argon2. This 'never implement your own crypto' business went a little too far."

wildchild 9y ago

Also good reading https://steemit.com/monero/@luigi1111/understanding-monero-cryptography-privacy-introduction https://steemit.com/monero/@luigi1111/understanding-monero-c...