Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Elliptic Curves

math.mit.edu

Post reply on HN
Print view View original

21–30 of 36 posts

Re: Elliptic Curves

#21

Post by tptacek »

ColinWright wrote: post #13
ColinWright wrote: post #12

Earlier quoted context omitted.

Ignoring many important details ... Many algorithms for crypto and similar can be phrased elegantly and abstractly not in terms of the actual numbers, but in terms of what are called "Groups"[0]. A group is a set of things, and a binary operation that satisfies certain rules. At first glance a group appears to be pointless abstract nonsense, but most of the properties of numbers that we use in, say, RSA, or Diffie-He…

As to why they are trending ... With recent(ish) leaks about what the NSA is doing in terms of breaking widely-available crypto, the question has arising about what weaknesses might exist in current classical techniques. RSA and DHMW have been around for a long time, and much is known about specific weaknesses. Some primes need to be avoided, for example in DHMW one should avoid primes P where (P-1)/2 has lots of sma…

I'm going to push back a little on "new" and "weaknesses still being found". The underlying theory of curves and their hardness has been pretty stable for awhile --- since well before 2000, I think. More progress has been made against conventional multiplicative group Diffie-Hellman than has against curves.

The complicating factor isn't the curve problems themselves, but rather implementation details, some of them particular to specific curves.

Re: Elliptic Curves

#22

Post by ColinWright »

tptacek wrote: post #21
ColinWright wrote: post #13

Earlier quoted context omitted.

As to why they are trending ... With recent(ish) leaks about what the NSA is doing in terms of breaking widely-available crypto, the question has arising about what weaknesses might exist in current classical techniques. RSA and DHMW have been around for a long time, and much is known about specific weaknesses. Some primes need to be avoided, for example in DHMW one should avoid primes P where (P-1)/2 has lots of sma…

I'm going to push back a little on "new" and "weaknesses still being found". The underlying theory of curves and their hardness has been pretty stable for awhile --- since well before 2000, I think. More progress has been made against conventional multiplicative group Diffie-Hellman than has against curves. The complicating factor isn't the curve problems themselves, but rather implementation details , some of them p…

That's a reasonable point and I agree with you, but I think you've read into my comment something that's not there. I said:

>> But all the elliptic curve cryptography is comparatively new, and weaknesses are still being found.

It's the elliptic curve cryptography that's comparatively new, and the weaknesses are being found in the full crypto package. That includes, and in many cases is primarily in, the implementation.

So actually I think you're not pushing back, I think you're clarifying exactly what I said.

Of course, I may yet have misunderstood you, so feel free to add more. You certainly know more about this than I do, and I'm happy to learn (or have it clarified further).

Re: Elliptic Curves

#23

Post by sdevlin »

gogoengie wrote: post #15
lukejduncan wrote: post #5

I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?

