g1.go

Documentation: github.com/cloudflare/circl/ecc/bls12381

     1  package bls12381
     2  
     3  import (
     4  	"crypto"
     5  	_ "crypto/sha256"
     6  	"crypto/subtle"
     7  	"fmt"
     8  	"math/big"
     9  
    10  	"github.com/cloudflare/circl/ecc/bls12381/ff"
    11  	"github.com/cloudflare/circl/expander"
    12  )
    13  
    14  // G1Size is the length in bytes of an element in G1 in uncompressed form..
    15  const G1Size = 2 * ff.FpSize
    16  
    17  // G1SizeCompressed is the length in bytes of an element in G1 in compressed form.
    18  const G1SizeCompressed = ff.FpSize
    19  
    20  // G1 is a point in the BLS12 curve over Fp.
    21  type G1 struct{ x, y, z ff.Fp }
    22  
    23  func (g G1) String() string { return fmt.Sprintf("x: %v\ny: %v\nz: %v", g.x, g.y, g.z) }
    24  
    25  // Bytes serializes a G1 element in uncompressed form.
    26  func (g G1) Bytes() []byte { return g.encodeBytes(false) }
    27  
    28  // Bytes serializes a G1 element in compressed form.
    29  func (g G1) BytesCompressed() []byte { return g.encodeBytes(true) }
    30  
    31  // SetBytes sets g to the value in bytes, and returns a non-nil error if not in G1.
    32  func (g *G1) SetBytes(b []byte) error {
    33  	if len(b) < G1SizeCompressed {
    34  		return errInputLength
    35  	}
    36  
    37  	isCompressed := int((b[0] >> 7) & 0x1)
    38  	isInfinity := int((b[0] >> 6) & 0x1)
    39  	isBigYCoord := int((b[0] >> 5) & 0x1)
    40  
    41  	if isInfinity == 1 {
    42  		l := G1Size
    43  		if isCompressed == 1 {
    44  			l = G1SizeCompressed
    45  		}
    46  		zeros := make([]byte, l-1)
    47  		if (b[0]&0x1F) != 0 || subtle.ConstantTimeCompare(b[1:], zeros) != 1 {
    48  			return errEncoding
    49  		}
    50  		g.SetIdentity()
    51  		return nil
    52  	}
    53  
    54  	x := (&[ff.FpSize]byte{})[:]
    55  	copy(x, b)
    56  	x[0] &= 0x1F
    57  	if err := g.x.UnmarshalBinary(x); err != nil {
    58  		return err
    59  	}
    60  
    61  	if isCompressed == 1 {
    62  		x3b := &ff.Fp{}
    63  		x3b.Sqr(&g.x)
    64  		x3b.Mul(x3b, &g.x)
    65  		x3b.Add(x3b, &g1Params.b)
    66  		if g.y.Sqrt(x3b) == 0 {
    67  			return errEncoding
    68  		}
    69  		if g.y.IsNegative() != isBigYCoord {
    70  			g.y.Neg()
    71  		}
    72  	} else {
    73  		if len(b) < G1Size {
    74  			return errInputLength
    75  		}
    76  		if err := g.y.UnmarshalBinary(b[ff.FpSize:G1Size]); err != nil {
    77  			return err
    78  		}
    79  	}
    80  
    81  	g.z.SetOne()
    82  	if !g.IsOnG1() {
    83  		return errEncoding
    84  	}
    85  	return nil
    86  }
    87  
    88  func (g G1) encodeBytes(compressed bool) []byte {
    89  	g.toAffine()
    90  
    91  	var isCompressed, isInfinity, isBigYCoord byte
    92  	if compressed {
    93  		isCompressed = 1
    94  	}
    95  	if g.z.IsZero() == 1 {
    96  		isInfinity = 1
    97  	}
    98  	if isCompressed == 1 && isInfinity == 0 {
    99  		isBigYCoord = byte(g.y.IsNegative())
   100  	}
   101  
   102  	bytes, _ := g.x.MarshalBinary()
   103  	if isCompressed == 0 {
   104  		yBytes, _ := g.y.MarshalBinary()
   105  		bytes = append(bytes, yBytes...)
   106  	}
   107  	if isInfinity == 1 {
   108  		l := len(bytes)
   109  		for i := 0; i < l; i++ {
   110  			bytes[i] = 0
   111  		}
   112  	}
   113  
   114  	bytes[0] = bytes[0]&0x1F | headerEncoding(isCompressed, isInfinity, isBigYCoord)
   115  
   116  	return bytes
   117  }
   118  
   119  // Neg inverts g.
   120  func (g *G1) Neg() { g.y.Neg() }
   121  
   122  // SetIdentity assigns g to the identity element.
   123  func (g *G1) SetIdentity() { g.x = ff.Fp{}; g.y.SetOne(); g.z = ff.Fp{} }
   124  
   125  // isValidProjective returns true if the point is not a projective point.
   126  func (g *G1) isValidProjective() bool { return (g.x.IsZero() & g.y.IsZero() & g.z.IsZero()) != 1 }
   127  
   128  // IsOnG1 returns true if the point is in the group G1.
   129  func (g *G1) IsOnG1() bool { return g.isValidProjective() && g.isOnCurve() && g.isRTorsion() }
   130  
   131  // IsIdentity return true if the point is the identity of G1.
   132  func (g *G1) IsIdentity() bool { return g.isValidProjective() && (g.z.IsZero() == 1) }
   133  
   134  // cmov sets g to P if b == 1
   135  func (g *G1) cmov(P *G1, b int) {
   136  	(&g.x).CMov(&g.x, &P.x, b)
   137  	(&g.y).CMov(&g.y, &P.y, b)
   138  	(&g.z).CMov(&g.z, &P.z, b)
   139  }
   140  
   141  // sigma is an edomorphism defined by (x, y) → (βx, y) for some β ∈ Fp of
   142  // multiplicative order 3.
   143  func (g *G1) sigma(P *G1) { *g = *P; g.x.Mul(&g.x, &g1Sigma.beta0) }
   144  
   145  // sigma2 is sigma(sigma(P)).
   146  func (g *G1) sigma2(P *G1) { *g = *P; g.x.Mul(&g.x, &g1Sigma.beta1) }
   147  
   148  // isRTorsion returns true if point is in the r-torsion subgroup.
   149  func (g *G1) isRTorsion() bool {
   150  	// Bowe, "Faster Subgroup Checks for BLS12-381" (https://eprint.iacr.org/2019/814)
   151  	Q, _2sP, ssP := &G1{}, &G1{}, &G1{}
   152  	coef := bls12381.g1Check[:]
   153  
   154  	_2sP.sigma(g)              // s(P)
   155  	_2sP.Double()              // 2*s(P)
   156  	ssP.sigma2(g)              // s(s(P))
   157  	Q.Add(g, ssP)              // P + s(s(P))
   158  	Q.Neg()                    // -P - s(s(P))
   159  	Q.Add(Q, _2sP)             // 2*s(P) - P - s(s(P))
   160  	Q.scalarMultShort(coef, Q) // coef * [2*s(P) - P - s(s(P))]
   161  	ssP.Neg()                  // -s(s(P))
   162  	Q.Add(Q, ssP)              // coef * [2*s(P) - P - s(s(P))] - s(s(P))
   163  
   164  	return Q.IsIdentity()
   165  }
   166  
   167  // clearCofactor maps g to a point in the r-torsion subgroup.
   168  //
   169  // This method multiplies g times (1-z) rather than (z-1)^2/3, where z is the
   170  // BLS12 parameter. This is enough to remove points of order
   171  //
   172  //	h \in {3, 11, 10177, 859267, 52437899},
   173  //
   174  // and because there are no points of order h^2. See Section 5 of Wahby-Boneh
   175  // "Fast and simple constant-time hashing to the BLS12-381 elliptic curve" at
   176  // https://eprint.iacr.org/2019/403
   177  func (g *G1) clearCofactor() { g.scalarMultShort(bls12381.oneMinusZ[:], g) }
   178  
   179  // Double updates g = 2g.
   180  func (g *G1) Double() {
   181  	// Reference:
   182  	//   "Complete addition formulas for prime order elliptic curves" by
   183  	//   Costello-Renes-Batina. [Alg.9] (eprint.iacr.org/2015/1060).
   184  	var R G1
   185  	X, Y, Z := &g.x, &g.y, &g.z
   186  	X3, Y3, Z3 := &R.x, &R.y, &R.z
   187  	var f0, f1, f2 ff.Fp
   188  	t0, t1, t2 := &f0, &f1, &f2
   189  	_3B := &g1Params._3b
   190  	t0.Sqr(Y)       // 1.  t0 =  Y * Y
   191  	Z3.Add(t0, t0)  // 2.  Z3 = t0 + t0
   192  	Z3.Add(Z3, Z3)  // 3.  Z3 = Z3 + Z3
   193  	Z3.Add(Z3, Z3)  // 4.  Z3 = Z3 + Z3
   194  	t1.Mul(Y, Z)    // 5.  t1 =  Y * Z
   195  	t2.Sqr(Z)       // 6.  t2 =  Z * Z
   196  	t2.Mul(_3B, t2) // 7.  t2 = b3 * t2
   197  	X3.Mul(t2, Z3)  // 8.  X3 = t2 * Z3
   198  	Y3.Add(t0, t2)  // 9.  Y3 = t0 + t2
   199  	Z3.Mul(t1, Z3)  // 10. Z3 = t1 * Z3
   200  	t1.Add(t2, t2)  // 11. t1 = t2 + t2
   201  	t2.Add(t1, t2)  // 12. t2 = t1 + t2
   202  	t0.Sub(t0, t2)  // 13. t0 = t0 - t2
   203  	Y3.Mul(t0, Y3)  // 14. Y3 = t0 * Y3
   204  	Y3.Add(X3, Y3)  // 15. Y3 = X3 + Y3
   205  	t1.Mul(X, Y)    // 16. t1 =  X * Y
   206  	X3.Mul(t0, t1)  // 17. X3 = t0 * t1
   207  	X3.Add(X3, X3)  // 18. X3 = X3 + X3
   208  	*g = R
   209  }
   210  
   211  // Add updates g=P+Q.
   212  func (g *G1) Add(P, Q *G1) {
   213  	// Reference:
   214  	//   "Complete addition formulas for prime order elliptic curves" by
   215  	//   Costello-Renes-Batina. [Alg.7] (eprint.iacr.org/2015/1060).
   216  	var R G1
   217  	X1, Y1, Z1 := &P.x, &P.y, &P.z
   218  	X2, Y2, Z2 := &Q.x, &Q.y, &Q.z
   219  	X3, Y3, Z3 := &R.x, &R.y, &R.z
   220  	_3B := &g1Params._3b
   221  	var f0, f1, f2, f3, f4 ff.Fp
   222  	t0, t1, t2, t3, t4 := &f0, &f1, &f2, &f3, &f4
   223  	t0.Mul(X1, X2)  // 1.  t0 = X1 * X2
   224  	t1.Mul(Y1, Y2)  // 2.  t1 = Y1 * Y2
   225  	t2.Mul(Z1, Z2)  // 3.  t2 = Z1 * Z2
   226  	t3.Add(X1, Y1)  // 4.  t3 = X1 + Y1
   227  	t4.Add(X2, Y2)  // 5.  t4 = X2 + Y2
   228  	t3.Mul(t3, t4)  // 6.  t3 = t3 * t4
   229  	t4.Add(t0, t1)  // 7.  t4 = t0 + t1
   230  	t3.Sub(t3, t4)  // 8.  t3 = t3 - t4
   231  	t4.Add(Y1, Z1)  // 9.  t4 = Y1 + Z1
   232  	X3.Add(Y2, Z2)  // 10. X3 = Y2 + Z2
   233  	t4.Mul(t4, X3)  // 11. t4 = t4 * X3
   234  	X3.Add(t1, t2)  // 12. X3 = t1 + t2
   235  	t4.Sub(t4, X3)  // 13. t4 = t4 - X3
   236  	X3.Add(X1, Z1)  // 14. X3 = X1 + Z1
   237  	Y3.Add(X2, Z2)  // 15. Y3 = X2 + Z2
   238  	X3.Mul(X3, Y3)  // 16. X3 = X3 * Y3
   239  	Y3.Add(t0, t2)  // 17. Y3 = t0 + t2
   240  	Y3.Sub(X3, Y3)  // 18. Y3 = X3 - Y3
   241  	X3.Add(t0, t0)  // 19. X3 = t0 + t0
   242  	t0.Add(X3, t0)  // 20. t0 = X3 + t0
   243  	t2.Mul(_3B, t2) // 21. t2 = b3 * t2
   244  	Z3.Add(t1, t2)  // 22. Z3 = t1 + t2
   245  	t1.Sub(t1, t2)  // 23. t1 = t1 - t2
   246  	Y3.Mul(_3B, Y3) // 24. Y3 = b3 * Y3
   247  	X3.Mul(t4, Y3)  // 25. X3 = t4 * Y3
   248  	t2.Mul(t3, t1)  // 26. t2 = t3 * t1
   249  	X3.Sub(t2, X3)  // 27. X3 = t2 - X3
   250  	Y3.Mul(Y3, t0)  // 28. Y3 = Y3 * t0
   251  	t1.Mul(t1, Z3)  // 29. t1 = t1 * Z3
   252  	Y3.Add(t1, Y3)  // 30. Y3 = t1 + Y3
   253  	t0.Mul(t0, t3)  // 31. t0 = t0 * t3
   254  	Z3.Mul(Z3, t4)  // 32. Z3 = Z3 * t4
   255  	Z3.Add(Z3, t0)  // 33. Z3 = Z3 + t0
   256  	*g = R
   257  }
   258  
   259  // ScalarMult calculates g = kP.
   260  func (g *G1) ScalarMult(k *Scalar, P *G1) { b, _ := k.MarshalBinary(); g.scalarMult(b, P) }
   261  
   262  // scalarMult calculates g = kP, where k is the scalar in big-endian order.
   263  func (g *G1) scalarMult(k []byte, P *G1) {
   264  	var Q G1
   265  	Q.SetIdentity()
   266  	T := &G1{}
   267  	var mults [16]G1
   268  	mults[0].SetIdentity()
   269  	mults[1] = *P
   270  	for i := 1; i < 8; i++ {
   271  		mults[2*i] = mults[i]
   272  		mults[2*i].Double()
   273  		mults[2*i+1].Add(&mults[2*i], P)
   274  	}
   275  	N := 8 * len(k)
   276  	for i := 0; i < N; i += 4 {
   277  		Q.Double()
   278  		Q.Double()
   279  		Q.Double()
   280  		Q.Double()
   281  		idx := 0xf & (k[i/8] >> uint(4-i%8))
   282  		for j := 0; j < 16; j++ {
   283  			T.cmov(&mults[j], subtle.ConstantTimeByteEq(idx, uint8(j)))
   284  		}
   285  		Q.Add(&Q, T)
   286  	}
   287  	*g = Q
   288  }
   289  
   290  // scalarMultShort multiplies by a short, constant scalar k, where k is the
   291  // scalar in big-endian order. Runtime depends on the scalar.
   292  func (g *G1) scalarMultShort(k []byte, P *G1) {
   293  	// Since the scalar is short and low Hamming weight not much helps.
   294  	var Q G1
   295  	Q.SetIdentity()
   296  	N := 8 * len(k)
   297  	for i := 0; i < N; i++ {
   298  		Q.Double()
   299  		bit := 0x1 & (k[i/8] >> uint(7-i%8))
   300  		if bit != 0 {
   301  			Q.Add(&Q, P)
   302  		}
   303  	}
   304  	*g = Q
   305  }
   306  
   307  // IsEqual returns true if g and p are equivalent.
   308  func (g *G1) IsEqual(p *G1) bool {
   309  	var lx, rx, ly, ry ff.Fp
   310  	lx.Mul(&g.x, &p.z) // lx = x1*z2
   311  	rx.Mul(&p.x, &g.z) // rx = x2*z1
   312  	lx.Sub(&lx, &rx)   // lx = lx-rx
   313  	ly.Mul(&g.y, &p.z) // ly = y1*z2
   314  	ry.Mul(&p.y, &g.z) // ry = y2*z1
   315  	ly.Sub(&ly, &ry)   // ly = ly-ry
   316  	return g.isValidProjective() && p.isValidProjective() && lx.IsZero() == 1 && ly.IsZero() == 1
   317  }
   318  
   319  // isOnCurve returns true if g is a valid point on the curve.
   320  func (g *G1) isOnCurve() bool {
   321  	var x3, z3, y2 ff.Fp
   322  	y2.Sqr(&g.y)             // y2 = y^2
   323  	y2.Mul(&y2, &g.z)        // y2 = y^2*z
   324  	x3.Sqr(&g.x)             // x3 = x^2
   325  	x3.Mul(&x3, &g.x)        // x3 = x^3
   326  	z3.Sqr(&g.z)             // z3 = z^2
   327  	z3.Mul(&z3, &g.z)        // z3 = z^3
   328  	z3.Mul(&z3, &g1Params.b) // z3 = 4*z^3
   329  	x3.Add(&x3, &z3)         // x3 = x^3 + 4*z^3
   330  	y2.Sub(&y2, &x3)         // y2 = y^2*z - (x^3 + 4*z^3)
   331  	return y2.IsZero() == 1
   332  }
   333  
   334  // toAffine updates g with its affine representation.
   335  func (g *G1) toAffine() {
   336  	if g.z.IsZero() != 1 {
   337  		var invZ ff.Fp
   338  		invZ.Inv(&g.z)
   339  		g.x.Mul(&g.x, &invZ)
   340  		g.y.Mul(&g.y, &invZ)
   341  		g.z.SetOne()
   342  	}
   343  }
   344  
   345  // EncodeToCurve is a non-uniform encoding from an input byte string (and
   346  // an optional domain separation tag) to elements in G1. This function must not
   347  // be used as a hash function, otherwise use G1.Hash instead.
   348  func (g *G1) Encode(input, dst []byte) {
   349  	const L = 64
   350  	pseudo := expander.NewExpanderMD(crypto.SHA256, dst).Expand(input, L)
   351  
   352  	bu := new(big.Int).SetBytes(pseudo)
   353  	bu.Mod(bu, new(big.Int).SetBytes(ff.FpOrder()))
   354  
   355  	var u ff.Fp
   356  	u.SetBytes(pseudo[:L])
   357  
   358  	var q isogG1Point
   359  	q.sswu(&u)
   360  	g.evalIsogG1(&q)
   361  	g.clearCofactor()
   362  }
   363  
   364  // Hash produces an element of G1 from the hash of an input byte string and
   365  // an optional domain separation tag. This function is safe to use when a
   366  // random oracle returning points in G1 be required.
   367  func (g *G1) Hash(input, dst []byte) {
   368  	const L = 64
   369  	pseudo := expander.NewExpanderMD(crypto.SHA256, dst).Expand(input, 2*L)
   370  
   371  	var u0, u1 ff.Fp
   372  	u0.SetBytes(pseudo[0*L : 1*L])
   373  	u1.SetBytes(pseudo[1*L : 2*L])
   374  
   375  	var q0, q1 isogG1Point
   376  	q0.sswu(&u0)
   377  	q1.sswu(&u1)
   378  	var p0, p1 G1
   379  	p0.evalIsogG1(&q0)
   380  	p1.evalIsogG1(&q1)
   381  	g.Add(&p0, &p1)
   382  	g.clearCofactor()
   383  }
   384  
   385  // G1Generator returns the generator point of G1.
   386  func G1Generator() *G1 {
   387  	var G G1
   388  	G.x = g1Params.genX
   389  	G.y = g1Params.genY
   390  	G.z.SetOne()
   391  	return &G
   392  }
   393  
   394  // affinize converts an entire slice to affine at once
   395  func affinize(points []*G1) {
   396  	if len(points) == 0 {
   397  		return
   398  	}
   399  	ws := make([]ff.Fp, len(points)+1)
   400  	ws[0].SetOne()
   401  	for i := 0; i < len(points); i++ {
   402  		ws[i+1].Mul(&ws[i], &points[i].z)
   403  	}
   404  
   405  	w := &ff.Fp{}
   406  	w.Inv(&ws[len(points)])
   407  
   408  	zinv := &ff.Fp{}
   409  	for i := len(points) - 1; i >= 0; i-- {
   410  		zinv.Mul(w, &ws[i])
   411  		w.Mul(w, &points[i].z)
   412  
   413  		points[i].x.Mul(&points[i].x, zinv)
   414  		points[i].y.Mul(&points[i].y, zinv)
   415  		points[i].z.SetOne()
   416  	}
   417  }
   418
View as plain text