Elliptic curve cryptography
Encyclopedia
Elliptic curve cryptography (ECC) is an approach to public-key cryptography
Public-key cryptography
Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...

 based on the algebraic structure of elliptic curve
Elliptic curve
In mathematics, an elliptic curve is a smooth, projective algebraic curve of genus one, on which there is a specified point O. An elliptic curve is in fact an abelian variety — that is, it has a multiplication defined algebraically with respect to which it is a group — and O serves as the identity...

s over finite field
Finite field
In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

s. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz
Neal Koblitz
Neal I. Koblitz is a Professor of Mathematics at the University of Washington in the Department of Mathematics. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyperelliptic curve cryptography and the...

 and Victor S. Miller
Victor S. Miller
Victor Saul Miller is an American mathematician at the Center for Communications Research of the Institute for Defense Analyses in Princeton, New Jersey, US. He received his A.B. in mathematics from Columbia University in 1968, and his Ph.D. in mathematics from Harvard University in 1975...

 in 1985.

Elliptic curves are also used in several integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....

 algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s that have applications in cryptography, such as Lenstra elliptic curve factorization
Lenstra elliptic curve factorization
The Lenstra elliptic curve factorization or the elliptic curve factorization method is a fast, sub-exponential running time algorithm for integer factorization which employs elliptic curves. For general purpose factoring, ECM is the third-fastest known factoring method...

.

Introduction

Public-key cryptography is based on the intractability of certain mathematical problems. Early public-key systems are secure assuming that it is difficult to factor a large integer composed of two or more large prime factors. For elliptic-curve-based protocols, it is assumed that finding the discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

 of a random elliptic curve element with respect to a publicly-known base point is infeasible. The size of the elliptic curve determines the difficulty of the problem. It is believed that the same level of security afforded by an RSA-based system with a large modulus can be achieved with a much smaller elliptic curve group. Using a small group reduces storage and transmission requirements.

For current cryptographic purposes, an elliptic curve is a plane curve
Plane curve
In mathematics, a plane curve is a curve in a Euclidean plane . The most frequently studied cases are smooth plane curves , and algebraic plane curves....

 which consists of the points satisfying the equation


along with a distinguished point at infinity, denoted ∞. (The coordinates here are to be chosen from a fixed finite field of characteristic not equal to 2 or 3, or the curve equation will be somewhat more complicated.)

This set together with the group operation of the elliptic group theory form an Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...

, with the point at infinity as identity element. The structure of the group is inherited from the divisor group
Divisor (algebraic geometry)
In algebraic geometry, divisors are a generalization of codimension one subvarieties of algebraic varieties; two different generalizations are in common use, Cartier divisors and Weil divisors...

 of the underlying algebraic variety
Algebraic variety
In mathematics, an algebraic variety is the set of solutions of a system of polynomial equations. Algebraic varieties are one of the central objects of study in algebraic geometry...

.

As for other popular public key cryptosystems, no mathematical proof of security has been published for ECC . However, the U.S. National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...

 has endorsed ECC by including schemes based on it in its Suite B
NSA Suite B
Suite B is a set of cryptographic algorithms promulgated by the National Security Agency as part of its Cryptographic Modernization Program. It is to serve as an interoperable cryptographic base for both unclassified information and most classified information. Suite B was announced on 16...

 set of recommended algorithms and allows their use for protecting information classified up to top secret
Classified information in the United States
The United States government classification system is currently established under Executive Order 13526, the latest in a long series of executive orders on the topic. Issued by President Barack Obama in 2009, Executive Order 13526 replaced earlier executive orders on the topic and modified the...

 with 384-bit keys. While the RSA patent expired in 2000, there are patents in force covering certain aspects of ECC technology
ECC patents
Patent-related uncertainty around elliptic curve cryptography , or ECC patents, is one of the main factors limiting its wide acceptance. For example, the OpenSSL team accepted an ECC patch only in 2005 , despite the fact that it was submitted in 2002.According to Bruce Schneier as of May 31, 2007,...

, though some argue that the Federal elliptic curve digital signature standard (ECDSA; NIST FIPS 186-3) and certain practical ECC-based key exchange schemes (including ECDH) can be implemented without infringing them.