Regarding importance, it provides an efficient alternative to RSA. [edit: this paragraph, based on my old notes on the subject, seems to be incorrect, see sdevlin's comment below] More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the k…

> More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the key space is very dense, which reduces the key size for an "equivalent" encryption strength.

This isn't correct.

The reason RSA (and classic DH) keys are gigantic is because index calculus techniques yield efficient attacks on systems based on finite fields. We need big keys to make them impractical.

EC systems are not susceptible to these attacks because the points on a curve comprise only a group and not a field. Counterintuitively (to me, at least!), they're safer because they have less structure.

Re: Elliptic Curves

#24

Post by nhaehnle »

sdevlin wrote: post #23
gogoengie wrote: post #15

Earlier quoted context omitted.

Regarding importance, it provides an efficient alternative to RSA. [edit: this paragraph, based on my old notes on the subject, seems to be incorrect, see sdevlin's comment below] More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the k…

> More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the key space is very dense, which reduces the key size for an "equivalent" encryption strength. This isn't correct. The reason RSA (and classic DH) keys are gigantic is because index…

On the question of whether it's intuitive or not: NP-complete problems tend to have fairly little structure. A problem like boolean satisfiability has basically no structure: all you have is a soup of clauses. The "tricky" problems that have solutions in P get their solutions from clever exploitation of structure.

At least, that's how it becomes more intuitive to me.

Re: Elliptic Curves

#25

Post by tptacek »

ColinWright wrote: post #22
tptacek wrote: post #21

Earlier quoted context omitted.

I'm going to push back a little on "new" and "weaknesses still being found". The underlying theory of curves and their hardness has been pretty stable for awhile --- since well before 2000, I think. More progress has been made against conventional multiplicative group Diffie-Hellman than has against curves. The complicating factor isn't the curve problems themselves, but rather implementation details , some of them p…

That's a reasonable point and I agree with you, but I think you've read into my comment something that's not there. I said: >> But all the elliptic curve cryptography is comparatively new, and weaknesses are still being found. It's the elliptic curve cryptography that's comparatively new, and the weaknesses are being found in the full crypto package. That includes, and in many cases is primarily in, the implementatio…

Sure! I think we agree.

The whole field of misuse-resistant cryptography is very new, relative to the field as a whole. We didn't even have a usage model of cryptography that was sound until the later 1990s, when the connection was made between authentication and indistinguishability. It's only in the last few years that we've begun to prioritize constructions that make implementation bugs harder to blunder into.

Which is a long way of saying, that's true, but also still an issue relevant to RSA and DH and DSA.

I think the primary reason we read a lot about elliptic curves today is that the field has, at least to the extent that it's not directly promoting post-quantum algorithms, pretty much coalesced around curves as the best modern way to implement asymmetric cryptography.

Re: Elliptic Curves

#26

Post by ColinWright »

ColinWright wrote: post #12
lukejduncan wrote: post #5

I've seen a few links to resources on elliptic curves on HN, but I don't understand their importance or why they're trending with folks here. Can someone give me some context?

Ignoring many important details ... Many algorithms for crypto and similar can be phrased elegantly and abstractly not in terms of the actual numbers, but in terms of what are called "Groups"[0]. A group is a set of things, and a binary operation that satisfies certain rules. At first glance a group appears to be pointless abstract nonsense, but most of the properties of numbers that we use in, say, RSA, or Diffie-He…

A smidgen too late to edit the comment to add this ...

One advantage of ECC (Elliptic Curve Crypto) is that the keys are smaller, and hence it's easier to implement on resources constrained devices such as smart-cards and IoT devices.

Re: Elliptic Curves

#27

Post by gogoengie »

sdevlin wrote: post #23
gogoengie wrote: post #15

Earlier quoted context omitted.

Regarding importance, it provides an efficient alternative to RSA. [edit: this paragraph, based on my old notes on the subject, seems to be incorrect, see sdevlin's comment below] More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the k…

> More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the key space is very dense, which reduces the key size for an "equivalent" encryption strength. This isn't correct. The reason RSA (and classic DH) keys are gigantic is because index…

Very informative, thanks for the detailed response. To be clear, was my statement incorrect in terms of the "16%" quotation (from [0], which I now realize I misquoted in my private notes), or in the claim that the RSA key space density is low due to the dependency on prime numbers?

My private notes include a claim (original source uncited, sadly) that because the prime density from 1..n decreases (approximately) as `1/ln(n)`, then the corresponding effective key space density for RSA decreases at a related rate, which was what led to the corresponding reduction in the "equivalent" key size. If my notes on this are complete bunk I'd love to hear it. (Even a simple 'yes' would suffice and I'll revisit the subject.) Ta!

[0] https://www.yubico.com/2015/02/big-debate-2048-4096-yubicos-...

Re: Elliptic Curves

#28

Post by dom0 »

nhaehnle wrote: post #24
sdevlin wrote: post #23

Earlier quoted context omitted.

> More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the key space is very dense, which reduces the key size for an "equivalent" encryption strength. This isn't correct. The reason RSA (and classic DH) keys are gigantic is because index…

On the question of whether it's intuitive or not: NP-complete problems tend to have fairly little structure. A problem like boolean satisfiability has basically no structure: all you have is a soup of clauses. The "tricky" problems that have solutions in P get their solutions from clever exploitation of structure. At least, that's how it becomes more intuitive to me.

The structure of a problem specifies it; an unstructured problem is less well-specified, and that makes it intuitively more difficult to approach.

E.g. summation of a column of decimal numbers is a highly structured problem that's very easy to solve. Parsing the speech of yelling drunkards is not so structured, and much harder to solve.

Re: Elliptic Curves

#29

Post by nincompope »

tptacek wrote: post #21
ColinWright wrote: post #13

Earlier quoted context omitted.

As to why they are trending ... With recent(ish) leaks about what the NSA is doing in terms of breaking widely-available crypto, the question has arising about what weaknesses might exist in current classical techniques. RSA and DHMW have been around for a long time, and much is known about specific weaknesses. Some primes need to be avoided, for example in DHMW one should avoid primes P where (P-1)/2 has lots of sma…

I'm going to push back a little on "new" and "weaknesses still being found". The underlying theory of curves and their hardness has been pretty stable for awhile --- since well before 2000, I think. More progress has been made against conventional multiplicative group Diffie-Hellman than has against curves. The complicating factor isn't the curve problems themselves, but rather implementation details , some of them p…

> More progress has been made against conventional multiplicative group Diffie-Hellman than has against curves.

How is "none" more than "none"?

Re: Elliptic Curves

#30

Post by sdevlin »

gogoengie wrote: post #27
sdevlin wrote: post #23

Earlier quoted context omitted.

> More specifically, because of the RSA dependency on prime numbers, the RSA effective key space is very sparse (which is why going from 2048-bit RSA to 4096-bit RSA only increases the effective key space by ~16%). With elliptic curves, the key space is very dense, which reduces the key size for an "equivalent" encryption strength. This isn't correct. The reason RSA (and classic DH) keys are gigantic is because index…

Very informative, thanks for the detailed response. To be clear, was my statement incorrect in terms of the "16%" quotation (from [0], which I now realize I misquoted in my private notes), or in the claim that the RSA key space density is low due to the dependency on prime numbers? My private notes include a claim (original source uncited, sadly) that because the prime density from 1..n decreases (approximately) as `…

It's true that the space of valid RSA keys is sparse relative to size, but this isn't why we need big keys. As a counterexample, classic DH keys are also big (or they can be), even though the space of valid keys is dense.

We need big keys (or rather big fields) due to index calculus. This is a family of algorithms used to factor integers and compute discrete logarithms in finite fields. The fact that index calculus is (thus far) inapplicable to elliptic curve groups is the primary motivation for ECC.

Post reply on HN