g2.go

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

     1  package bls12381
     2  
     3  import (
     4  	"crypto"
     5  	"crypto/subtle"
     6  	"fmt"
     7  
     8  	"github.com/cloudflare/circl/ecc/bls12381/ff"
     9  	"github.com/cloudflare/circl/expander"
    10  )
    11  
    12  // G2Size is the length in bytes of an element in G2 in uncompressed form..
    13  const G2Size = 2 * ff.Fp2Size
    14  
    15  // G2SizeCompressed is the length in bytes of an element in G2 in compressed form.
    16  const G2SizeCompressed = ff.Fp2Size
    17  
    18  // G2 is a point in the twist of the BLS12 curve over Fp2.
    19  type G2 struct{ x, y, z ff.Fp2 }
    20  
    21  func (g G2) String() string { return fmt.Sprintf("x: %v\ny: %v\nz: %v", g.x, g.y, g.z) }
    22  
    23  // Bytes serializes a G2 element in uncompressed form.
    24  func (g G2) Bytes() []byte { return g.encodeBytes(false) }
    25  
    26  // Bytes serializes a G2 element in compressed form.
    27  func (g G2) BytesCompressed() []byte { return g.encodeBytes(true) }
    28  
    29  // SetBytes sets g to the value in bytes, and returns a non-nil error if not in G2.
    30  func (g *G2) SetBytes(b []byte) error {
    31  	if len(b) < G2SizeCompressed {
    32  		return errInputLength
    33  	}
    34  
    35  	isCompressed := int((b[0] >> 7) & 0x1)
    36  	isInfinity := int((b[0] >> 6) & 0x1)
    37  	isBigYCoord := int((b[0] >> 5) & 0x1)
    38  
    39  	if isInfinity == 1 {
    40  		l := G2Size
    41  		if isCompressed == 1 {
    42  			l = G2SizeCompressed
    43  		}
    44  		zeros := make([]byte, l-1)
    45  		if (b[0]&0x1F) != 0 || subtle.ConstantTimeCompare(b[1:], zeros) != 1 {
    46  			return errEncoding
    47  		}
    48  		g.SetIdentity()
    49  		return nil
    50  	}
    51  
    52  	x := (&[ff.Fp2Size]byte{})[:]
    53  	copy(x, b)
    54  	x[0] &= 0x1F
    55  	if err := g.x.UnmarshalBinary(x); err != nil {
    56  		return err
    57  	}
    58  
    59  	if isCompressed == 1 {
    60  		x3b := &ff.Fp2{}
    61  		x3b.Sqr(&g.x)
    62  		x3b.Mul(x3b, &g.x)
    63  		x3b.Add(x3b, &g2Params.b)
    64  		if g.y.Sqrt(x3b) == 0 {
    65  			return errEncoding
    66  		}
    67  		if g.y.IsNegative() != isBigYCoord {
    68  			g.y.Neg()
    69  		}
    70  	} else {
    71  		if len(b) < G2Size {
    72  			return errInputLength
    73  		}
    74  		if err := g.y.UnmarshalBinary(b[ff.Fp2Size:G2Size]); err != nil {
    75  			return err
    76  		}
    77  	}
    78  
    79  	g.z.SetOne()
    80  	if !g.IsOnG2() {
    81  		return errEncoding
    82  	}
    83  	return nil
    84  }
    85  
    86  func (g G2) encodeBytes(compressed bool) []byte {
    87  	g.toAffine()
    88  	var isCompressed, isInfinity, isBigYCoord byte
    89  	if compressed {
    90  		isCompressed = 1
    91  	}
    92  	if g.z.IsZero() == 1 {
    93  		isInfinity = 1
    94  	}
    95  	if isCompressed == 1 && isInfinity == 0 {
    96  		isBigYCoord = byte(g.y.IsNegative())
    97  	}
    98  
    99  	bytes, _ := g.x.MarshalBinary()
   100  	if isCompressed == 0 {
   101  		yBytes, _ := g.y.MarshalBinary()
   102  		bytes = append(bytes, yBytes...)
   103  	}
   104  	if isInfinity == 1 {
   105  		l := len(bytes)
   106  		for i := 0; i < l; i++ {
   107  			bytes[i] = 0
   108  		}
   109  	}
   110  
   111  	bytes[0] = bytes[0]&0x1F | headerEncoding(isCompressed, isInfinity, isBigYCoord)
   112  
   113  	return bytes
   114  }
   115  
   116  // Neg inverts g.
   117  func (g *G2) Neg() { g.y.Neg() }
   118  
   119  // SetIdentity assigns g to the identity element.
   120  func (g *G2) SetIdentity() { g.x = ff.Fp2{}; g.y.SetOne(); g.z = ff.Fp2{} }
   121  
   122  // isValidProjective returns true if the point is not a projective point.
   123  func (g *G2) isValidProjective() bool { return (g.x.IsZero() & g.y.IsZero() & g.z.IsZero()) != 1 }
   124  
   125  // IsOnG2 returns true if the point is in the group G2.
   126  func (g *G2) IsOnG2() bool { return g.isValidProjective() && g.isOnCurve() && g.isRTorsion() }
   127  
   128  // IsIdentity return true if the point is the identity of G2.
   129  func (g *G2) IsIdentity() bool { return g.isValidProjective() && (g.z.IsZero() == 1) }
   130  
   131  // cmov sets g to P if b == 1
   132  func (g *G2) cmov(P *G2, b int) {
   133  	(&g.x).CMov(&g.x, &P.x, b)
   134  	(&g.y).CMov(&g.y, &P.y, b)
   135  	(&g.z).CMov(&g.z, &P.z, b)
   136  }
   137  
   138  // isRTorsion returns true if point is in the r-torsion subgroup.
   139  func (g *G2) isRTorsion() bool {
   140  	// Bowe, "Faster Subgroup Checks for BLS12-381" (https://eprint.iacr.org/2019/814)
   141  	_z := bls12381.minusZ[:]
   142  	Q := *g
   143  	Q.psi()                   // Q = \psi(g)
   144  	Q.scalarMultShort(_z, &Q) // Q = -[z]\psi(g)
   145  	Q.Add(&Q, g)              // Q = -[z]\psi(g)+g
   146  	Q.psi()                   // Q = -[z]\psi^2(g)+\psi(g)
   147  	Q.psi()                   // Q = -[z]\psi^3(g)+\psi^2(g)
   148  
   149  	return Q.IsEqual(g) // Equivalent to verification equation in paper
   150  }
   151  
   152  // psi is the Galbraith-Scott endomorphism. See https://eprint.iacr.org/2008/117.
   153  func (g *G2) psi() {
   154  	g.x.Frob(&g.x)
   155  	g.y.Frob(&g.y)
   156  	g.z.Frob(&g.z)
   157  	g.x.Mul(&g2Psi.alpha, &g.x)
   158  	g.y.Mul(&g2Psi.beta, &g.y)
   159  }
   160  
   161  // clearCofactor maps g to a point in the r-torsion subgroup.
   162  //
   163  // This method multiplies g times a multiple of the cofactor as proposed by
   164  // Fuentes-Knapp-Rodríguez at https://doi.org/10.1007/978-3-642-28496-0_25.
   165  //
   166  // The explicit formulas for BLS curves are in Section 4.1 of Budroni-Pintore
   167  // "Efficient hash maps to G2 on BLS curves" at https://eprint.iacr.org/2017/419
   168  //
   169  //	h(a)P = [x^2-x-1]P + [x-1]ψ(P) + ψ^2(2P)
   170  func (g *G2) clearCofactor() {
   171  	x := bls12381.minusZ[:]
   172  	xP, psiP := &G2{}, &G2{}
   173  	_2P := *g
   174  
   175  	_2P.Double()              // 2P
   176  	_2P.psi()                 // ψ(2P)
   177  	_2P.psi()                 // ψ^2(2P)
   178  	xP.scalarMultShort(x, g)  // -xP
   179  	xP.Add(xP, g)             // -xP + P = [-x+1]P
   180  	*psiP = *xP               //
   181  	psiP.psi()                // ψ(-xP + P) = [-x+1]ψ(P)
   182  	xP.scalarMultShort(x, xP) // x^2P - xP = [x^2-x]P
   183  	g.Add(g, psiP)            // P + [-x+1]ψ(P)
   184  	g.Neg()                   // -P + [x-1]ψ(P)
   185  	g.Add(g, xP)              // [x^2-x-1]P + [x-1]ψ(P)
   186  	g.Add(g, &_2P)            // [x^2-x-1]P + [x-1]ψ(P) + 2ψ^2(P)
   187  }
   188  
   189  // Double updates g = 2g.
   190  func (g *G2) Double() { doubleAndLine(g, nil) }
   191  
   192  // Add updates g=P+Q.
   193  func (g *G2) Add(P, Q *G2) { addAndLine(g, P, Q, nil) }
   194  
   195  // ScalarMult calculates g = kP.
   196  func (g *G2) ScalarMult(k *Scalar, P *G2) { b, _ := k.MarshalBinary(); g.scalarMult(b, P) }
   197  
   198  // scalarMult calculates g = kP, where k is the scalar in big-endian order.
   199  func (g *G2) scalarMult(k []byte, P *G2) {
   200  	var Q G2
   201  	Q.SetIdentity()
   202  	T := &G2{}
   203  	var mults [16]G2
   204  	mults[0].SetIdentity()
   205  	mults[1] = *P
   206  	for i := 1; i < 8; i++ {
   207  		mults[2*i] = mults[i]
   208  		mults[2*i].Double()
   209  		mults[2*i+1].Add(&mults[2*i], P)
   210  	}
   211  	N := 8 * len(k)
   212  	for i := 0; i < N; i += 4 {
   213  		Q.Double()
   214  		Q.Double()
   215  		Q.Double()
   216  		Q.Double()
   217  		idx := 0xf & (k[i/8] >> uint(4-i%8))
   218  		for j := 0; j < 16; j++ {
   219  			T.cmov(&mults[j], subtle.ConstantTimeByteEq(idx, uint8(j)))
   220  		}
   221  		Q.Add(&Q, T)
   222  	}
   223  	*g = Q
   224  }
   225  
   226  // scalarMultShort multiplies by a short, constant scalar k, where k is the
   227  // scalar in big-endian order. Runtime depends on the scalar.
   228  func (g *G2) scalarMultShort(k []byte, P *G2) {
   229  	// Since the scalar is short and low Hamming weight not much helps.
   230  	var Q G2
   231  	Q.SetIdentity()
   232  	N := 8 * len(k)
   233  	for i := 0; i < N; i++ {
   234  		Q.Double()
   235  		bit := 0x1 & (k[i/8] >> uint(7-i%8))
   236  		if bit != 0 {
   237  			Q.Add(&Q, P)
   238  		}
   239  	}
   240  	*g = Q
   241  }
   242  
   243  // IsEqual returns true if g and p are equivalent.
   244  func (g *G2) IsEqual(p *G2) bool {
   245  	var lx, rx, ly, ry ff.Fp2
   246  	lx.Mul(&g.x, &p.z) // lx = x1*z2
   247  	rx.Mul(&p.x, &g.z) // rx = x2*z1
   248  	lx.Sub(&lx, &rx)   // lx = lx-rx
   249  	ly.Mul(&g.y, &p.z) // ly = y1*z2
   250  	ry.Mul(&p.y, &g.z) // ry = y2*z1
   251  	ly.Sub(&ly, &ry)   // ly = ly-ry
   252  	return lx.IsZero() == 1 && ly.IsZero() == 1
   253  }
   254  
   255  // EncodeToCurve is a non-uniform encoding from an input byte string (and
   256  // an optional domain separation tag) to elements in G2. This function must not
   257  // be used as a hash function, otherwise use G2.Hash instead.
   258  func (g *G2) Encode(input, dst []byte) {
   259  	const L = 64
   260  	pseudo := expander.NewExpanderMD(crypto.SHA256, dst).Expand(input, 2*L)
   261  
   262  	var u ff.Fp2
   263  	u[0].SetBytes(pseudo[0*L : 1*L])
   264  	u[1].SetBytes(pseudo[1*L : 2*L])
   265  
   266  	var q isogG2Point
   267  	q.sswu(&u)
   268  	g.evalIsogG2(&q)
   269  	g.clearCofactor()
   270  }
   271  
   272  // Hash produces an element of G2 from the hash of an input byte string and
   273  // an optional domain separation tag. This function is safe to use when a
   274  // random oracle returning points in G2 be required.
   275  func (g *G2) Hash(input, dst []byte) {
   276  	const L = 64
   277  	pseudo := expander.NewExpanderMD(crypto.SHA256, dst).Expand(input, 4*L)
   278  
   279  	var u0, u1 ff.Fp2
   280  	u0[0].SetBytes(pseudo[0*L : 1*L])
   281  	u0[1].SetBytes(pseudo[1*L : 2*L])
   282  	u1[0].SetBytes(pseudo[2*L : 3*L])
   283  	u1[1].SetBytes(pseudo[3*L : 4*L])
   284  
   285  	var q0, q1 isogG2Point
   286  	q0.sswu(&u0)
   287  	q1.sswu(&u1)
   288  	var p0, p1 G2
   289  	p0.evalIsogG2(&q0)
   290  	p1.evalIsogG2(&q1)
   291  	g.Add(&p0, &p1)
   292  	g.clearCofactor()
   293  }
   294  
   295  // isOnCurve returns true if g is a valid point on the curve.
   296  func (g *G2) isOnCurve() bool {
   297  	var x3, z3, y2 ff.Fp2
   298  	y2.Sqr(&g.y)             // y2 = y^2
   299  	y2.Mul(&y2, &g.z)        // y2 = y^2*z
   300  	x3.Sqr(&g.x)             // x3 = x^2
   301  	x3.Mul(&x3, &g.x)        // x3 = x^3
   302  	z3.Sqr(&g.z)             // z3 = z^2
   303  	z3.Mul(&z3, &g.z)        // z3 = z^3
   304  	z3.Mul(&z3, &g2Params.b) // z3 = (4+4i)*z^3
   305  	x3.Add(&x3, &z3)         // x3 = x^3 + (4+4i)*z^3
   306  	y2.Sub(&y2, &x3)         // y2 = y^2*z - (x^3 + (4+4i)*z^3)
   307  	return y2.IsZero() == 1
   308  }
   309  
   310  // toAffine updates g with its affine representation.
   311  func (g *G2) toAffine() {
   312  	if g.z.IsZero() != 1 {
   313  		var invZ ff.Fp2
   314  		invZ.Inv(&g.z)
   315  		g.x.Mul(&g.x, &invZ)
   316  		g.y.Mul(&g.y, &invZ)
   317  		g.z.SetOne()
   318  	}
   319  }
   320  
   321  // G2Generator returns the generator point of G2.
   322  func G2Generator() *G2 {
   323  	var G G2
   324  	G.x = g2Params.genX
   325  	G.y = g2Params.genY
   326  	G.z.SetOne()
   327  	return &G
   328  }
   329
View as plain text