scalar.go raw
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