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