6 ms·
Elliptic Curve Cryptography: A Basic Introduction
- quantumcrypt 5y agoAnyone 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 5y agoThe 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)!
- mypastself 5y agoThis 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 5y agoAgree, the book "Programming Bitcoin" by Song provides a detailed explanation of the algorithm.
- ineiti 5y agoPoint 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 5y agoReading 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 https://knowyourmeme.com/memes/how-to-draw-an-owl
- ghoshbishakh 5y agoI learned about EC from Craig Costello's book on pairings. Amazing read with concrete examples. https://www.craigcostello.com.au/tutorials https://www.craigcostello.com.au/tutorials
- palata 5y agoI 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 5y agoOh 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 5y agoInstead 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.
- quenix 5y agoAs 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-cryptography-a-gentle-introduction/ https://andrea.corbellini.name/2015/05/17/elliptic-curve-cry...
- kebman 5y agoI 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 5y agoThis is a lot better, thanks!
- cgshep 5y agoIt'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-protecting-against-quantum-computer-attacks/?ftag=COS-05-10aaa0g&taid=6254b2f12c26f70001946bff&utm_campaign=trueAnthem%3A+Trending+Content&utm_medium=trueAnthem&utm_source=twitter&fr=operanews https://www.zdnet.com/article/openssh-now-defaults-to-protec...
- akvadrako 5y agoThis 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.
- adgjlsfhk1 5y agoalso, elliptic curves are much more vulnerable to quantum attacks than regular rsa since it uses smaller keys.
- politelemon 5y agoI 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 5y agoIsn't coherence time the big challenge?
- dmlerner 5y agoI imagine it's a similar tradeoff - with more qubits there are more interactions, ergo lower coherence time
- IYasha 5y agoAsymmetric 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 5y agoI saw that analogy in Simon Singh's The Code Book and found it very helpful.
- legutierr 5y agoLately I've been looking for a good book introducing zero-knowledge proofs. Would anyone here have any recommendations?
- Anunayj 5y agoit is posts like these I sometimes want a reminder for, does HN have a !remindme equivalent of reddit? P.S. I'm just making this comment so I can keep a track of this.
- jedberg 5y agoA 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.
- not2b 5y agoThey 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.
- jjoonathan 5y agoHa. 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.
- lamontcg 5y agoIs 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).
- Robotbeat 5y agoUsually 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.)
- lamontcg 5y agoYeah that's where I should have taken abstract algebra in college (I did get up to graduate level QM though in physics).
- less_less 5y agoNot 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.