Elliptic Curve Cryptography

In Elliptic Curve Cryptography ( ECC) or German Elliptic curve cryptography is meant asymmetric cryptosystems use the operations on elliptic curves over finite fields. The security of this method is based on the difficulty of computing the discrete logarithm in the group of the elliptic curve points.

Each method based on the discrete logarithm in finite fields, such as the Digital Signature Algorithm, the ElGamal encryption scheme or the Diffie -Hellman key exchange, can be transmitted in a simple manner on elliptic curves and therefore to Elliptic Curve Cryptosystem reshape. The operations used in the original process (multiplication and exponentiation ) are replaced on the finite field with the appropriate operations ( point addition and point multiplication ) of the points on the elliptic curve. The times adding a point to itself ( ie the multiplication by the scalar) is denoted by and corresponds to an exponentiation in the original method.

The principle was proposed mid-1980s by Victor S. Miller and Neal Koblitz independently.

• 5.1 ANSI
• 5.2 NIST
• 5.3 IETF
• 5.4 ISO
• 5.5 IEEE
• 5.6 ECC Brain Pool
• 5.7 SECG
• 5.8 BSI

Principle of operation

On elliptical curves, an additive cyclic group can be defined which consists of the multiples of a point on the curve, the generator of the group. The addition of two points in the group is simple, but there are curves on which the "division" between two points is difficult, that is, there is no known efficient method for a at a given point in a generated by a point group to find natural number. So that there is an analogue of this curve discrete logarithm problem (DLP) in multiplicative groups, which is also called DLP.

Analogously, one can define the Computational Diffie -Hellman problem (CDH to given and calculate ) and the decisional Diffie -Hellman problem ( DDH ). This allows cryptographic procedures whose security is based on these problems, may be transferred to elliptic curves, for which these problems are likely to be difficult. Examples are

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

Moreover, there are curves on which a pairing said bilinear mapping in a group exists. In these curves while DDH is easy, as is true, but the existence of the pairing allows many novel applications.

Efficiency and safety

Since the discrete logarithm problem in elliptic curve ( ECDLP ) is much more difficult than the calculation of discrete logarithms in finite fields and factorization of integers, come cryptosystems based on elliptic curves - with a comparable safety - with considerably shorter keys than the conventional asymmetric cryptosystems such as the RSA cryptosystem or the Diffie -Hellman key exchange. The fastest algorithms are the baby-step giant-step algorithm and Pollard 's rho method whose running time is, the bit length of the size of the underlying body. According to current knowledge is, for example, with a key length of 160 bits achieves a similar security as RSA with 1024 bit. ECC is therefore particularly suitable when the memory or computing capacity is limited, such as smart cards or other embedded systems.

By the U.S. National Institute of Standards and Technology (NIST ) and ECRYPT lists specified equivalent key sizes for RSA and Diffie -Hellman keys for a given level of security by way of example here.

The mathematical operations on elliptic curves are more complicated to calculate than comparable operations in large finite fields or RSA moduli. Because of the significantly shorter keys can cryptosystems based on elliptic curves, with a comparable level of security still be faster than the same method based on the discrete logarithm in a finite field or as RSA. A comparison of the computational efficiency of this cryptographic method is highly dependent on the details of implementation ( cryptographic parameters, arithmetic, optimization, programming language and compiler, underlying hardware ).

Side-channel attacks

In May 2011, the researchers Billy Bob Brumley and Nicola Tuveri published a paper in which they describe a successful timing attack on ECDSA. The researchers relied on a server with OpenSSL. The attack took place about the fact that the encryption and decryption with different ECDSA keys takes different amounts of time to complete. So Brumley and Tuveri were able to calculate the private key without access to the server.

Use

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

Products of the Mozilla Foundation ( including Firefox, Thunderbird ) support ECC with min. 256 bit key length (P -256 and up).

The common citizen card in Austria ( e-card, debit card or a-sign premium card) use ECC since its introduction in 2004/2005, which Austria is among the pioneers in their wide use.

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

In Germany the new ID card is also used ECC, both for Extended Access Control as well as for Passive Authentication.

Sony uses Elliptic Curve DSA for digital signing of software for the PlayStation 3 In 2010, a group of hackers managed to determine the private key used and thus an almost complete breakdown of security systems. However, this was mainly due to implementation errors by Sony and used no security vulnerabilities in the ECC method you are using.

Patents

According to the U.S. National Security Agency ( NSA) implementations are faced with patent problems. Especially the Canadian Certicom Inc. therefore has more than 130 patents, which are required for ECC or public-key cryptography. 26 of which have been licensed by the NSA to ECC method to implement for purposes of national security.

In a study by the Centre for Secure Information Technology Austria (A -SIT ) is used in efficient implementations pointed to patents, where the ECC itself " principle, patent-free " is.

Standardization bodies and standards

ANSI

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

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

NIST

• FIPS 186-3

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, eg 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 )

ISO

• ISO 14888-3

• ISO 15946

IEEE

• IEEE 1363

ECC Brain Pool

The ECC brain pool, a working group of companies and institutions on the subject of Elliptic Curve Cryptography has, in 2005, a number of elliptic curves specifies which was standardized in March 2010 in RFC 5639 of the IETF. In these curves, the particular choice of the bit length is 512 to mention a contrast to many other institutions (eg NIST SECG ) 's preferred bit length 521

SECG

The "Standards for Efficient Cryptography Group" ( SECG ) is a consortium founded in 1998 to promote the use of ECC algorithms.

BSI

The Federal Office for Security in Information Technology sets TR- 03111 specifications and recommendations for the implementation of elliptic curve cryptography based on ISO / IEC 15946 in the Technical Guideline.