[HN Gopher] Elliptic Curve Cryptography: A Basic Introduction
___________________________________________________________________
Elliptic Curve Cryptography: A Basic Introduction
Author : wagslane
Score : 162 points
Date : 2022-04-15 14:21 UTC (8 hours ago)
(HTM) web link (blog.boot.dev)
(TXT) w3m dump (blog.boot.dev)
| palata wrote:
| I don't get the trap problem here. So I start with A, compute -B
| as A dot A, then continue my way until I decide to stop at E. So
| I had to compute the whole path, right?
|
| Now you give me A and E, why can't I just compute the path from A
| until I hit E? That looks like the same effort, so what did I
| miss?
| palata wrote:
| Oh that's actually the point of the exponentiation trick: I
| choose the private key first and then compute the path from it.
|
| Got it, sorry xD
| quantumcrypt wrote:
| Instead of computing nA = A + A + ... + A you can use the
| "exponentiation" by squaring trick: nA = (n/2)A + (n/2)A +
| (n%2)A. It takes logarithmically many steps.
| quantumcrypt wrote:
| Anyone know of an accessible intermediate resource on ECC? There
| are many blogs talking about the basics of point addition , but
| hardly anything approachable that talks about different curve
| properties, what makes a curve safe, how to break vulnerable
| curves, and how to prove properties, etc.
| ghoshbishakh wrote:
| The properties of curves make certain protocols safe/unsafe in
| my opinion. For example some curve might be a good choice for
| BLS while being very bad for ECDSA. Therefore the choice of the
| curve is really tied to the encryption/signature scheme I
| think. I am not an expert though. Contact the cryptographers
| they are really friendly (not a sarcasm)!
| IYasha wrote:
| Asymmetric encryption learning would be a lot quicker if they'd
| call public keys "locks". Maybe not very accurate, but when I
| heard the word once, I immediately understood the whole concept,
| easily.
| mikepurvis wrote:
| I saw that analogy in Simon Singh's The Code Book and found it
| very helpful.
| mypastself wrote:
| This is indeed basic. Half the article explains public key
| cryptography, the other gives a basic overview that omits key
| details, such as the purpose of reflection, and how the curve can
| get combined with finite fields in practical applications
| (although point 2 does partly address this aspect). Not a bad way
| to get a general intuition of the algorithm, but not overly
| useful, either.
| Sherlock wrote:
| Agree, the book "Programming Bitcoin" by Song provides a
| detailed explanation of the algorithm.
| ineiti wrote:
| Point 2 is a simplification that borders on wrong: you don't
| "wrap around if it's too big" - the point operation will always
| cross the curve (except for the zero point)!
|
| You "wrap around" because you're using a finite field. As far
| as I understand, the finite field of the scalars allows you to
| have an inverse for the multiplication, and the finite field of
| the points is there to make the calculation easier.
| magicalhippo wrote:
| Reading the article, it reminded me of the "how to draw an owl"
| meme[1].
|
| Not quite as bad but, I didn't really get any good insight in
| how ECC works.
|
| [1]: https://knowyourmeme.com/memes/how-to-draw-an-owl
| quenix wrote:
| As some others have pointed out, this is very basic stuff, but a
| good introduction. I have found this series of blog posts [0] as
| a super useful explanation of ECC that starts with the basics but
| covers the math and underlying group theory well, building up to
| an intermediate-level understanding of the matter.
|
| [0] https://andrea.corbellini.name/2015/05/17/elliptic-curve-
| cry...
| kebman wrote:
| I remember making inputs into Desmos or some similar graphing
| package. Gave some pretty interesting and surprising results in
| that the whole thing broke apart into something more akin to
| noise. If I indeed did it correctly, then it makes a lot of
| sense.
| edflsafoiewq wrote:
| This is a lot better, thanks!
| lamontcg wrote:
| Is ECC at all mathematically related to Kepler's equation?
| (although now that i look at it, I'm not confident that is a
| trapdoor function because while its much easier to code one way
| than the other, the sin function itself needs an iterative
| approximation).
| less_less wrote:
| Not really. Elliptic Curves are only distantly related to
| ellipses. You can soooorta do the same thing with an ellipse
| instead, but it's not nearly as secure.
| Robotbeat wrote:
| Usually need lossless integer math for cryptography to work. So
| the form might be similar, but you're working over finite
| fields (ie of integers mod some number), not real numbers.
|
| (Okay, I have only a tenuous understanding of this myself. I'm
| a physicist, not a mathematician! Mathematicians are
| intimidating.)
| legutierr wrote:
| Lately I've been looking for a good book introducing zero-
| knowledge proofs. Would anyone here have any recommendations?
| cgshep wrote:
| It's important to note that most ECC is _not_ quantum-resistant
| and will be obsoleted in the coming years following completion of
| NIST 's post-quantum cryptography competition.
|
| Indeed, OpenSSH recently enabled PQC by default (NTRU Prime over
| X25519) [1]. ECC has, at best, a short-to-medium term lifespan
| right now.
|
| 1. https://www.zdnet.com/article/openssh-now-defaults-to-
| protec...
| xiphias2 wrote:
| I just recently played with an online quantum computer
| simulator to get a better understanding of how quantum fourier
| transform works, it's a lot of fun:
|
| https://algassert.com/quirk
| adgjlsfhk1 wrote:
| also, elliptic curves are much more vulnerable to quantum
| attacks than regular rsa since it uses smaller keys.
| politelemon wrote:
| I wouldn't say more vulnerable necessarily -- it requires
| fewer qubits, but requires larger coherence time. RSA
| requires more qubits and drastically less time. They're both
| vulnerable in different ways.
| eternityforest wrote:
| Isn't coherence time the big challenge?
| dmlerner wrote:
| I imagine it's a similar tradeoff - with more qubits
| there are more interactions, ergo lower coherence time
| jjice wrote:
| I'm very excited to see the results of the post-quantum crypto
| competition. Most of it is above my head, but it's neat to read
| about lattice problems. Asymmetric cryptography in general is
| incredible to me.
| KMag wrote:
| I have a mind to write a PQC daemon to negotiate/rotate
| WireGuard pre-shared keys. Even though WireGuard uses 3-way
| ECDH using Curve25519, with a 256-bit pre-shared key, an
| attacker will either need 2^128 work using Grover's quantum
| search algorithm or else find statistical flaws in ChaCha20.
|
| That way, you keep the post-quantum crypto out of the kernel,
| and if done carefully by hashing together PQC, ECDH, and a pre-
| shared-pre-key to generate the pre-shared key, it would be
| easier to demonstrate that it's no weaker than WireGuard. If
| the daemon removes and forgets the negotiated pre-shared-keys
| after 24 hours, then against classic attackers you'd still have
| perfect forward secrecy, and against quantum attackers you'd
| have 24-hour forward secrecy (assuming no statistical flaws in
| ChaCha20).
| acchow wrote:
| Depends on how quickly quantum computer size grows? We don't
| seem to have anything resembling a Moore's Law yet
| als0 wrote:
| The Cloud Security Alliance is assuming something powerful
| enough shall exist in under 8 years.
|
| https://cloudsecurityalliance.org/press-
| releases/2022/03/09/...
| akvadrako wrote:
| This assumes people consider practical million qubit quantum
| computers relevant. They might actually be impossible or close
| to it, i.e. millions of years away.
|
| I'd say by far the most important thing will stay resistance to
| unknown classical algorithms, at least until trends change.
| tooltower wrote:
| AFAIK post-quantum crypto all has larger key sizes and much(?)
| worse performance. Has that changed? If not, I don't see ECC
| becoming obsolete any time soon.
| marcelluscat wrote:
| I thought ring-lwe was pretty good. It's at least very
| embarrassingly parallel
| less_less wrote:
| They're all worse in terms of size and/or speed, but not
| disastrously so.
|
| Ring-LWE is faster than ECC, but has keys and ciphertexts
| of 600+B instead of as few as 32 B (for eg curve/ed25519).
| NTRU is pretty similar, with slower key generation and
| slightly smaller ciphertexts. If you go to the bleeding
| edge, you might be able to cut these to 300-400 bytes with
| severe compromises in eg error rate and security margin.
| There are also structured code-based systems with fairly
| similar sizes to the Ring-LWE ones, but they aren't
| finalists.
|
| McEliece is fast to encrypt and decrypt and has small
| ciphertexts (as few as 128 bytes), but has enormous public
| keys (multi-hundred KB) that are also slow to generate. The
| biggest benefit of McEliece is that we're pretty confident
| it will hold up to analysis.
|
| SIKE (an alternate) has reasonable keys and ciphertexts
| (200-250 B) but is pretty slow, on the order of 5ms on a
| laptop for the smallest parameters. The bleeding-edge CSIDH
| is much slower, but has even smaller keys, but we can't be
| at all confident that CSIDH is secure.
|
| On the sig side, Falcon is fast but extremely complicated,
| and has as low as ~660B sigs. Its main competitor,
| Dilithium, is modestly slower and larger, and also
| significantly simpler. The much more conservative SPHINCS+
| is very slow and produces ~8kB sigs.
| eternityforest wrote:
| We will probably just see more tricks like computing keys
| from random seeds and storing cached key exchanges, and AMP
| style clickbait accelerators to funnel stuff through CDNs you
| already have the key for(Assuming the EU lets us do that....)
| ghoshbishakh wrote:
| I learned about EC from Craig Costello's book on pairings.
| Amazing read with concrete examples.
|
| https://www.craigcostello.com.au/tutorials
| jedberg wrote:
| A funny story related to ECC: I was hanging out with a friend of
| mine about 10 years ago, and I was asking him what he was
| researching (he is a math professor in Colorado). He told me he
| was researching Ecliptic curves and their properties. So I said,
| "oh you must be really interested in elliptic curve cryptography
| then!" and he said, "what's that?".
|
| He was so deeply into math theory that he hadn't even looked at
| or cared about the practical applications of his work.
| jjoonathan wrote:
| Ha. I have a similar story with chemistry/spectroscopy and
| representation theory.
|
| I was taking a chemistry class where we were learning by rote
| how to apply the Grand Orthogonality Theorem. We were clearly
| computing inner products, but I couldn't suss out the big
| picture and the chem professor didn't know either, so I went to
| the math department and joined a seminar, which happened to be
| almost nextdoor to the chemistry class. The professor teaching
| it had never heard of the applications to
| chemistry/spectroscopy, though he was delighted to find out.
|
| Not 30 yards apart, two groups of people were approaching the
| same subject from opposite angles with zero awareness of each
| other.
|
| Silos are amazing.
| not2b wrote:
| They form a key part of Wiles' proof of Fermat's Last Theorem
| as well as in efforts to unify very disparate parts of
| mathematics, they aren't just for cryptography.
___________________________________________________________________
(page generated 2022-04-15 23:00 UTC)