Wow, I always thought that elliptic curves were an algorithm to break cryptography like RSA.
If I remember well, RSA is based on the fact that Z/pZ is a group when p is prime (for those who don't know, it's about taking the addition and multiplications for the numbers in [0..p-1] and taking the result modulo p), and elliptic curves offer a more generic framework for that...
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
But Euler's extension of Fermat's Little Theorem says that if gcd(a,n)=1, then a^phi(n)=1 (mod n). Therefore M^r=1 (mod n), and so D=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
There is also Lentra's Elliptic Curve Integer Factoring Algorithm. That is basically the Pollard Rho factoring method, but in a group corresponding to an Elliptic Curve, rather than in the usual Z/nZ. Factoring integers can result in breaking RSA, and Elliptic Curves can be used in factoring, but that's a different question.
Z/pZ is a field when p is prime. That's somewhat (indirectly) related to how the RSA algorithm works, but at a high level you're doing arithmetic in Z/nZ, where n = p * q for primes p and q.
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 thought the most interesting thing in the stack overflow was the complete lack of systems analysis.
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.
You don't need to replace your entire anything, and it's not "just for fun".
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.
"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.
> Finally its highly unclear why anyone uses SSL for these apps
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.
I've often heard the claim that elliptic curve cryptography is not used much in practice compared to RSA. I don't doubt its true but I would like to have some evidence for it so I can also say it without being a parrot.
I don't know anything about real world implementations of cryptography. How can I go about getting data that RSA is more widely used?
Well, probably the most widely used cryptography is SSL, specifically the kind used in HTTPS. The whole HTTPS ecosystem revolves around certificates authorities that sign your RSA key. So on that fact alone, I would say there's more RSA out there than ECC.
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.
SSL/X.509 and that whole ecosystem can use ECDSA based certificates and ECDH as key exchange, because it is explicitly designed to allow multiple variants of encryption algorithms.
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.
The top answer tries to brush off the difference in hardness assumptions as "semi-valid", and I think that's rather odd. Assumptions about hardness are pretty damned important in cryptography, and 25 years is not really all that long for mathematicians to have been thinking about a problem.
As another answer points out, the mathematics of the discrete logarithm on elliptic curves is closely related to factoring, and most factoring algorithms have close analogs for the discrete logarithm, so the difference is actually not that great.
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.
check out www.surespot.me for a great example of elliptic curve cryptography. surespot is a free and open source mobile messenger encrypting all messages end-to-end with 256 bit AES symmetric-key encryption using keys created with 521 bit ECDH shared secret derivation. surespot was built from the ground up to provide this exceptional security in an unobtrusive way, this is not a layer over something existing. surespot is like whatsapp but actually encrypted! group chat on the way.
I red somwhere that RSA signature verifcation (decryption with the pulic key) is significantly faster than with ECC. I didn't check it my self, but that is the reason. CryptoPP author told me the same thing.
Not relevant to ECC, but if anyone here has spare time and any interest at all in crypto, please contribute to the linked site (http://crypto.stackexchange.com)! In case anyone doesn't know, StackExchange is a network of Q&A websites, of which StackOverflow was the first. Sites go through a proposal process and, if enough people commit, a private and then public beta. The Cryptography StackExchange site is currently in public beta. If it reaches a critical mass, then it will graduate and become fully-fledged member of the SE network.
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.
To explain a potential adversary, how crypto works or how he becomes a valueable asset for any given intelligence service without any given payment may not even attract people like me.
> 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.
ECC is the emerging new standard for asymmetric crypto. It's misleading to say it's not widely used. It's not widely used in mainstream protocols, because those protocols were almost invariably designed in the 1990s. During the '90s, ECC was both patent-encumbered and a less conservative choice than RSA.
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.
The one main reason ECC was not adopted initially is also patents. Certicom held a majority of the patents on those and every time I tried to push for elliptic curves the first thing every one talked about was patents. So we mostly stayed away from it to avoid any issues later on. One other reason is Openssl did not implement support for them until recently (a few years ago), probably because of the patent confusion. It will pick up in a few years.
I can't find a smartcard that does ECC. Anyone has one? PGPcard only does RSA (granted, up to 3072 bits -- but that makes for extra long signatures and messages).
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?
30 comments
[ 3.3 ms ] story [ 73.7 ms ] thread[1] https://bugzilla.redhat.com/show_bug.cgi?id=319901
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:
But Euler's extension of Fermat's Little Theorem says that if gcd(a,n)=1, then a^phi(n)=1 (mod n). Therefore M^r=1 (mod n), and so D=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:
There is also Lentra's Elliptic Curve Integer Factoring Algorithm. That is basically the Pollard Rho factoring method, but in a group corresponding to an Elliptic Curve, rather than in the usual Z/nZ. Factoring integers can result in breaking RSA, and Elliptic Curves can be used in factoring, but that's a different question.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.
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.
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.
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.
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.
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.
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?