g2Isog.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 isogG2Point struct{ x, y, z ff.Fp2 }
    10  
    11  func (p isogG2Point) 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 *isogG2Point) IsOnCurve() bool {
    15  	var x2, x3, z2, z3, y2 ff.Fp2
    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, &g2Isog3.b) // z3 = B*z^3
    21  	x2.Sqr(&p.x)            // x2 = x^2
    22  	x3.Mul(&z2, &g2Isog3.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 != isogG2Point{}
    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 *isogG2Point) sswu(u *ff.Fp2) {
    33  	// Method in Appendix-G.2.3 of
    34  	// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11
    35  	tv1, tv2, tv3, tv4 := &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}
    36  	tv5, xd, x1n, gxd := &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}
    37  	gx1, y, xn, gx2 := &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}
    38  
    39  	tv1.Sqr(u)                      // 1.  tv1 = u^2
    40  	tv3.Mul(&g2sswu.Z, tv1)         // 2.  tv3 = Z * tv1
    41  	tv5.Sqr(tv3)                    // 3.  tv5 = tv3^2
    42  	xd.Add(tv5, tv3)                // 4.   xd = tv5 + tv3
    43  	tv2.SetOne()                    // 5.  tv2 = 1
    44  	x1n.Add(xd, tv2)                //     x1n = xd + tv2
    45  	x1n.Mul(x1n, &g2Isog3.b)        // 6.  x1n = x1n * B
    46  	xd.Mul(&g2Isog3.a, xd)          // 7.   xd = A * xd
    47  	xd.Neg()                        //      xd = -xd
    48  	e1 := xd.IsZero()               // 8.   e1 = xd == 0
    49  	tv2.Mul(&g2sswu.Z, &g2Isog3.a)  // 9.  tv2 = Z * A
    50  	xd.CMov(xd, tv2, e1)            //      xd = CMOV(xd, tv2, e1)
    51  	tv2.Sqr(xd)                     // 10. tv2 = xd^2
    52  	gxd.Mul(tv2, xd)                // 11. gxd = tv2 * xd
    53  	tv2.Mul(&g2Isog3.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(&g2Isog3.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(tv4, gxd)               // 19. tv2 = tv4 * gxd
    61  	tv4.Sqr(tv4)                    // 20. tv4 = tv4^2
    62  	tv2.Mul(tv2, tv4)               // 21. tv2 = tv2 * tv4
    63  	tv2.Mul(tv2, gx1)               // 22. tv2 = tv2 * gx1
    64  	tv4.Sqr(tv4)                    // 23. tv4 = tv4^2
    65  	tv4.Mul(tv2, tv4)               // 24. tv4 = tv2 * tv4
    66  	y.ExpVarTime(tv4, g2sswu.c1[:]) // 25.   y = tv4^c1
    67  	y.Mul(y, tv2)                   // 26.   y = y * tv2
    68  	tv4.Mul(y, &g2sswu.c2)          // 27. tv4 = y * c2
    69  	tv2.Sqr(tv4)                    // 28. tv2 = tv4^2
    70  	tv2.Mul(tv2, gxd)               // 29. tv2 = tv2 * gxd
    71  	e2 := tv2.IsEqual(gx1)          // 30.  e2 = tv2 == gx1
    72  	y.CMov(y, tv4, e2)              // 31.   y = CMOV(y, tv4, e2)
    73  	tv4.Mul(y, &g2sswu.c3)          // 32. tv4 = y * c3
    74  	tv2.Sqr(tv4)                    // 33. tv2 = tv4^2
    75  	tv2.Mul(tv2, gxd)               // 34. tv2 = tv2 * gxd
    76  	e3 := tv2.IsEqual(gx1)          // 35.  e3 = tv2 == gx1
    77  	y.CMov(y, tv4, e3)              // 36.   y = CMOV(y, tv4, e3)
    78  	tv4.Mul(tv4, &g2sswu.c2)        // 37. tv4 = tv4 * c2
    79  	tv2.Sqr(tv4)                    // 38. tv2 = tv4^2
    80  	tv2.Mul(tv2, gxd)               // 39. tv2 = tv2 * gxd
    81  	e4 := tv2.IsEqual(gx1)          // 40.  e4 = tv2 == gx1
    82  	y.CMov(y, tv4, e4)              // 41.   y = CMOV(y, tv4, e4)
    83  	gx2.Mul(gx1, tv5)               // 42. gx2 = gx1 * tv5
    84  	gx2.Mul(gx2, tv3)               // 43. gx2 = gx2 * tv3
    85  	tv5.Mul(y, tv1)                 // 44. tv5 = y * tv1
    86  	tv5.Mul(tv5, u)                 // 45. tv5 = tv5 * u
    87  	tv1.Mul(tv5, &g2sswu.c4)        // 46. tv1 = tv5 * c4
    88  	tv4.Mul(tv1, &g2sswu.c2)        // 47. tv4 = tv1 * c2
    89  	tv2.Sqr(tv4)                    // 48. tv2 = tv4^2
    90  	tv2.Mul(tv2, gxd)               // 49. tv2 = tv2 * gxd
    91  	e5 := tv2.IsEqual(gx2)          // 50.  e5 = tv2 == gx2
    92  	tv1.CMov(tv1, tv4, e5)          // 51. tv1 = CMOV(tv1, tv4, e5)
    93  	tv4.Mul(tv5, &g2sswu.c5)        // 52. tv4 = tv5 * c5
    94  	tv2.Sqr(tv4)                    // 53. tv2 = tv4^2
    95  	tv2.Mul(tv2, gxd)               // 54. tv2 = tv2 * gxd
    96  	e6 := tv2.IsEqual(gx2)          // 55.  e6 = tv2 == gx2
    97  	tv1.CMov(tv1, tv4, e6)          // 56. tv1 = CMOV(tv1, tv4, e6)
    98  	tv4.Mul(tv4, &g2sswu.c2)        // 57. tv4 = tv4 * c2
    99  	tv2.Sqr(tv4)                    // 58. tv2 = tv4^2
   100  	tv2.Mul(tv2, gxd)               // 59. tv2 = tv2 * gxd
   101  	e7 := tv2.IsEqual(gx2)          // 60.  e7 = tv2 == gx2
   102  	tv1.CMov(tv1, tv4, e7)          // 61. tv1 = CMOV(tv1, tv4, e7)
   103  	tv2.Sqr(y)                      // 62. tv2 = y^2
   104  	tv2.Mul(tv2, gxd)               // 63. tv2 = tv2 * gxd
   105  	e8 := tv2.IsEqual(gx1)          // 64.  e8 = tv2 == gx1
   106  	y.CMov(tv1, y, e8)              // 65.   y = CMOV(tv1, y, e8)
   107  	tv2.Mul(tv3, x1n)               // 66. tv2 = tv3 * x1n
   108  	xn.CMov(tv2, x1n, e8)           // 67.  xn = CMOV(tv2, x1n, e8)
   109  	e9 := 1 ^ u.Sgn0() ^ y.Sgn0()   // 68.  e9 = sgn0(u) == sgn0(y)
   110  	*tv1 = *y                       // 69. tv1 = y
   111  	tv1.Neg()                       //     tv1 = -y
   112  	y.CMov(tv1, y, e9)              //       y = CMOV(tv1, y, e9)
   113  	p.x = *xn                       // 70. return
   114  	p.y.Mul(y, xd)                  //       (x,y) = (xn/xd, y/1)
   115  	p.z = *xd                       //       (X,Y,Z) = (xn, y*xd, xd)
   116  }
   117  
   118  // evalIsogG2 calculates g = g2Isog3(p), where g2Isog3 is an isogeny of
   119  // degree 3 to the curve used in G2.
   120  func (g *G2) evalIsogG2(p *isogG2Point) {
   121  	x, y, z := &p.x, &p.y, &p.z
   122  	t, zi := &ff.Fp2{}, &ff.Fp2{}
   123  	xNum, xDen, yNum, yDen := &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}, &ff.Fp2{}
   124  
   125  	ixn := len(g2Isog3.xNum) - 1
   126  	ixd := len(g2Isog3.xDen) - 1
   127  	iyn := len(g2Isog3.yNum) - 1
   128  	iyd := len(g2Isog3.yDen) - 1
   129  
   130  	*xNum = g2Isog3.xNum[ixn]
   131  	*xDen = g2Isog3.xDen[ixd]
   132  	*yNum = g2Isog3.yNum[iyn]
   133  	*yDen = g2Isog3.yDen[iyd]
   134  	*zi = *z
   135  
   136  	for (ixn | ixd | iyn | iyd) != 0 {
   137  		if ixn > 0 {
   138  			ixn--
   139  			t.Mul(zi, &g2Isog3.xNum[ixn])
   140  			xNum.Mul(xNum, x)
   141  			xNum.Add(xNum, t)
   142  		}
   143  		if ixd > 0 {
   144  			ixd--
   145  			t.Mul(zi, &g2Isog3.xDen[ixd])
   146  			xDen.Mul(xDen, x)
   147  			xDen.Add(xDen, t)
   148  		}
   149  		if iyn > 0 {
   150  			iyn--
   151  			t.Mul(zi, &g2Isog3.yNum[iyn])
   152  			yNum.Mul(yNum, x)
   153  			yNum.Add(yNum, t)
   154  		}
   155  		if iyd > 0 {
   156  			iyd--
   157  			t.Mul(zi, &g2Isog3.yDen[iyd])
   158  			yDen.Mul(yDen, x)
   159  			yDen.Add(yDen, t)
   160  		}
   161  
   162  		zi.Mul(zi, z)
   163  	}
   164  
   165  	g.x.Mul(xNum, yDen)
   166  	g.y.Mul(yNum, xDen)
   167  	g.y.Mul(&g.y, y)
   168  	g.z.Mul(xDen, yDen)
   169  	g.z.Mul(&g.z, z)
   170  }
   171
View as plain text