Cryptographic premise

The entire security of ECC depends on the ability to compute a point multiplication
Elliptic curve point multiplication
Elliptic curve point multiplication is the operation of successively adding a point along an elliptic curve to itself repeatedly. It is used in elliptic curve cryptography as a means of producing a trap door function.-Basics:...

 and the inability to compute the multiplicand given the original and product points.

Cryptographic schemes

Several discrete logarithm
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

-based protocols have been adapted to elliptic curves, replacing the group with an elliptic curve:
  • the elliptic curve Diffie–Hellman key agreement scheme is based on the Diffie–Hellman scheme,
  • the Elliptic Curve Integrated Encryption Scheme
    Integrated Encryption Scheme
    Integrated Encryption Scheme is a hybrid encryption scheme which provides semantic security against an adversary who is allowed to use chosen-plaintext and chosen-ciphertext attacks. The security of the scheme is based on the Diffie–Hellman problem...

     (ECIES), also known as Elliptic Curve Augmented Encryption Scheme or simply the Elliptic Curve Encryption Scheme,
  • the Elliptic Curve Digital Signature Algorithm
    Elliptic Curve DSA
    The Elliptic Curve Digital Signature Algorithm is a variant of the Digital Signature Algorithm which uses Elliptic curve cryptography.-Key and signature size comparison to DSA:...

     is based on the Digital Signature Algorithm
    Digital Signature Algorithm
    The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...

    ,
  • the ECMQV key agreement scheme is based on the MQV key agreement scheme.
  • the ECQV implicit certificate scheme.


At the RSA Conference 2005, the National Security Agency
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...

 (NSA) announced Suite B
NSA Suite B
Suite B is a set of cryptographic algorithms promulgated by the National Security Agency as part of its Cryptographic Modernization Program. It is to serve as an interoperable cryptographic base for both unclassified information and most classified information. Suite B was announced on 16...

 which exclusively uses ECC for digital signature generation and key exchange. The suite is intended to protect both classified and unclassified national security systems and information.

Recently, a large number of cryptographic primitives based on bilinear mappings on various elliptic curve groups, such as the Weil
Weil pairing
In mathematics, the Weil pairing is a construction of roots of unity by means of functions on an elliptic curve E, in such a way as to constitute a pairing on the torsion subgroup of E...

 and Tate pairings, have been introduced. Schemes based on these primitives provide efficient identity-based encryption as well as pairing-based signatures, signcryption, key agreement, and proxy re-encryption.

Implementation considerations

Although the details of each particular elliptic curve scheme are described in the article referenced above some common implementation considerations are discussed here.

Domain parameters

To use ECC all parties must agree on all the elements defining the elliptic curve, that is, the domain parameters of the scheme. The field is defined by p in the prime case and the pair of m and f in the binary case. The elliptic curve is defined by the constants a and b used in its defining equation. Finally, the cyclic subgroup is defined by its generator (aka. base point) G. For cryptographic application the order
Order (group theory)
In group theory, a branch of mathematics, the term order is used in two closely related senses:* The order of a group is its cardinality, i.e., the number of its elements....

 of G, that is the smallest non-negative number n such that , is normally prime. Since n is the size of a subgroup of it follows from Lagrange's theorem
Lagrange's theorem (group theory)
Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the order of every subgroup H of G divides the order of G. The theorem is named after Joseph Lagrange....

 that the number is an integer. In cryptographic applications this number h, called the cofactor, must be small () and, preferably, . Let us summarize: in the prime case the domain parameters are and in the binary case they are .

Unless there is an assurance that domain parameters were generated by a party trusted with respect to their use, the domain parameters must be validated before use.

The generation of domain parameters is not usually done by each participant since this involves counting the number of points on a curve which is time-consuming and troublesome to implement. As a result several standard bodies published domain parameters of elliptic curves for several common field sizes:
Test vectors are also available.

