g1Isog.go

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

     1  package bls12381
     2  
     3  import (
     4  	"fmt"
     5  
     6  	"github.com/cloudflare/circl/ecc/bls12381/ff"
     7  )
     8  
     9  type isogG1Point struct{ x, y, z ff.Fp }
    10  
    11  func (p isogG1Point) String() string { return fmt.Sprintf("x: %v\ny: %v\nz: %v", p.x, p.y, p.z) }
    12  
    13  // IsOnCurve returns true if g is a valid point on the curve.
    14  func (p *isogG1Point) IsOnCurve() bool {
    15  	var x2, x3, z2, z3, y2 ff.Fp
    16  	y2.Sqr(&p.y)             // y2 = y^2
    17  	y2.Mul(&y2, &p.z)        // y2 = y^2*z
    18  	z2.Sqr(&p.z)             // z2 = z^2
    19  	z3.Mul(&z2, &p.z)        // z3 = z^3
    20  	z3.Mul(&z3, &g1Isog11.b) // z3 = B*z^3
    21  	x2.Sqr(&p.x)             // x2 = x^2
    22  	x3.Mul(&z2, &g1Isog11.a) // x3 = A*z^2
    23  	x3.Add(&x3, &x2)         // x3 = x^2 + A*z^2
    24  	x3.Mul(&x3, &p.x)        // x3 = x^3 + A*x*z^2
    25  	x3.Add(&x3, &z3)         // x3 = x^3 + A*x*z^2 + Bz^3
    26  
    27  	return y2.IsEqual(&x3) == 1 && *p != isogG1Point{}
    28  }
    29  
    30  // sswu implements the Simplified Shallue-van de Woestijne-Ulas method for
    31  // mapping a field element to a point on the isogenous curve.
    32  func (p *isogG1Point) sswu(u *ff.Fp) {
    33  	// Method in Appendix-G.2.1 of
    34  	// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11
    35  	tv1, tv2, tv3, tv4 := &ff.Fp{}, &ff.Fp{}, &ff.Fp{}, &ff.Fp{}
    36  	xd, x1n, gxd, gx1 := &ff.Fp{}, &ff.Fp{}, &ff.Fp{}, &ff.Fp{}
    37  	y, y1, x2n, y2, xn := &ff.Fp{}, &ff.Fp{}, &ff.Fp{}, &ff.Fp{}, &ff.Fp{}
    38  
    39  	tv1.Sqr(u)                       // 1.  tv1 = u^2
    40  	tv3.Mul(&g1sswu.Z, tv1)          // 2.  tv3 = Z * tv1
    41  	tv2.Sqr(tv3)                     // 3.  tv2 = tv3^2
    42  	xd.Add(tv2, tv3)                 // 4.   xd = tv2 + tv3
    43  	tv4.SetOne()                     // 5.  tv4 = 1
    44  	x1n.Add(xd, tv4)                 //     x1n = xd + tv4
    45  	x1n.Mul(x1n, &g1Isog11.b)        // 6.  x1n = x1n * B
    46  	xd.Mul(&g1Isog11.a, xd)          // 7.   xd = A * xd
    47  	xd.Neg()                         //      xd = -xd
    48  	e1 := xd.IsZero()                // 8.   e1 = xd == 0
    49  	tv4.Mul(&g1sswu.Z, &g1Isog11.a)  // 9.  tv4 = Z * A
    50  	xd.CMov(xd, tv4, e1)             //      xd = CMOV(xd, tv4, e1)
    51  	tv2.Sqr(xd)                      // 10. tv2 = xd^2
    52  	gxd.Mul(tv2, xd)                 // 11. gxd = tv2 * xd
    53  	tv2.Mul(&g1Isog11.a, tv2)        // 12. tv2 = A * tv2
    54  	gx1.Sqr(x1n)                     // 13. gx1 = x1n^2
    55  	gx1.Add(gx1, tv2)                // 14. gx1 = gx1 + tv2
    56  	gx1.Mul(gx1, x1n)                // 15. gx1 = gx1 * x1n
    57  	tv2.Mul(&g1Isog11.b, gxd)        // 16. tv2 = B * gxd
    58  	gx1.Add(gx1, tv2)                // 17. gx1 = gx1 + tv2
    59  	tv4.Sqr(gxd)                     // 18. tv4 = gxd^2
    60  	tv2.Mul(gx1, gxd)                // 19. tv2 = gx1 * gxd
    61  	tv4.Mul(tv4, tv2)                // 20. tv4 = tv4 * tv2
    62  	y1.ExpVarTime(tv4, g1sswu.c1[:]) // 21.  y1 = tv4^c1
    63  	y1.Mul(y1, tv2)                  // 22.  y1 = y1 * tv2
    64  	x2n.Mul(tv3, x1n)                // 23. x2n = tv3 * x1n
    65  	y2.Mul(y1, &g1sswu.c2)           // 24.  y2 = y1 * c2
    66  	y2.Mul(y2, tv1)                  // 25.  y2 = y2 * tv1
    67  	y2.Mul(y2, u)                    // 26.  y2 = y2 * u
    68  	tv2.Sqr(y1)                      // 27. tv2 = y1^2
    69  	tv2.Mul(tv2, gxd)                // 28. tv2 = tv2 * gxd
    70  	e2 := tv2.IsEqual(gx1)           // 29.  e2 = tv2 == gx1
    71  	xn.CMov(x2n, x1n, e2)            // 30.  xn = CMOV(x2n, x1n, e2)
    72  	y.CMov(y2, y1, e2)               // 31.   y = CMOV(y2, y1, e2)
    73  	e3 := u.Sgn0() ^ y.Sgn0()        // 32.  e3 = sgn0(u) == sgn0(y)
    74  	*tv1 = *y                        // 33. tv1 = y
    75  	tv1.Neg()                        //     tv1 = -y
    76  	y.CMov(tv1, y, ^e3)              //       y = CMOV(tv1, y, e3)
    77  	p.x = *xn                        // 34. return
    78  	p.y.Mul(y, xd)                   //       (x,y) = (xn/xd, y/1)
    79  	p.z = *xd                        //       (X,Y,Z) = (xn, y*xd, xd)
    80  }
    81  
    82  // evalIsogG1 calculates g = g1Isog11(p), where g1Isog11 is an isogeny of
    83  // degree 11 to the curve used in G1.
    84  func (g *G1) evalIsogG1(p *isogG1Point) {
    85  	x, y, z := &p.x, &p.y, &p.z
    86  	t, zi := &ff.Fp{}, &ff.Fp{}
    87  	xNum, xDen, yNum, yDen := &ff.Fp{}, &ff.Fp{}, &ff.Fp{}, &ff.Fp{}
    88  
    89  	ixn := len(g1Isog11.xNum) - 1
    90  	ixd := len(g1Isog11.xDen) - 1
    91  	iyn := len(g1Isog11.yNum) - 1
    92  	iyd := len(g1Isog11.yDen) - 1
    93  
    94  	*xNum = g1Isog11.xNum[ixn]
    95  	*xDen = g1Isog11.xDen[ixd]
    96  	*yNum = g1Isog11.yNum[iyn]
    97  	*yDen = g1Isog11.yDen[iyd]
    98  	*zi = *z
    99  
   100  	for (ixn | ixd | iyn | iyd) != 0 {
   101  		if ixn > 0 {
   102  			ixn--
   103  			t.Mul(zi, &g1Isog11.xNum[ixn])
   104  			xNum.Mul(xNum, x)
   105  			xNum.Add(xNum, t)
   106  		}
   107  		if ixd > 0 {
   108  			ixd--
   109  			t.Mul(zi, &g1Isog11.xDen[ixd])
   110  			xDen.Mul(xDen, x)
   111  			xDen.Add(xDen, t)
   112  		}
   113  		if iyn > 0 {
   114  			iyn--
   115  			t.Mul(zi, &g1Isog11.yNum[iyn])
   116  			yNum.Mul(yNum, x)
   117  			yNum.Add(yNum, t)
   118  		}
   119  		if iyd > 0 {
   120  			iyd--
   121  			t.Mul(zi, &g1Isog11.yDen[iyd])
   122  			yDen.Mul(yDen, x)
   123  			yDen.Add(yDen, t)
   124  		}
   125  
   126  		zi.Mul(zi, z)
   127  	}
   128  
   129  	g.x.Mul(xNum, yDen)
   130  	g.y.Mul(yNum, xDen)
   131  	g.y.Mul(&g.y, y)
   132  	g.z.Mul(xDen, yDen)
   133  	g.z.Mul(&g.z, z)
   134  }
   135
View as plain text