Elliptic Curve Cryptography: A Basic Introduction | Hacker News Reader

Elliptic Curve Cryptography: A Basic Introduction

blog.boot.dev

215 pointswagslane40 comments

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...

also, elliptic curves are much more vulnerable to quantum attacks than regular rsa since it uses smaller keys.

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.

Isn't coherence time the big challenge?

I imagine it's a similar tradeoff - with more qubits there are more interactions, ergo lower coherence time

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

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.

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.

I thought ring-lwe was pretty good. It's at least very embarrassingly parallel

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.

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....)

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).

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.

Depends on how quickly quantum computer size grows? We don't seem to have anything resembling a Moore's Law yet

The Cloud Security Alliance is assuming something powerful enough shall exist in under 8 years.

https://cloudsecurityalliance.org/press-releases/2022/03/09/...

But their job is to figure the realistic worst case I.e fastest plausible timeoine. Not the most likely / expected time it will take.

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...

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.

This is a lot better, thanks!

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.

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.

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.

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.

Agree, the book "Programming Bitcoin" by Song provides a detailed explanation of the algorithm.

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.

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

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.

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)!

Lately I've been looking for a good book introducing zero-knowledge proofs. Would anyone here have any recommendations?

it 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.

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?

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

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.

I learned about EC from Craig Costello's book on pairings. Amazing read with concrete examples.

https://www.craigcostello.com.au/tutorials

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.

I saw that analogy in Simon Singh's The Code Book and found it very helpful.

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).

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.)

Yeah that's where I should have taken abstract algebra in college (I did get up to graduate level QM though in physics).

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.

Reply on news.ycombinator.com