If one (despite the said above) wants to build one's own domain parameters one should select the underlying field and then use one of the following strategies to find a curve with appropriate (i.e., near prime) number of points using one of the following methods:
  • select a random curve and use a general point-counting algorithm, for example, Schoof's algorithm
    Schoof's algorithm
    Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of...

     or Schoof–Elkies–Atkin algorithm,
  • select a random curve from a family which allows easy calculation of the number of points (e.g., Koblitz curves), or
  • select the number of points and generate a curve with this number of points using complex multiplication technique.


Several classes of curves are weak and should be avoided:
  • curves over with non-prime m are vulnerable to Weil descent attacks.
  • curves such that n divides (where p is the characteristic of the field – q for a prime field, or for a binary field) for sufficiently small B are vulnerable to MOV attack which applies usual DLP in a small degree extension field of to solve ECDLP. The bound B should be chosen so that discrete logarithms in the field are at least as difficult to compute as discrete logs on the elliptic curve .
  • curves such that are vulnerable to the attack that maps the points on the curve to the additive group of

Key sizes

Since all the fastest known algorithms that allow to solve the ECDLP (baby-step giant-step
Baby-step giant-step
In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm computing the discrete logarithm. The discrete log problem is of fundamental importance to the area of public key cryptography...

, Pollard's rho
Pollard's rho algorithm for logarithms
Pollard's rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer factorization problem....

, etc.), need steps, it follows that the size of the underlying field shall be roughly twice the security parameter. For example, for 128-bit security one needs a curve over , where . This can be contrasted with finite-field cryptography (e.g., DSA
Digital Signature Algorithm
The Digital Signature Algorithm is a United States Federal Government standard or FIPS for digital signatures. It was proposed by the National Institute of Standards and Technology in August 1991 for use in their Digital Signature Standard , specified in FIPS 186, adopted in 1993. A minor...

) which requires 3072-bit public keys and 256-bit private keys, and integer factorization cryptography (e.g., RSA) which requires 3072-bit public and private keys.

The hardest ECC scheme (publicly) broken to date had a 112-bit key for the prime field case and a 109-bit key for the binary field case. For the prime field case this was broken in July 2009 using a cluster of over 200 PlayStation 3
PlayStation 3
The is the third home video game console produced by Sony Computer Entertainment and the successor to the PlayStation 2 as part of the PlayStation series. The PlayStation 3 competes with Microsoft's Xbox 360 and Nintendo's Wii as part of the seventh generation of video game consoles...

 game consoles and could have been finished in 3.5 months using this cluster when running continuously (see ). For the binary field case, it was broken in April 2004 using 2600 computers for 17 months.

A current project is aiming at breaking the ECC2K-130 challenge by Certicom, by using a wide range of different hardware : CPUs, GPUs, FPGA.

Projective coordinates

A close examination of the addition rules shows that in order to add two points one needs not only several additions and multiplications in but also an inversion operation. The inversion (for given find such that ) is one to two orders of magnitude slower than multiplication. Fortunately, points on a curve can be represented in different coordinate systems which do not require an inversion operation to add two points. Several such systems were proposed: in the projective system each point is represented by three coordinates using the following relation: , ; in the Jacobian system a point is also represented with three coordinates , but a different relation is used: , ; in the López–Dahab system the relation is , ; in the modified Jacobian system the same relations are used but four coordinates are stored and used for calculations ; and in the Chudnovsky Jacobian system five coordinates are used . Note that there may be different naming conventions, for example, IEEE P1363
IEEE P1363
IEEE P1363 is an Institute of Electrical and Electronics Engineers standardization project for public-key cryptography. It includes specifications for:* Traditional public-key cryptography...

-2000 standard uses "projective coordinates" to refer to what is commonly called Jacobian coordinates. An additional speed-up is possible if mixed coordinates are used.

Fast reduction (NIST curves)

Reduction modulo p (which is needed for addition and multiplication) can be executed much faster if the prime p is a pseudo-Mersenne prime
Mersenne prime
In mathematics, a Mersenne number, named after Marin Mersenne , is a positive integer that is one less than a power of two: M_p=2^p-1.\,...

 that is , for example, or Compared to Barrett reduction
