Nigel Smart's Cryptography Made Simple is a great book which covers elliptic curve cryptography amougst many other topics; despite its name it's a very technical book, but it's easily accessible to anyone with a CS/EE/Maths/Physics degree.
Agreed. Also Christof Paar's book [1] and 25-episode YouTube series[2] do an excellent job of explaining not only elliptic curve cryptography, but also RSA and a lot of other cryptography, including symmetric ciphers and cryptographic hash functions.
The blog post seems to be essentially, "I read these good posts on Ars [3] and F5 [4] [5] and here is my summary of my understanding of them". Nothing wrong with that, but the post has some issues and doesn't add anything to the sources cited IMO.
Fun fact: elliptic curves (specifically the Taniyama–Shimura conjecture about their relationship to modular forms) played a key role in Wiles' proof of Fermat's Last Theorem, one of the most famous problems in mathematics.
Those who seek to go a step further and actually implement elliptic curves should see the ECC Hacks talk by djb and Tanja Lange: https://www.youtube.com/watch?v=vEt-D8xZmgE
A couple claims there are a little outdated (we now have better ways of dealing with short Weierstraß curves), but the advice there is sound.
> we now have better ways of dealing with short Weierstraß curves
We do? The complete Renes/Costello/Batina formulas for point addition are significantly slower at a factor of 1.4.[1] The complete formulas presented by Hamburg are still somewhat slower than what you can get on twisted Edwards and almost certain to be patent encumbered by the end of the year.[2] Did I miss something?
SafeCurves discounts Renes/Costello/Batina and the like because “many of these formulas are considerably slower and more complicated than standard incomplete scalar-multiplication formulas, creating major conflicts between simplicity, efficiency, and security”.[3]
Correct, but my point was that even if they're slower, we do have complete formulas that aren't the nightmare djb describes.
I do reckon however that having to chose between speed and safety is a big problem. Someone is bound to go the fast route and screw up some special case, or leak timing information.
I didn't know about possible patents, that sucks. (I live in the EU though, so I can still give them the finger if I need to.)
In any case, the best general purpose thing we have now is probably Decaf/Ristretto over (twisted) Edwards curves. Fast complete formulas and a prime order group. Dealing with the cofactor is not too hard, but it's not trivial either: http://loup-vaillant.fr/tutorials/cofactor
(I still love Montgomery curves for variable base scalar multiplication.)
> I didn't know about possible patents, that sucks. (I live in the EU, though, so I can still give them the finger if I need to.)
Hamburg made this IP risk pretty clear in the paper, for a bit more context on it, see [1]. Because in the U.S. you have a full year before you even need to file a patent after publishing, we'll still have to wait and see if Hamburg's employer files a patent on his method. If they don't, nice; if they do, fucking hell this is why we can't have nice things. Renes/Costello/Batina is unencumbered as far as I know.
I have no idea. I'm self taught, and I tend to limit myself to implementation techniques. My tutorials on the subjects are mostly implementation focused:
If you want a to get this stuff into your head reasonably fast, go implement a curve. Then do it again, but in Rust (or C) and in constant-time. Then do it again, but actually computationally efficiently (i.e. optimize the hell out of a Rust or C implementation once it works). Choose a different curve each time. Then go and cook your own curve for shits and giggles.
You may easily spend a year upwards on this, but by the time you're done, you've basically run into every resource worth knowing about and are able to decently reason about elliptic curves (but by no means are in a position to write papers still).
Basically, doing this now. I tried to implement x25519 in a highly optimized way in cpp/c and I’m in my 8 month. I dogged through countless of articles and learned a ton of abstract algebra. Though, I still feel like a beginner in this field.
I’ve done a few hard projects in my career (compilers, and graphic editor). And I think implementing a elliptic curve in a optimized way, without a math library, must be one of the hardest thing in programming.
Images (at least now) link to an ArsTechnica article [0] written by Nick Sullivan, the same person who wrote said blog post (the article and CF's blog post are the same thing, with ArsTechnica going up a day later).
Cool stuff. I wrote a similar post explaining and implementing RSA in python on Colab[0]. I did NOT leave the math out because that was the most exciting part that I enjoyed while studying RSA. Maybe you'd wanna make a similar implementation for fun for ECC.
I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times?
Otherwise, determining n given A and an end point would just be a matter of iterating from A until you hit the end point and counting, right?
Also, how do you actually use the keys to encrypt/decrypt?
> Also, how do you actually use the keys to encrypt/decrypt?
One of the changes in modern cryptography compared to stuff from the 1990s is that we rarely have cause to use public key encryption at all.
A typical modern design uses a key agreement algorithm to choose a large shared secret known to both parties which is then used to do encryption with symmetric algorithms.
The elliptic curves show up in the key agreement algorithm and in a Digital Signature scheme used after the encryption switches on to prove who you really are, but we often don't use them to actually encrypt anything (and so likewise we don't use them to decrypt anything either).
Sure, fine, but even in RSA signing there's some message you transform with one of the keys and then undo the transformation with the other key (the transformation is encryption when the first key is the public key, and signing when the first key is the private key). I just mean, given these EC keys, how do you actually apply them to data?
I mean, firstly, no. What you're describing is what we call "Textbook RSA" and that's a classroom exercise rather than a technology you should use in practice - it's unsafe. Perhaps more importantly while you can (almost) do this in RSA you really can't do it with something like Curve25519.
As a classroom exercise you can use RSA to encrypt the message "I like toast". You turn "I like toast" into a big number. Using a public key you do the (textbook) RSA operation and out comes a different big number. The recipient uses the private key to get the first big number back - and it translates as "I like toast". Nobody did that in real crypto systems, even in the 1990s, and the way you'd do it as a classroom exercise is inherently unsafe, but you can watch it being done and it's somewhat helpful in understanding RSA.
Nothing like that is usually done with elliptic curves.
Fortunately we didn't want to send a message like "I like toast" with public key crypto anyway, we always actually want to agree symmetric cryptographic keys.
What's the difference? The key agreement protocol doesn't let you choose the message. Alice and Bob will definitely agree on some shared key at the end of the protocol, but neither Alice nor Bob can choose what it is. For a key this doesn't matter, indeed it's arguably desirable to use random keys nobody actually picked, lots of things to like about that outcome.
> I mean, firstly, no. What you're describing is what we call "Textbook RSA" and that's a classroom exercise rather than a technology you should use in practice - it's unsafe.
? I'm not talking about encrypting data with RSA, but how else do you perform signing with RSA except by using the private key to transform some message that can then be verified with the public key?
I see now the article's trying to describe elliptic curve Diffie-Hellman, which makes much more sense (but makes the comparison to RSA in the article confusing...)
There is, but it's not a special operation: it's called scalar multiplication and it's just a lot of grouped additions.
If you want 13P you do
2P = P + P
4P = 2P + 2P
8P = 4P + 4P
12P = 8P + 4P
13P = 12P + P
To use this for encryption you do a Diffie-Hellman operation, where A and B pick secrets a and b, send each other a x G and b x G, and compute the shared secret a x b x G = b x a x G. (Where G is a standard point.)
You can call "b x G" the public key and do ephemeral-static DH if you are not doing a key exchange between two online peers.
Oh, I see, we're just doing Diffie-Hellman but with elliptic curves? Ok, that makes much more sense... it was confusing for the article to compare it with RSA instead of vanilla Diffie-Hellman.
> I'm assuming that given a starting point A and a number of operations n, there's a much faster way of computing the end point than just iterating n times?
Yes, this is in fact the basis of the cryptographic security. There's a way to iterate the generator whatever number of times, fast. This is called multiplication, just like there's a way to multiply arithmetic numbers in school without adding over and over.
The thing is it isn't quite so easy given the starting point and the result what you multiplied by.
Right, but while most people understand multiplication, it doesn't seem clear how to efficiently perform repeated application of the dot operation. I'm guessing the operation is associative, which lets you do it fast.
Basically, adding point to itself n times requires O(log(n)) operations. That's how you can have n be as big as 2^255 or 2^448.
So yeah, you can still count back, but I'm not sure you'll be done before the heat death of the universe. There are better attacks than that, but they're still O(sqrt(n)), which is exponentially bigger than the O(log(n)) required for legitimate uses.
> I'm not sure you'll be done before the heat death of the universe
According to [0], the Stelliferous Era alone will last ~3 zettaseconds, which at a best already achieved clock rate of 12 attoseconds gives ~2^127 cycles, easily enough to break common 128-bit-'secure' cryptography with good probability on a single, serial computer.
Checking [1], converting the Virgo Supercluster into sand-grain-sized computer cores would give parallelism on the order of 2^170, enough to break 297-bit security ratings with certainty, and uncomfortably cut into even 384-bit security.
> as big as 2^255 or 2^448.
448-bit security (not 448-bit elliptic curves, but 896-bit curves) is probably okay, despite that these are still fairly underestimated[2] limits - you get better (smaller) limits based off dissipating waste heat at CMB temperatures, so even 384-bit security might be safe in practice.
These are all rather off-the-cuff estimates (read, I looked up the largest and smallest plausible-sounding numbers and divided them), but it's rather disturbing that most people don't even seem to think to wonder "what if the adversary was willing/able to sink a significant fraction of the mass and lifespan of the universe into breaking this cryptography?", much less keep semi-exact numbers handy when estimating security margins.
2: 2^127 and 2^170 are both fairly achieveable (ie underestimated) individually, but dismantling all the stars you can access to build computers raises the question of how you're then going to power those computers, so I'm not sure just multiplying them together to get 2^297 actually works.
> ould just be a matter of iterating from A until you hit the end point and counting, right?
Yes, you could brute-force all the points. The good thing is, ECC is done on fields that are very large, so that actually enumerating them is not practical. Check out Curve25519[1] for some numbers.
Right, but the point is that doing the transformation in one direction needs to be fast in order of the scheme to be viable. So there must be some faster way of doing n iterations, which the post doesn't mention.
On an unrelated note, DKIM's latest RFC includes ed25519-sha256 but nobody is actually accepting a properly signed email using this signature algorithm. Bummer
That would be RFC8463 "A New Cryptographic Signature Method for DomainKeys Identified Mail (DKIM)" [0]
The biggest improvement on using EC over RSA in DKIM is that the public key will fit in a single DNS TXT rr.
The problem here is that email servers are often horribly outdated, so don't expect widespread adoption of the new RFC anytime soon.
The suggested transition method would be include both a EC and RSA signature in the email, and publish both keys under separate selectors. The receiver should ignore the EC signature if it doesn't support it, and when it is supported the receiver should only use the EC signature. However, it wouldn't surprise me of this is going to be poorly implemented and you'll en up with the receiver validating both signatures, thus performing multiple DNS lookups.
I'm planning on doing a write-up about support for RFC8463 in popular email services.
Disclaimer: Founder of an email hardening service.
I wanted to point out this thing because I'm in the middle of migrating my mail server and wanted to improve the whole setup by using chasquid and a set of dkim tools [1] that I've forked an improved to include ed25519-sha256. Unfortunately pretty much nobody has implemented RFC8463 yet, and my DNS provider doesn't allow me to use RSA 2048bit DKIM keys because they have a stupid limit on the TXT field value :(
You shouldn't rely on only ed25519 for DKIM, always double-sign your email with RSA as a fallback
The problem with email will forever be that there are so many badly configured email servers out there. Any new standard in email will always need a backwards compatibility ad infinitum.
In your case I'd recommend moving your DNS to another DNS provider. Just pick any and go with that.
I finally get it now. I feel like "public key" is a misnomer. It's really a "public safe". You put something in the public safe and then it's locked. Then only the person with the private key can unlock it.
I don't know much about Cryptography but this article made me want to ask this:
In his example with facebook and trump, the original handshake to get facebook's public key isn't encrypted, isn't that a problem ?
I may be totally not understanding this at all, but lets say when somebody connect to Tor if the original connection isn't encrypted and everybody know that I just connected to Tor isn't that bad even though they can't tell what I'm doing afterward ?
That example used is a bit weird and I'm not sure it really motivates the rest of the article well.
Encryption can deliver a variety of desirable features, and which you need in particular occasions will vary.
For example for getting Facebook's public key you would certainly care about Integrity - the key you received should be the one sent, and about Authenticity - you want to get an answer from Facebook and not the CIA or your kid sister but you may not care about Confidentiality - maybe it doesn't matter to you who knows what you asked, and as a Public key it isn't important to Facebook who knows what it is.
Tor itself is not designed to ensure that people can't tell you are using Tor. Its purpose is to ensure adversaries, including an adversary who controls some Tor nodes, can't tell what information you are sending and receiving and who you are sending it to/ receiving it from.
Hiding Tor usage from a sophisticated adversary is difficult, technologies such as ScrambleSuit and OBFS try to help you do this, but it can be difficult to assess how well they work unless the adversary is actively blocking you. Perhaps they know exactly what you're doing but are choosing not to intervene?
I down voted the other responder. Because Trump is using public key to encrypt the message. You can share your public key as much as you want and people will be able to send you messages that only you(owner of private key) can decrypt. There is no problem. That is normal use of public key to send encrypted messages to the owner of private key.
You can do it also the other way around, encrypt data with private key and only people who have your public key will be able to decrypt it. Which is a bit less useful but it can confirm your identity. So they can be sure that you sent the message.
Composite order attacks: things that are prime tend to be hard to attack. If your curve doesn’t use prime stuff then you can take the factors of the thing and attack it in little groups.
Anomalous curves: elliptic curves have a total number of points. We call that the order. So does the “field” (kinda like a box) that the curve lives in. If the number of elements in the field and the number of elements in the curve are the same, you can kinda “lift” the curve out of its box and put it in another box that’s easier to smash it in. :)
When coming here to comment, it's best to react to the most interesting thing, not the most provocative thing. Otherwise we tend to get a chain-reaction of provocations, as one commenter gets provoked by another's provokedness, and frequently an entire thread ends up burning itself on what was not even a tertiary point.
That doesn't mean it wasn't provocative, just that a community like this needs its members to work on core strength, so we can keep this place functioning for curious conversation.
I don't know, I liked it for being relevant and showing a real use case. Politics is a good example because if it was like grocery stores or something, it would be easy to conclude, I guess if you're paranoid okay but that sounds like overkill for such a modest use case. Basically for 'enterprise' but not for me.
In reading this I thought, yes I'm sure FaceBook wants a secure fast way to communicate with high-value users, that's a good example, and also something real-life people would want to corrupt. They could've used "Ambassador of Country A would like to send a message to Ambassador of Country B" but that would've made it seem like something only high level infosec types would care about; this made it seem topical to me.
And as it happens, as a US resident, I can confirm the example wasn't sensationalized - that's something that would realistically be posted in that situation, without exaggeration or underhanded commentary.
Yeah, maybe it's just the fact that things are particularly tense here at the moment, but the choice of example definitely adds some extra baggage that wasn't necessary. For me personally it interferes a bit with my ability to simply read and enjoy the post.
Just read the original Ars Technica article he "borrowed" all the images from. It's a great article I've referred back to many times; it's better-written and still easy to understand for those not familiar w/ the concepts.
You can grab a copy from SpringerLink for free at the moment here: https://link.springer.com/book/10.1007%2F978-3-319-21936-3