fp.go

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

     1  package ff
     2  
     3  import (
     4  	"io"
     5  
     6  	"github.com/cloudflare/circl/internal/conv"
     7  )
     8  
     9  // FpSize is the length in bytes of an Fp element.
    10  const FpSize = 48
    11  
    12  // fpMont represents an element in the Montgomery domain (little-endian).
    13  type fpMont = [FpSize / 8]uint64
    14  
    15  // fpRaw represents an element in the integers domain (little-endian).
    16  type fpRaw = [FpSize / 8]uint64
    17  
    18  // Fp represents prime field elements as positive integers less than FpOrder.
    19  type Fp struct{ i fpMont }
    20  
    21  func (z Fp) String() string            { x := z.fromMont(); return conv.Uint64Le2Hex(x[:]) }
    22  func (z *Fp) SetUint64(n uint64)       { z.toMont(&fpRaw{n}) }
    23  func (z *Fp) SetOne()                  { z.SetUint64(1) }
    24  func (z *Fp) Random(r io.Reader) error { return randomInt(z.i[:], r, fpOrder[:]) }
    25  
    26  // IsNegative returns 0 if the least absolute residue for z is in [0,(p-1)/2],
    27  // and 1 otherwise. Equivalently, this function returns 1 if z is
    28  // lexicographically larger than -z.
    29  func (z Fp) IsNegative() int {
    30  	b, _ := z.MarshalBinary()
    31  	return 1 - isLessThan(b, fpOrderPlus1Div2[:])
    32  }
    33  
    34  // IsZero returns 1 if z == 0 and 0 otherwise.
    35  func (z Fp) IsZero() int { return ctUint64Eq(z.i[:], (&fpMont{})[:]) }
    36  
    37  // IsEqual returns 1 if z == x and 0 otherwise.
    38  func (z Fp) IsEqual(x *Fp) int     { return ctUint64Eq(z.i[:], x.i[:]) }
    39  func (z *Fp) Neg()                 { fiatFpMontSub(&z.i, &fpMont{}, &z.i) }
    40  func (z *Fp) Add(x, y *Fp)         { fiatFpMontAdd(&z.i, &x.i, &y.i) }
    41  func (z *Fp) Sub(x, y *Fp)         { fiatFpMontSub(&z.i, &x.i, &y.i) }
    42  func (z *Fp) Mul(x, y *Fp)         { fiatFpMontMul(&z.i, &x.i, &y.i) }
    43  func (z *Fp) Sqr(x *Fp)            { fiatFpMontSquare(&z.i, &x.i) }
    44  func (z *Fp) toMont(in *fpRaw)     { fiatFpMontMul(&z.i, in, &fpRSquare) }
    45  func (z Fp) fromMont() (out fpRaw) { fiatFpMontMul(&out, &z.i, &fpMont{1}); return }
    46  func (z Fp) Sgn0() int             { return int(z.fromMont()[0]) & 1 }
    47  
    48  // Sqrt returns 1 and sets z=sqrt(x) only if x is a quadratic-residue; otherwise, returns 0 and z is unmodified.
    49  func (z *Fp) Sqrt(x *Fp) int {
    50  	var y, y2 Fp
    51  	y.ExpVarTime(x, fpOrderPlus1Div4[:])
    52  	y2.Sqr(&y)
    53  	isQR := y2.IsEqual(x)
    54  	z.CMov(z, &y, isQR)
    55  	return isQR
    56  }
    57  
    58  // CMov sets z=x if b == 0 and z=y if b == 1. Its behavior is undefined if b takes any other value.
    59  func (z *Fp) CMov(x, y *Fp, b int) {
    60  	mask := -uint64(b & 0x1)
    61  	for i := 0; i < FpSize/8; i++ {
    62  		z.i[i] = (x.i[i] &^ mask) | (y.i[i] & mask)
    63  	}
    64  }
    65  
    66  // FpOrder is the order of the base field for towering returned as a big-endian slice.
    67  //
    68  //	FpOrder = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab.
    69  func FpOrder() []byte { o := fpOrder; return o[:] }
    70  
    71  // ExpVarTime calculates z=x^n, where n is the exponent in big-endian order.
    72  func (z *Fp) ExpVarTime(x *Fp, n []byte) {
    73  	zz := new(Fp)
    74  	zz.SetOne()
    75  	N := 8 * len(n)
    76  	for i := 0; i < N; i++ {
    77  		zz.Sqr(zz)
    78  		bit := 0x1 & (n[i/8] >> uint(7-i%8))
    79  		if bit != 0 {
    80  			zz.Mul(zz, x)
    81  		}
    82  	}
    83  	*z = *zz
    84  }
    85  
    86  // SetBytes assigns to z the number modulo FpOrder stored in the slice
    87  // (in big-endian order).
    88  func (z *Fp) SetBytes(data []byte) {
    89  	in64 := setBytesUnbounded(data, fpOrder[:])
    90  	s := &fpRaw{}
    91  	copy(s[:], in64[:FpSize/8])
    92  	z.toMont(s)
    93  }
    94  
    95  // MarshalBinary returns a slice of FpSize bytes that contains the minimal
    96  // residue of z such that 0 <= z < FpOrder (in big-endian order).
    97  func (z *Fp) MarshalBinary() ([]byte, error) {
    98  	x := z.fromMont()
    99  	return conv.Uint64Le2BytesBe(x[:]), nil
   100  }
   101  
   102  // UnmarshalBinary reconstructs a Fp from a slice that must have at least
   103  // FpSize bytes and contain a number (in big-endian order) from 0
   104  // to FpOrder-1.
   105  func (z *Fp) UnmarshalBinary(b []byte) error {
   106  	if len(b) < FpSize {
   107  		return errInputLength
   108  	}
   109  	in64, err := setBytesBounded(b[:FpSize], fpOrder[:])
   110  	if err == nil {
   111  		s := &fpRaw{}
   112  		copy(s[:], in64[:FpSize/8])
   113  		z.toMont(s)
   114  	}
   115  	return err
   116  }
   117  
   118  // SetString reconstructs a Fp from a numeric string from 0 to FpOrder-1.
   119  func (z *Fp) SetString(s string) error {
   120  	in64, err := setString(s, fpOrder[:])
   121  	if err == nil {
   122  		s := &fpRaw{}
   123  		copy(s[:], in64[:FpSize/8])
   124  		z.toMont(s)
   125  	}
   126  	return err
   127  }
   128  
   129  func fiatFpMontCmovznzU64(z *uint64, b, x, y uint64) { cselectU64(z, b, x, y) }
   130  
   131  func (z *Fp) Inv(x *Fp) {
   132  	// Addition chain found using mmcloughlin/addchain: v0.3.0
   133  	// McLoughlin, Michael Ben. (2021). https://doi.org/10.5281/zenodo.4758226
   134  	var i2, i4, i8, i9, i11, i13, i17, i20, i25, i26, i52, i54, i55, i77, i79,
   135  		i86, i93, i103, i105, i119, i123, i137, i149, i151, i169, i177, i191,
   136  		i195, i208, i215, i225, i229, i235, i245, i255 Fp
   137  
   138  	i2.Sqr(x)
   139  	i4.Sqr(&i2)
   140  	i8.Sqr(&i4)
   141  	i9.Mul(&i8, x)
   142  	i11.Mul(&i9, &i2)
   143  	i13.Mul(&i11, &i2)
   144  	i17.Mul(&i13, &i4)
   145  	i20.Mul(&i11, &i9)
   146  	i25.Mul(&i17, &i8)
   147  	i26.Mul(&i25, x)
   148  	i52.Sqr(&i26)
   149  	i54.Mul(&i52, &i2)
   150  	i55.Mul(&i54, x)
   151  	i77.Mul(&i52, &i25)
   152  	i79.Mul(&i77, &i2)
   153  	i86.Mul(&i77, &i8)
   154  	i93.Mul(&i86, &i8)
   155  	i103.Mul(&i77, &i26)
   156  	i105.Mul(&i103, &i2)
   157  	i119.Mul(&i93, &i26)
   158  	i123.Mul(&i119, &i4)
   159  	i137.Mul(&i86, &i52)
   160  	i149.Mul(&i123, &i26)
   161  	i151.Mul(&i149, &i2)
   162  	i169.Mul(&i149, &i20)
   163  	i177.Mul(&i169, &i8)
   164  	i191.Mul(&i137, &i54)
   165  	i195.Mul(&i191, &i4)
   166  	i208.Mul(&i195, &i13)
   167  	i215.Mul(&i195, &i20)
   168  	i225.Mul(&i208, &i17)
   169  	i229.Mul(&i225, &i4)
   170  	i235.Mul(&i215, &i20)
   171  	i245.Mul(&i225, &i20)
   172  	i255.Mul(&i235, &i20)
   173  	z.Mul(&i225, &i191)
   174  
   175  	for _, s := range []struct {
   176  		l int
   177  		x *Fp
   178  	}{
   179  		{8, &i17},
   180  		{11, &i245},
   181  		{11, &i229},
   182  		{8, &i255},
   183  		{7, &i77},
   184  		{9, &i105},
   185  		{10, &i177},
   186  		{7, &i93},
   187  		{9, &i123},
   188  		{6, &i25},
   189  		{11, &i105},
   190  		{9, &i235},
   191  		{10, &i215},
   192  		{6, &i25},
   193  		{10, &i119},
   194  		{9, &i151},
   195  		{11, &i79},
   196  		{10, &i225},
   197  		{9, &i137},
   198  		{9, &i191},
   199  		{8, &i103},
   200  		{10, &i195},
   201  		{9, &i149},
   202  		{12, &i123},
   203  		{5, &i11},
   204  		{11, &i123},
   205  		{7, &i9},
   206  		{13, &i245},
   207  		{9, &i191},
   208  		{8, &i255},
   209  		{8, &i235},
   210  		{11, &i169},
   211  		{8, &i255},
   212  		{8, &i255},
   213  		{6, &i55},
   214  		{10, &i255},
   215  		{9, &i255},
   216  		{8, &i255},
   217  		{8, &i255},
   218  		{8, &i255},
   219  		{7, &i86},
   220  		{9, &i169},
   221  	} {
   222  		for i := 0; i < s.l; i++ {
   223  			z.Sqr(z)
   224  		}
   225  		z.Mul(z, s.x)
   226  	}
   227  }
   228  
   229  var (
   230  	// fpOrder is the order of the Fp field (big-endian).
   231  	fpOrder = [FpSize]byte{
   232  		0x1a, 0x01, 0x11, 0xea, 0x39, 0x7f, 0xe6, 0x9a,
   233  		0x4b, 0x1b, 0xa7, 0xb6, 0x43, 0x4b, 0xac, 0xd7,
   234  		0x64, 0x77, 0x4b, 0x84, 0xf3, 0x85, 0x12, 0xbf,
   235  		0x67, 0x30, 0xd2, 0xa0, 0xf6, 0xb0, 0xf6, 0x24,
   236  		0x1e, 0xab, 0xff, 0xfe, 0xb1, 0x53, 0xff, 0xff,
   237  		0xb9, 0xfe, 0xff, 0xff, 0xff, 0xff, 0xaa, 0xab,
   238  	}
   239  	// fpOrderPlus1Div2 is the half of (fpOrder plus one) used for lexicographically order (big-endian).
   240  	fpOrderPlus1Div2 = [FpSize]byte{
   241  		0x0d, 0x00, 0x88, 0xf5, 0x1c, 0xbf, 0xf3, 0x4d,
   242  		0x25, 0x8d, 0xd3, 0xdb, 0x21, 0xa5, 0xd6, 0x6b,
   243  		0xb2, 0x3b, 0xa5, 0xc2, 0x79, 0xc2, 0x89, 0x5f,
   244  		0xb3, 0x98, 0x69, 0x50, 0x7b, 0x58, 0x7b, 0x12,
   245  		0x0f, 0x55, 0xff, 0xff, 0x58, 0xa9, 0xff, 0xff,
   246  		0xdc, 0xff, 0x7f, 0xff, 0xff, 0xff, 0xd5, 0x56,
   247  	}
   248  	// fpOrderPlus1Div4 is (fpOrder plus one) divided by four used for square-roots (big-endian).
   249  	fpOrderPlus1Div4 = [FpSize]byte{
   250  		0x06, 0x80, 0x44, 0x7a, 0x8e, 0x5f, 0xf9, 0xa6,
   251  		0x92, 0xc6, 0xe9, 0xed, 0x90, 0xd2, 0xeb, 0x35,
   252  		0xd9, 0x1d, 0xd2, 0xe1, 0x3c, 0xe1, 0x44, 0xaf,
   253  		0xd9, 0xcc, 0x34, 0xa8, 0x3d, 0xac, 0x3d, 0x89,
   254  		0x07, 0xaa, 0xff, 0xff, 0xac, 0x54, 0xff, 0xff,
   255  		0xee, 0x7f, 0xbf, 0xff, 0xff, 0xff, 0xea, 0xab,
   256  	}
   257  	// fpRSquare is R^2 mod fpOrder, where R=2^384 (little-endian).
   258  	fpRSquare = fpMont{
   259  		0xf4df1f341c341746, 0x0a76e6a609d104f1,
   260  		0x8de5476c4c95b6d5, 0x67eb88a9939d83c0,
   261  		0x9a793e85b519952d, 0x11988fe592cae3aa,
   262  	}
   263  )
   264
View as plain text