Elliptic Curve Playground

Notes

1. Before anything can be done, choose a random curve and a modulus. Elliptic curves also have prominent roles in factoring, so if the modulus isn't a prime, things might break horribly on occasion.
2. Check random x-coordinates until you find a point on the curve. (With the "Find Point" helper.)
3. Generate a cyclic group or add/multiply points to find more points. The addition helper is animated, to demonstrate the chord-tangent law of composition (a line through any two points necessarily intersects a third point) and the group law (the chord-tangent law + an x-axis flip). The addition helper also doesn't verify that points are on the curve, so you can play with (as they're called in crypto) invalid-curve attacks.
4. If the modulus is q, then the number of points on the curve N is bounded by: (Hasse's Theorem)
5. The order of a generated cyclic group is a divisor of N. (Lagrange's Theorem)
6. Most elliptic curves create modules (Abelian ring acting on a set of vectors). If you find a subgroup of prime order, that subgroup/subspace is a vector space (field acting on a set of vectors)
7. The curve E: y² = x³ (mod p) is called a singular curve and is always isomorphic to Z_p, disregarding the singularity (0, 0). There's an efficiently computable group isomorphism from E(Z_p) to Z_p defined by (x, y) → x/y, ∞ → 0.
8. Given a curve E: y² = x³ + Ax + B (mod p) and a quadratic non-residue d, the twist of E is defined as E^d: y² = x³ + Ad²x + Bd³ (mod p)
   1. E and E^d share 2, 1, or 0 points. The x-coordinate of these points is (Bd³ - B) / (A - Ad²)
   2. If E, mod p, has p + 1 - a points, then E^d has p + 1 + a points. As mentioned above, knowledge of the order of all curves E^d allows us to classify the structures of all of the quadratic twists of E.

Interesting Curves

• y² = x³ + 3x + 0 (mod 5)
  • E(F_q) ≅ <(2, 2)> ≅ Z₁₀ ≅ Z₂×Z₅
  • The decomposition shows that there's one non-zero point of order 2 and four non-zero points of order 5--exactly the same as in the integers modulo 10.
• y² = x³ + 3x + 1 (mod 7)
  • E(F_q) ≅ <(2, 1)> ≅ Z₁₂ ≅ Z₃×Z₄
  • Z₄ is in the decomposition instead of Z₂×Z₂ because there're only 2 points of order 2 (only 1 root of the equation and the zero point).
• y² = x³ + 7x + 3 (mod 13)
  • E(F_q) ≅ <(0, 4)> ≅ Z₁₃
  • This curve has a similar structure to the NIST ECC curves in that it has only one large subgroup of prime order.
  • The second reason it's special is that the number of points on the curve is equal to modulus (unlike the NIST curves). Because of that, it's called an anomalous curve. The DLP can be efficiently solved on anomalous elliptic curves.
  • All of this curve's quadratic twists have order 15, which is a square-free number, so all of its twists must be isomorphic to Z_15.
• y² = x³ + 2x + 12 (mod 29)
  • E(F_q) ≅ <(14, 0), (17, 0), (18, 14)> ≅ Z₂×Z₂×Z₇
  • Unlike the second curve, there are 4 points of order 2 on this curve, but no points of order 4.
  • The modulus 29 was chosen because it's close to 28 = 4 * 7 (the desired order of the curve group). This is how curves in ECC standards often look--they have a few small subgroups and one large group of prime order.