Elliptic curve cryptography (ECC)
Elliptic curve cryptography (ECC) is an approach to public-key
cryptography. It is based on the algebraic Structure of elliptic curves
over finite fields. ECC was first mentioned in [33]. Compared to RSA,
ECC appears to provide equal security for a far smaller key
size(approximately one-eighth the key size), thus reducing processing
overhead [57]. For example, a 160-bit ECC key provides the same level
of security as a 1024-bit RSA key and 224-bit ECC is equivalent to
2048-bit RSA [56]. It means ECC offers faster computations, lower power
consumption, and memory & bandwidth savings. These properties are
useful for mobile devices which are typically limited in the resource
of CPU, power and network connectivity. In this way, ECC is more
suitable for securing mobile banking than RSA theoretically.
Elliptic curve used in cryptography are defined over two kinds of fields:
• prime curves: GF(p), p is a large prime number;
• binary curves: GF(2m), 2m element are binary polynomials;
A pointed in [14] that prime curves are best for software
implementations,but binary curves are best for hardware applications.
Sounds exciting. So, is Sun or anyone else working to add ECC to the SSL standard?
Posted by George on December 16, 2008 at 12:03 PM PST #
Elliptic curves are a simple mathematic function.
The way you apply it in cripto while fascinating doesn't replace RSA/DSA/whatever. As you said, and quite well, it just improves the key mechanism giving the same security with a smaller key.
Good article :)
Posted by Nuno Job on December 16, 2008 at 09:13 PM PST #
Certainly, TLS has had ECC suites defined for quite a while now. Sun's JES Web Server 7 supports ECC for TLS since a couple years ago. Some articles on the topic:
http://blogs.sun.com/jyrivirkki/entry/web_server_7_ecc_performance
http://blogs.sun.com/jyrivirkki/entry/more_on_web_server_ecc
http://blogs.sun.com/jyrivirkki/entry/sun_ecc_and_web_server
http://blogs.sun.com/jyrivirkki/entry/ecc_at_javaone_2007
http://blogs.sun.com/jyrivirkki/entry/elliptic_curve_cryptography_the_future
Posted by Jyri Virkki on December 16, 2008 at 09:17 PM PST #
Hi Jyri Virkki,
I saw your article: http://blogs.sun.com/jyrivirkki/entry/web_server_7_ecc_performance
Did you make some evaluation on the performance ECC implemented on mobile devices?
Posted by Yunpu Zhu on December 18, 2008 at 09:18 AM PST #
Hi Nuno Job,
Yes it is. If some cryptography algorithms meed to be implemented on resources limited devices, such as PDAs, mobile phones, key size is a big parameter in balancing computational intensive workload and security. EC is one good choice to realize digital signature or encypto/decrypt.
Posted by Yunpu Zhu on December 18, 2008 at 09:23 AM PST #
Hi Geoge,
you can check Jyri Virkki's comment.
Posted by Yunpu Zhu on December 18, 2008 at 09:24 AM PST #
http://research.sun.com/spotlight/2006/2006-02-13_ECC.html
Posted by Kim on December 18, 2008 at 04:44 PM PST #
From a previous comment, "Elliptic curves are a simple mathematic function. The way you apply it in cripto while fascinating doesn't replace RSA/DSA/whatever."
For clarity, elliptic curves are defined by simple formulas, which can be understood by someone with a year of algebra. They are not, in general, functions, because there are infinite sets of x values that correspond to more than one y value, and vice versa.
The use of suitable elliptic curves in cryptography more ingredients than the curves' formulae. 1) A "point at infinity" is defined, and a set is defined that contains this point, and points on the elliptic curve. 2) An operation (something like addition) is defined that, between any two points from this set, will produce a result that is also in the set. The set and operator together form an Abelian group.
Many cryptographic schemes (for example, DSA and Diffie-Hellman key exchange) base their security on the difficulty of the "discrete logarithm problem", which is the difficult (for suitable groups) of finding an integer exponent x such that a base raised to the power of x will equal some given value y.
Usually, such schemes are based on integer multiplication groups, but they can be modified to use an elliptic curve group instead. This gains the benefits of smaller key size, to gain an equal degree of estimated security.
Elliptic curves are NOT useful for systems such as RSA, whose security is not based on the discrete logarithm problem.
Elliptic curve cryptography is still not widely used: although it is very attractive for the reasons stated above, various aspects of it are covered by patents. Corporations and standards organizations that don't wish to become entangled in patent licensing tend to avoid ECC.
Posted by markh on December 21, 2008 at 12:14 PM PST #
Hi markh,
Thanks for your comments. Is patent the biggest problem that blocks ECC's acceptation by Corporations and standards organizations? Is there any articles that explain the patent problem of ECC?
Posted by Yunpu Zhu on December 21, 2008 at 03:58 PM PST #
@Yunpu Zhu: Wikipedia has an brief overview of the patent situation, see http://en.wikipedia.org/wiki/ECC_patents . One of the links in this article is to http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm , which has comments on the ECC patent situation from the perspective of the US government's National Security Agency (a Defense Department Agency responsible for signals intelligence, and cryptographic technologies).
Posted by markh on December 21, 2008 at 11:57 PM PST #
@Yunpu Zhu: This link from 2005 is interesting: http://www.mail-archive.com/cryptography@metzdowd.com/msg04965.html . It goes into some detail about Certicom patents, and the author's opinion is that ECC systems can be implemented without infringing the patents.
It seems to me that because several of Certicom's patents are for methods of efficient implementation, they may be less of a problem for implementations on ordinary computers (PCs etc.), and much more of a problem in cases where you most need the benefits of ECC: small microcontroller systems, smart cards, etc.
Posted by markh on December 22, 2008 at 05:41 AM PST #
One more observation on the patent situation...
Table 1 in http://www.nsa.gov/ia/industry/crypto_elliptic_curve.cfm gives recommended key sizes for various "equivalent security levels". The key sizes given for ECC assume point compression. While the technique of point compression is trivial, it is also claimed by U.S. patent 6,141,420.
While several people argue that this claim is invalid (for example, because it was prior art, and because it so obvious), if an implementer wants to avoid either (1) getting a license from Certicom, or (2) risking a patent infringement suit, they must use keys twice as large as those in Table 1, to get the recommended security level.
The key sizes are still much smaller than needed for systems based on multiplication groups, but the double-size key could be a problem for some critical applications.
This is an example of the "patent cloud" that is perceived to hang over the use of elliptic curve cryptography.
Posted by markh on December 22, 2008 at 05:57 AM PST #