Elliptic Curve Cryptography

Elliptic curve across ${\displaystyle \mathbb {R} }$

Under Elliptic Curve Cryptography ( ECC ) or German  elliptic curve cryptography is understood asymmetric cryptosystems , the operations on elliptic curves over finite fields use. These methods are only safe if discrete logarithms in the group of points on the elliptic curve cannot be calculated efficiently.

Any method that is based on the discrete logarithm in finite fields, such as B. the Digital Signature Algorithm , the Elgamal encryption method or the Diffie-Hellman key exchange , can be easily transferred to elliptic curves and thus transformed into an elliptic curve cryptosystem. The operations used in the original method (multiplication and exponentiation) on the finite body are replaced by corresponding operations (point addition and scalar multiplication) of the points on the elliptical curve. The -fold addition of a point to itself (i.e. the multiplication with the scalar ) is denoted by and corresponds to a power in the original method. ${\displaystyle n}$ ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle nP}$ ${\displaystyle x^{n}}$

The principle was proposed by Victor S. Miller and Neal Koblitz independently of one another in the mid-1980s .

Working principle

An additive cyclic group can be defined on elliptic curves , which consists of the multiples of a point on the curve, the generator of the group. Adding two points in the group is easy, but there are curves where it is difficult to "divide" two points; H. there is no efficient method known for a given point in one of a point group generated a natural number with to find. There is thus an analogue to the discrete logarithm problem (DLP) in multiplicative groups on these curves , which is also called DLP. ${\displaystyle A}$ ${\displaystyle P}$ ${\displaystyle a}$ ${\displaystyle aP=A}$

The computational Diffie-Hellman problem (CDH, to be given and calculated ) and the decisional Diffie-Hellman problem (DDH) can be defined analogously . This allows cryptographic methods whose security is based on these problems to be transferred to elliptic curves for which these problems are presumably difficult. Examples are ${\displaystyle aP}$ ${\displaystyle bP}$ ${\displaystyle abP}$

• Elliptic Curve Diffie-Hellman (ECDH)
• Integrated encryption scheme , and (ECIES) Integrated Encryption Scheme (IES) called
• Elliptic Curve Digital Signature Algorithm (ECDSA)
• ECMQV, a key agreement protocol proposed by Menezes, Qu, and Vanstone

In addition, there are curves on which a bilinear mapping into a group , called pairing , exists. Although DDH is easy in these curves , the existence of pairing allows many new types of applications. ${\displaystyle E}$ ${\displaystyle e:E\times E\to G}$ ${\displaystyle G}$ ${\displaystyle e(aP,bP)=e(P,abP)}$

Efficiency and security

Since the problem of the discrete logarithm in elliptic curves (ECDLP) is significantly more difficult than the computation of the discrete logarithm in finite fields or the factorization of whole numbers, cryptosystems based on elliptic curves get by with considerably shorter keys than these - with comparable security conventional asymmetric cryptographic methods, such as B. the RSA cryptosystem or the Diffie-Hellman key exchange . The fastest algorithms currently available are the Babystep-Giantstep-Algorithm and the Pollard-Rho-Method , the running time of which is, where the bit length is the size of the underlying body. According to current knowledge, z. B. with a key length of 160 bits achieves a similar level of security as with RSA with 1024 bits. ECC is therefore particularly suitable when the memory or computing capacity is limited, e.g. B. in smart cards or other embedded systems . ${\displaystyle {\mathcal {O}}(2^{n/2})}$ ${\displaystyle n}$

The US National Institute of Standards and Technology (NIST) and ECRYPT list the equivalent key lengths for RSA and Diffie-Hellman keys for certain security levels as an example.

Comparison of encryption strengths

Security level	RSA / DH (NIST)	RSA / DH (ECRYPT)	ECDH
80	1024	1248	160
112	2048	2432	224
128	3072	3248	256
192	7680	7936	384
256	15360	15424	512

Comparison of the calculation effort

Security level (bit)	Ratio at DH: ECDH
80	3: 1
112	6: 1
128	10: 1
192	32: 1
256	64: 1