Barrett reduction
In modular arithmetic, Barrett reduction is a reduction algorithm introduced in 1986 by P.D. Barrett. A naive way of computingc = a \times b \pmod n. \,...

 there can be an order of magnitude speedup. The speedup here is a practical rather than theoretical one, and derives from the fact that the moduli of numbers against numbers near powers of two can be performed efficiently by computers operating on binary numbers with bitwise operation
Bitwise operation
A bitwise operation operates on one or more bit patterns or binary numerals at the level of their individual bits. This is used directly at the digital hardware level as well as in microcode, machine code and certain kinds of high level languages...

s.

The curves over with pseudo-Mersenne p are recommended by NIST. Yet another advantage of the NIST curves is the fact that they use a = −3 which improves addition in Jacobian coordinates.

NIST-recommended elliptic curves

NIST recommends fifteen elliptic curves. Specifically, FIPS 186-3 has ten recommended finite fields:
  • Five prime fields for certain primes p of sizes 192, 224, 256, 384, and 521 bits. For each of the prime fields, one elliptic curve is recommended.
  • Five binary fields for m equal 163, 233, 283, 409, and 571. For each of the binary fields, one elliptic curve and one Koblitz
    Neal Koblitz
    Neal I. Koblitz is a Professor of Mathematics at the University of Washington in the Department of Mathematics. He is also an adjunct professor with the Centre for Applied Cryptographic Research at the University of Waterloo. He is the creator of hyperelliptic curve cryptography and the...

     curve was selected.


The NIST recommendation thus contains a total of five prime curves and ten binary curves. The curves were chosen for optimal security and implementation efficiency.

Side-channel attacks

Unlike DLP
Discrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...

 systems (where it is possible to use the same procedure for squaring and multiplication) the EC addition is significantly different for doubling () and general addition () depending on the coordinate system used. Consequently, it is important to counteract side channel attack
Side channel attack
In cryptography, a side channel attack is any attack based on information gained from the physical implementation of a cryptosystem, rather than brute force or theoretical weaknesses in the algorithms...

s (e.g., timing or simple/differential power analysis attacks
Power analysis
In cryptography, power analysis is a form of side channel attack in which the attacker studies the power consumption of a cryptographic hardware device...

) using, for example, fixed pattern window (aka. comb) methods (note that this does not increase the computation time). Another concern for ECC-systems is the danger of fault attacks
Differential fault analysis
Differential fault analysis is a type of side channel attack in the field of cryptography, specifically cryptanalysis. The principle is to induce faults—unexpected environmental conditions—into cryptographic implementations, to reveal their internal states....

, especially when running on smart card
Smart card
A smart card, chip card, or integrated circuit card , is any pocket-sized card with embedded integrated circuits. A smart card or microprocessor cards contain volatile memory and microprocessor components. The card is made of plastic, generally polyvinyl chloride, but sometimes acrylonitrile...

s.

Quantum computing attacks

Elliptic curve cryptography is vulnerable to a modified Shor's algorithm
Shor's algorithm
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...

 for solving the discrete logarithm problem on elliptic curves.

Patents

At least one ECC scheme (ECMQV) and some implementation techniques are covered by patents.

Open source


Proprietary/commercial

  • MIRACL: Multiprecision Integer and Rational Arithmetic C/C++ Library
  • CNG
    Cryptographic Application Programming Interface
    The Cryptographic Application Programming Interface is an application programming interface included with Microsoft Windows operating systems that provides services to enable developers to secure Windows-based applications using cryptography...

     API in Windows Vista
    Windows Vista
    Windows Vista is an operating system released in several variations developed by Microsoft for use on personal computers, including home and business desktops, laptops, tablet PCs, and media center PCs...

     and Windows Server 2008 with managed
    Managed code
    Managed code is a term coined by Microsoft to identify computer program code that requires and will only execute under the "management" of a Common Language Runtime virtual machine ....

     wrappers for CNG in .NET Framework
    .NET Framework
    The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...

     3.5
  • Sun Java System Web Server 7.0 and later
  • Java SE
    Java Platform, Standard Edition
    Java Platform, Standard Edition or Java SE is a widely used platform for programming in the Java language. It is the Java Platform used to deploy portable applications for general use...

     6
  • Java Card
    Java Card
    Java Card refers to a technology that allows Java-dd applications to be run securely on smart cards and similar small memory footprint devices. Java Card is the tiniest of Java targeted for embedded devices. Java Card gives the user ability to program the device and make them application...

  • Security Builder Crypto
  • Elliptic Curve Point Multiply and Verify Core
  • RSA BSAFE(R) Crypto-J and Crypto-C ME

