[HN Gopher] Basic Intro to Elliptic Curve Cryptography (2019)
___________________________________________________________________
Basic Intro to Elliptic Curve Cryptography (2019)
Author : lanecwagner
Score : 236 points
Date : 2020-05-31 15:07 UTC (7 hours ago)
(HTM) web link (qvault.io)
(TXT) w3m dump (qvault.io)
| svnpenn wrote:
| 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.
| seesawtron wrote:
| 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.
|
| [0]
| https://colab.research.google.com/drive/1ccyVKHHXFczk_3u5WoV...
| staycoolboy wrote:
| Very cool. I would love an ELI5 why some curves are more or less
| secure than others (e.g. p256r1 is the hot curve now, but why?)
| p0llard wrote:
| 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.
|
| 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
| ykevinator wrote:
| I second this m
| loup-vaillant wrote:
| 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 Weierstrass curves), but the advice
| there is sound.
| beefhash wrote:
| > _we now have better ways of dealing with short Weierstrass
| 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]
|
| [1] https://cryptojedi.org/papers/complete1-20191011.pdf
|
| [2] https://eprint.iacr.org/2020/437
|
| [3] https://safecurves.cr.yp.to/complete.html
| loup-vaillant wrote:
| 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.)
| beefhash wrote:
| > _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.
|
| [1] https://www.reddit.com/r/crypto/comments/g46pft/_/fnwp9
| p2/?c...
| vmception wrote:
| What class would one take to understand this?
|
| I had a cryptography elective I wanted to take in undergrad but
| it was in the wrong semester.
| beefhash wrote:
| 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).
| tinganho wrote:
| 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.
| lordnacho wrote:
| Probably more than one class, but I ran into it in a descrete
| math course at the end of uni.
| loup-vaillant wrote:
| 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:
|
| http://loup-vaillant.fr/tutorials/fast-scalarmult
|
| http://loup-vaillant.fr/tutorials/cofactor
|
| http://loup-vaillant.fr/tutorials/128-bits-of-security (This
| one is more about choosing your primitive than implementing
| it.)
|
| If you want to get started in cryptography in general, I can
| recommend 2 sources: Dan Boneh's course, and crypto101 by
| lvh:
|
| https://www.coursera.org/learn/crypto
|
| https://www.crypto101.io/
| denysvitali wrote:
| 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
| LeonM wrote:
| 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.
|
| [0] https://www.rfc-editor.org/rfc/rfc8463.html
| denysvitali wrote:
| 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 :(
|
| [1]: https://github.com/denysvitali/dkim
| anothermoron wrote:
| 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 ?
| tialaramex wrote:
| 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?
| ozim wrote:
| 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.
| sage3 wrote:
| I can't even escape US internal politics on a cryptography blog
| julianeon wrote:
| 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.
| dang wrote:
| 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.
|
| https://news.ycombinator.com/newsguidelines.html
| JshWright wrote:
| 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.
| irontoby wrote:
| 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.
|
| The ECC-specific content begins on page 2.
|
| https://arstechnica.com/information-
| technology/2013/10/a-rel...
| [deleted]
| alecbenzer wrote:
| 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?
| tialaramex wrote:
| > 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).
| alecbenzer wrote:
| 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?
| FiloSottile wrote:
| 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.
| alecbenzer wrote:
| Ah ok, so the dot operation is associative I guess?
|
| ---
|
| I mean, once you have the keys, how do you actually use them
| to transform data?
| loup-vaillant wrote:
| I have compiled many fast methods in detail here: http://loup-
| vaillant.fr/tutorials/fast-scalarmult
|
| 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.
| a1369209993 wrote:
| > 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.
|
| 0: http://en.wikipedia.org/wiki/Orders_of_magnitude_(time)
|
| 1: http://en.wikipedia.org/wiki/Orders_of_magnitude_(mass)
|
| 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.
| lordnacho wrote:
| > 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.
| alecbenzer wrote:
| 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.
| neikos wrote:
| > 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.
|
| [1]: https://en.wikipedia.org/wiki/Curve25519
| alecbenzer wrote:
| 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.
| blargmaster33 wrote:
| Next time do not insert you TDS in your tech article.
| techman9 wrote:
| It looks like several of the images in this post are taken
| (without credit?) from Cloudflare's primer?
| https://blog.cloudflare.com/a-relatively-easy-to-understand-...
| [deleted]
| lordgrenville wrote:
| The Ars Technica article linked in the article is much better-
| written and more comprehensive.
| https://arstechnica.com/information-technology/2013/10/a-rel...
|
| 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.
| nbardy wrote:
| Yea. This article just hijacks all the graphics from the ars
| technica article and makes it harder to read.
___________________________________________________________________
(page generated 2020-05-31 23:00 UTC)