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.
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.
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:
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).
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.
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....)
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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)!
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?
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.
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.
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.)
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.
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...