fp2.go

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

     1  package ff
     2  
     3  import "fmt"
     4  
     5  // Fp2Size is the length in bytes of an Fp2 element.
     6  const Fp2Size = 2 * FpSize
     7  
     8  type Fp2 [2]Fp
     9  
    10  func (z Fp2) String() string { return fmt.Sprintf("0: %v\n1: %v", z[0], z[1]) }
    11  func (z *Fp2) SetOne()       { z[0].SetOne(); z[1] = Fp{} }
    12  
    13  // IsNegative returns 1 if z is lexicographically larger than -z; otherwise returns 0.
    14  func (z Fp2) IsNegative() int    { return z[1].IsNegative() | (z[1].IsZero() & z[0].IsNegative()) }
    15  func (z Fp2) IsZero() int        { return z.IsEqual(&Fp2{}) }
    16  func (z Fp2) IsEqual(x *Fp2) int { return z[0].IsEqual(&x[0]) & z[1].IsEqual(&x[1]) }
    17  func (z *Fp2) MulBeta()          { t := z[0]; z[0].Sub(&z[0], &z[1]); z[1].Add(&t, &z[1]) }
    18  func (z *Fp2) Frob(x *Fp2)       { *z = *x; z.Cjg() }
    19  func (z *Fp2) Cjg()              { z[1].Neg() }
    20  func (z *Fp2) Neg()              { z[0].Neg(); z[1].Neg() }
    21  func (z *Fp2) Add(x, y *Fp2)     { z[0].Add(&x[0], &y[0]); z[1].Add(&x[1], &y[1]) }
    22  func (z *Fp2) Sub(x, y *Fp2)     { z[0].Sub(&x[0], &y[0]); z[1].Sub(&x[1], &y[1]) }
    23  func (z *Fp2) Mul(x, y *Fp2) {
    24  	var x0y0, x1y1, sx, sy, k Fp
    25  	x0y0.Mul(&x[0], &y[0])
    26  	x1y1.Mul(&x[1], &y[1])
    27  	sx.Add(&x[0], &x[1])
    28  	sy.Add(&y[0], &y[1])
    29  	k.Mul(&sx, &sy)
    30  	z[0].Sub(&x0y0, &x1y1)
    31  	z[1].Sub(&k, &x0y0)
    32  	z[1].Sub(&z[1], &x1y1)
    33  }
    34  
    35  func (z *Fp2) Sqr(x *Fp2) {
    36  	var x02, x12, k Fp
    37  	x02.Sqr(&x[0])
    38  	x12.Sqr(&x[1])
    39  	k.Mul(&x[0], &x[1])
    40  	z[0].Sub(&x02, &x12)
    41  	z[1].Add(&k, &k)
    42  }
    43  
    44  func (z *Fp2) Inv(x *Fp2) {
    45  	var x02, x12, den Fp
    46  	x02.Sqr(&x[0])
    47  	x12.Sqr(&x[1])
    48  	den.Add(&x02, &x12)
    49  	den.Inv(&den)
    50  	z[0].Mul(&x[0], &den)
    51  	z[1].Mul(&x[1], &den)
    52  	z[1].Neg()
    53  }
    54  
    55  func (z Fp2) Sgn0() int {
    56  	s0, s1 := z[0].Sgn0(), z[1].Sgn0()
    57  	z0 := z[0].IsZero()
    58  	return s0 | (z0 & s1)
    59  }
    60  
    61  func (z *Fp2) UnmarshalBinary(b []byte) error {
    62  	if len(b) < Fp2Size {
    63  		return errInputLength
    64  	}
    65  	return errFirst(
    66  		z[1].UnmarshalBinary(b[:FpSize]),
    67  		z[0].UnmarshalBinary(b[FpSize:2*FpSize]),
    68  	)
    69  }
    70  
    71  func (z Fp2) MarshalBinary() (b []byte, e error) {
    72  	var b0, b1 []byte
    73  	if b1, e = z[1].MarshalBinary(); e == nil {
    74  		if b0, e = z[0].MarshalBinary(); e == nil {
    75  			return append(b1, b0...), e
    76  		}
    77  	}
    78  	return
    79  }
    80  
    81  // SetString reconstructs a Fp2 element as s0+s1*i, where s0 and s1 are numeric
    82  // strings from 0 to FpOrder-1.
    83  func (z *Fp2) SetString(s0, s1 string) (err error) {
    84  	if err = z[0].SetString(s0); err == nil {
    85  		err = z[1].SetString(s1)
    86  	}
    87  	return
    88  }
    89  
    90  func (z *Fp2) CMov(x, y *Fp2, b int) {
    91  	z[0].CMov(&x[0], &y[0], b)
    92  	z[1].CMov(&x[1], &y[1], b)
    93  }
    94  
    95  // ExpVarTime calculates z=x^n, where n is the exponent in big-endian order.
    96  func (z *Fp2) ExpVarTime(x *Fp2, n []byte) {
    97  	zz := new(Fp2)
    98  	zz.SetOne()
    99  	N := 8 * len(n)
   100  	for i := 0; i < N; i++ {
   101  		zz.Sqr(zz)
   102  		bit := 0x1 & (n[i/8] >> uint(7-i%8))
   103  		if bit != 0 {
   104  			zz.Mul(zz, x)
   105  		}
   106  	}
   107  	*z = *zz
   108  }
   109  
   110  // Sqrt returns 1 and sets z=sqrt(x) only if x is a quadratic-residue; otherwise, returns 0 and z is unmodified.
   111  func (z *Fp2) Sqrt(x *Fp2) int {
   112  	// "Square-root for q = p^2 = 9 (mod 16)" Appendix I.3 of Hashing to elliptic curves.
   113  	// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#appendix-I.3
   114  	var t, tv1, tv2, tv3, tv4 Fp2
   115  	tv1.ExpVarTime(x, fp2SqrtConst.c4[:])
   116  	tv2.Mul(&fp2SqrtConst.c1, &tv1)
   117  	tv3.Mul(&fp2SqrtConst.c2, &tv1)
   118  	tv4.Mul(&fp2SqrtConst.c3, &tv1)
   119  
   120  	t.Sqr(&tv1)
   121  	e1 := t.IsEqual(x)
   122  	z.CMov(z, &tv1, e1)
   123  
   124  	t.Sqr(&tv2)
   125  	e2 := t.IsEqual(x)
   126  	z.CMov(z, &tv2, e2)
   127  
   128  	t.Sqr(&tv3)
   129  	e3 := t.IsEqual(x)
   130  	z.CMov(z, &tv3, e3)
   131  
   132  	t.Sqr(&tv4)
   133  	e4 := t.IsEqual(x)
   134  	z.CMov(z, &tv4, e4)
   135  
   136  	return e1 | e2 | e3 | e4
   137  }
   138  
   139  var fp2SqrtConst = struct {
   140  	// "Square-root for q = p^2 = 9 (mod 16)" Appendix I.3 of Hashing to elliptic curves.
   141  	// https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-11#appendix-I.3
   142  	c1 Fp2      // c1 = sqrt( -1) = u
   143  	c2 Fp2      // c2 = sqrt( c1)
   144  	c3 Fp2      // c3 = sqrt(-c1)
   145  	c4 [95]byte // c4 = (p^2 + 7) / 16 (big-endian)
   146  }{
   147  	c1: Fp2{ // (little-endian)
   148  		Fp{fpMont{}},
   149  		Fp{fpMont{0x760900000002fffd, 0xebf4000bc40c0002, 0x5f48985753c758ba, 0x77ce585370525745, 0x5c071a97a256ec6d, 0x15f65ec3fa80e493}},
   150  	},
   151  	c2: Fp2{ // (little-endian)
   152  		Fp{fpMont{0x3e2f585da55c9ad1, 0x4294213d86c18183, 0x382844c88b623732, 0x92ad2afd19103e18, 0x1d794e4fac7cf0b9, 0x0bd592fc7d825ec8}},
   153  		Fp{fpMont{0x7bcfa7a25aa30fda, 0xdc17dec12a927e7c, 0x2f088dd86b4ebef1, 0xd1ca2087da74d4a7, 0x2da2596696cebc1d, 0x0e2b7eedbbfd87d2}},
   154  	},
   155  	c3: Fp2{ // (little-endian)
   156  		Fp{fpMont{0x7bcfa7a25aa30fda, 0xdc17dec12a927e7c, 0x2f088dd86b4ebef1, 0xd1ca2087da74d4a7, 0x2da2596696cebc1d, 0x0e2b7eedbbfd87d2}},
   157  		Fp{fpMont{0x7bcfa7a25aa30fda, 0xdc17dec12a927e7c, 0x2f088dd86b4ebef1, 0xd1ca2087da74d4a7, 0x2da2596696cebc1d, 0x0e2b7eedbbfd87d2}},
   158  	},
   159  	c4: [95]byte{ // (big-endian)
   160  		0x2a, 0x43, 0x7a, 0x4b, 0x8c, 0x35, 0xfc, 0x74, 0xbd, 0x27, 0x8e, 0xaa,
   161  		0x22, 0xf2, 0x5e, 0x9e, 0x2d, 0xc9, 0x0e, 0x50, 0xe7, 0x04, 0x6b, 0x46,
   162  		0x6e, 0x59, 0xe4, 0x93, 0x49, 0xe8, 0xbd, 0x05, 0x0a, 0x62, 0xcf, 0xd1,
   163  		0x6d, 0xdc, 0xa6, 0xef, 0x53, 0x14, 0x93, 0x30, 0x97, 0x8e, 0xf0, 0x11,
   164  		0xd6, 0x86, 0x19, 0xc8, 0x61, 0x85, 0xc7, 0xb2, 0x92, 0xe8, 0x5a, 0x87,
   165  		0x09, 0x1a, 0x04, 0x96, 0x6b, 0xf9, 0x1e, 0xd3, 0xe7, 0x1b, 0x74, 0x31,
   166  		0x62, 0xc3, 0x38, 0x36, 0x21, 0x13, 0xcf, 0xd7, 0xce, 0xd6, 0xb1, 0xd7,
   167  		0x63, 0x82, 0xea, 0xb2, 0x6a, 0xa0, 0x00, 0x01, 0xc7, 0x18, 0xe4,
   168  	},
   169  }
   170
View as plain text