fp.go

Documentation: github.com/cloudflare/circl/math/fp25519

     1  // Package fp25519 provides prime field arithmetic over GF(2^255-19).
     2  package fp25519
     3  
     4  import (
     5  	"errors"
     6  
     7  	"github.com/cloudflare/circl/internal/conv"
     8  )
     9  
    10  // Size in bytes of an element.
    11  const Size = 32
    12  
    13  // Elt is a prime field element.
    14  type Elt [Size]byte
    15  
    16  func (e Elt) String() string { return conv.BytesLe2Hex(e[:]) }
    17  
    18  // p is the prime modulus 2^255-19.
    19  var p = Elt{
    20  	0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    21  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    22  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
    23  	0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f,
    24  }
    25  
    26  // P returns the prime modulus 2^255-19.
    27  func P() Elt { return p }
    28  
    29  // ToBytes stores in b the little-endian byte representation of x.
    30  func ToBytes(b []byte, x *Elt) error {
    31  	if len(b) != Size {
    32  		return errors.New("wrong size")
    33  	}
    34  	Modp(x)
    35  	copy(b, x[:])
    36  	return nil
    37  }
    38  
    39  // IsZero returns true if x is equal to 0.
    40  func IsZero(x *Elt) bool { Modp(x); return *x == Elt{} }
    41  
    42  // SetOne assigns x=1.
    43  func SetOne(x *Elt) { *x = Elt{}; x[0] = 1 }
    44  
    45  // Neg calculates z = -x.
    46  func Neg(z, x *Elt) { Sub(z, &p, x) }
    47  
    48  // InvSqrt calculates z = sqrt(x/y) iff x/y is a quadratic-residue, which is
    49  // indicated by returning isQR = true. Otherwise, when x/y is a quadratic
    50  // non-residue, z will have an undetermined value and isQR = false.
    51  func InvSqrt(z, x, y *Elt) (isQR bool) {
    52  	sqrtMinusOne := &Elt{
    53  		0xb0, 0xa0, 0x0e, 0x4a, 0x27, 0x1b, 0xee, 0xc4,
    54  		0x78, 0xe4, 0x2f, 0xad, 0x06, 0x18, 0x43, 0x2f,
    55  		0xa7, 0xd7, 0xfb, 0x3d, 0x99, 0x00, 0x4d, 0x2b,
    56  		0x0b, 0xdf, 0xc1, 0x4f, 0x80, 0x24, 0x83, 0x2b,
    57  	}
    58  	t0, t1, t2, t3 := &Elt{}, &Elt{}, &Elt{}, &Elt{}
    59  
    60  	Mul(t0, x, y)   // t0 = u*v
    61  	Sqr(t1, y)      // t1 = v^2
    62  	Mul(t2, t0, t1) // t2 = u*v^3
    63  	Sqr(t0, t1)     // t0 = v^4
    64  	Mul(t1, t0, t2) // t1 = u*v^7
    65  
    66  	var Tab [4]*Elt
    67  	Tab[0] = &Elt{}
    68  	Tab[1] = &Elt{}
    69  	Tab[2] = t3
    70  	Tab[3] = t1
    71  
    72  	*Tab[0] = *t1
    73  	Sqr(Tab[0], Tab[0])
    74  	Sqr(Tab[1], Tab[0])
    75  	Sqr(Tab[1], Tab[1])
    76  	Mul(Tab[1], Tab[1], Tab[3])
    77  	Mul(Tab[0], Tab[0], Tab[1])
    78  	Sqr(Tab[0], Tab[0])
    79  	Mul(Tab[0], Tab[0], Tab[1])
    80  	Sqr(Tab[1], Tab[0])
    81  	for i := 0; i < 4; i++ {
    82  		Sqr(Tab[1], Tab[1])
    83  	}
    84  	Mul(Tab[1], Tab[1], Tab[0])
    85  	Sqr(Tab[2], Tab[1])
    86  	for i := 0; i < 4; i++ {
    87  		Sqr(Tab[2], Tab[2])
    88  	}
    89  	Mul(Tab[2], Tab[2], Tab[0])
    90  	Sqr(Tab[1], Tab[2])
    91  	for i := 0; i < 14; i++ {
    92  		Sqr(Tab[1], Tab[1])
    93  	}
    94  	Mul(Tab[1], Tab[1], Tab[2])
    95  	Sqr(Tab[2], Tab[1])
    96  	for i := 0; i < 29; i++ {
    97  		Sqr(Tab[2], Tab[2])
    98  	}
    99  	Mul(Tab[2], Tab[2], Tab[1])
   100  	Sqr(Tab[1], Tab[2])
   101  	for i := 0; i < 59; i++ {
   102  		Sqr(Tab[1], Tab[1])
   103  	}
   104  	Mul(Tab[1], Tab[1], Tab[2])
   105  	for i := 0; i < 5; i++ {
   106  		Sqr(Tab[1], Tab[1])
   107  	}
   108  	Mul(Tab[1], Tab[1], Tab[0])
   109  	Sqr(Tab[2], Tab[1])
   110  	for i := 0; i < 124; i++ {
   111  		Sqr(Tab[2], Tab[2])
   112  	}
   113  	Mul(Tab[2], Tab[2], Tab[1])
   114  	Sqr(Tab[2], Tab[2])
   115  	Sqr(Tab[2], Tab[2])
   116  	Mul(Tab[2], Tab[2], Tab[3])
   117  
   118  	Mul(z, t3, t2) // z = xy^(p+3)/8 = xy^3*(xy^7)^(p-5)/8
   119  	// Checking whether y z^2 == x
   120  	Sqr(t0, z)     // t0 = z^2
   121  	Mul(t0, t0, y) // t0 = yz^2
   122  	Sub(t1, t0, x) // t1 = t0-u
   123  	Add(t2, t0, x) // t2 = t0+u
   124  	if IsZero(t1) {
   125  		return true
   126  	} else if IsZero(t2) {
   127  		Mul(z, z, sqrtMinusOne) // z = z*sqrt(-1)
   128  		return true
   129  	} else {
   130  		return false
   131  	}
   132  }
   133  
   134  // Inv calculates z = 1/x mod p.
   135  func Inv(z, x *Elt) {
   136  	x0, x1, x2 := &Elt{}, &Elt{}, &Elt{}
   137  	Sqr(x1, x)
   138  	Sqr(x0, x1)
   139  	Sqr(x0, x0)
   140  	Mul(x0, x0, x)
   141  	Mul(z, x0, x1)
   142  	Sqr(x1, z)
   143  	Mul(x0, x0, x1)
   144  	Sqr(x1, x0)
   145  	for i := 0; i < 4; i++ {
   146  		Sqr(x1, x1)
   147  	}
   148  	Mul(x0, x0, x1)
   149  	Sqr(x1, x0)
   150  	for i := 0; i < 9; i++ {
   151  		Sqr(x1, x1)
   152  	}
   153  	Mul(x1, x1, x0)
   154  	Sqr(x2, x1)
   155  	for i := 0; i < 19; i++ {
   156  		Sqr(x2, x2)
   157  	}
   158  	Mul(x2, x2, x1)
   159  	for i := 0; i < 10; i++ {
   160  		Sqr(x2, x2)
   161  	}
   162  	Mul(x2, x2, x0)
   163  	Sqr(x0, x2)
   164  	for i := 0; i < 49; i++ {
   165  		Sqr(x0, x0)
   166  	}
   167  	Mul(x0, x0, x2)
   168  	Sqr(x1, x0)
   169  	for i := 0; i < 99; i++ {
   170  		Sqr(x1, x1)
   171  	}
   172  	Mul(x1, x1, x0)
   173  	for i := 0; i < 50; i++ {
   174  		Sqr(x1, x1)
   175  	}
   176  	Mul(x1, x1, x2)
   177  	for i := 0; i < 5; i++ {
   178  		Sqr(x1, x1)
   179  	}
   180  	Mul(z, z, x1)
   181  }
   182  
   183  // Cmov assigns y to x if n is 1.
   184  func Cmov(x, y *Elt, n uint) { cmov(x, y, n) }
   185  
   186  // Cswap interchanges x and y if n is 1.
   187  func Cswap(x, y *Elt, n uint) { cswap(x, y, n) }
   188  
   189  // Add calculates z = x+y mod p.
   190  func Add(z, x, y *Elt) { add(z, x, y) }
   191  
   192  // Sub calculates z = x-y mod p.
   193  func Sub(z, x, y *Elt) { sub(z, x, y) }
   194  
   195  // AddSub calculates (x,y) = (x+y mod p, x-y mod p).
   196  func AddSub(x, y *Elt) { addsub(x, y) }
   197  
   198  // Mul calculates z = x*y mod p.
   199  func Mul(z, x, y *Elt) { mul(z, x, y) }
   200  
   201  // Sqr calculates z = x^2 mod p.
   202  func Sqr(z, x *Elt) { sqr(z, x) }
   203  
   204  // Modp ensures that z is between [0,p-1].
   205  func Modp(z *Elt) { modp(z) }
   206
View as plain text