ECC is about a group created via:
- a 2-dimension elliptic curve: an equation with unknowns x and y
- every Elliptic Curve follows this formula: y2 + a1 x y + a3 y = x3 + a2 x2 + a4 x + a6 (for some specified a1, a2, a3, a4, a6)
- actually, it can be shorten to this y2 = x3 + a x + b (short weierstrass form) in practice because the characteristic (order of a prime field) 2 and 3 points in prime fields (except for binary (GF(2x)) and GF(3x) curves)
- a curve of characteristic 2 (defined over GF(2x)) can be simplified to y2 + xy = x3 + ax2 + b
- a curve of characteristic 3 (defined over GF(3x)) can be simplified to y2 = x3 + x2 + b
- a finite field GF(p^m). But in practice today we mostly use curves in GF(p) where the elliptic curve's points will have coordinates modulo p.
- an addition operation (called group law):
+
will be defined (geometricaly) over these points.
Since coordinates are modulo a field, our crypto curve in reality looks more like this:
For example, NIST P-256 is defined on:
- the curve of equation
y^2 = x^3-3x+41058363725152142129326129780047268409114441015993725554835256314039467401291
- coordinates of the points are taken modulo
p = 2^256 - 2^224 + 2^192 + 2^96 - 1
- the addition operation is the typical one.
To my knowledge the same addition operation is used in ECC (see the figure below). For it to work the group needs an identity point, which does not exist. So we add a fictive point called "the point at infinity" and often written a large O.
To do crypto with all of that, you use the group as you use a group with normal (FF)DH or DSA.
A curve can always be expressed in Weierstrass normal form: y^2 = 4 x^3 - a x - c
There exist different types of curves:
- Curves in short-Weierstrass form
- Montgomery Curves
- Twisted Edwards Curves
- and probably some others?
The number of points in a subgroup is called the group order. Coincidentally, the number of times a point P
has to be added to itself to result in the point at infinity is also called the order of P
.
The torsion group of an ECC is the set of points that have a finite order (some points can add themselves ad infinitum).
There are different ways to see points, different representations allow for different levels of efficiency when it comes to computing point addition. For example you have affine coordinates (the normal (x,y)
) and projective coordinates
You can also compress points: since you can easily recover the y-coordinate from the x-coordinate
. One can just store the x-coordinate
and the sign of y
.
ECC works in a group, not in a field, and is hence not prone to strong attacks on normal (FF)DH like the index calculus and the number field sieve (NFS) algorithms.
Yet, there are still attacks to be aware of:
- twist-security.
- "all curves are twist secure in the following sense. Either the number of rational points on the curve and its twist are both prime, or, if the curve is Montgomery compatible, both orders are four times a prime.".
- djb page
- invalid curve attacks. TKTK
- anomalous curve. TKTK
- binary curves. TKTK
- small subgroup attacks: same as with normal (FF)DH. One can verify public keys received to make sure they are in the right subgroup. Interestingly, the main group of an ECC can have a prime order (unlike normal (FF)DH). If the order is not prime, we call the small factor the co-factor. (Curve25519 has a co-factor of 8.)
- MOV attack: if there exists a pairing from a curve to a weak finite field, then we can attack the finite field itself (which is easier)
- The Frey-Rück Attack: another pairing attack
- typical DLOG attacks: Pohlig-Hellman, Pollard Rho, Baby-Step-Giant-Step. These attacks work in groups, so they are as efficient in (FF)DH as in ECDH. It's easy to counter them by using large parameters though.
- 1985 - Victor S. Miller - Use of elliptic curves in cryptography
- 1987 - Neal Koblitz - Elliptic Curve Cryptosystems
- Elliptic curve cryptography algorithms entered wide use in ~2000.
- Edward curves invented in 2007
- ANSI X9.62 (1999)
- IEEE P1363 (2000)
- SEC 2 (2000): includes the bitcoin curve secp256k1.
- NIST FIPS 186-2 (2000)
- ANSI X9.63 (2001)
- Brainpool (2005): the german curves from BSI
- NSA Suite B (2005)
- ANSSI FRP256V1 (2011): the french curves
- curve25519/curve448 defined in RFC 7748 (2016)
- Barreto-Lynn-Scott (BLS) curves: BLS12-381 is one of them. Curve for pairings.
- long weierstrass form (every elliptic curve is defined like that)
- short weierstrass form (if char != 2 and 3)
- montgomery (just a change of variable from the short weierstrass form)
- extended jacobi quartic form
- (twisted) hessian form
- (twisted) Edward form
- this is "birationnaly" equivalent to a short weierstrass form, meaning that there is a mapping between the two curves but it's not perfect and is missing some points.
- (twisted) jacobi intersection form
or alternative representations:
- Hessian curve
- Edwards curve
- Twisted curve
- Twisted Hessian curve
- Twisted Edwards curve
- Doubling-oriented Doche–Icart–Kohel curve
- Tripling-oriented Doche–Icart–Kohel curve
- Jacobian curve
- Montgomery curve
- ECDH
- X25519/X448
- EdDSA
- ECDSA
- qDSA
- schnorr-curve25519 (strobe)
- Boneh-Lynn-Shacham (BLS) signature, being standardized and provide aggregation.
- Affine
- projective
- normal? http://www.ams.org/journals/bull/2007-44-03/S0273-0979-07-01153-6/S0273-0979-07-01153-6.pdf
- jacobi? https://en.wikipedia.org/wiki/Jacobian_curve
- safecurves: A comparison of all the standards from djb