Why is elliptic curve cryptography not widely used, compared to RSA?
crypto.stackexchange.com
crypto.stackexchange.com
In 2013, the scales have tipped. RSA is now the less conservative choice. Classical number-theoretic asymmetric cryptography has been getting weaker and weaker with improvements both on factoring and the DLP. ECC has been deployed in more and more systems without patent debacles. Research has firmed up our confidence in ECC.
You should generally be distrustful of any new system that uses asymmetric crypto of any sort. Asymmetric crypto is very difficult to get right; it has more corner cases than AES/SHA constructions do. But you should be especially distrustful if you see a new system that uses RSA.
As it is, the site is doing relatively well but daily activity is low (too few questions, too few visitors). But there are lots of knowledgeable people on it, and crypto is one of those areas everyone seems interested in, so the only real thing holding it back is a critical mass of good, active users. For many professions here on HN, it's useful to have a bit of crypto knowledge, so this post is a shameless plug. :)
You don't have to be an expert to contribute. In fact, one of the problem areas is a lack of good, well-researched, quality questions. Of course, any new expert is welcome too.
https://news.ycombinator.com/item?id=5853601
Feel free to email - probably better than cluttering up the threads here.
> how he becomes a valueable asset for any given intelligence
How who becomes a valuable asset? Unless I am misreading this somehow, I don't even know what you're trying to say.
> without any given payment may not even attract people like me
If you're saying that you have no interest in answering questions because there's no pay involved, then I can understand that position. But a huge part of what the Crypto SE lacks is a study influx of quality questions. And the flip side of not being paid to answer is that you don't have to pay to ask.
I suppose if you are a cryptographer, you have little incentive to spend time roaming the site, true. However, other Stack Exchange sites have a bunch of experts on them too (ignoring the Big Three, the Math SE is one such place, as well as essentially all of the other graduated sites) and they don't seem to mind not being paid. I agree it's not for everyone, though.
99% of people who need encryption already have it, and they probably use RSA or at least a non-EC system. So almost by definition you're talking about converting an entire system, not just linking in a new library or CSS file...
The question is really, "Why aren't people replacing their entire SSL cert system and all their SSH shared keys just for fun?". Or maybe "Why is gradual generational turnover rate in security systems so slow?". Combining the two questions is strangely reminiscent of why does it take forever to roll out ipv6 and sunset ipv4?
Its possible for new stuff I'd evaluate the field and possibly an E.C. tech might win. But if turnover is perhaps 1% annually, its going to take a century unless theres a "crisis" or major revolutionary kick to the system.
No, the question is really "EC has these benefits (lower CPU and memory usage) - why aren't these benefits attractive enough for someone to start experimenting with it?" - with those someones probably being companies like Google, Facebook, Dropbox etc that have very substantial amounts of SSL traffic and could surely benefit from saving on memory and CPU.
... at a certain labor cost. And memory and CPU prices are forever decreasing and labor cost is sorta increasing. So if it doesn't make sense as a system to do it today it probably never will, for an established organization anyway.
Also its not "why aren't they experimenting" but "why aren't they publicly experimenting". And it would nearly be a first in the security field to discuss algo changes this long in advance of rollout, if its ever discussed in public at all...
Finally its highly unclear why anyone uses SSL for these apps. That solely protects the relatively highly secure comm channel between two wide open insecure endpoints, so there's no point other than security theater/marketing. For email auth, yeah maybe. For finance its theater but necessary theater. But for G+, FB, DB as listed its just a waste of time. The MS windows enduser is probably owned 100x over with worms and keyloggers, and the server side will roll over and play dead to anyone remotely in .gov.
Huh? The reason you use SSL for Google and Facebook is so 15 random strangers don't get access to your accounts just because you go online for five minutes in Starbucks.
PRISM is awful and all but that doesn't mean non-state adversaries stopped being a thing overnight.
Very briefly ...
==== Start RSA recap
Given an integer n>1, the numbers a s.t. 0<=a<n and gcd(a,n) form a group under multiplication. That means that for every e with gcd(e,n)=1 there is a d s.t. d.e=1 (mod n).
Now take n=pq where p and q are primes. The function phi(n) counts how many elements are co-prime to n, and since n=pq that turns out to be (p-1)(q-1). So phi(n)=(p-1)(q-1). I'm going to write r=phi(n).
Take any e with gcd(e,r)=1. We can compute d s.t. d.e=1 (mod r), which means d.e = k.r+1 for some k. (Note: I'm doing this mod r, not mod n.)
Right.
Now take a message M (with 0<=M<n and gcd(M,n)=1) and compute E=M^e. We can do that fairly quickly using an adapted Russian Peasant Multiplication algorithm. This number "looks random" in some sense. You can transmit it to someone else.
They compute D=E^d. So what's that? Well, working modulo n:
D = E^d
= (M^e)^d
= M^(d.e)
= M^(k.r+1)
= M^(k.r) x M
= (M^r)^k x M
Therefore we can recover M, so we can decrypt E.
So if you publish n and e, but keep d secret, people can send you E=M^e (mod n) and only you can read it.
Probably.
If someone can compute phi(n) then they can compute d from e and n, but we think that's the same as factoring n. Similarly, if you can compute discrete logarithms, but that seems to be about as hard as factoring.
==== End RSA recap.
All of this can be cast more abstractly in the group (Z/nZ, * ). Doing so gives us the same system in more generality. This is what ECC does. You choose and publish an elliptic curve - C. Then you choose an element, e, and compute its inverse d in C. You encrypt a message M by taking e.M (remembering that in ECC we usually use + as the operation symbol instead of * - so this is the equivalent of M^e).
And it all works.
Possibly someone who knows more about this than I will find gaping holes in the above, but I think that should get you started.
To address the other question:
> I always thought that elliptic curves were
> an algorithm to break cryptography like RSA
Both RSA and ECC are based on the idea that exponentials are easy to compute, and undoing them is hard. In the case of RSA, you're exponentiating in Z/nZ and in ECC you're exponentiating in the group of points that arises from the chosen elliptic curve.
The first book in that list is a good text. It includes an appendix that includes almost everything you need to know about projective geometry to understand the theory of elliptic curves.
I don't know anything about real world implementations of cryptography. How can I go about getting data that RSA is more widely used?
SSH is also very widely used and it has traditionally used RSA keys, though it supports DSA keys, too and, more recently, ECDSA (the "EC" being elliptic curve). Sadly, Mac OS X's built in openssh is an older version that doesn't support ECDSA and apparently Redhat turns off ECDSA support for some sort of legal/patent reasons. So that's another case where RSA is more popular.
There are relatively many widely deployed systems that use ECC because of resource constrains (short signatures, mainly). For example both Microsoft's product keys and FlexLM use something that is at least described in marketing materials as ECDSA.
GPG and SSH can do ECC for a long time now - where's the trustworthy hardware to help them?
Anyone know of something that can run e.g. on the YubiKey NEO?
However it does have a subtle consequence. We've developed some very good sieve based algorithms for factoring in recent decades that do not have obvious analogs for elliptic curves. A large part of the performance advantage that elliptic curves have is that you can get away with shorter keys. However if we developed an analog to our best factoring algorithms, then that size (and therefore performance) benefit becomes much less.
If you choose key size to "be good enough that people won't be able to break this for X years" you really should assume that such analogs exist, and will be discovered within X years.