Editing Elliptic-curve cryptography (section)

== Elliptic curve theory ==
For the purposes of this article, an ''elliptic curve'' is a [[plane curve]] over a [[finite field]] (rather than the real numbers) which consists of the points satisfying the equation
: <math>y^2 = x^3 + ax + b,</math>
along with a distinguished [[point at infinity]], denoted ∞. The coordinates here are to be chosen from a fixed [[finite field]] of [[Characteristic (algebra)#Case of fields|characteristic]] not equal to 2 or 3, or the curve equation would be somewhat more complicated.

This set of points, together with the [[Elliptic curve#The group law|group operation of elliptic curves]], is an [[abelian group]], with the point at infinity as an identity element. The structure of the group is inherited from the [[Divisor (algebraic geometry)|divisor group]] of the underlying [[algebraic variety]]:
: <math>\operatorname{Div}^0(E) \to \operatorname{Pic}^0(E) \simeq E.</math>

=== Application to cryptography ===
[[Public-key cryptography]] is based on the [[Intractability (complexity)#Intractability|intractability]] of certain mathematical [[Computational hardness assumption|problems]]. Early public-key systems, such as [[RSA_(cryptosystem)|RSA]]'s 1983 patent, based their security on the assumption that it is difficult to [[Integer factorization|factor]] a large integer composed of two or more large prime factors which are far apart. For later elliptic-curve-based protocols, the base assumption is that finding the [[discrete logarithm]] of a random elliptic curve element with respect to a publicly known base point is infeasible (the [[computational Diffie–Hellman assumption]]): this is the "elliptic curve discrete logarithm problem" (ECDLP). The security of elliptic curve cryptography depends on the ability to compute a [[elliptic curve point multiplication|point multiplication]] and the inability to compute the multiplicand given the original point and product point. The size of the elliptic curve, measured by the total number of discrete integer pairs satisfying the curve equation, determines the difficulty of the problem.

The primary benefit promised by elliptic curve cryptography over alternatives such as RSA is a smaller [[key size]], reducing storage and transmission requirements.<ref name=":0" /> For example, a 256-bit elliptic curve public key should provide [[Security level|comparable security]] to a 3072-bit RSA public key.

=== Cryptographic schemes ===
Several [[discrete logarithm]]-based protocols have been adapted to elliptic curves, replacing the group <math>(\mathbb{Z}_{p})^\times</math> with an elliptic curve:
* The [[Elliptic-curve Diffie–Hellman]] (ECDH) key agreement scheme is based on the [[Diffie–Hellman]] scheme,
* The Elliptic Curve [[Integrated Encryption Scheme]] (ECIES), also known as Elliptic Curve Augmented Encryption Scheme or simply the Elliptic Curve Encryption Scheme,
* The [[Elliptic Curve Digital Signature Algorithm]] (ECDSA) is based on the [[Digital Signature Algorithm]],
* The deformation scheme using Harrison's p-adic Manhattan metric,
* The [[EdDSA|Edwards-curve Digital Signature Algorithm]] (EdDSA) is based on [[Schnorr signature]] and uses [[twisted Edwards curve]]s,
* The [[ECMQV]] key agreement scheme is based on the [[Menezes–Qu–Vanstone|MQV]] key agreement scheme,
* The [[Implicit certificate|ECQV]] implicit certificate scheme.