Alternative representations of elliptic curves

  • Hessian curves
  • Edwards curves
  • Twisted curves
  • Twisted Hessian curves
    Twisted Hessian curves
    In mathematics, the Twisted Hessian curve represents a generalization of Hessian curves; it was introduced in elliptic curve cryptography to speed up the addition and doubling formulas and to have strongly unified arithmetic. In some operations , it is close in speed to Edwards...

  • Twisted Edwards curve
    Twisted Edwards curve
    In algebraic geometry, the Twisted Edwards curves are plane models of elliptic curves, a generalisation of Edwards curves introduced by Bernstein et al. and named after Harold M. Edwards...

  • Doubling-oriented Doche–Icart–Kohel curve
    Doubling-oriented Doche–Icart–Kohel curve
    In mathematics, the doubling-oriented Doche–Icart–Kohel curve is a form in which an elliptic curve can be written. It is a special case of Weierstrass form and it is also important in elliptic-curve cryptography because the doubling speeds up considerably .It has been introduced by Christophe...

  • Tripling-oriented Doche–Icart–Kohel curve
    Tripling-oriented Doche–Icart–Kohel curve
    The tripling-oriented Doche–Icart–Kohel curve is a form of an elliptic curve that has been used lately in cryptography; it is a particular type of Weierstrass curve...

  • Jacobian curve
    Jacobian curve
    In mathematics, the Jacobi curve is a representantion of an elliptic curve different than the usual one . Sometimes it is used in cryptography instead of the Weierstrass form because it can provide a defence against simple and differential power analysis style attacks; it is possible, indeed, to...

  • Montgomery curve

See also

  • DNSCurve
    DNSCurve
    DNSCurve is a proposed new secure protocol for the Domain Name System , designed by Daniel J. Bernstein. The basic idea is to define a secure new transport layer protocol to replace TCP, called CurveCP, using elliptic curve cryptography on top of UDP then doing DNS queries inside CurveCP...

  • ECC patents
    ECC patents
    Patent-related uncertainty around elliptic curve cryptography , or ECC patents, is one of the main factors limiting its wide acceptance. For example, the OpenSSL team accepted an ECC patch only in 2005 , despite the fact that it was submitted in 2002.According to Bruce Schneier as of May 31, 2007,...

  • ECDH
  • ECDSA
  • ECMQV
  • Public-key cryptography
    Public-key cryptography
    Public-key cryptography refers to a cryptographic system requiring two separate keys, one to lock or encrypt the plaintext, and one to unlock or decrypt the cyphertext. Neither key will do both functions. One of these keys is published or public and the other is kept private...

  • Quantum cryptography
    Quantum cryptography
    Quantum key distribution uses quantum mechanics to guarantee secure communication. It enables two parties to produce a shared random secret key known only to them, which can then be used to encrypt and decrypt messages...

  • Pairing-based cryptography
    Pairing-based cryptography
    Pairing-based cryptography is the use of a pairing between elements of two cryptographic groups to a third group to construct cryptographic systems. If the same group is used for the first two groups, the pairing is called symmetric and is a mapping from two elements of one group to an element from...

  • Homomorphic Signatures for Network Coding
    Homomorphic signatures for network coding
    Network coding has been shown to optimally use bandwidth in a network, maximizing information flow but the scheme is very inherently vulnerable to pollution attacks by malicious nodes in the network. A node injecting garbage can quickly affect many receivers...

  • Universal Metering Interface
    Universal Metering Interface
    UMI is a set of 3 free open specifications for smart metering and smart home products. The UMI specifications define; a module interface based on SPI, an optical communications interface based on EN62056-21 and a security interface based on ECC-256 and AES-128...

     (UMI) an open standard, originally created by Cambridge Consultants for use in Smart Metering devices/systems and home automation, which uses AES-128 alongside ECC-256 for various security purposes.

External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK