[HN Gopher] (Very) Basic Intro to Elliptic Curve Cryptography
___________________________________________________________________
(Very) Basic Intro to Elliptic Curve Cryptography
Author : wagslane
Score : 123 points
Date : 2021-02-14 17:33 UTC (5 hours ago)
(HTM) web link (qvault.io)
(TXT) w3m dump (qvault.io)
| nathanfig wrote:
| Does the EC function provide any guarantees around how often a
| given endpoint can be hit? e.g. over the course of infinite hops
| starting at point a, how frequently will point b be landed upon?
| ragona wrote:
| This post leaves out a key difference between something like RSA
| and EC, which is that EC doesn't actually provide an encryption
| function. You end up using an integrated encryption scheme.
|
| https://en.m.wikipedia.org/wiki/Integrated_Encryption_Scheme
|
| This is intuitively similar to how TLS works, in which asymmetric
| concepts are used in conjunction with a KDF and hashing algorithm
| to agree upon a per-session symmetric key.
| tialaramex wrote:
| > This is intuitively similar to how TLS works
|
| How TLS 1.3 works.
|
| This way of proceeding was introduced earlier, but wasn't the
| only option until TLS 1.3, in TLS 1.2 for example, even though
| chances are any TLS 1.2 sites you run offer a more modern
| Elliptic curve scheme, it was mandatory to implement
| TLS_RSA_WITH_AES_128_CBC_SHA.
|
| For TLS_RSA_WITH_AES_128_CBC_SHA (and many other schemes) RSA
| is being used to transport the session keys chosen by the
| client (and thus implicitly authenticate the server). This
| means if an adversary gains possession of the server's RSA
| private key, even perhaps several _years_ later, that 's enough
| to decrypt the session key and thus decrypt all messages that
| adversary might have captured before.
|
| Whereas with the schemes using Ephemeral Diffie Hellman
| (whether conventional or elliptic curve) once those ephemeral
| values are discarded going forward the only way to decrypt the
| messages secured by them would be something like Shor's
| algorithm to break DH, hence the term "Forward Secrecy".
| some_furry wrote:
| The fact that ECC doesn't provide an encryption function is
| actually a feature, in my opinion:
|
| It's impossible to accidentally encrypt a message with the
| asymmetric cryptographic primitive in the ECC case, but not in
| the RSA case. This makes ECC misuse-resistant in a way that RSA
| isn't.
|
| (Although, strictly speaking, you can "encrypt directly" with
| elliptic curve schemes if you use ElGamal--which might even be
| desirable in weird systems. Fortunately, most high-level
| cryptography libraries that offer ECC don't expose the APIs to
| facilitate this.)
| ddoolin wrote:
| Cool intro, I had no idea about ECC. However something is a bit
| lost on me: if the number of hops is the "private key" in this
| scenario, couldn't you just hop until you've found the endpoint?
| What makes this particularly difficult?
| hoppla wrote:
| I am also puzzled by this, and if the number is hops is so
| large that it's unfeasible to enumerate, how does the key
| generator know many hops it should be...
| ufo wrote:
| I remember watching a presentation by Tanja Lange and djb
| that explained that kind of thing very well. It starts with
| easy to visualize examples using "clock crypto" and then
| transitions to real ECC curves.
|
| https://media.ccc.de/v/31c3_-_6369_-_en_-
| _saal_1_-_201412272...
| hoppla wrote:
| Thanks, that was a truly good talk
| dan-robertson wrote:
| The number may be very large (think: much bigger than 2^64).
| The reason it's possible to compute these in logarithmic time
| (ie linear in the number of bits of the key) is the same reason
| that it is possible to compute a^b (mod c) even when b is very
| large: there are operations in elliptic curves akin to
| multiplying and squaring so a^(2 _b_1 + b_2) = a^(b_2)_
| (a^2)^(b_1) can have the cost of computing a^(b_1) (say b_1 is
| 0 or 1, so this is constant), the cost of a multiply
| (constant), the cost of a square (constant), and the cost of an
| exponentiation of a number with one less bit, hence by
| induction the cost is linear in the number of bits.
| wagslane wrote:
| Thanks for helping out with this explanation. I just updated
| the article and added an answer section briefly addressing
| this. Maybe check it out and let me know if you think the
| answer is sufficient?
| pfortuny wrote:
| And exponentiating is (relatively) easy beacuse
|
| a^(xyz) = ((a^x)^y)^z
|
| and as long as you know how to square, you can pretty much
| compute exponentials in log2(exponent) time.
| speedgoose wrote:
| > ECC is used as the cryptographic key algorithm in Bitcoin
| because it potentially can save ~90% of the resources used by a
| similar RSA system.
|
| But bitcoin is a waste of resources by design. The whole point is
| to waste resources.
| er4hn wrote:
| Bitcoin wants to waste resources for a specific operation -
| which is to prove that work was performed. The other aspects of
| bitcoin, such as sending transactions and validating
| transactions, have no need to waste resources and are designed
| to be efficient.
|
| A good analogy is password hashes. If you have a hashed value,
| it is expensive to find the original input. If you want to
| check that an input is equal to the hashed value, that is a
| cheap operation.
| tylersmith wrote:
| Disregarding the quibbling about what is waste and what isn't,
| there's a difference between the work done to validate blocks
| and work done for the PoW based Nakamoto consensus. You want
| block validation to be as fast as possible which is a separate
| concern from deciding on a chain which is where you want lots
| of work.
| aeturnum wrote:
| I appreciate that this post focuses on the key element that I
| hadn't understood about ECC: how it replaces factoring as a 'easy
| to do, difficult to undo' algorithm. This is a great example of a
| post that has enough information to be able to explain it in
| plain language without giving the impression that you know enough
| to implement it.
| dan-robertson wrote:
| It's maybe good that the post doesn't really have to talk about
| group theory, but for the record, the standard way to answer
| this question is:
|
| 1. Integers modulo a prime form a (cyclic) group
|
| 2. Cryptographic algorithms like Diffie-Hellman group exchange
| don't really care about the integers modulo a prime and can be
| translated to other groups
|
| 3. The security of these algorithms rely on the discrete
| logarithm (computing a given g and g^a) being hard. For Diffie-
| Hellman, it is a related problem of computing g^{ab} given g,
| g^a, and g^b, which might be easier.
|
| 4. For integers modulo a prime discrete log is hard but not
| _that_ hard. Security is measured in the number of bits of one-
| time-pad the security is equivalent to. It is generally
| believed that discrete log is harder in elliptic curves, such
| that a shorter elliptic curve problem (which also gives faster
| computation) is the same difficulty (ie security) as a larger
| mod p problem. This is the promise of elliptic curves.
|
| Note here that factoring in general is not replaced: RSA, for
| which factoring is the important problem, relies on specific
| properties of modular arithmetic that aren't really the case
| for general groups.
| dan-robertson wrote:
| Let me add to this by talking about cyclic groups. All cyclic
| groups are equivalent to addition modulo an integer, but they
| can be different computationally: to go from an element of
| your cyclic group to the equivalent integer may be very
| difficult. For addition modulo n, the computational Diffie-
| Hellman problem is effectively:
|
| Given integers 1, a, and b, compute ab. This is obviously
| easy. The problem of translating from an arbitrary cyclic
| group to addition mod n is the discrete log problem, so
| perhaps that explains why it is important to cryptography
| that it be hard for your group.
| andy_ppp wrote:
| Here is Arstechnica on the very same subject in 2013:
| https://arstechnica.com/information-technology/2013/10/a-rel...
| er4hn wrote:
| Something else worth noting from the article
|
| ===
|
| If however, you know the number of hops you can use an
| exponentiation trick to find the ending point quite quickly. For
| example, and omitting the details of elliptic curve operations:
| 2P = P dot P and then 4P = 2P dot 2P. This allows you to get up
| to those crazy high calculations exponentially faster.
|
| ===
|
| One big difficulty in ECC vs RSA is how to do the math required
| for the operations. With RSA choosing the keys is the part where
| dragons lie and you need to make sure the numbers chosen satisfy
| various criteria. The algorithms for working with keys in RSA are
| well defined. The opposite is true for ECC. It is easier to
| choose numbers but depending on the curve used as well as how it
| is implemented there can be information leaked about the key in
| timings and other behavior.
|
| If you want to read more check out the Wikipedia article on the
| Montgomery Ladder (
| https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplic...)
| as well as DJB's comparison chart of curves that don't support
| the Montgomery Lader: https://safecurves.cr.yp.to/ladder.html .
| The real kicker here is that the NIST P-### curves are what ends
| up in official US government requirements.. and they are
| vulnerable to side channel attacks due to their design.
| qorrect wrote:
| Love the visuals, and a great job of making it simple to
| understand , thanks!
| runeks wrote:
| Certicom also wrote a rather beginner friendly ECC tutorial:
| https://www.certicom.com/content/certicom/en/ecc-tutorial.ht...
| LennyWhiteJr wrote:
| How are the curves defined? Is there a 'standard' curve that's
| generally used or is the curve itself randomly generated along
| with the keys?
| outlace wrote:
| It was never mentioned in the article so I just looked it up on
| Wikipedia, but Elliptic curve cryptography is not secure against
| future quantum computers.
| er4hn wrote:
| Neither is RSA. Most present day asymmetric crypto has its
| strength (amount of computing required to break it)
| significantly reduced by quantum computers. The solution is
| quantum safe algorithms which are a developing field.
|
| Symmetric algorithms such as AES can have their strength
| reduced as well, but (I have no sources to cite) I believe this
| reduces it from 256-bit to 128-bit. At 128 bits of security it
| is still widely considered safe to use.
| upofadown wrote:
| Yeah and the currently known quantum resistant algorithms have
| huge keys. Much larger than RSA. So we shouldn't get too
| dependent on short keys when designing protocols...
| marcodiego wrote:
| Best looks simple but is complicated problem related to ECC:
| https://medium.com/iotex/elliptic-curve-cryptography-iot-sec...
___________________________________________________________________
(page generated 2021-02-14 23:00 UTC)