scalar.go

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

     1  package goldilocks
     2  
     3  import (
     4  	"encoding/binary"
     5  	"math/bits"
     6  )
     7  
     8  // ScalarSize is the size (in bytes) of scalars.
     9  const ScalarSize = 56 // 448 / 8
    10  
    11  // _N is the number of 64-bit words to store scalars.
    12  const _N = 7 // 448 / 64
    13  
    14  // Scalar represents a positive integer stored in little-endian order.
    15  type Scalar [ScalarSize]byte
    16  
    17  type scalar64 [_N]uint64
    18  
    19  func (z *scalar64) fromScalar(x *Scalar) {
    20  	z[0] = binary.LittleEndian.Uint64(x[0*8 : 1*8])
    21  	z[1] = binary.LittleEndian.Uint64(x[1*8 : 2*8])
    22  	z[2] = binary.LittleEndian.Uint64(x[2*8 : 3*8])
    23  	z[3] = binary.LittleEndian.Uint64(x[3*8 : 4*8])
    24  	z[4] = binary.LittleEndian.Uint64(x[4*8 : 5*8])
    25  	z[5] = binary.LittleEndian.Uint64(x[5*8 : 6*8])
    26  	z[6] = binary.LittleEndian.Uint64(x[6*8 : 7*8])
    27  }
    28  
    29  func (z *scalar64) toScalar(x *Scalar) {
    30  	binary.LittleEndian.PutUint64(x[0*8:1*8], z[0])
    31  	binary.LittleEndian.PutUint64(x[1*8:2*8], z[1])
    32  	binary.LittleEndian.PutUint64(x[2*8:3*8], z[2])
    33  	binary.LittleEndian.PutUint64(x[3*8:4*8], z[3])
    34  	binary.LittleEndian.PutUint64(x[4*8:5*8], z[4])
    35  	binary.LittleEndian.PutUint64(x[5*8:6*8], z[5])
    36  	binary.LittleEndian.PutUint64(x[6*8:7*8], z[6])
    37  }
    38  
    39  // add calculates z = x + y. Assumes len(z) > max(len(x),len(y)).
    40  func add(z, x, y []uint64) uint64 {
    41  	l, L, zz := len(x), len(y), y
    42  	if l > L {
    43  		l, L, zz = L, l, x
    44  	}
    45  	c := uint64(0)
    46  	for i := 0; i < l; i++ {
    47  		z[i], c = bits.Add64(x[i], y[i], c)
    48  	}
    49  	for i := l; i < L; i++ {
    50  		z[i], c = bits.Add64(zz[i], 0, c)
    51  	}
    52  	return c
    53  }
    54  
    55  // sub calculates z = x - y. Assumes len(z) > max(len(x),len(y)).
    56  func sub(z, x, y []uint64) uint64 {
    57  	l, L, zz := len(x), len(y), y
    58  	if l > L {
    59  		l, L, zz = L, l, x
    60  	}
    61  	c := uint64(0)
    62  	for i := 0; i < l; i++ {
    63  		z[i], c = bits.Sub64(x[i], y[i], c)
    64  	}
    65  	for i := l; i < L; i++ {
    66  		z[i], c = bits.Sub64(zz[i], 0, c)
    67  	}
    68  	return c
    69  }
    70  
    71  // mulWord calculates z = x * y. Assumes len(z) >= len(x)+1.
    72  func mulWord(z, x []uint64, y uint64) {
    73  	for i := range z {
    74  		z[i] = 0
    75  	}
    76  	carry := uint64(0)
    77  	for i := range x {
    78  		hi, lo := bits.Mul64(x[i], y)
    79  		lo, cc := bits.Add64(lo, z[i], 0)
    80  		hi, _ = bits.Add64(hi, 0, cc)
    81  		z[i], cc = bits.Add64(lo, carry, 0)
    82  		carry, _ = bits.Add64(hi, 0, cc)
    83  	}
    84  	z[len(x)] = carry
    85  }
    86  
    87  // Cmov moves x into z if b=1.
    88  func (z *scalar64) Cmov(b uint64, x *scalar64) {
    89  	m := uint64(0) - b
    90  	for i := range z {
    91  		z[i] = (z[i] &^ m) | (x[i] & m)
    92  	}
    93  }
    94  
    95  // leftShift shifts to the left the words of z returning the more significant word.
    96  func (z *scalar64) leftShift(low uint64) uint64 {
    97  	high := z[_N-1]
    98  	for i := _N - 1; i > 0; i-- {
    99  		z[i] = z[i-1]
   100  	}
   101  	z[0] = low
   102  	return high
   103  }
   104  
   105  // reduceOneWord calculates z = z + 2^448*x such that the result fits in a Scalar.
   106  func (z *scalar64) reduceOneWord(x uint64) {
   107  	prod := (&scalar64{})[:]
   108  	mulWord(prod, residue448[:], x)
   109  	cc := add(z[:], z[:], prod)
   110  	mulWord(prod, residue448[:], cc)
   111  	add(z[:], z[:], prod)
   112  }
   113  
   114  // modOrder reduces z mod order.
   115  func (z *scalar64) modOrder() {
   116  	var o64, x scalar64
   117  	o64.fromScalar(&order)
   118  	// Performs: while (z >= order) { z = z-order }
   119  	// At most 8 (eight) iterations reduce 3 bits by subtracting.
   120  	for i := 0; i < 8; i++ {
   121  		c := sub(x[:], z[:], o64[:]) // (c || x) = z-order
   122  		z.Cmov(1-c, &x)              // if c != 0 { z = x }
   123  	}
   124  }
   125  
   126  // FromBytes stores z = x mod order, where x is a number stored in little-endian order.
   127  func (z *Scalar) FromBytes(x []byte) {
   128  	n := len(x)
   129  	nCeil := (n + 7) >> 3
   130  	for i := range z {
   131  		z[i] = 0
   132  	}
   133  	if nCeil < _N {
   134  		copy(z[:], x)
   135  		return
   136  	}
   137  	copy(z[:], x[8*(nCeil-_N):])
   138  	var z64 scalar64
   139  	z64.fromScalar(z)
   140  	for i := nCeil - _N - 1; i >= 0; i-- {
   141  		low := binary.LittleEndian.Uint64(x[8*i:])
   142  		high := z64.leftShift(low)
   143  		z64.reduceOneWord(high)
   144  	}
   145  	z64.modOrder()
   146  	z64.toScalar(z)
   147  }
   148  
   149  // divBy4 calculates z = x/4 mod order.
   150  func (z *Scalar) divBy4(x *Scalar) { z.Mul(x, &invFour) }
   151  
   152  // Red reduces z mod order.
   153  func (z *Scalar) Red() { var t scalar64; t.fromScalar(z); t.modOrder(); t.toScalar(z) }
   154  
   155  // Neg calculates z = -z mod order.
   156  func (z *Scalar) Neg() { z.Sub(&order, z) }
   157  
   158  // Add calculates z = x+y mod order.
   159  func (z *Scalar) Add(x, y *Scalar) {
   160  	var z64, x64, y64, t scalar64
   161  	x64.fromScalar(x)
   162  	y64.fromScalar(y)
   163  	c := add(z64[:], x64[:], y64[:])
   164  	add(t[:], z64[:], residue448[:])
   165  	z64.Cmov(c, &t)
   166  	z64.modOrder()
   167  	z64.toScalar(z)
   168  }
   169  
   170  // Sub calculates z = x-y mod order.
   171  func (z *Scalar) Sub(x, y *Scalar) {
   172  	var z64, x64, y64, t scalar64
   173  	x64.fromScalar(x)
   174  	y64.fromScalar(y)
   175  	c := sub(z64[:], x64[:], y64[:])
   176  	sub(t[:], z64[:], residue448[:])
   177  	z64.Cmov(c, &t)
   178  	z64.modOrder()
   179  	z64.toScalar(z)
   180  }
   181  
   182  // Mul calculates z = x*y mod order.
   183  func (z *Scalar) Mul(x, y *Scalar) {
   184  	var z64, x64, y64 scalar64
   185  	prod := (&[_N + 1]uint64{})[:]
   186  	x64.fromScalar(x)
   187  	y64.fromScalar(y)
   188  	mulWord(prod, x64[:], y64[_N-1])
   189  	copy(z64[:], prod[:_N])
   190  	z64.reduceOneWord(prod[_N])
   191  	for i := _N - 2; i >= 0; i-- {
   192  		h := z64.leftShift(0)
   193  		z64.reduceOneWord(h)
   194  		mulWord(prod, x64[:], y64[i])
   195  		c := add(z64[:], z64[:], prod[:_N])
   196  		z64.reduceOneWord(prod[_N] + c)
   197  	}
   198  	z64.modOrder()
   199  	z64.toScalar(z)
   200  }
   201  
   202  // IsZero returns true if z=0.
   203  func (z *Scalar) IsZero() bool { z.Red(); return *z == Scalar{} }
   204
View as plain text