The mathematical operations on elliptical curves are more complex to calculate than operations in finite bodies of comparable size or RSA modules. However, with significantly shorter keys, a level of security can be achieved that is comparable with procedures based on the discrete logarithm or with RSA. Due to the shorter key, among other things, elliptic curve cryptosystems can be faster with a comparable level of security. However, a comparison of the computing efficiency of these cryptographic methods depends heavily on the details of the implementation (cryptographic parameters, arithmetic, optimizations, programming language and compiler, underlying hardware).

Side channel attacks

In May 2011, the researchers Billy Bob Brumley and Nicola Tuveri published a scientific paper in which they described a successful timing attack on ECDSA. The researchers set up a server with OpenSSL . The attack was based on the fact that encryption and decryption with different ECDSA keys in the implementation of OpenSSL (versions 0.9.8o and 1.0.0.a) take different amounts of time. Brumley and Tuveri were able to calculate the private key without access to the server. An implementation with randomized parameters or a suitable choice of the curve parameters, however, allows operations with a constant time requirement.

use

Elliptic Curve Cryptography is supported by modern Windows operating systems (from Vista).

Mozilla Foundation products (including Firefox , Thunderbird ) support ECC with min. 256 bit key length (P-256 upwards).

The citizen cards common in Austria (e-card, ATM or a-sign Premium card) have been using ECC since their introduction in 2004/2005, making Austria one of the pioneers in their widespread use.

The passports of most European countries (including Germany) use ECC at least to protect access to the chip using Extended Access Control , some countries (including Germany and Switzerland) also use it to protect the data stored on the chip with Passive Authentication .

In Germany, the new ID card also uses ECC, both for Extended Access Control and for Passive Authentication.

Sony uses Elliptic Curve DSA to digitally sign software for the PlayStation 3 . In 2010, a group of hackers succeeded in determining the private key used and thus almost completely breached the security systems. However, this was mainly due to implementation errors by Sony and did not exploit any security gaps in the ECC process used.

Patents

Implementations face patent issues, according to the US National Security Agency (NSA). In particular, the Canadian Certicom Inc. owns more than 130 patents that are required for ECC or public key cryptography . Twenty-six of these have been licensed by the NSA to implement ECC procedures for national security purposes.

A study by the Center for Secure Information Technology Austria (A-SIT) points to patents in efficient implementations, whereby ECC itself is "in principle patent-free".

RFC 6090 describes basic ECC algorithms that were published as early as 1994 or before (and are therefore no longer subject to patents today). The ECC processes that are widespread on the Internet today are based on these algorithms, so that they were able to prevail without problems after the publication of RFC 6090 .

Standardization bodies and norms

ANSI

ANSI X9.62-2005 is the current standardization of the ECDSA.

• ANSI X9.62 (ECDSA)
• ANSI X9.63 (Key Agreement and Key Transport)

The curves of X9.62-2005 were designed by the NSA secret service and a back door cannot be ruled out due to the degrees of freedom in the curve selection method. According to an analysis by Dan Bernstein , the evidence for the randomness of the curves, which the curve selection method represents according to the standard, is simply non-existent.

NIST

• FIPS 186-3

The NIST curves were designed by the NSA secret service and are based on basic constants of unexplained origin, which means that a back door cannot be ruled out. You are also not sure about some desirable properties.

IETF

