curve.go raw

   1  // Package goldilocks provides elliptic curve operations over the goldilocks curve.
   2  package goldilocks
   3  
   4  import fp "github.com/cloudflare/circl/math/fp448"
   5  
   6  // Curve is the Goldilocks curve x^2+y^2=z^2-39081x^2y^2.
   7  type Curve struct{}
   8  
   9  // Identity returns the identity point.
  10  func (Curve) Identity() *Point {
  11  	return &Point{
  12  		y: fp.One(),
  13  		z: fp.One(),
  14  	}
  15  }
  16  
  17  // IsOnCurve returns true if the point lies on the curve.
  18  func (Curve) IsOnCurve(P *Point) bool {
  19  	x2, y2, t, t2, z2 := &fp.Elt{}, &fp.Elt{}, &fp.Elt{}, &fp.Elt{}, &fp.Elt{}
  20  	rhs, lhs := &fp.Elt{}, &fp.Elt{}
  21  	// Check z != 0
  22  	eq0 := !fp.IsZero(&P.z)
  23  
  24  	fp.Mul(t, &P.ta, &P.tb)  // t = ta*tb
  25  	fp.Sqr(x2, &P.x)         // x^2
  26  	fp.Sqr(y2, &P.y)         // y^2
  27  	fp.Sqr(z2, &P.z)         // z^2
  28  	fp.Sqr(t2, t)            // t^2
  29  	fp.Add(lhs, x2, y2)      // x^2 + y^2
  30  	fp.Mul(rhs, t2, &paramD) // dt^2
  31  	fp.Add(rhs, rhs, z2)     // z^2 + dt^2
  32  	fp.Sub(lhs, lhs, rhs)    // x^2 + y^2 - (z^2 + dt^2)
  33  	eq1 := fp.IsZero(lhs)
  34  
  35  	fp.Mul(lhs, &P.x, &P.y) // xy
  36  	fp.Mul(rhs, t, &P.z)    // tz
  37  	fp.Sub(lhs, lhs, rhs)   // xy - tz
  38  	eq2 := fp.IsZero(lhs)
  39  
  40  	return eq0 && eq1 && eq2
  41  }
  42  
  43  // Generator returns the generator point.
  44  func (Curve) Generator() *Point {
  45  	return &Point{
  46  		x:  genX,
  47  		y:  genY,
  48  		z:  fp.One(),
  49  		ta: genX,
  50  		tb: genY,
  51  	}
  52  }
  53  
  54  // Order returns the number of points in the prime subgroup.
  55  func (Curve) Order() Scalar { return order }
  56  
  57  // Double returns 2P.
  58  func (Curve) Double(P *Point) *Point { R := *P; R.Double(); return &R }
  59  
  60  // Add returns P+Q.
  61  func (Curve) Add(P, Q *Point) *Point { R := *P; R.Add(Q); return &R }
  62  
  63  // ScalarMult returns kP. This function runs in constant time.
  64  func (e Curve) ScalarMult(k *Scalar, P *Point) *Point {
  65  	k4 := &Scalar{}
  66  	k4.divBy4(k)
  67  	return e.pull(twistCurve{}.ScalarMult(k4, e.push(P)))
  68  }
  69  
  70  // ScalarBaseMult returns kG where G is the generator point. This function runs in constant time.
  71  func (e Curve) ScalarBaseMult(k *Scalar) *Point {
  72  	k4 := &Scalar{}
  73  	k4.divBy4(k)
  74  	return e.pull(twistCurve{}.ScalarBaseMult(k4))
  75  }
  76  
  77  // CombinedMult returns mG+nP, where G is the generator point. This function is non-constant time.
  78  func (e Curve) CombinedMult(m, n *Scalar, P *Point) *Point {
  79  	m4 := &Scalar{}
  80  	n4 := &Scalar{}
  81  	m4.divBy4(m)
  82  	n4.divBy4(n)
  83  	return e.pull(twistCurve{}.CombinedMult(m4, n4, twistCurve{}.pull(P)))
  84  }
  85