fp_generic.go raw
1 package fp25519
2
3 import (
4 "encoding/binary"
5 "math/bits"
6 )
7
8 func cmovGeneric(x, y *Elt, n uint) {
9 m := -uint64(n & 0x1)
10 x0 := binary.LittleEndian.Uint64(x[0*8 : 1*8])
11 x1 := binary.LittleEndian.Uint64(x[1*8 : 2*8])
12 x2 := binary.LittleEndian.Uint64(x[2*8 : 3*8])
13 x3 := binary.LittleEndian.Uint64(x[3*8 : 4*8])
14
15 y0 := binary.LittleEndian.Uint64(y[0*8 : 1*8])
16 y1 := binary.LittleEndian.Uint64(y[1*8 : 2*8])
17 y2 := binary.LittleEndian.Uint64(y[2*8 : 3*8])
18 y3 := binary.LittleEndian.Uint64(y[3*8 : 4*8])
19
20 x0 = (x0 &^ m) | (y0 & m)
21 x1 = (x1 &^ m) | (y1 & m)
22 x2 = (x2 &^ m) | (y2 & m)
23 x3 = (x3 &^ m) | (y3 & m)
24
25 binary.LittleEndian.PutUint64(x[0*8:1*8], x0)
26 binary.LittleEndian.PutUint64(x[1*8:2*8], x1)
27 binary.LittleEndian.PutUint64(x[2*8:3*8], x2)
28 binary.LittleEndian.PutUint64(x[3*8:4*8], x3)
29 }
30
31 func cswapGeneric(x, y *Elt, n uint) {
32 m := -uint64(n & 0x1)
33 x0 := binary.LittleEndian.Uint64(x[0*8 : 1*8])
34 x1 := binary.LittleEndian.Uint64(x[1*8 : 2*8])
35 x2 := binary.LittleEndian.Uint64(x[2*8 : 3*8])
36 x3 := binary.LittleEndian.Uint64(x[3*8 : 4*8])
37
38 y0 := binary.LittleEndian.Uint64(y[0*8 : 1*8])
39 y1 := binary.LittleEndian.Uint64(y[1*8 : 2*8])
40 y2 := binary.LittleEndian.Uint64(y[2*8 : 3*8])
41 y3 := binary.LittleEndian.Uint64(y[3*8 : 4*8])
42
43 t0 := m & (x0 ^ y0)
44 t1 := m & (x1 ^ y1)
45 t2 := m & (x2 ^ y2)
46 t3 := m & (x3 ^ y3)
47 x0 ^= t0
48 x1 ^= t1
49 x2 ^= t2
50 x3 ^= t3
51 y0 ^= t0
52 y1 ^= t1
53 y2 ^= t2
54 y3 ^= t3
55
56 binary.LittleEndian.PutUint64(x[0*8:1*8], x0)
57 binary.LittleEndian.PutUint64(x[1*8:2*8], x1)
58 binary.LittleEndian.PutUint64(x[2*8:3*8], x2)
59 binary.LittleEndian.PutUint64(x[3*8:4*8], x3)
60
61 binary.LittleEndian.PutUint64(y[0*8:1*8], y0)
62 binary.LittleEndian.PutUint64(y[1*8:2*8], y1)
63 binary.LittleEndian.PutUint64(y[2*8:3*8], y2)
64 binary.LittleEndian.PutUint64(y[3*8:4*8], y3)
65 }
66
67 func addGeneric(z, x, y *Elt) {
68 x0 := binary.LittleEndian.Uint64(x[0*8 : 1*8])
69 x1 := binary.LittleEndian.Uint64(x[1*8 : 2*8])
70 x2 := binary.LittleEndian.Uint64(x[2*8 : 3*8])
71 x3 := binary.LittleEndian.Uint64(x[3*8 : 4*8])
72
73 y0 := binary.LittleEndian.Uint64(y[0*8 : 1*8])
74 y1 := binary.LittleEndian.Uint64(y[1*8 : 2*8])
75 y2 := binary.LittleEndian.Uint64(y[2*8 : 3*8])
76 y3 := binary.LittleEndian.Uint64(y[3*8 : 4*8])
77
78 z0, c0 := bits.Add64(x0, y0, 0)
79 z1, c1 := bits.Add64(x1, y1, c0)
80 z2, c2 := bits.Add64(x2, y2, c1)
81 z3, c3 := bits.Add64(x3, y3, c2)
82
83 z0, c0 = bits.Add64(z0, (-c3)&38, 0)
84 z1, c1 = bits.Add64(z1, 0, c0)
85 z2, c2 = bits.Add64(z2, 0, c1)
86 z3, c3 = bits.Add64(z3, 0, c2)
87 z0, _ = bits.Add64(z0, (-c3)&38, 0)
88
89 binary.LittleEndian.PutUint64(z[0*8:1*8], z0)
90 binary.LittleEndian.PutUint64(z[1*8:2*8], z1)
91 binary.LittleEndian.PutUint64(z[2*8:3*8], z2)
92 binary.LittleEndian.PutUint64(z[3*8:4*8], z3)
93 }
94
95 func subGeneric(z, x, y *Elt) {
96 x0 := binary.LittleEndian.Uint64(x[0*8 : 1*8])
97 x1 := binary.LittleEndian.Uint64(x[1*8 : 2*8])
98 x2 := binary.LittleEndian.Uint64(x[2*8 : 3*8])
99 x3 := binary.LittleEndian.Uint64(x[3*8 : 4*8])
100
101 y0 := binary.LittleEndian.Uint64(y[0*8 : 1*8])
102 y1 := binary.LittleEndian.Uint64(y[1*8 : 2*8])
103 y2 := binary.LittleEndian.Uint64(y[2*8 : 3*8])
104 y3 := binary.LittleEndian.Uint64(y[3*8 : 4*8])
105
106 z0, c0 := bits.Sub64(x0, y0, 0)
107 z1, c1 := bits.Sub64(x1, y1, c0)
108 z2, c2 := bits.Sub64(x2, y2, c1)
109 z3, c3 := bits.Sub64(x3, y3, c2)
110
111 z0, c0 = bits.Sub64(z0, (-c3)&38, 0)
112 z1, c1 = bits.Sub64(z1, 0, c0)
113 z2, c2 = bits.Sub64(z2, 0, c1)
114 z3, c3 = bits.Sub64(z3, 0, c2)
115 z0, _ = bits.Sub64(z0, (-c3)&38, 0)
116
117 binary.LittleEndian.PutUint64(z[0*8:1*8], z0)
118 binary.LittleEndian.PutUint64(z[1*8:2*8], z1)
119 binary.LittleEndian.PutUint64(z[2*8:3*8], z2)
120 binary.LittleEndian.PutUint64(z[3*8:4*8], z3)
121 }
122
123 func addsubGeneric(x, y *Elt) {
124 z := &Elt{}
125 addGeneric(z, x, y)
126 subGeneric(y, x, y)
127 *x = *z
128 }
129
130 func mulGeneric(z, x, y *Elt) {
131 x0 := binary.LittleEndian.Uint64(x[0*8 : 1*8])
132 x1 := binary.LittleEndian.Uint64(x[1*8 : 2*8])
133 x2 := binary.LittleEndian.Uint64(x[2*8 : 3*8])
134 x3 := binary.LittleEndian.Uint64(x[3*8 : 4*8])
135
136 y0 := binary.LittleEndian.Uint64(y[0*8 : 1*8])
137 y1 := binary.LittleEndian.Uint64(y[1*8 : 2*8])
138 y2 := binary.LittleEndian.Uint64(y[2*8 : 3*8])
139 y3 := binary.LittleEndian.Uint64(y[3*8 : 4*8])
140
141 yi := y0
142 h0, l0 := bits.Mul64(x0, yi)
143 h1, l1 := bits.Mul64(x1, yi)
144 h2, l2 := bits.Mul64(x2, yi)
145 h3, l3 := bits.Mul64(x3, yi)
146
147 z0 := l0
148 a0, c0 := bits.Add64(h0, l1, 0)
149 a1, c1 := bits.Add64(h1, l2, c0)
150 a2, c2 := bits.Add64(h2, l3, c1)
151 a3, _ := bits.Add64(h3, 0, c2)
152
153 yi = y1
154 h0, l0 = bits.Mul64(x0, yi)
155 h1, l1 = bits.Mul64(x1, yi)
156 h2, l2 = bits.Mul64(x2, yi)
157 h3, l3 = bits.Mul64(x3, yi)
158
159 z1, c0 := bits.Add64(a0, l0, 0)
160 h0, c1 = bits.Add64(h0, l1, c0)
161 h1, c2 = bits.Add64(h1, l2, c1)
162 h2, c3 := bits.Add64(h2, l3, c2)
163 h3, _ = bits.Add64(h3, 0, c3)
164
165 a0, c0 = bits.Add64(a1, h0, 0)
166 a1, c1 = bits.Add64(a2, h1, c0)
167 a2, c2 = bits.Add64(a3, h2, c1)
168 a3, _ = bits.Add64(0, h3, c2)
169
170 yi = y2
171 h0, l0 = bits.Mul64(x0, yi)
172 h1, l1 = bits.Mul64(x1, yi)
173 h2, l2 = bits.Mul64(x2, yi)
174 h3, l3 = bits.Mul64(x3, yi)
175
176 z2, c0 := bits.Add64(a0, l0, 0)
177 h0, c1 = bits.Add64(h0, l1, c0)
178 h1, c2 = bits.Add64(h1, l2, c1)
179 h2, c3 = bits.Add64(h2, l3, c2)
180 h3, _ = bits.Add64(h3, 0, c3)
181
182 a0, c0 = bits.Add64(a1, h0, 0)
183 a1, c1 = bits.Add64(a2, h1, c0)
184 a2, c2 = bits.Add64(a3, h2, c1)
185 a3, _ = bits.Add64(0, h3, c2)
186
187 yi = y3
188 h0, l0 = bits.Mul64(x0, yi)
189 h1, l1 = bits.Mul64(x1, yi)
190 h2, l2 = bits.Mul64(x2, yi)
191 h3, l3 = bits.Mul64(x3, yi)
192
193 z3, c0 := bits.Add64(a0, l0, 0)
194 h0, c1 = bits.Add64(h0, l1, c0)
195 h1, c2 = bits.Add64(h1, l2, c1)
196 h2, c3 = bits.Add64(h2, l3, c2)
197 h3, _ = bits.Add64(h3, 0, c3)
198
199 z4, c0 := bits.Add64(a1, h0, 0)
200 z5, c1 := bits.Add64(a2, h1, c0)
201 z6, c2 := bits.Add64(a3, h2, c1)
202 z7, _ := bits.Add64(0, h3, c2)
203
204 red64(z, z0, z1, z2, z3, z4, z5, z6, z7)
205 }
206
207 func sqrGeneric(z, x *Elt) {
208 x0 := binary.LittleEndian.Uint64(x[0*8 : 1*8])
209 x1 := binary.LittleEndian.Uint64(x[1*8 : 2*8])
210 x2 := binary.LittleEndian.Uint64(x[2*8 : 3*8])
211 x3 := binary.LittleEndian.Uint64(x[3*8 : 4*8])
212
213 h0, a0 := bits.Mul64(x0, x1)
214 h1, l1 := bits.Mul64(x0, x2)
215 h2, l2 := bits.Mul64(x0, x3)
216 h3, l3 := bits.Mul64(x3, x1)
217 h4, l4 := bits.Mul64(x3, x2)
218 h, l := bits.Mul64(x1, x2)
219
220 a1, c0 := bits.Add64(l1, h0, 0)
221 a2, c1 := bits.Add64(l2, h1, c0)
222 a3, c2 := bits.Add64(l3, h2, c1)
223 a4, c3 := bits.Add64(l4, h3, c2)
224 a5, _ := bits.Add64(h4, 0, c3)
225
226 a2, c0 = bits.Add64(a2, l, 0)
227 a3, c1 = bits.Add64(a3, h, c0)
228 a4, c2 = bits.Add64(a4, 0, c1)
229 a5, c3 = bits.Add64(a5, 0, c2)
230 a6, _ := bits.Add64(0, 0, c3)
231
232 a0, c0 = bits.Add64(a0, a0, 0)
233 a1, c1 = bits.Add64(a1, a1, c0)
234 a2, c2 = bits.Add64(a2, a2, c1)
235 a3, c3 = bits.Add64(a3, a3, c2)
236 a4, c4 := bits.Add64(a4, a4, c3)
237 a5, c5 := bits.Add64(a5, a5, c4)
238 a6, _ = bits.Add64(a6, a6, c5)
239
240 b1, b0 := bits.Mul64(x0, x0)
241 b3, b2 := bits.Mul64(x1, x1)
242 b5, b4 := bits.Mul64(x2, x2)
243 b7, b6 := bits.Mul64(x3, x3)
244
245 b1, c0 = bits.Add64(b1, a0, 0)
246 b2, c1 = bits.Add64(b2, a1, c0)
247 b3, c2 = bits.Add64(b3, a2, c1)
248 b4, c3 = bits.Add64(b4, a3, c2)
249 b5, c4 = bits.Add64(b5, a4, c3)
250 b6, c5 = bits.Add64(b6, a5, c4)
251 b7, _ = bits.Add64(b7, a6, c5)
252
253 red64(z, b0, b1, b2, b3, b4, b5, b6, b7)
254 }
255
256 func modpGeneric(x *Elt) {
257 x0 := binary.LittleEndian.Uint64(x[0*8 : 1*8])
258 x1 := binary.LittleEndian.Uint64(x[1*8 : 2*8])
259 x2 := binary.LittleEndian.Uint64(x[2*8 : 3*8])
260 x3 := binary.LittleEndian.Uint64(x[3*8 : 4*8])
261
262 // CX = C[255] ? 38 : 19
263 cx := uint64(19) << (x3 >> 63)
264 // PUT BIT 255 IN CARRY FLAG AND CLEAR
265 x3 &^= 1 << 63
266
267 x0, c0 := bits.Add64(x0, cx, 0)
268 x1, c1 := bits.Add64(x1, 0, c0)
269 x2, c2 := bits.Add64(x2, 0, c1)
270 x3, _ = bits.Add64(x3, 0, c2)
271
272 // TEST FOR BIT 255 AGAIN; ONLY TRIGGERED ON OVERFLOW MODULO 2^255-19
273 // cx = C[255] ? 0 : 19
274 cx = uint64(19) &^ (-(x3 >> 63))
275 // CLEAR BIT 255
276 x3 &^= 1 << 63
277
278 x0, c0 = bits.Sub64(x0, cx, 0)
279 x1, c1 = bits.Sub64(x1, 0, c0)
280 x2, c2 = bits.Sub64(x2, 0, c1)
281 x3, _ = bits.Sub64(x3, 0, c2)
282
283 binary.LittleEndian.PutUint64(x[0*8:1*8], x0)
284 binary.LittleEndian.PutUint64(x[1*8:2*8], x1)
285 binary.LittleEndian.PutUint64(x[2*8:3*8], x2)
286 binary.LittleEndian.PutUint64(x[3*8:4*8], x3)
287 }
288
289 func red64(z *Elt, x0, x1, x2, x3, x4, x5, x6, x7 uint64) {
290 h0, l0 := bits.Mul64(x4, 38)
291 h1, l1 := bits.Mul64(x5, 38)
292 h2, l2 := bits.Mul64(x6, 38)
293 h3, l3 := bits.Mul64(x7, 38)
294
295 l1, c0 := bits.Add64(h0, l1, 0)
296 l2, c1 := bits.Add64(h1, l2, c0)
297 l3, c2 := bits.Add64(h2, l3, c1)
298 l4, _ := bits.Add64(h3, 0, c2)
299
300 l0, c0 = bits.Add64(l0, x0, 0)
301 l1, c1 = bits.Add64(l1, x1, c0)
302 l2, c2 = bits.Add64(l2, x2, c1)
303 l3, c3 := bits.Add64(l3, x3, c2)
304 l4, _ = bits.Add64(l4, 0, c3)
305
306 _, l4 = bits.Mul64(l4, 38)
307 l0, c0 = bits.Add64(l0, l4, 0)
308 z1, c1 := bits.Add64(l1, 0, c0)
309 z2, c2 := bits.Add64(l2, 0, c1)
310 z3, c3 := bits.Add64(l3, 0, c2)
311 z0, _ := bits.Add64(l0, (-c3)&38, 0)
312
313 binary.LittleEndian.PutUint64(z[0*8:1*8], z0)
314 binary.LittleEndian.PutUint64(z[1*8:2*8], z1)
315 binary.LittleEndian.PutUint64(z[2*8:3*8], z2)
316 binary.LittleEndian.PutUint64(z[3*8:4*8], z3)
317 }
318