• RFC 6090 (Algorithms for ECC)
• RFC 3279 , RFC 5480 , RFC 5758 (use of ECC in X.509 certificates)
• RFC 2409 , RFC 4754 , RFC 5903 (use of ECC in IKE )
• RFC 4492 , RFC 5246 , RFC 5289 , RFC 5489 , RFC 6040 (use of ECC in TLS )
• RFC 5656 , RFC 6239 , RFC 6594 (use of ECC in SSH )
• RFC 5753 , RFC 6161 , RFC 6162 , RFC 6278 (use of ECC in CMS )
• RFC 4050 (use of ECC in XML signatures )
• RFC 6637 (use of ECC in OpenPGP )
• RFC 6605 (use of ECC in DNSSEC )
• RFC 5349 (Use of ECC in Kerberos )
• RFC 5915 (Elliptic Curve Private Key Structure, e.g. for PKCS # 8)
• RFC 5114 (additional elliptic curves for X.509 certificates, IKE, TLS, SSH and S / MIME )
• RFC 5639 (additional elliptic curves for X.509 certificates, IKE, TLS, XML signatures and CMS)
• RFC 5901 , RFC 6507 (Identity-Based Elliptic Curve Cryptosystems)

The RFCs use the Brainpool curves.

ISO

• ISO 14888-3
• ISO 15946

IEEE

• IEEE 1363

The IEEE standard uses the same curve selection method as the ANSI standard, so the same criticism has been expressed.

ECC brain pool

The ECC-Brainpool, a working group of the state-industrial association TeleTrusT (members including BKA, BSI) on the subject of Elliptic Curve Cryptography, specified a number of elliptic curves in 2005, which were standardized in March 2010 in RFC 5639 of the IETF. For these curves, the choice of bit length 512 should be mentioned, in contrast to the bit length 521 preferred by many other institutions (e.g. NIST, SECG) .

The design space of the Brainpool curves contains so many degrees of freedom that a back door cannot be safely excluded. The Brainpool curves are also not certain about some desirable properties.

SECG

The “Standards for Efficient Cryptography Group” (SECG) is a consortium founded in 1998 to promote the use of ECC algorithms. SECG was the first to specify the 521-bit curve, which was then adopted by NIST. This particular choice is based on the fact that is a prime and calculating with remainder classes modulo that prime is easy. ${\displaystyle 2^{521}-1}$

SECG SEC 2 uses the NSA curves from the NIST standard and also adopts the inaccurate assertion of the ANSI standard that they were verifiably chosen at random.

BSI

In the Technical Guideline TR-03111 Version 2.0, the Federal Office for Information Security lays down specifications and recommendations for the implementation of elliptic curve cryptography. Please note, however, that the EC-Schnorr algorithm defined there is not compatible with the Schnorr signatures EC-SDSA and EC-FSDSA defined in ISO 14888-3.

SafeCurves

Bernstein's SafeCurves project has now created a de facto standard with the safe, academic curves Curve25519 (or Ed25519), Ed448-Goldilocks and E-521. The state curves have lost the trust of some leading cryptographers, since the choice of curve is not completely transparent and therefore a kleptographic back door similar to that of Dual_EC_DRBG or another back door cannot be safely excluded.

See also

• DNSCurve
• Elliptic Curve DSA

literature

• Annette Werner: Elliptic Curves in Cryptography . Springer, 2002, ISBN 978-3-540-42518-2 .
• Lawrence C. Washington: Elliptic Curves: Number Theory and Cryptography . CRC, 2008, ISBN 978-1-4200-7146-7 .
• David H. von Seggern: CRC Standard Curves and Surfaces with Mathematica, Third Edition . CRC, 2016, ISBN 978-1-4822-5021-3 .

Web links

• Video of a lecture by Neal Koblitz ´on Elliptic-Curve-Cryptology , 1998, (MPG; 1.8 GB, English)
• ECC working group, domain parameters
• Free implementation of the "Elliptic Curve DSA" for Windows and Linux, download and instructions (English)

Individual evidence

1. ^ Victor S. Miller: Use of Elliptic Curves in Cryptography . In: Advances in Cryptology - CRYPTO '85 Proceedings (=  Lecture Notes in Computer Science ). tape 218 . Springer, 1986, p. 417-426 , doi : 10.1007 / 3-540-39799-X_31 .
2. ^ Neal Koblitz: Elliptic Curve Cryptosystems . In: Mathematics of Computation . tape 48 , no. 177 . American Mathematical Society, 1987, pp. 203-209 , JSTOR : 2007884 .
3. ^ Cryptographic Key Length Recommendation. BlueKrypt, accessed November 3, 2011 . 
4. ↑ ^{a b c} The Case for Elliptic Curve Cryptography. January 15, 2009, accessed November 3, 2011 . 
5. ↑ ECRYPT II Yearly Report on Algorithms and Keysizes (2011–2012). (PDF; 885.7 kB) September 30, 2012, accessed on December 15, 2016 (English). 
6. ↑ NIST has only standardized a 521-bit curve and therefore specifies 521-bit as the equivalent security level.
7. ↑ R. Szerwinski, T. Güneysu: Exploiting the Power of GPUs for Asymmetric Cryptography. Proceedings of CHES 2008 , pp. 79-99, 2008
8. ^ Billy Bob Brumley, Nicola Tuveri: Remote Timing Attacks are Still Practical. In: Cryptology ePrint Archive: Report 2011/232. May 11, 2011, accessed on November 3, 2011 (English, available as PDF). 
9. ↑ Successful timing attacks on encryption with elliptic curves. heise.de, May 23, 2011, accessed on November 3, 2011 (German). 
10. ↑ ^{a b c} SafeCurves: choosing safe curves for elliptic-curve cryptography. Retrieved June 7, 2016 . 
11. ↑ Elisabeth Oswald: Cryptosystems based on elliptical curves, use and distribution in standard software. (PDF; 445 kB) (No longer available online.) Center for Secure Information Technology - Austria (A-SIT), July 29, 2009, archived from the original on March 5, 2014 ; accessed on November 2, 2011 (German). Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
12. ↑ Mozilla CA Certificate Maintenance Policy (Version 2.0). mozilla.org, November 4, 2011, accessed on November 4, 2011 (English): "We consider the following algorithms and key sizes to be acceptable and supported in Mozilla products:… Elliptic Curve Digital Signature Algorithm (using ANSI X9.62) over SECG and NIST named curves P-256, P-384, and P-512; "  
13. ↑ Elliptic curves. (No longer available online.) Archived from the original on December 5, 2011 ; accessed on November 3, 2011 (German). Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
14. ^ Zdeněk Říha: Electronic passports. (PDF) JRC Ispra, European Commission, Masaryk University, Brno, September 13, 2008, archived from the original on February 15, 2010 ; accessed on November 3, 2011 . 
15. ↑ Dr. Manfred Locher and Dr. Johannes Merkle: A new standard for elliptic curves. (PDF; 796 kB) May 2009, accessed on January 14, 2018 (German, presentation from the 11th German IT Security Congress 2009). 
16. ↑ 27C3: Playstation 3 security system levered out. heise.de, December 30, 2010, accessed November 5, 2011 . 
17. ^ Elisabeth Oswald: Use and meaning of elliptical curves for the electronic signature. (PDF; 443 kB) (No longer available online.) A-SIT, 2001, p. 27 , archived from the original on February 3, 2014 ; accessed on November 2, 2011 (German). Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
18. ↑ ANSI X9.62-2005, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)
19. ↑ ^{a b c d e f} https://bada55.cr.yp.to/bada55-20150927.pdf
20. ↑ ^{a b c d} http://safecurves.cr.yp.to/rigid.html
21. ↑ (ECDSA) Digital Signature Standard (DSS). (PDF; 1.2 MB) FIPS PUB 186-3. National Institute of Standards and Technology (NIST), June 2009, accessed November 3, 2011 . 
22. ↑ https://www.miracl.com/press/backdoors-in-nist-elliptic-curves
23. ↑ Information technology - Security techniques - Digital signatures with appendix - Part 3: Discrete logarithm based mechanisms. ISO / IEC, accessed on November 3, 2011 (English, chargeable PDF access): "ISO / IEC 14888-3: 2006 specifies digital signature mechanisms with appendix whose security is based on the discrete logarithm problem. It provides a general description of a digital signature with appendix mechanism, and a variety of mechanisms that provide digital signatures with appendix. " 
24. ^ Information technology - Security techniques - Cryptographic techniques based on elliptic curves. ISO / IEC, accessed on November 3, 2011 (English, chargeable PDF access): "ISO / IEC 15946 specifies public-key cryptographic techniques based on elliptic curves. It consists of five parts and includes the establishment of keys for symmetric cryptographic techniques, and digital signature mechanisms (Part 15946-2 was revoked in 2007, and replaced by 14888-8). " 
25. ^ Standard Specifications For Public-Key Cryptography. The IEEE P1363 project develops Standard Specifications For Public-Key Cryptography, towards the goal of issuing a series of IEEE standards documents. (No longer available online.) IEEE October 10, 2008, archived from the original on November 1, 2011 ; accessed on November 3, 2011 . Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.   
26. ↑ http://www.secg.org/sec2-v2.pdf
27. ↑ https://www.schneier.com/blog/archives/2013/09/the_nsa_is_brea.html#c1675929