blob: c43b13fc83e70c2dc738b44441a434cde4543d11 [file] [log] [blame]
Filippo Valsordafe705322019-11-07 16:06:22 -05001// Copyright 2013 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package curve25519
6
7import "encoding/binary"
8
9// This code is a port of the public domain, "ref10" implementation of
10// curve25519 from SUPERCOP 20130419 by D. J. Bernstein.
11
12// fieldElement represents an element of the field GF(2^255 - 19). An element
13// t, entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77
14// t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on
15// context.
16type fieldElement [10]int32
17
18func feZero(fe *fieldElement) {
19 for i := range fe {
20 fe[i] = 0
21 }
22}
23
24func feOne(fe *fieldElement) {
25 feZero(fe)
26 fe[0] = 1
27}
28
29func feAdd(dst, a, b *fieldElement) {
30 for i := range dst {
31 dst[i] = a[i] + b[i]
32 }
33}
34
35func feSub(dst, a, b *fieldElement) {
36 for i := range dst {
37 dst[i] = a[i] - b[i]
38 }
39}
40
41func feCopy(dst, src *fieldElement) {
42 for i := range dst {
43 dst[i] = src[i]
44 }
45}
46
47// feCSwap replaces (f,g) with (g,f) if b == 1; replaces (f,g) with (f,g) if b == 0.
48//
49// Preconditions: b in {0,1}.
50func feCSwap(f, g *fieldElement, b int32) {
51 b = -b
52 for i := range f {
53 t := b & (f[i] ^ g[i])
54 f[i] ^= t
55 g[i] ^= t
56 }
57}
58
59// load3 reads a 24-bit, little-endian value from in.
60func load3(in []byte) int64 {
61 var r int64
62 r = int64(in[0])
63 r |= int64(in[1]) << 8
64 r |= int64(in[2]) << 16
65 return r
66}
67
68// load4 reads a 32-bit, little-endian value from in.
69func load4(in []byte) int64 {
70 return int64(binary.LittleEndian.Uint32(in))
71}
72
73func feFromBytes(dst *fieldElement, src *[32]byte) {
74 h0 := load4(src[:])
75 h1 := load3(src[4:]) << 6
76 h2 := load3(src[7:]) << 5
77 h3 := load3(src[10:]) << 3
78 h4 := load3(src[13:]) << 2
79 h5 := load4(src[16:])
80 h6 := load3(src[20:]) << 7
81 h7 := load3(src[23:]) << 5
82 h8 := load3(src[26:]) << 4
83 h9 := (load3(src[29:]) & 0x7fffff) << 2
84
85 var carry [10]int64
86 carry[9] = (h9 + 1<<24) >> 25
87 h0 += carry[9] * 19
88 h9 -= carry[9] << 25
89 carry[1] = (h1 + 1<<24) >> 25
90 h2 += carry[1]
91 h1 -= carry[1] << 25
92 carry[3] = (h3 + 1<<24) >> 25
93 h4 += carry[3]
94 h3 -= carry[3] << 25
95 carry[5] = (h5 + 1<<24) >> 25
96 h6 += carry[5]
97 h5 -= carry[5] << 25
98 carry[7] = (h7 + 1<<24) >> 25
99 h8 += carry[7]
100 h7 -= carry[7] << 25
101
102 carry[0] = (h0 + 1<<25) >> 26
103 h1 += carry[0]
104 h0 -= carry[0] << 26
105 carry[2] = (h2 + 1<<25) >> 26
106 h3 += carry[2]
107 h2 -= carry[2] << 26
108 carry[4] = (h4 + 1<<25) >> 26
109 h5 += carry[4]
110 h4 -= carry[4] << 26
111 carry[6] = (h6 + 1<<25) >> 26
112 h7 += carry[6]
113 h6 -= carry[6] << 26
114 carry[8] = (h8 + 1<<25) >> 26
115 h9 += carry[8]
116 h8 -= carry[8] << 26
117
118 dst[0] = int32(h0)
119 dst[1] = int32(h1)
120 dst[2] = int32(h2)
121 dst[3] = int32(h3)
122 dst[4] = int32(h4)
123 dst[5] = int32(h5)
124 dst[6] = int32(h6)
125 dst[7] = int32(h7)
126 dst[8] = int32(h8)
127 dst[9] = int32(h9)
128}
129
130// feToBytes marshals h to s.
131// Preconditions:
132// |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
133//
134// Write p=2^255-19; q=floor(h/p).
135// Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
136//
137// Proof:
138// Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
139// Also have |h-2^230 h9|<2^230 so |19 2^(-255)(h-2^230 h9)|<1/4.
140//
141// Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
142// Then 0<y<1.
143//
144// Write r=h-pq.
145// Have 0<=r<=p-1=2^255-20.
146// Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
147//
148// Write x=r+19(2^-255)r+y.
149// Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
150//
151// Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
152// so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
153func feToBytes(s *[32]byte, h *fieldElement) {
154 var carry [10]int32
155
156 q := (19*h[9] + (1 << 24)) >> 25
157 q = (h[0] + q) >> 26
158 q = (h[1] + q) >> 25
159 q = (h[2] + q) >> 26
160 q = (h[3] + q) >> 25
161 q = (h[4] + q) >> 26
162 q = (h[5] + q) >> 25
163 q = (h[6] + q) >> 26
164 q = (h[7] + q) >> 25
165 q = (h[8] + q) >> 26
166 q = (h[9] + q) >> 25
167
168 // Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20.
169 h[0] += 19 * q
170 // Goal: Output h-2^255 q, which is between 0 and 2^255-20.
171
172 carry[0] = h[0] >> 26
173 h[1] += carry[0]
174 h[0] -= carry[0] << 26
175 carry[1] = h[1] >> 25
176 h[2] += carry[1]
177 h[1] -= carry[1] << 25
178 carry[2] = h[2] >> 26
179 h[3] += carry[2]
180 h[2] -= carry[2] << 26
181 carry[3] = h[3] >> 25
182 h[4] += carry[3]
183 h[3] -= carry[3] << 25
184 carry[4] = h[4] >> 26
185 h[5] += carry[4]
186 h[4] -= carry[4] << 26
187 carry[5] = h[5] >> 25
188 h[6] += carry[5]
189 h[5] -= carry[5] << 25
190 carry[6] = h[6] >> 26
191 h[7] += carry[6]
192 h[6] -= carry[6] << 26
193 carry[7] = h[7] >> 25
194 h[8] += carry[7]
195 h[7] -= carry[7] << 25
196 carry[8] = h[8] >> 26
197 h[9] += carry[8]
198 h[8] -= carry[8] << 26
199 carry[9] = h[9] >> 25
200 h[9] -= carry[9] << 25
201 // h10 = carry9
202
203 // Goal: Output h[0]+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
204 // Have h[0]+...+2^230 h[9] between 0 and 2^255-1;
205 // evidently 2^255 h10-2^255 q = 0.
206 // Goal: Output h[0]+...+2^230 h[9].
207
208 s[0] = byte(h[0] >> 0)
209 s[1] = byte(h[0] >> 8)
210 s[2] = byte(h[0] >> 16)
211 s[3] = byte((h[0] >> 24) | (h[1] << 2))
212 s[4] = byte(h[1] >> 6)
213 s[5] = byte(h[1] >> 14)
214 s[6] = byte((h[1] >> 22) | (h[2] << 3))
215 s[7] = byte(h[2] >> 5)
216 s[8] = byte(h[2] >> 13)
217 s[9] = byte((h[2] >> 21) | (h[3] << 5))
218 s[10] = byte(h[3] >> 3)
219 s[11] = byte(h[3] >> 11)
220 s[12] = byte((h[3] >> 19) | (h[4] << 6))
221 s[13] = byte(h[4] >> 2)
222 s[14] = byte(h[4] >> 10)
223 s[15] = byte(h[4] >> 18)
224 s[16] = byte(h[5] >> 0)
225 s[17] = byte(h[5] >> 8)
226 s[18] = byte(h[5] >> 16)
227 s[19] = byte((h[5] >> 24) | (h[6] << 1))
228 s[20] = byte(h[6] >> 7)
229 s[21] = byte(h[6] >> 15)
230 s[22] = byte((h[6] >> 23) | (h[7] << 3))
231 s[23] = byte(h[7] >> 5)
232 s[24] = byte(h[7] >> 13)
233 s[25] = byte((h[7] >> 21) | (h[8] << 4))
234 s[26] = byte(h[8] >> 4)
235 s[27] = byte(h[8] >> 12)
236 s[28] = byte((h[8] >> 20) | (h[9] << 6))
237 s[29] = byte(h[9] >> 2)
238 s[30] = byte(h[9] >> 10)
239 s[31] = byte(h[9] >> 18)
240}
241
242// feMul calculates h = f * g
243// Can overlap h with f or g.
244//
245// Preconditions:
246// |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
247// |g| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
248//
249// Postconditions:
250// |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
251//
252// Notes on implementation strategy:
253//
254// Using schoolbook multiplication.
255// Karatsuba would save a little in some cost models.
256//
257// Most multiplications by 2 and 19 are 32-bit precomputations;
258// cheaper than 64-bit postcomputations.
259//
260// There is one remaining multiplication by 19 in the carry chain;
261// one *19 precomputation can be merged into this,
262// but the resulting data flow is considerably less clean.
263//
264// There are 12 carries below.
265// 10 of them are 2-way parallelizable and vectorizable.
266// Can get away with 11 carries, but then data flow is much deeper.
267//
268// With tighter constraints on inputs can squeeze carries into int32.
269func feMul(h, f, g *fieldElement) {
270 f0 := f[0]
271 f1 := f[1]
272 f2 := f[2]
273 f3 := f[3]
274 f4 := f[4]
275 f5 := f[5]
276 f6 := f[6]
277 f7 := f[7]
278 f8 := f[8]
279 f9 := f[9]
280 g0 := g[0]
281 g1 := g[1]
282 g2 := g[2]
283 g3 := g[3]
284 g4 := g[4]
285 g5 := g[5]
286 g6 := g[6]
287 g7 := g[7]
288 g8 := g[8]
289 g9 := g[9]
290 g1_19 := 19 * g1 // 1.4*2^29
291 g2_19 := 19 * g2 // 1.4*2^30; still ok
292 g3_19 := 19 * g3
293 g4_19 := 19 * g4
294 g5_19 := 19 * g5
295 g6_19 := 19 * g6
296 g7_19 := 19 * g7
297 g8_19 := 19 * g8
298 g9_19 := 19 * g9
299 f1_2 := 2 * f1
300 f3_2 := 2 * f3
301 f5_2 := 2 * f5
302 f7_2 := 2 * f7
303 f9_2 := 2 * f9
304 f0g0 := int64(f0) * int64(g0)
305 f0g1 := int64(f0) * int64(g1)
306 f0g2 := int64(f0) * int64(g2)
307 f0g3 := int64(f0) * int64(g3)
308 f0g4 := int64(f0) * int64(g4)
309 f0g5 := int64(f0) * int64(g5)
310 f0g6 := int64(f0) * int64(g6)
311 f0g7 := int64(f0) * int64(g7)
312 f0g8 := int64(f0) * int64(g8)
313 f0g9 := int64(f0) * int64(g9)
314 f1g0 := int64(f1) * int64(g0)
315 f1g1_2 := int64(f1_2) * int64(g1)
316 f1g2 := int64(f1) * int64(g2)
317 f1g3_2 := int64(f1_2) * int64(g3)
318 f1g4 := int64(f1) * int64(g4)
319 f1g5_2 := int64(f1_2) * int64(g5)
320 f1g6 := int64(f1) * int64(g6)
321 f1g7_2 := int64(f1_2) * int64(g7)
322 f1g8 := int64(f1) * int64(g8)
323 f1g9_38 := int64(f1_2) * int64(g9_19)
324 f2g0 := int64(f2) * int64(g0)
325 f2g1 := int64(f2) * int64(g1)
326 f2g2 := int64(f2) * int64(g2)
327 f2g3 := int64(f2) * int64(g3)
328 f2g4 := int64(f2) * int64(g4)
329 f2g5 := int64(f2) * int64(g5)
330 f2g6 := int64(f2) * int64(g6)
331 f2g7 := int64(f2) * int64(g7)
332 f2g8_19 := int64(f2) * int64(g8_19)
333 f2g9_19 := int64(f2) * int64(g9_19)
334 f3g0 := int64(f3) * int64(g0)
335 f3g1_2 := int64(f3_2) * int64(g1)
336 f3g2 := int64(f3) * int64(g2)
337 f3g3_2 := int64(f3_2) * int64(g3)
338 f3g4 := int64(f3) * int64(g4)
339 f3g5_2 := int64(f3_2) * int64(g5)
340 f3g6 := int64(f3) * int64(g6)
341 f3g7_38 := int64(f3_2) * int64(g7_19)
342 f3g8_19 := int64(f3) * int64(g8_19)
343 f3g9_38 := int64(f3_2) * int64(g9_19)
344 f4g0 := int64(f4) * int64(g0)
345 f4g1 := int64(f4) * int64(g1)
346 f4g2 := int64(f4) * int64(g2)
347 f4g3 := int64(f4) * int64(g3)
348 f4g4 := int64(f4) * int64(g4)
349 f4g5 := int64(f4) * int64(g5)
350 f4g6_19 := int64(f4) * int64(g6_19)
351 f4g7_19 := int64(f4) * int64(g7_19)
352 f4g8_19 := int64(f4) * int64(g8_19)
353 f4g9_19 := int64(f4) * int64(g9_19)
354 f5g0 := int64(f5) * int64(g0)
355 f5g1_2 := int64(f5_2) * int64(g1)
356 f5g2 := int64(f5) * int64(g2)
357 f5g3_2 := int64(f5_2) * int64(g3)
358 f5g4 := int64(f5) * int64(g4)
359 f5g5_38 := int64(f5_2) * int64(g5_19)
360 f5g6_19 := int64(f5) * int64(g6_19)
361 f5g7_38 := int64(f5_2) * int64(g7_19)
362 f5g8_19 := int64(f5) * int64(g8_19)
363 f5g9_38 := int64(f5_2) * int64(g9_19)
364 f6g0 := int64(f6) * int64(g0)
365 f6g1 := int64(f6) * int64(g1)
366 f6g2 := int64(f6) * int64(g2)
367 f6g3 := int64(f6) * int64(g3)
368 f6g4_19 := int64(f6) * int64(g4_19)
369 f6g5_19 := int64(f6) * int64(g5_19)
370 f6g6_19 := int64(f6) * int64(g6_19)
371 f6g7_19 := int64(f6) * int64(g7_19)
372 f6g8_19 := int64(f6) * int64(g8_19)
373 f6g9_19 := int64(f6) * int64(g9_19)
374 f7g0 := int64(f7) * int64(g0)
375 f7g1_2 := int64(f7_2) * int64(g1)
376 f7g2 := int64(f7) * int64(g2)
377 f7g3_38 := int64(f7_2) * int64(g3_19)
378 f7g4_19 := int64(f7) * int64(g4_19)
379 f7g5_38 := int64(f7_2) * int64(g5_19)
380 f7g6_19 := int64(f7) * int64(g6_19)
381 f7g7_38 := int64(f7_2) * int64(g7_19)
382 f7g8_19 := int64(f7) * int64(g8_19)
383 f7g9_38 := int64(f7_2) * int64(g9_19)
384 f8g0 := int64(f8) * int64(g0)
385 f8g1 := int64(f8) * int64(g1)
386 f8g2_19 := int64(f8) * int64(g2_19)
387 f8g3_19 := int64(f8) * int64(g3_19)
388 f8g4_19 := int64(f8) * int64(g4_19)
389 f8g5_19 := int64(f8) * int64(g5_19)
390 f8g6_19 := int64(f8) * int64(g6_19)
391 f8g7_19 := int64(f8) * int64(g7_19)
392 f8g8_19 := int64(f8) * int64(g8_19)
393 f8g9_19 := int64(f8) * int64(g9_19)
394 f9g0 := int64(f9) * int64(g0)
395 f9g1_38 := int64(f9_2) * int64(g1_19)
396 f9g2_19 := int64(f9) * int64(g2_19)
397 f9g3_38 := int64(f9_2) * int64(g3_19)
398 f9g4_19 := int64(f9) * int64(g4_19)
399 f9g5_38 := int64(f9_2) * int64(g5_19)
400 f9g6_19 := int64(f9) * int64(g6_19)
401 f9g7_38 := int64(f9_2) * int64(g7_19)
402 f9g8_19 := int64(f9) * int64(g8_19)
403 f9g9_38 := int64(f9_2) * int64(g9_19)
404 h0 := f0g0 + f1g9_38 + f2g8_19 + f3g7_38 + f4g6_19 + f5g5_38 + f6g4_19 + f7g3_38 + f8g2_19 + f9g1_38
405 h1 := f0g1 + f1g0 + f2g9_19 + f3g8_19 + f4g7_19 + f5g6_19 + f6g5_19 + f7g4_19 + f8g3_19 + f9g2_19
406 h2 := f0g2 + f1g1_2 + f2g0 + f3g9_38 + f4g8_19 + f5g7_38 + f6g6_19 + f7g5_38 + f8g4_19 + f9g3_38
407 h3 := f0g3 + f1g2 + f2g1 + f3g0 + f4g9_19 + f5g8_19 + f6g7_19 + f7g6_19 + f8g5_19 + f9g4_19
408 h4 := f0g4 + f1g3_2 + f2g2 + f3g1_2 + f4g0 + f5g9_38 + f6g8_19 + f7g7_38 + f8g6_19 + f9g5_38
409 h5 := f0g5 + f1g4 + f2g3 + f3g2 + f4g1 + f5g0 + f6g9_19 + f7g8_19 + f8g7_19 + f9g6_19
410 h6 := f0g6 + f1g5_2 + f2g4 + f3g3_2 + f4g2 + f5g1_2 + f6g0 + f7g9_38 + f8g8_19 + f9g7_38
411 h7 := f0g7 + f1g6 + f2g5 + f3g4 + f4g3 + f5g2 + f6g1 + f7g0 + f8g9_19 + f9g8_19
412 h8 := f0g8 + f1g7_2 + f2g6 + f3g5_2 + f4g4 + f5g3_2 + f6g2 + f7g1_2 + f8g0 + f9g9_38
413 h9 := f0g9 + f1g8 + f2g7 + f3g6 + f4g5 + f5g4 + f6g3 + f7g2 + f8g1 + f9g0
414 var carry [10]int64
415
416 // |h0| <= (1.1*1.1*2^52*(1+19+19+19+19)+1.1*1.1*2^50*(38+38+38+38+38))
417 // i.e. |h0| <= 1.2*2^59; narrower ranges for h2, h4, h6, h8
418 // |h1| <= (1.1*1.1*2^51*(1+1+19+19+19+19+19+19+19+19))
419 // i.e. |h1| <= 1.5*2^58; narrower ranges for h3, h5, h7, h9
420
421 carry[0] = (h0 + (1 << 25)) >> 26
422 h1 += carry[0]
423 h0 -= carry[0] << 26
424 carry[4] = (h4 + (1 << 25)) >> 26
425 h5 += carry[4]
426 h4 -= carry[4] << 26
427 // |h0| <= 2^25
428 // |h4| <= 2^25
429 // |h1| <= 1.51*2^58
430 // |h5| <= 1.51*2^58
431
432 carry[1] = (h1 + (1 << 24)) >> 25
433 h2 += carry[1]
434 h1 -= carry[1] << 25
435 carry[5] = (h5 + (1 << 24)) >> 25
436 h6 += carry[5]
437 h5 -= carry[5] << 25
438 // |h1| <= 2^24; from now on fits into int32
439 // |h5| <= 2^24; from now on fits into int32
440 // |h2| <= 1.21*2^59
441 // |h6| <= 1.21*2^59
442
443 carry[2] = (h2 + (1 << 25)) >> 26
444 h3 += carry[2]
445 h2 -= carry[2] << 26
446 carry[6] = (h6 + (1 << 25)) >> 26
447 h7 += carry[6]
448 h6 -= carry[6] << 26
449 // |h2| <= 2^25; from now on fits into int32 unchanged
450 // |h6| <= 2^25; from now on fits into int32 unchanged
451 // |h3| <= 1.51*2^58
452 // |h7| <= 1.51*2^58
453
454 carry[3] = (h3 + (1 << 24)) >> 25
455 h4 += carry[3]
456 h3 -= carry[3] << 25
457 carry[7] = (h7 + (1 << 24)) >> 25
458 h8 += carry[7]
459 h7 -= carry[7] << 25
460 // |h3| <= 2^24; from now on fits into int32 unchanged
461 // |h7| <= 2^24; from now on fits into int32 unchanged
462 // |h4| <= 1.52*2^33
463 // |h8| <= 1.52*2^33
464
465 carry[4] = (h4 + (1 << 25)) >> 26
466 h5 += carry[4]
467 h4 -= carry[4] << 26
468 carry[8] = (h8 + (1 << 25)) >> 26
469 h9 += carry[8]
470 h8 -= carry[8] << 26
471 // |h4| <= 2^25; from now on fits into int32 unchanged
472 // |h8| <= 2^25; from now on fits into int32 unchanged
473 // |h5| <= 1.01*2^24
474 // |h9| <= 1.51*2^58
475
476 carry[9] = (h9 + (1 << 24)) >> 25
477 h0 += carry[9] * 19
478 h9 -= carry[9] << 25
479 // |h9| <= 2^24; from now on fits into int32 unchanged
480 // |h0| <= 1.8*2^37
481
482 carry[0] = (h0 + (1 << 25)) >> 26
483 h1 += carry[0]
484 h0 -= carry[0] << 26
485 // |h0| <= 2^25; from now on fits into int32 unchanged
486 // |h1| <= 1.01*2^24
487
488 h[0] = int32(h0)
489 h[1] = int32(h1)
490 h[2] = int32(h2)
491 h[3] = int32(h3)
492 h[4] = int32(h4)
493 h[5] = int32(h5)
494 h[6] = int32(h6)
495 h[7] = int32(h7)
496 h[8] = int32(h8)
497 h[9] = int32(h9)
498}
499
500// feSquare calculates h = f*f. Can overlap h with f.
501//
502// Preconditions:
503// |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
504//
505// Postconditions:
506// |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
507func feSquare(h, f *fieldElement) {
508 f0 := f[0]
509 f1 := f[1]
510 f2 := f[2]
511 f3 := f[3]
512 f4 := f[4]
513 f5 := f[5]
514 f6 := f[6]
515 f7 := f[7]
516 f8 := f[8]
517 f9 := f[9]
518 f0_2 := 2 * f0
519 f1_2 := 2 * f1
520 f2_2 := 2 * f2
521 f3_2 := 2 * f3
522 f4_2 := 2 * f4
523 f5_2 := 2 * f5
524 f6_2 := 2 * f6
525 f7_2 := 2 * f7
526 f5_38 := 38 * f5 // 1.31*2^30
527 f6_19 := 19 * f6 // 1.31*2^30
528 f7_38 := 38 * f7 // 1.31*2^30
529 f8_19 := 19 * f8 // 1.31*2^30
530 f9_38 := 38 * f9 // 1.31*2^30
531 f0f0 := int64(f0) * int64(f0)
532 f0f1_2 := int64(f0_2) * int64(f1)
533 f0f2_2 := int64(f0_2) * int64(f2)
534 f0f3_2 := int64(f0_2) * int64(f3)
535 f0f4_2 := int64(f0_2) * int64(f4)
536 f0f5_2 := int64(f0_2) * int64(f5)
537 f0f6_2 := int64(f0_2) * int64(f6)
538 f0f7_2 := int64(f0_2) * int64(f7)
539 f0f8_2 := int64(f0_2) * int64(f8)
540 f0f9_2 := int64(f0_2) * int64(f9)
541 f1f1_2 := int64(f1_2) * int64(f1)
542 f1f2_2 := int64(f1_2) * int64(f2)
543 f1f3_4 := int64(f1_2) * int64(f3_2)
544 f1f4_2 := int64(f1_2) * int64(f4)
545 f1f5_4 := int64(f1_2) * int64(f5_2)
546 f1f6_2 := int64(f1_2) * int64(f6)
547 f1f7_4 := int64(f1_2) * int64(f7_2)
548 f1f8_2 := int64(f1_2) * int64(f8)
549 f1f9_76 := int64(f1_2) * int64(f9_38)
550 f2f2 := int64(f2) * int64(f2)
551 f2f3_2 := int64(f2_2) * int64(f3)
552 f2f4_2 := int64(f2_2) * int64(f4)
553 f2f5_2 := int64(f2_2) * int64(f5)
554 f2f6_2 := int64(f2_2) * int64(f6)
555 f2f7_2 := int64(f2_2) * int64(f7)
556 f2f8_38 := int64(f2_2) * int64(f8_19)
557 f2f9_38 := int64(f2) * int64(f9_38)
558 f3f3_2 := int64(f3_2) * int64(f3)
559 f3f4_2 := int64(f3_2) * int64(f4)
560 f3f5_4 := int64(f3_2) * int64(f5_2)
561 f3f6_2 := int64(f3_2) * int64(f6)
562 f3f7_76 := int64(f3_2) * int64(f7_38)
563 f3f8_38 := int64(f3_2) * int64(f8_19)
564 f3f9_76 := int64(f3_2) * int64(f9_38)
565 f4f4 := int64(f4) * int64(f4)
566 f4f5_2 := int64(f4_2) * int64(f5)
567 f4f6_38 := int64(f4_2) * int64(f6_19)
568 f4f7_38 := int64(f4) * int64(f7_38)
569 f4f8_38 := int64(f4_2) * int64(f8_19)
570 f4f9_38 := int64(f4) * int64(f9_38)
571 f5f5_38 := int64(f5) * int64(f5_38)
572 f5f6_38 := int64(f5_2) * int64(f6_19)
573 f5f7_76 := int64(f5_2) * int64(f7_38)
574 f5f8_38 := int64(f5_2) * int64(f8_19)
575 f5f9_76 := int64(f5_2) * int64(f9_38)
576 f6f6_19 := int64(f6) * int64(f6_19)
577 f6f7_38 := int64(f6) * int64(f7_38)
578 f6f8_38 := int64(f6_2) * int64(f8_19)
579 f6f9_38 := int64(f6) * int64(f9_38)
580 f7f7_38 := int64(f7) * int64(f7_38)
581 f7f8_38 := int64(f7_2) * int64(f8_19)
582 f7f9_76 := int64(f7_2) * int64(f9_38)
583 f8f8_19 := int64(f8) * int64(f8_19)
584 f8f9_38 := int64(f8) * int64(f9_38)
585 f9f9_38 := int64(f9) * int64(f9_38)
586 h0 := f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38
587 h1 := f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38
588 h2 := f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19
589 h3 := f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38
590 h4 := f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38
591 h5 := f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38
592 h6 := f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19
593 h7 := f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38
594 h8 := f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38
595 h9 := f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2
596 var carry [10]int64
597
598 carry[0] = (h0 + (1 << 25)) >> 26
599 h1 += carry[0]
600 h0 -= carry[0] << 26
601 carry[4] = (h4 + (1 << 25)) >> 26
602 h5 += carry[4]
603 h4 -= carry[4] << 26
604
605 carry[1] = (h1 + (1 << 24)) >> 25
606 h2 += carry[1]
607 h1 -= carry[1] << 25
608 carry[5] = (h5 + (1 << 24)) >> 25
609 h6 += carry[5]
610 h5 -= carry[5] << 25
611
612 carry[2] = (h2 + (1 << 25)) >> 26
613 h3 += carry[2]
614 h2 -= carry[2] << 26
615 carry[6] = (h6 + (1 << 25)) >> 26
616 h7 += carry[6]
617 h6 -= carry[6] << 26
618
619 carry[3] = (h3 + (1 << 24)) >> 25
620 h4 += carry[3]
621 h3 -= carry[3] << 25
622 carry[7] = (h7 + (1 << 24)) >> 25
623 h8 += carry[7]
624 h7 -= carry[7] << 25
625
626 carry[4] = (h4 + (1 << 25)) >> 26
627 h5 += carry[4]
628 h4 -= carry[4] << 26
629 carry[8] = (h8 + (1 << 25)) >> 26
630 h9 += carry[8]
631 h8 -= carry[8] << 26
632
633 carry[9] = (h9 + (1 << 24)) >> 25
634 h0 += carry[9] * 19
635 h9 -= carry[9] << 25
636
637 carry[0] = (h0 + (1 << 25)) >> 26
638 h1 += carry[0]
639 h0 -= carry[0] << 26
640
641 h[0] = int32(h0)
642 h[1] = int32(h1)
643 h[2] = int32(h2)
644 h[3] = int32(h3)
645 h[4] = int32(h4)
646 h[5] = int32(h5)
647 h[6] = int32(h6)
648 h[7] = int32(h7)
649 h[8] = int32(h8)
650 h[9] = int32(h9)
651}
652
653// feMul121666 calculates h = f * 121666. Can overlap h with f.
654//
655// Preconditions:
656// |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
657//
658// Postconditions:
659// |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
660func feMul121666(h, f *fieldElement) {
661 h0 := int64(f[0]) * 121666
662 h1 := int64(f[1]) * 121666
663 h2 := int64(f[2]) * 121666
664 h3 := int64(f[3]) * 121666
665 h4 := int64(f[4]) * 121666
666 h5 := int64(f[5]) * 121666
667 h6 := int64(f[6]) * 121666
668 h7 := int64(f[7]) * 121666
669 h8 := int64(f[8]) * 121666
670 h9 := int64(f[9]) * 121666
671 var carry [10]int64
672
673 carry[9] = (h9 + (1 << 24)) >> 25
674 h0 += carry[9] * 19
675 h9 -= carry[9] << 25
676 carry[1] = (h1 + (1 << 24)) >> 25
677 h2 += carry[1]
678 h1 -= carry[1] << 25
679 carry[3] = (h3 + (1 << 24)) >> 25
680 h4 += carry[3]
681 h3 -= carry[3] << 25
682 carry[5] = (h5 + (1 << 24)) >> 25
683 h6 += carry[5]
684 h5 -= carry[5] << 25
685 carry[7] = (h7 + (1 << 24)) >> 25
686 h8 += carry[7]
687 h7 -= carry[7] << 25
688
689 carry[0] = (h0 + (1 << 25)) >> 26
690 h1 += carry[0]
691 h0 -= carry[0] << 26
692 carry[2] = (h2 + (1 << 25)) >> 26
693 h3 += carry[2]
694 h2 -= carry[2] << 26
695 carry[4] = (h4 + (1 << 25)) >> 26
696 h5 += carry[4]
697 h4 -= carry[4] << 26
698 carry[6] = (h6 + (1 << 25)) >> 26
699 h7 += carry[6]
700 h6 -= carry[6] << 26
701 carry[8] = (h8 + (1 << 25)) >> 26
702 h9 += carry[8]
703 h8 -= carry[8] << 26
704
705 h[0] = int32(h0)
706 h[1] = int32(h1)
707 h[2] = int32(h2)
708 h[3] = int32(h3)
709 h[4] = int32(h4)
710 h[5] = int32(h5)
711 h[6] = int32(h6)
712 h[7] = int32(h7)
713 h[8] = int32(h8)
714 h[9] = int32(h9)
715}
716
717// feInvert sets out = z^-1.
718func feInvert(out, z *fieldElement) {
719 var t0, t1, t2, t3 fieldElement
720 var i int
721
722 feSquare(&t0, z)
723 for i = 1; i < 1; i++ {
724 feSquare(&t0, &t0)
725 }
726 feSquare(&t1, &t0)
727 for i = 1; i < 2; i++ {
728 feSquare(&t1, &t1)
729 }
730 feMul(&t1, z, &t1)
731 feMul(&t0, &t0, &t1)
732 feSquare(&t2, &t0)
733 for i = 1; i < 1; i++ {
734 feSquare(&t2, &t2)
735 }
736 feMul(&t1, &t1, &t2)
737 feSquare(&t2, &t1)
738 for i = 1; i < 5; i++ {
739 feSquare(&t2, &t2)
740 }
741 feMul(&t1, &t2, &t1)
742 feSquare(&t2, &t1)
743 for i = 1; i < 10; i++ {
744 feSquare(&t2, &t2)
745 }
746 feMul(&t2, &t2, &t1)
747 feSquare(&t3, &t2)
748 for i = 1; i < 20; i++ {
749 feSquare(&t3, &t3)
750 }
751 feMul(&t2, &t3, &t2)
752 feSquare(&t2, &t2)
753 for i = 1; i < 10; i++ {
754 feSquare(&t2, &t2)
755 }
756 feMul(&t1, &t2, &t1)
757 feSquare(&t2, &t1)
758 for i = 1; i < 50; i++ {
759 feSquare(&t2, &t2)
760 }
761 feMul(&t2, &t2, &t1)
762 feSquare(&t3, &t2)
763 for i = 1; i < 100; i++ {
764 feSquare(&t3, &t3)
765 }
766 feMul(&t2, &t3, &t2)
767 feSquare(&t2, &t2)
768 for i = 1; i < 50; i++ {
769 feSquare(&t2, &t2)
770 }
771 feMul(&t1, &t2, &t1)
772 feSquare(&t1, &t1)
773 for i = 1; i < 5; i++ {
774 feSquare(&t1, &t1)
775 }
776 feMul(out, &t1, &t0)
777}
778
779func scalarMultGeneric(out, in, base *[32]byte) {
780 var e [32]byte
781
782 copy(e[:], in[:])
783 e[0] &= 248
784 e[31] &= 127
785 e[31] |= 64
786
787 var x1, x2, z2, x3, z3, tmp0, tmp1 fieldElement
788 feFromBytes(&x1, base)
789 feOne(&x2)
790 feCopy(&x3, &x1)
791 feOne(&z3)
792
793 swap := int32(0)
794 for pos := 254; pos >= 0; pos-- {
795 b := e[pos/8] >> uint(pos&7)
796 b &= 1
797 swap ^= int32(b)
798 feCSwap(&x2, &x3, swap)
799 feCSwap(&z2, &z3, swap)
800 swap = int32(b)
801
802 feSub(&tmp0, &x3, &z3)
803 feSub(&tmp1, &x2, &z2)
804 feAdd(&x2, &x2, &z2)
805 feAdd(&z2, &x3, &z3)
806 feMul(&z3, &tmp0, &x2)
807 feMul(&z2, &z2, &tmp1)
808 feSquare(&tmp0, &tmp1)
809 feSquare(&tmp1, &x2)
810 feAdd(&x3, &z3, &z2)
811 feSub(&z2, &z3, &z2)
812 feMul(&x2, &tmp1, &tmp0)
813 feSub(&tmp1, &tmp1, &tmp0)
814 feSquare(&z2, &z2)
815 feMul121666(&z3, &tmp1)
816 feSquare(&x3, &x3)
817 feAdd(&tmp0, &tmp0, &z3)
818 feMul(&z3, &x1, &z2)
819 feMul(&z2, &tmp1, &tmp0)
820 }
821
822 feCSwap(&x2, &x3, swap)
823 feCSwap(&z2, &z3, swap)
824
825 feInvert(&z2, &z2)
826 feMul(&x2, &x2, &z2)
827 feToBytes(out, &x2)
828}