diff options
author | Jake Champlin <jake@gnu.space> | 2017-06-09 17:54:32 +0000 |
---|---|---|
committer | Jake Champlin <jake@gnu.space> | 2017-06-09 17:54:32 +0000 |
commit | 9b12e4fe6f3c95986f1f3ec791636c58ca7e7583 (patch) | |
tree | 38f5f12bec0e488a12f0459a7356e6b7de7d8f84 /vendor/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go | |
parent | cec3de8a3bcaffd21dedd1bf42da4b490cae7e16 (diff) | |
download | terraform-provider-statuscake-9b12e4fe6f3c95986f1f3ec791636c58ca7e7583.tar.gz terraform-provider-statuscake-9b12e4fe6f3c95986f1f3ec791636c58ca7e7583.tar.zst terraform-provider-statuscake-9b12e4fe6f3c95986f1f3ec791636c58ca7e7583.zip |
Transfer of provider code
Diffstat (limited to 'vendor/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go')
-rw-r--r-- | vendor/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go | 1771 |
1 files changed, 0 insertions, 1771 deletions
diff --git a/vendor/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go b/vendor/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go deleted file mode 100644 index 5f8b994..0000000 --- a/vendor/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go +++ /dev/null | |||
@@ -1,1771 +0,0 @@ | |||
1 | // Copyright 2016 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 | package edwards25519 | ||
6 | |||
7 | // This code is a port of the public domain, “ref10” implementation of ed25519 | ||
8 | // from SUPERCOP. | ||
9 | |||
10 | // FieldElement represents an element of the field GF(2^255 - 19). An element | ||
11 | // t, entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77 | ||
12 | // t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on | ||
13 | // context. | ||
14 | type FieldElement [10]int32 | ||
15 | |||
16 | var zero FieldElement | ||
17 | |||
18 | func FeZero(fe *FieldElement) { | ||
19 | copy(fe[:], zero[:]) | ||
20 | } | ||
21 | |||
22 | func FeOne(fe *FieldElement) { | ||
23 | FeZero(fe) | ||
24 | fe[0] = 1 | ||
25 | } | ||
26 | |||
27 | func FeAdd(dst, a, b *FieldElement) { | ||
28 | dst[0] = a[0] + b[0] | ||
29 | dst[1] = a[1] + b[1] | ||
30 | dst[2] = a[2] + b[2] | ||
31 | dst[3] = a[3] + b[3] | ||
32 | dst[4] = a[4] + b[4] | ||
33 | dst[5] = a[5] + b[5] | ||
34 | dst[6] = a[6] + b[6] | ||
35 | dst[7] = a[7] + b[7] | ||
36 | dst[8] = a[8] + b[8] | ||
37 | dst[9] = a[9] + b[9] | ||
38 | } | ||
39 | |||
40 | func FeSub(dst, a, b *FieldElement) { | ||
41 | dst[0] = a[0] - b[0] | ||
42 | dst[1] = a[1] - b[1] | ||
43 | dst[2] = a[2] - b[2] | ||
44 | dst[3] = a[3] - b[3] | ||
45 | dst[4] = a[4] - b[4] | ||
46 | dst[5] = a[5] - b[5] | ||
47 | dst[6] = a[6] - b[6] | ||
48 | dst[7] = a[7] - b[7] | ||
49 | dst[8] = a[8] - b[8] | ||
50 | dst[9] = a[9] - b[9] | ||
51 | } | ||
52 | |||
53 | func FeCopy(dst, src *FieldElement) { | ||
54 | copy(dst[:], src[:]) | ||
55 | } | ||
56 | |||
57 | // Replace (f,g) with (g,g) if b == 1; | ||
58 | // replace (f,g) with (f,g) if b == 0. | ||
59 | // | ||
60 | // Preconditions: b in {0,1}. | ||
61 | func FeCMove(f, g *FieldElement, b int32) { | ||
62 | b = -b | ||
63 | f[0] ^= b & (f[0] ^ g[0]) | ||
64 | f[1] ^= b & (f[1] ^ g[1]) | ||
65 | f[2] ^= b & (f[2] ^ g[2]) | ||
66 | f[3] ^= b & (f[3] ^ g[3]) | ||
67 | f[4] ^= b & (f[4] ^ g[4]) | ||
68 | f[5] ^= b & (f[5] ^ g[5]) | ||
69 | f[6] ^= b & (f[6] ^ g[6]) | ||
70 | f[7] ^= b & (f[7] ^ g[7]) | ||
71 | f[8] ^= b & (f[8] ^ g[8]) | ||
72 | f[9] ^= b & (f[9] ^ g[9]) | ||
73 | } | ||
74 | |||
75 | func load3(in []byte) int64 { | ||
76 | var r int64 | ||
77 | r = int64(in[0]) | ||
78 | r |= int64(in[1]) << 8 | ||
79 | r |= int64(in[2]) << 16 | ||
80 | return r | ||
81 | } | ||
82 | |||
83 | func load4(in []byte) int64 { | ||
84 | var r int64 | ||
85 | r = int64(in[0]) | ||
86 | r |= int64(in[1]) << 8 | ||
87 | r |= int64(in[2]) << 16 | ||
88 | r |= int64(in[3]) << 24 | ||
89 | return r | ||
90 | } | ||
91 | |||
92 | func FeFromBytes(dst *FieldElement, src *[32]byte) { | ||
93 | h0 := load4(src[:]) | ||
94 | h1 := load3(src[4:]) << 6 | ||
95 | h2 := load3(src[7:]) << 5 | ||
96 | h3 := load3(src[10:]) << 3 | ||
97 | h4 := load3(src[13:]) << 2 | ||
98 | h5 := load4(src[16:]) | ||
99 | h6 := load3(src[20:]) << 7 | ||
100 | h7 := load3(src[23:]) << 5 | ||
101 | h8 := load3(src[26:]) << 4 | ||
102 | h9 := (load3(src[29:]) & 8388607) << 2 | ||
103 | |||
104 | FeCombine(dst, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9) | ||
105 | } | ||
106 | |||
107 | // FeToBytes marshals h to s. | ||
108 | // Preconditions: | ||
109 | // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. | ||
110 | // | ||
111 | // Write p=2^255-19; q=floor(h/p). | ||
112 | // Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))). | ||
113 | // | ||
114 | // Proof: | ||
115 | // Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4. | ||
116 | // Also have |h-2^230 h9|<2^230 so |19 2^(-255)(h-2^230 h9)|<1/4. | ||
117 | // | ||
118 | // Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9). | ||
119 | // Then 0<y<1. | ||
120 | // | ||
121 | // Write r=h-pq. | ||
122 | // Have 0<=r<=p-1=2^255-20. | ||
123 | // Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1. | ||
124 | // | ||
125 | // Write x=r+19(2^-255)r+y. | ||
126 | // Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q. | ||
127 | // | ||
128 | // Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1)) | ||
129 | // so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q. | ||
130 | func FeToBytes(s *[32]byte, h *FieldElement) { | ||
131 | var carry [10]int32 | ||
132 | |||
133 | q := (19*h[9] + (1 << 24)) >> 25 | ||
134 | q = (h[0] + q) >> 26 | ||
135 | q = (h[1] + q) >> 25 | ||
136 | q = (h[2] + q) >> 26 | ||
137 | q = (h[3] + q) >> 25 | ||
138 | q = (h[4] + q) >> 26 | ||
139 | q = (h[5] + q) >> 25 | ||
140 | q = (h[6] + q) >> 26 | ||
141 | q = (h[7] + q) >> 25 | ||
142 | q = (h[8] + q) >> 26 | ||
143 | q = (h[9] + q) >> 25 | ||
144 | |||
145 | // Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. | ||
146 | h[0] += 19 * q | ||
147 | // Goal: Output h-2^255 q, which is between 0 and 2^255-20. | ||
148 | |||
149 | carry[0] = h[0] >> 26 | ||
150 | h[1] += carry[0] | ||
151 | h[0] -= carry[0] << 26 | ||
152 | carry[1] = h[1] >> 25 | ||
153 | h[2] += carry[1] | ||
154 | h[1] -= carry[1] << 25 | ||
155 | carry[2] = h[2] >> 26 | ||
156 | h[3] += carry[2] | ||
157 | h[2] -= carry[2] << 26 | ||
158 | carry[3] = h[3] >> 25 | ||
159 | h[4] += carry[3] | ||
160 | h[3] -= carry[3] << 25 | ||
161 | carry[4] = h[4] >> 26 | ||
162 | h[5] += carry[4] | ||
163 | h[4] -= carry[4] << 26 | ||
164 | carry[5] = h[5] >> 25 | ||
165 | h[6] += carry[5] | ||
166 | h[5] -= carry[5] << 25 | ||
167 | carry[6] = h[6] >> 26 | ||
168 | h[7] += carry[6] | ||
169 | h[6] -= carry[6] << 26 | ||
170 | carry[7] = h[7] >> 25 | ||
171 | h[8] += carry[7] | ||
172 | h[7] -= carry[7] << 25 | ||
173 | carry[8] = h[8] >> 26 | ||
174 | h[9] += carry[8] | ||
175 | h[8] -= carry[8] << 26 | ||
176 | carry[9] = h[9] >> 25 | ||
177 | h[9] -= carry[9] << 25 | ||
178 | // h10 = carry9 | ||
179 | |||
180 | // Goal: Output h[0]+...+2^255 h10-2^255 q, which is between 0 and 2^255-20. | ||
181 | // Have h[0]+...+2^230 h[9] between 0 and 2^255-1; | ||
182 | // evidently 2^255 h10-2^255 q = 0. | ||
183 | // Goal: Output h[0]+...+2^230 h[9]. | ||
184 | |||
185 | s[0] = byte(h[0] >> 0) | ||
186 | s[1] = byte(h[0] >> 8) | ||
187 | s[2] = byte(h[0] >> 16) | ||
188 | s[3] = byte((h[0] >> 24) | (h[1] << 2)) | ||
189 | s[4] = byte(h[1] >> 6) | ||
190 | s[5] = byte(h[1] >> 14) | ||
191 | s[6] = byte((h[1] >> 22) | (h[2] << 3)) | ||
192 | s[7] = byte(h[2] >> 5) | ||
193 | s[8] = byte(h[2] >> 13) | ||
194 | s[9] = byte((h[2] >> 21) | (h[3] << 5)) | ||
195 | s[10] = byte(h[3] >> 3) | ||
196 | s[11] = byte(h[3] >> 11) | ||
197 | s[12] = byte((h[3] >> 19) | (h[4] << 6)) | ||
198 | s[13] = byte(h[4] >> 2) | ||
199 | s[14] = byte(h[4] >> 10) | ||
200 | s[15] = byte(h[4] >> 18) | ||
201 | s[16] = byte(h[5] >> 0) | ||
202 | s[17] = byte(h[5] >> 8) | ||
203 | s[18] = byte(h[5] >> 16) | ||
204 | s[19] = byte((h[5] >> 24) | (h[6] << 1)) | ||
205 | s[20] = byte(h[6] >> 7) | ||
206 | s[21] = byte(h[6] >> 15) | ||
207 | s[22] = byte((h[6] >> 23) | (h[7] << 3)) | ||
208 | s[23] = byte(h[7] >> 5) | ||
209 | s[24] = byte(h[7] >> 13) | ||
210 | s[25] = byte((h[7] >> 21) | (h[8] << 4)) | ||
211 | s[26] = byte(h[8] >> 4) | ||
212 | s[27] = byte(h[8] >> 12) | ||
213 | s[28] = byte((h[8] >> 20) | (h[9] << 6)) | ||
214 | s[29] = byte(h[9] >> 2) | ||
215 | s[30] = byte(h[9] >> 10) | ||
216 | s[31] = byte(h[9] >> 18) | ||
217 | } | ||
218 | |||
219 | func FeIsNegative(f *FieldElement) byte { | ||
220 | var s [32]byte | ||
221 | FeToBytes(&s, f) | ||
222 | return s[0] & 1 | ||
223 | } | ||
224 | |||
225 | func FeIsNonZero(f *FieldElement) int32 { | ||
226 | var s [32]byte | ||
227 | FeToBytes(&s, f) | ||
228 | var x uint8 | ||
229 | for _, b := range s { | ||
230 | x |= b | ||
231 | } | ||
232 | x |= x >> 4 | ||
233 | x |= x >> 2 | ||
234 | x |= x >> 1 | ||
235 | return int32(x & 1) | ||
236 | } | ||
237 | |||
238 | // FeNeg sets h = -f | ||
239 | // | ||
240 | // Preconditions: | ||
241 | // |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. | ||
242 | // | ||
243 | // Postconditions: | ||
244 | // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. | ||
245 | func FeNeg(h, f *FieldElement) { | ||
246 | h[0] = -f[0] | ||
247 | h[1] = -f[1] | ||
248 | h[2] = -f[2] | ||
249 | h[3] = -f[3] | ||
250 | h[4] = -f[4] | ||
251 | h[5] = -f[5] | ||
252 | h[6] = -f[6] | ||
253 | h[7] = -f[7] | ||
254 | h[8] = -f[8] | ||
255 | h[9] = -f[9] | ||
256 | } | ||
257 | |||
258 | func FeCombine(h *FieldElement, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64) { | ||
259 | var c0, c1, c2, c3, c4, c5, c6, c7, c8, c9 int64 | ||
260 | |||
261 | /* | ||
262 | |h0| <= (1.1*1.1*2^52*(1+19+19+19+19)+1.1*1.1*2^50*(38+38+38+38+38)) | ||
263 | i.e. |h0| <= 1.2*2^59; narrower ranges for h2, h4, h6, h8 | ||
264 | |h1| <= (1.1*1.1*2^51*(1+1+19+19+19+19+19+19+19+19)) | ||
265 | i.e. |h1| <= 1.5*2^58; narrower ranges for h3, h5, h7, h9 | ||
266 | */ | ||
267 | |||
268 | c0 = (h0 + (1 << 25)) >> 26 | ||
269 | h1 += c0 | ||
270 | h0 -= c0 << 26 | ||
271 | c4 = (h4 + (1 << 25)) >> 26 | ||
272 | h5 += c4 | ||
273 | h4 -= c4 << 26 | ||
274 | /* |h0| <= 2^25 */ | ||
275 | /* |h4| <= 2^25 */ | ||
276 | /* |h1| <= 1.51*2^58 */ | ||
277 | /* |h5| <= 1.51*2^58 */ | ||
278 | |||
279 | c1 = (h1 + (1 << 24)) >> 25 | ||
280 | h2 += c1 | ||
281 | h1 -= c1 << 25 | ||
282 | c5 = (h5 + (1 << 24)) >> 25 | ||
283 | h6 += c5 | ||
284 | h5 -= c5 << 25 | ||
285 | /* |h1| <= 2^24; from now on fits into int32 */ | ||
286 | /* |h5| <= 2^24; from now on fits into int32 */ | ||
287 | /* |h2| <= 1.21*2^59 */ | ||
288 | /* |h6| <= 1.21*2^59 */ | ||
289 | |||
290 | c2 = (h2 + (1 << 25)) >> 26 | ||
291 | h3 += c2 | ||
292 | h2 -= c2 << 26 | ||
293 | c6 = (h6 + (1 << 25)) >> 26 | ||
294 | h7 += c6 | ||
295 | h6 -= c6 << 26 | ||
296 | /* |h2| <= 2^25; from now on fits into int32 unchanged */ | ||
297 | /* |h6| <= 2^25; from now on fits into int32 unchanged */ | ||
298 | /* |h3| <= 1.51*2^58 */ | ||
299 | /* |h7| <= 1.51*2^58 */ | ||
300 | |||
301 | c3 = (h3 + (1 << 24)) >> 25 | ||
302 | h4 += c3 | ||
303 | h3 -= c3 << 25 | ||
304 | c7 = (h7 + (1 << 24)) >> 25 | ||
305 | h8 += c7 | ||
306 | h7 -= c7 << 25 | ||
307 | /* |h3| <= 2^24; from now on fits into int32 unchanged */ | ||
308 | /* |h7| <= 2^24; from now on fits into int32 unchanged */ | ||
309 | /* |h4| <= 1.52*2^33 */ | ||
310 | /* |h8| <= 1.52*2^33 */ | ||
311 | |||
312 | c4 = (h4 + (1 << 25)) >> 26 | ||
313 | h5 += c4 | ||
314 | h4 -= c4 << 26 | ||
315 | c8 = (h8 + (1 << 25)) >> 26 | ||
316 | h9 += c8 | ||
317 | h8 -= c8 << 26 | ||
318 | /* |h4| <= 2^25; from now on fits into int32 unchanged */ | ||
319 | /* |h8| <= 2^25; from now on fits into int32 unchanged */ | ||
320 | /* |h5| <= 1.01*2^24 */ | ||
321 | /* |h9| <= 1.51*2^58 */ | ||
322 | |||
323 | c9 = (h9 + (1 << 24)) >> 25 | ||
324 | h0 += c9 * 19 | ||
325 | h9 -= c9 << 25 | ||
326 | /* |h9| <= 2^24; from now on fits into int32 unchanged */ | ||
327 | /* |h0| <= 1.8*2^37 */ | ||
328 | |||
329 | c0 = (h0 + (1 << 25)) >> 26 | ||
330 | h1 += c0 | ||
331 | h0 -= c0 << 26 | ||
332 | /* |h0| <= 2^25; from now on fits into int32 unchanged */ | ||
333 | /* |h1| <= 1.01*2^24 */ | ||
334 | |||
335 | h[0] = int32(h0) | ||
336 | h[1] = int32(h1) | ||
337 | h[2] = int32(h2) | ||
338 | h[3] = int32(h3) | ||
339 | h[4] = int32(h4) | ||
340 | h[5] = int32(h5) | ||
341 | h[6] = int32(h6) | ||
342 | h[7] = int32(h7) | ||
343 | h[8] = int32(h8) | ||
344 | h[9] = int32(h9) | ||
345 | } | ||
346 | |||
347 | // FeMul calculates h = f * g | ||
348 | // Can overlap h with f or g. | ||
349 | // | ||
350 | // Preconditions: | ||
351 | // |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. | ||
352 | // |g| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. | ||
353 | // | ||
354 | // Postconditions: | ||
355 | // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. | ||
356 | // | ||
357 | // Notes on implementation strategy: | ||
358 | // | ||
359 | // Using schoolbook multiplication. | ||
360 | // Karatsuba would save a little in some cost models. | ||
361 | // | ||
362 | // Most multiplications by 2 and 19 are 32-bit precomputations; | ||
363 | // cheaper than 64-bit postcomputations. | ||
364 | // | ||
365 | // There is one remaining multiplication by 19 in the carry chain; | ||
366 | // one *19 precomputation can be merged into this, | ||
367 | // but the resulting data flow is considerably less clean. | ||
368 | // | ||
369 | // There are 12 carries below. | ||
370 | // 10 of them are 2-way parallelizable and vectorizable. | ||
371 | // Can get away with 11 carries, but then data flow is much deeper. | ||
372 | // | ||
373 | // With tighter constraints on inputs, can squeeze carries into int32. | ||
374 | func FeMul(h, f, g *FieldElement) { | ||
375 | f0 := int64(f[0]) | ||
376 | f1 := int64(f[1]) | ||
377 | f2 := int64(f[2]) | ||
378 | f3 := int64(f[3]) | ||
379 | f4 := int64(f[4]) | ||
380 | f5 := int64(f[5]) | ||
381 | f6 := int64(f[6]) | ||
382 | f7 := int64(f[7]) | ||
383 | f8 := int64(f[8]) | ||
384 | f9 := int64(f[9]) | ||
385 | |||
386 | f1_2 := int64(2 * f[1]) | ||
387 | f3_2 := int64(2 * f[3]) | ||
388 | f5_2 := int64(2 * f[5]) | ||
389 | f7_2 := int64(2 * f[7]) | ||
390 | f9_2 := int64(2 * f[9]) | ||
391 | |||
392 | g0 := int64(g[0]) | ||
393 | g1 := int64(g[1]) | ||
394 | g2 := int64(g[2]) | ||
395 | g3 := int64(g[3]) | ||
396 | g4 := int64(g[4]) | ||
397 | g5 := int64(g[5]) | ||
398 | g6 := int64(g[6]) | ||
399 | g7 := int64(g[7]) | ||
400 | g8 := int64(g[8]) | ||
401 | g9 := int64(g[9]) | ||
402 | |||
403 | g1_19 := int64(19 * g[1]) /* 1.4*2^29 */ | ||
404 | g2_19 := int64(19 * g[2]) /* 1.4*2^30; still ok */ | ||
405 | g3_19 := int64(19 * g[3]) | ||
406 | g4_19 := int64(19 * g[4]) | ||
407 | g5_19 := int64(19 * g[5]) | ||
408 | g6_19 := int64(19 * g[6]) | ||
409 | g7_19 := int64(19 * g[7]) | ||
410 | g8_19 := int64(19 * g[8]) | ||
411 | g9_19 := int64(19 * g[9]) | ||
412 | |||
413 | h0 := f0*g0 + f1_2*g9_19 + f2*g8_19 + f3_2*g7_19 + f4*g6_19 + f5_2*g5_19 + f6*g4_19 + f7_2*g3_19 + f8*g2_19 + f9_2*g1_19 | ||
414 | h1 := f0*g1 + f1*g0 + f2*g9_19 + f3*g8_19 + f4*g7_19 + f5*g6_19 + f6*g5_19 + f7*g4_19 + f8*g3_19 + f9*g2_19 | ||
415 | h2 := f0*g2 + f1_2*g1 + f2*g0 + f3_2*g9_19 + f4*g8_19 + f5_2*g7_19 + f6*g6_19 + f7_2*g5_19 + f8*g4_19 + f9_2*g3_19 | ||
416 | h3 := f0*g3 + f1*g2 + f2*g1 + f3*g0 + f4*g9_19 + f5*g8_19 + f6*g7_19 + f7*g6_19 + f8*g5_19 + f9*g4_19 | ||
417 | h4 := f0*g4 + f1_2*g3 + f2*g2 + f3_2*g1 + f4*g0 + f5_2*g9_19 + f6*g8_19 + f7_2*g7_19 + f8*g6_19 + f9_2*g5_19 | ||
418 | h5 := f0*g5 + f1*g4 + f2*g3 + f3*g2 + f4*g1 + f5*g0 + f6*g9_19 + f7*g8_19 + f8*g7_19 + f9*g6_19 | ||
419 | h6 := f0*g6 + f1_2*g5 + f2*g4 + f3_2*g3 + f4*g2 + f5_2*g1 + f6*g0 + f7_2*g9_19 + f8*g8_19 + f9_2*g7_19 | ||
420 | h7 := f0*g7 + f1*g6 + f2*g5 + f3*g4 + f4*g3 + f5*g2 + f6*g1 + f7*g0 + f8*g9_19 + f9*g8_19 | ||
421 | h8 := f0*g8 + f1_2*g7 + f2*g6 + f3_2*g5 + f4*g4 + f5_2*g3 + f6*g2 + f7_2*g1 + f8*g0 + f9_2*g9_19 | ||
422 | h9 := f0*g9 + f1*g8 + f2*g7 + f3*g6 + f4*g5 + f5*g4 + f6*g3 + f7*g2 + f8*g1 + f9*g0 | ||
423 | |||
424 | FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9) | ||
425 | } | ||
426 | |||
427 | func feSquare(f *FieldElement) (h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64) { | ||
428 | f0 := int64(f[0]) | ||
429 | f1 := int64(f[1]) | ||
430 | f2 := int64(f[2]) | ||
431 | f3 := int64(f[3]) | ||
432 | f4 := int64(f[4]) | ||
433 | f5 := int64(f[5]) | ||
434 | f6 := int64(f[6]) | ||
435 | f7 := int64(f[7]) | ||
436 | f8 := int64(f[8]) | ||
437 | f9 := int64(f[9]) | ||
438 | f0_2 := int64(2 * f[0]) | ||
439 | f1_2 := int64(2 * f[1]) | ||
440 | f2_2 := int64(2 * f[2]) | ||
441 | f3_2 := int64(2 * f[3]) | ||
442 | f4_2 := int64(2 * f[4]) | ||
443 | f5_2 := int64(2 * f[5]) | ||
444 | f6_2 := int64(2 * f[6]) | ||
445 | f7_2 := int64(2 * f[7]) | ||
446 | f5_38 := 38 * f5 // 1.31*2^30 | ||
447 | f6_19 := 19 * f6 // 1.31*2^30 | ||
448 | f7_38 := 38 * f7 // 1.31*2^30 | ||
449 | f8_19 := 19 * f8 // 1.31*2^30 | ||
450 | f9_38 := 38 * f9 // 1.31*2^30 | ||
451 | |||
452 | h0 = f0*f0 + f1_2*f9_38 + f2_2*f8_19 + f3_2*f7_38 + f4_2*f6_19 + f5*f5_38 | ||
453 | h1 = f0_2*f1 + f2*f9_38 + f3_2*f8_19 + f4*f7_38 + f5_2*f6_19 | ||
454 | h2 = f0_2*f2 + f1_2*f1 + f3_2*f9_38 + f4_2*f8_19 + f5_2*f7_38 + f6*f6_19 | ||
455 | h3 = f0_2*f3 + f1_2*f2 + f4*f9_38 + f5_2*f8_19 + f6*f7_38 | ||
456 | h4 = f0_2*f4 + f1_2*f3_2 + f2*f2 + f5_2*f9_38 + f6_2*f8_19 + f7*f7_38 | ||
457 | h5 = f0_2*f5 + f1_2*f4 + f2_2*f3 + f6*f9_38 + f7_2*f8_19 | ||
458 | h6 = f0_2*f6 + f1_2*f5_2 + f2_2*f4 + f3_2*f3 + f7_2*f9_38 + f8*f8_19 | ||
459 | h7 = f0_2*f7 + f1_2*f6 + f2_2*f5 + f3_2*f4 + f8*f9_38 | ||
460 | h8 = f0_2*f8 + f1_2*f7_2 + f2_2*f6 + f3_2*f5_2 + f4*f4 + f9*f9_38 | ||
461 | h9 = f0_2*f9 + f1_2*f8 + f2_2*f7 + f3_2*f6 + f4_2*f5 | ||
462 | |||
463 | return | ||
464 | } | ||
465 | |||
466 | // FeSquare calculates h = f*f. Can overlap h with f. | ||
467 | // | ||
468 | // Preconditions: | ||
469 | // |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. | ||
470 | // | ||
471 | // Postconditions: | ||
472 | // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. | ||
473 | func FeSquare(h, f *FieldElement) { | ||
474 | h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 := feSquare(f) | ||
475 | FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9) | ||
476 | } | ||
477 | |||
478 | // FeSquare2 sets h = 2 * f * f | ||
479 | // | ||
480 | // Can overlap h with f. | ||
481 | // | ||
482 | // Preconditions: | ||
483 | // |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc. | ||
484 | // | ||
485 | // Postconditions: | ||
486 | // |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc. | ||
487 | // See fe_mul.c for discussion of implementation strategy. | ||
488 | func FeSquare2(h, f *FieldElement) { | ||
489 | h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 := feSquare(f) | ||
490 | |||
491 | h0 += h0 | ||
492 | h1 += h1 | ||
493 | h2 += h2 | ||
494 | h3 += h3 | ||
495 | h4 += h4 | ||
496 | h5 += h5 | ||
497 | h6 += h6 | ||
498 | h7 += h7 | ||
499 | h8 += h8 | ||
500 | h9 += h9 | ||
501 | |||
502 | FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9) | ||
503 | } | ||
504 | |||
505 | func FeInvert(out, z *FieldElement) { | ||
506 | var t0, t1, t2, t3 FieldElement | ||
507 | var i int | ||
508 | |||
509 | FeSquare(&t0, z) // 2^1 | ||
510 | FeSquare(&t1, &t0) // 2^2 | ||
511 | for i = 1; i < 2; i++ { // 2^3 | ||
512 | FeSquare(&t1, &t1) | ||
513 | } | ||
514 | FeMul(&t1, z, &t1) // 2^3 + 2^0 | ||
515 | FeMul(&t0, &t0, &t1) // 2^3 + 2^1 + 2^0 | ||
516 | FeSquare(&t2, &t0) // 2^4 + 2^2 + 2^1 | ||
517 | FeMul(&t1, &t1, &t2) // 2^4 + 2^3 + 2^2 + 2^1 + 2^0 | ||
518 | FeSquare(&t2, &t1) // 5,4,3,2,1 | ||
519 | for i = 1; i < 5; i++ { // 9,8,7,6,5 | ||
520 | FeSquare(&t2, &t2) | ||
521 | } | ||
522 | FeMul(&t1, &t2, &t1) // 9,8,7,6,5,4,3,2,1,0 | ||
523 | FeSquare(&t2, &t1) // 10..1 | ||
524 | for i = 1; i < 10; i++ { // 19..10 | ||
525 | FeSquare(&t2, &t2) | ||
526 | } | ||
527 | FeMul(&t2, &t2, &t1) // 19..0 | ||
528 | FeSquare(&t3, &t2) // 20..1 | ||
529 | for i = 1; i < 20; i++ { // 39..20 | ||
530 | FeSquare(&t3, &t3) | ||
531 | } | ||
532 | FeMul(&t2, &t3, &t2) // 39..0 | ||
533 | FeSquare(&t2, &t2) // 40..1 | ||
534 | for i = 1; i < 10; i++ { // 49..10 | ||
535 | FeSquare(&t2, &t2) | ||
536 | } | ||
537 | FeMul(&t1, &t2, &t1) // 49..0 | ||
538 | FeSquare(&t2, &t1) // 50..1 | ||
539 | for i = 1; i < 50; i++ { // 99..50 | ||
540 | FeSquare(&t2, &t2) | ||
541 | } | ||
542 | FeMul(&t2, &t2, &t1) // 99..0 | ||
543 | FeSquare(&t3, &t2) // 100..1 | ||
544 | for i = 1; i < 100; i++ { // 199..100 | ||
545 | FeSquare(&t3, &t3) | ||
546 | } | ||
547 | FeMul(&t2, &t3, &t2) // 199..0 | ||
548 | FeSquare(&t2, &t2) // 200..1 | ||
549 | for i = 1; i < 50; i++ { // 249..50 | ||
550 | FeSquare(&t2, &t2) | ||
551 | } | ||
552 | FeMul(&t1, &t2, &t1) // 249..0 | ||
553 | FeSquare(&t1, &t1) // 250..1 | ||
554 | for i = 1; i < 5; i++ { // 254..5 | ||
555 | FeSquare(&t1, &t1) | ||
556 | } | ||
557 | FeMul(out, &t1, &t0) // 254..5,3,1,0 | ||
558 | } | ||
559 | |||
560 | func fePow22523(out, z *FieldElement) { | ||
561 | var t0, t1, t2 FieldElement | ||
562 | var i int | ||
563 | |||
564 | FeSquare(&t0, z) | ||
565 | for i = 1; i < 1; i++ { | ||
566 | FeSquare(&t0, &t0) | ||
567 | } | ||
568 | FeSquare(&t1, &t0) | ||
569 | for i = 1; i < 2; i++ { | ||
570 | FeSquare(&t1, &t1) | ||
571 | } | ||
572 | FeMul(&t1, z, &t1) | ||
573 | FeMul(&t0, &t0, &t1) | ||
574 | FeSquare(&t0, &t0) | ||
575 | for i = 1; i < 1; i++ { | ||
576 | FeSquare(&t0, &t0) | ||
577 | } | ||
578 | FeMul(&t0, &t1, &t0) | ||
579 | FeSquare(&t1, &t0) | ||
580 | for i = 1; i < 5; i++ { | ||
581 | FeSquare(&t1, &t1) | ||
582 | } | ||
583 | FeMul(&t0, &t1, &t0) | ||
584 | FeSquare(&t1, &t0) | ||
585 | for i = 1; i < 10; i++ { | ||
586 | FeSquare(&t1, &t1) | ||
587 | } | ||
588 | FeMul(&t1, &t1, &t0) | ||
589 | FeSquare(&t2, &t1) | ||
590 | for i = 1; i < 20; i++ { | ||
591 | FeSquare(&t2, &t2) | ||
592 | } | ||
593 | FeMul(&t1, &t2, &t1) | ||
594 | FeSquare(&t1, &t1) | ||
595 | for i = 1; i < 10; i++ { | ||
596 | FeSquare(&t1, &t1) | ||
597 | } | ||
598 | FeMul(&t0, &t1, &t0) | ||
599 | FeSquare(&t1, &t0) | ||
600 | for i = 1; i < 50; i++ { | ||
601 | FeSquare(&t1, &t1) | ||
602 | } | ||
603 | FeMul(&t1, &t1, &t0) | ||
604 | FeSquare(&t2, &t1) | ||
605 | for i = 1; i < 100; i++ { | ||
606 | FeSquare(&t2, &t2) | ||
607 | } | ||
608 | FeMul(&t1, &t2, &t1) | ||
609 | FeSquare(&t1, &t1) | ||
610 | for i = 1; i < 50; i++ { | ||
611 | FeSquare(&t1, &t1) | ||
612 | } | ||
613 | FeMul(&t0, &t1, &t0) | ||
614 | FeSquare(&t0, &t0) | ||
615 | for i = 1; i < 2; i++ { | ||
616 | FeSquare(&t0, &t0) | ||
617 | } | ||
618 | FeMul(out, &t0, z) | ||
619 | } | ||
620 | |||
621 | // Group elements are members of the elliptic curve -x^2 + y^2 = 1 + d * x^2 * | ||
622 | // y^2 where d = -121665/121666. | ||
623 | // | ||
624 | // Several representations are used: | ||
625 | // ProjectiveGroupElement: (X:Y:Z) satisfying x=X/Z, y=Y/Z | ||
626 | // ExtendedGroupElement: (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT | ||
627 | // CompletedGroupElement: ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T | ||
628 | // PreComputedGroupElement: (y+x,y-x,2dxy) | ||
629 | |||
630 | type ProjectiveGroupElement struct { | ||
631 | X, Y, Z FieldElement | ||
632 | } | ||
633 | |||
634 | type ExtendedGroupElement struct { | ||
635 | X, Y, Z, T FieldElement | ||
636 | } | ||
637 | |||
638 | type CompletedGroupElement struct { | ||
639 | X, Y, Z, T FieldElement | ||
640 | } | ||
641 | |||
642 | type PreComputedGroupElement struct { | ||
643 | yPlusX, yMinusX, xy2d FieldElement | ||
644 | } | ||
645 | |||
646 | type CachedGroupElement struct { | ||
647 | yPlusX, yMinusX, Z, T2d FieldElement | ||
648 | } | ||
649 | |||
650 | func (p *ProjectiveGroupElement) Zero() { | ||
651 | FeZero(&p.X) | ||
652 | FeOne(&p.Y) | ||
653 | FeOne(&p.Z) | ||
654 | } | ||
655 | |||
656 | func (p *ProjectiveGroupElement) Double(r *CompletedGroupElement) { | ||
657 | var t0 FieldElement | ||
658 | |||
659 | FeSquare(&r.X, &p.X) | ||
660 | FeSquare(&r.Z, &p.Y) | ||
661 | FeSquare2(&r.T, &p.Z) | ||
662 | FeAdd(&r.Y, &p.X, &p.Y) | ||
663 | FeSquare(&t0, &r.Y) | ||
664 | FeAdd(&r.Y, &r.Z, &r.X) | ||
665 | FeSub(&r.Z, &r.Z, &r.X) | ||
666 | FeSub(&r.X, &t0, &r.Y) | ||
667 | FeSub(&r.T, &r.T, &r.Z) | ||
668 | } | ||
669 | |||
670 | func (p *ProjectiveGroupElement) ToBytes(s *[32]byte) { | ||
671 | var recip, x, y FieldElement | ||
672 | |||
673 | FeInvert(&recip, &p.Z) | ||
674 | FeMul(&x, &p.X, &recip) | ||
675 | FeMul(&y, &p.Y, &recip) | ||
676 | FeToBytes(s, &y) | ||
677 | s[31] ^= FeIsNegative(&x) << 7 | ||
678 | } | ||
679 | |||
680 | func (p *ExtendedGroupElement) Zero() { | ||
681 | FeZero(&p.X) | ||
682 | FeOne(&p.Y) | ||
683 | FeOne(&p.Z) | ||
684 | FeZero(&p.T) | ||
685 | } | ||
686 | |||
687 | func (p *ExtendedGroupElement) Double(r *CompletedGroupElement) { | ||
688 | var q ProjectiveGroupElement | ||
689 | p.ToProjective(&q) | ||
690 | q.Double(r) | ||
691 | } | ||
692 | |||
693 | func (p *ExtendedGroupElement) ToCached(r *CachedGroupElement) { | ||
694 | FeAdd(&r.yPlusX, &p.Y, &p.X) | ||
695 | FeSub(&r.yMinusX, &p.Y, &p.X) | ||
696 | FeCopy(&r.Z, &p.Z) | ||
697 | FeMul(&r.T2d, &p.T, &d2) | ||
698 | } | ||
699 | |||
700 | func (p *ExtendedGroupElement) ToProjective(r *ProjectiveGroupElement) { | ||
701 | FeCopy(&r.X, &p.X) | ||
702 | FeCopy(&r.Y, &p.Y) | ||
703 | FeCopy(&r.Z, &p.Z) | ||
704 | } | ||
705 | |||
706 | func (p *ExtendedGroupElement) ToBytes(s *[32]byte) { | ||
707 | var recip, x, y FieldElement | ||
708 | |||
709 | FeInvert(&recip, &p.Z) | ||
710 | FeMul(&x, &p.X, &recip) | ||
711 | FeMul(&y, &p.Y, &recip) | ||
712 | FeToBytes(s, &y) | ||
713 | s[31] ^= FeIsNegative(&x) << 7 | ||
714 | } | ||
715 | |||
716 | func (p *ExtendedGroupElement) FromBytes(s *[32]byte) bool { | ||
717 | var u, v, v3, vxx, check FieldElement | ||
718 | |||
719 | FeFromBytes(&p.Y, s) | ||
720 | FeOne(&p.Z) | ||
721 | FeSquare(&u, &p.Y) | ||
722 | FeMul(&v, &u, &d) | ||
723 | FeSub(&u, &u, &p.Z) // y = y^2-1 | ||
724 | FeAdd(&v, &v, &p.Z) // v = dy^2+1 | ||
725 | |||
726 | FeSquare(&v3, &v) | ||
727 | FeMul(&v3, &v3, &v) // v3 = v^3 | ||
728 | FeSquare(&p.X, &v3) | ||
729 | FeMul(&p.X, &p.X, &v) | ||
730 | FeMul(&p.X, &p.X, &u) // x = uv^7 | ||
731 | |||
732 | fePow22523(&p.X, &p.X) // x = (uv^7)^((q-5)/8) | ||
733 | FeMul(&p.X, &p.X, &v3) | ||
734 | FeMul(&p.X, &p.X, &u) // x = uv^3(uv^7)^((q-5)/8) | ||
735 | |||
736 | var tmpX, tmp2 [32]byte | ||
737 | |||
738 | FeSquare(&vxx, &p.X) | ||
739 | FeMul(&vxx, &vxx, &v) | ||
740 | FeSub(&check, &vxx, &u) // vx^2-u | ||
741 | if FeIsNonZero(&check) == 1 { | ||
742 | FeAdd(&check, &vxx, &u) // vx^2+u | ||
743 | if FeIsNonZero(&check) == 1 { | ||
744 | return false | ||
745 | } | ||
746 | FeMul(&p.X, &p.X, &SqrtM1) | ||
747 | |||
748 | FeToBytes(&tmpX, &p.X) | ||
749 | for i, v := range tmpX { | ||
750 | tmp2[31-i] = v | ||
751 | } | ||
752 | } | ||
753 | |||
754 | if FeIsNegative(&p.X) != (s[31] >> 7) { | ||
755 | FeNeg(&p.X, &p.X) | ||
756 | } | ||
757 | |||
758 | FeMul(&p.T, &p.X, &p.Y) | ||
759 | return true | ||
760 | } | ||
761 | |||
762 | func (p *CompletedGroupElement) ToProjective(r *ProjectiveGroupElement) { | ||
763 | FeMul(&r.X, &p.X, &p.T) | ||
764 | FeMul(&r.Y, &p.Y, &p.Z) | ||
765 | FeMul(&r.Z, &p.Z, &p.T) | ||
766 | } | ||
767 | |||
768 | func (p *CompletedGroupElement) ToExtended(r *ExtendedGroupElement) { | ||
769 | FeMul(&r.X, &p.X, &p.T) | ||
770 | FeMul(&r.Y, &p.Y, &p.Z) | ||
771 | FeMul(&r.Z, &p.Z, &p.T) | ||
772 | FeMul(&r.T, &p.X, &p.Y) | ||
773 | } | ||
774 | |||
775 | func (p *PreComputedGroupElement) Zero() { | ||
776 | FeOne(&p.yPlusX) | ||
777 | FeOne(&p.yMinusX) | ||
778 | FeZero(&p.xy2d) | ||
779 | } | ||
780 | |||
781 | func geAdd(r *CompletedGroupElement, p *ExtendedGroupElement, q *CachedGroupElement) { | ||
782 | var t0 FieldElement | ||
783 | |||
784 | FeAdd(&r.X, &p.Y, &p.X) | ||
785 | FeSub(&r.Y, &p.Y, &p.X) | ||
786 | FeMul(&r.Z, &r.X, &q.yPlusX) | ||
787 | FeMul(&r.Y, &r.Y, &q.yMinusX) | ||
788 | FeMul(&r.T, &q.T2d, &p.T) | ||
789 | FeMul(&r.X, &p.Z, &q.Z) | ||
790 | FeAdd(&t0, &r.X, &r.X) | ||
791 | FeSub(&r.X, &r.Z, &r.Y) | ||
792 | FeAdd(&r.Y, &r.Z, &r.Y) | ||
793 | FeAdd(&r.Z, &t0, &r.T) | ||
794 | FeSub(&r.T, &t0, &r.T) | ||
795 | } | ||
796 | |||
797 | func geSub(r *CompletedGroupElement, p *ExtendedGroupElement, q *CachedGroupElement) { | ||
798 | var t0 FieldElement | ||
799 | |||
800 | FeAdd(&r.X, &p.Y, &p.X) | ||
801 | FeSub(&r.Y, &p.Y, &p.X) | ||
802 | FeMul(&r.Z, &r.X, &q.yMinusX) | ||
803 | FeMul(&r.Y, &r.Y, &q.yPlusX) | ||
804 | FeMul(&r.T, &q.T2d, &p.T) | ||
805 | FeMul(&r.X, &p.Z, &q.Z) | ||
806 | FeAdd(&t0, &r.X, &r.X) | ||
807 | FeSub(&r.X, &r.Z, &r.Y) | ||
808 | FeAdd(&r.Y, &r.Z, &r.Y) | ||
809 | FeSub(&r.Z, &t0, &r.T) | ||
810 | FeAdd(&r.T, &t0, &r.T) | ||
811 | } | ||
812 | |||
813 | func geMixedAdd(r *CompletedGroupElement, p *ExtendedGroupElement, q *PreComputedGroupElement) { | ||
814 | var t0 FieldElement | ||
815 | |||
816 | FeAdd(&r.X, &p.Y, &p.X) | ||
817 | FeSub(&r.Y, &p.Y, &p.X) | ||
818 | FeMul(&r.Z, &r.X, &q.yPlusX) | ||
819 | FeMul(&r.Y, &r.Y, &q.yMinusX) | ||
820 | FeMul(&r.T, &q.xy2d, &p.T) | ||
821 | FeAdd(&t0, &p.Z, &p.Z) | ||
822 | FeSub(&r.X, &r.Z, &r.Y) | ||
823 | FeAdd(&r.Y, &r.Z, &r.Y) | ||
824 | FeAdd(&r.Z, &t0, &r.T) | ||
825 | FeSub(&r.T, &t0, &r.T) | ||
826 | } | ||
827 | |||
828 | func geMixedSub(r *CompletedGroupElement, p *ExtendedGroupElement, q *PreComputedGroupElement) { | ||
829 | var t0 FieldElement | ||
830 | |||
831 | FeAdd(&r.X, &p.Y, &p.X) | ||
832 | FeSub(&r.Y, &p.Y, &p.X) | ||
833 | FeMul(&r.Z, &r.X, &q.yMinusX) | ||
834 | FeMul(&r.Y, &r.Y, &q.yPlusX) | ||
835 | FeMul(&r.T, &q.xy2d, &p.T) | ||
836 | FeAdd(&t0, &p.Z, &p.Z) | ||
837 | FeSub(&r.X, &r.Z, &r.Y) | ||
838 | FeAdd(&r.Y, &r.Z, &r.Y) | ||
839 | FeSub(&r.Z, &t0, &r.T) | ||
840 | FeAdd(&r.T, &t0, &r.T) | ||
841 | } | ||
842 | |||
843 | func slide(r *[256]int8, a *[32]byte) { | ||
844 | for i := range r { | ||
845 | r[i] = int8(1 & (a[i>>3] >> uint(i&7))) | ||
846 | } | ||
847 | |||
848 | for i := range r { | ||
849 | if r[i] != 0 { | ||
850 | for b := 1; b <= 6 && i+b < 256; b++ { | ||
851 | if r[i+b] != 0 { | ||
852 | if r[i]+(r[i+b]<<uint(b)) <= 15 { | ||
853 | r[i] += r[i+b] << uint(b) | ||
854 | r[i+b] = 0 | ||
855 | } else if r[i]-(r[i+b]<<uint(b)) >= -15 { | ||
856 | r[i] -= r[i+b] << uint(b) | ||
857 | for k := i + b; k < 256; k++ { | ||
858 | if r[k] == 0 { | ||
859 | r[k] = 1 | ||
860 | break | ||
861 | } | ||
862 | r[k] = 0 | ||
863 | } | ||
864 | } else { | ||
865 | break | ||
866 | } | ||
867 | } | ||
868 | } | ||
869 | } | ||
870 | } | ||
871 | } | ||
872 | |||
873 | // GeDoubleScalarMultVartime sets r = a*A + b*B | ||
874 | // where a = a[0]+256*a[1]+...+256^31 a[31]. | ||
875 | // and b = b[0]+256*b[1]+...+256^31 b[31]. | ||
876 | // B is the Ed25519 base point (x,4/5) with x positive. | ||
877 | func GeDoubleScalarMultVartime(r *ProjectiveGroupElement, a *[32]byte, A *ExtendedGroupElement, b *[32]byte) { | ||
878 | var aSlide, bSlide [256]int8 | ||
879 | var Ai [8]CachedGroupElement // A,3A,5A,7A,9A,11A,13A,15A | ||
880 | var t CompletedGroupElement | ||
881 | var u, A2 ExtendedGroupElement | ||
882 | var i int | ||
883 | |||
884 | slide(&aSlide, a) | ||
885 | slide(&bSlide, b) | ||
886 | |||
887 | A.ToCached(&Ai[0]) | ||
888 | A.Double(&t) | ||
889 | t.ToExtended(&A2) | ||
890 | |||
891 | for i := 0; i < 7; i++ { | ||
892 | geAdd(&t, &A2, &Ai[i]) | ||
893 | t.ToExtended(&u) | ||
894 | u.ToCached(&Ai[i+1]) | ||
895 | } | ||
896 | |||
897 | r.Zero() | ||
898 | |||
899 | for i = 255; i >= 0; i-- { | ||
900 | if aSlide[i] != 0 || bSlide[i] != 0 { | ||
901 | break | ||
902 | } | ||
903 | } | ||
904 | |||
905 | for ; i >= 0; i-- { | ||
906 | r.Double(&t) | ||
907 | |||
908 | if aSlide[i] > 0 { | ||
909 | t.ToExtended(&u) | ||
910 | geAdd(&t, &u, &Ai[aSlide[i]/2]) | ||
911 | } else if aSlide[i] < 0 { | ||
912 | t.ToExtended(&u) | ||
913 | geSub(&t, &u, &Ai[(-aSlide[i])/2]) | ||
914 | } | ||
915 | |||
916 | if bSlide[i] > 0 { | ||
917 | t.ToExtended(&u) | ||
918 | geMixedAdd(&t, &u, &bi[bSlide[i]/2]) | ||
919 | } else if bSlide[i] < 0 { | ||
920 | t.ToExtended(&u) | ||
921 | geMixedSub(&t, &u, &bi[(-bSlide[i])/2]) | ||
922 | } | ||
923 | |||
924 | t.ToProjective(r) | ||
925 | } | ||
926 | } | ||
927 | |||
928 | // equal returns 1 if b == c and 0 otherwise, assuming that b and c are | ||
929 | // non-negative. | ||
930 | func equal(b, c int32) int32 { | ||
931 | x := uint32(b ^ c) | ||
932 | x-- | ||
933 | return int32(x >> 31) | ||
934 | } | ||
935 | |||
936 | // negative returns 1 if b < 0 and 0 otherwise. | ||
937 | func negative(b int32) int32 { | ||
938 | return (b >> 31) & 1 | ||
939 | } | ||
940 | |||
941 | func PreComputedGroupElementCMove(t, u *PreComputedGroupElement, b int32) { | ||
942 | FeCMove(&t.yPlusX, &u.yPlusX, b) | ||
943 | FeCMove(&t.yMinusX, &u.yMinusX, b) | ||
944 | FeCMove(&t.xy2d, &u.xy2d, b) | ||
945 | } | ||
946 | |||
947 | func selectPoint(t *PreComputedGroupElement, pos int32, b int32) { | ||
948 | var minusT PreComputedGroupElement | ||
949 | bNegative := negative(b) | ||
950 | bAbs := b - (((-bNegative) & b) << 1) | ||
951 | |||
952 | t.Zero() | ||
953 | for i := int32(0); i < 8; i++ { | ||
954 | PreComputedGroupElementCMove(t, &base[pos][i], equal(bAbs, i+1)) | ||
955 | } | ||
956 | FeCopy(&minusT.yPlusX, &t.yMinusX) | ||
957 | FeCopy(&minusT.yMinusX, &t.yPlusX) | ||
958 | FeNeg(&minusT.xy2d, &t.xy2d) | ||
959 | PreComputedGroupElementCMove(t, &minusT, bNegative) | ||
960 | } | ||
961 | |||
962 | // GeScalarMultBase computes h = a*B, where | ||
963 | // a = a[0]+256*a[1]+...+256^31 a[31] | ||
964 | // B is the Ed25519 base point (x,4/5) with x positive. | ||
965 | // | ||
966 | // Preconditions: | ||
967 | // a[31] <= 127 | ||
968 | func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte) { | ||
969 | var e [64]int8 | ||
970 | |||
971 | for i, v := range a { | ||
972 | e[2*i] = int8(v & 15) | ||
973 | e[2*i+1] = int8((v >> 4) & 15) | ||
974 | } | ||
975 | |||
976 | // each e[i] is between 0 and 15 and e[63] is between 0 and 7. | ||
977 | |||
978 | carry := int8(0) | ||
979 | for i := 0; i < 63; i++ { | ||
980 | e[i] += carry | ||
981 | carry = (e[i] + 8) >> 4 | ||
982 | e[i] -= carry << 4 | ||
983 | } | ||
984 | e[63] += carry | ||
985 | // each e[i] is between -8 and 8. | ||
986 | |||
987 | h.Zero() | ||
988 | var t PreComputedGroupElement | ||
989 | var r CompletedGroupElement | ||
990 | for i := int32(1); i < 64; i += 2 { | ||
991 | selectPoint(&t, i/2, int32(e[i])) | ||
992 | geMixedAdd(&r, h, &t) | ||
993 | r.ToExtended(h) | ||
994 | } | ||
995 | |||
996 | var s ProjectiveGroupElement | ||
997 | |||
998 | h.Double(&r) | ||
999 | r.ToProjective(&s) | ||
1000 | s.Double(&r) | ||
1001 | r.ToProjective(&s) | ||
1002 | s.Double(&r) | ||
1003 | r.ToProjective(&s) | ||
1004 | s.Double(&r) | ||
1005 | r.ToExtended(h) | ||
1006 | |||
1007 | for i := int32(0); i < 64; i += 2 { | ||
1008 | selectPoint(&t, i/2, int32(e[i])) | ||
1009 | geMixedAdd(&r, h, &t) | ||
1010 | r.ToExtended(h) | ||
1011 | } | ||
1012 | } | ||
1013 | |||
1014 | // The scalars are GF(2^252 + 27742317777372353535851937790883648493). | ||
1015 | |||
1016 | // Input: | ||
1017 | // a[0]+256*a[1]+...+256^31*a[31] = a | ||
1018 | // b[0]+256*b[1]+...+256^31*b[31] = b | ||
1019 | // c[0]+256*c[1]+...+256^31*c[31] = c | ||
1020 | // | ||
1021 | // Output: | ||
1022 | // s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l | ||
1023 | // where l = 2^252 + 27742317777372353535851937790883648493. | ||
1024 | func ScMulAdd(s, a, b, c *[32]byte) { | ||
1025 | a0 := 2097151 & load3(a[:]) | ||
1026 | a1 := 2097151 & (load4(a[2:]) >> 5) | ||
1027 | a2 := 2097151 & (load3(a[5:]) >> 2) | ||
1028 | a3 := 2097151 & (load4(a[7:]) >> 7) | ||
1029 | a4 := 2097151 & (load4(a[10:]) >> 4) | ||
1030 | a5 := 2097151 & (load3(a[13:]) >> 1) | ||
1031 | a6 := 2097151 & (load4(a[15:]) >> 6) | ||
1032 | a7 := 2097151 & (load3(a[18:]) >> 3) | ||
1033 | a8 := 2097151 & load3(a[21:]) | ||
1034 | a9 := 2097151 & (load4(a[23:]) >> 5) | ||
1035 | a10 := 2097151 & (load3(a[26:]) >> 2) | ||
1036 | a11 := (load4(a[28:]) >> 7) | ||
1037 | b0 := 2097151 & load3(b[:]) | ||
1038 | b1 := 2097151 & (load4(b[2:]) >> 5) | ||
1039 | b2 := 2097151 & (load3(b[5:]) >> 2) | ||
1040 | b3 := 2097151 & (load4(b[7:]) >> 7) | ||
1041 | b4 := 2097151 & (load4(b[10:]) >> 4) | ||
1042 | b5 := 2097151 & (load3(b[13:]) >> 1) | ||
1043 | b6 := 2097151 & (load4(b[15:]) >> 6) | ||
1044 | b7 := 2097151 & (load3(b[18:]) >> 3) | ||
1045 | b8 := 2097151 & load3(b[21:]) | ||
1046 | b9 := 2097151 & (load4(b[23:]) >> 5) | ||
1047 | b10 := 2097151 & (load3(b[26:]) >> 2) | ||
1048 | b11 := (load4(b[28:]) >> 7) | ||
1049 | c0 := 2097151 & load3(c[:]) | ||
1050 | c1 := 2097151 & (load4(c[2:]) >> 5) | ||
1051 | c2 := 2097151 & (load3(c[5:]) >> 2) | ||
1052 | c3 := 2097151 & (load4(c[7:]) >> 7) | ||
1053 | c4 := 2097151 & (load4(c[10:]) >> 4) | ||
1054 | c5 := 2097151 & (load3(c[13:]) >> 1) | ||
1055 | c6 := 2097151 & (load4(c[15:]) >> 6) | ||
1056 | c7 := 2097151 & (load3(c[18:]) >> 3) | ||
1057 | c8 := 2097151 & load3(c[21:]) | ||
1058 | c9 := 2097151 & (load4(c[23:]) >> 5) | ||
1059 | c10 := 2097151 & (load3(c[26:]) >> 2) | ||
1060 | c11 := (load4(c[28:]) >> 7) | ||
1061 | var carry [23]int64 | ||
1062 | |||
1063 | s0 := c0 + a0*b0 | ||
1064 | s1 := c1 + a0*b1 + a1*b0 | ||
1065 | s2 := c2 + a0*b2 + a1*b1 + a2*b0 | ||
1066 | s3 := c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0 | ||
1067 | s4 := c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0 | ||
1068 | s5 := c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0 | ||
1069 | s6 := c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0 | ||
1070 | s7 := c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0 | ||
1071 | s8 := c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0 | ||
1072 | s9 := c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0 | ||
1073 | s10 := c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0 | ||
1074 | s11 := c11 + a0*b11 + a1*b10 + a2*b9 + a3*b8 + a4*b7 + a5*b6 + a6*b5 + a7*b4 + a8*b3 + a9*b2 + a10*b1 + a11*b0 | ||
1075 | s12 := a1*b11 + a2*b10 + a3*b9 + a4*b8 + a5*b7 + a6*b6 + a7*b5 + a8*b4 + a9*b3 + a10*b2 + a11*b1 | ||
1076 | s13 := a2*b11 + a3*b10 + a4*b9 + a5*b8 + a6*b7 + a7*b6 + a8*b5 + a9*b4 + a10*b3 + a11*b2 | ||
1077 | s14 := a3*b11 + a4*b10 + a5*b9 + a6*b8 + a7*b7 + a8*b6 + a9*b5 + a10*b4 + a11*b3 | ||
1078 | s15 := a4*b11 + a5*b10 + a6*b9 + a7*b8 + a8*b7 + a9*b6 + a10*b5 + a11*b4 | ||
1079 | s16 := a5*b11 + a6*b10 + a7*b9 + a8*b8 + a9*b7 + a10*b6 + a11*b5 | ||
1080 | s17 := a6*b11 + a7*b10 + a8*b9 + a9*b8 + a10*b7 + a11*b6 | ||
1081 | s18 := a7*b11 + a8*b10 + a9*b9 + a10*b8 + a11*b7 | ||
1082 | s19 := a8*b11 + a9*b10 + a10*b9 + a11*b8 | ||
1083 | s20 := a9*b11 + a10*b10 + a11*b9 | ||
1084 | s21 := a10*b11 + a11*b10 | ||
1085 | s22 := a11 * b11 | ||
1086 | s23 := int64(0) | ||
1087 | |||
1088 | carry[0] = (s0 + (1 << 20)) >> 21 | ||
1089 | s1 += carry[0] | ||
1090 | s0 -= carry[0] << 21 | ||
1091 | carry[2] = (s2 + (1 << 20)) >> 21 | ||
1092 | s3 += carry[2] | ||
1093 | s2 -= carry[2] << 21 | ||
1094 | carry[4] = (s4 + (1 << 20)) >> 21 | ||
1095 | s5 += carry[4] | ||
1096 | s4 -= carry[4] << 21 | ||
1097 | carry[6] = (s6 + (1 << 20)) >> 21 | ||
1098 | s7 += carry[6] | ||
1099 | s6 -= carry[6] << 21 | ||
1100 | carry[8] = (s8 + (1 << 20)) >> 21 | ||
1101 | s9 += carry[8] | ||
1102 | s8 -= carry[8] << 21 | ||
1103 | carry[10] = (s10 + (1 << 20)) >> 21 | ||
1104 | s11 += carry[10] | ||
1105 | s10 -= carry[10] << 21 | ||
1106 | carry[12] = (s12 + (1 << 20)) >> 21 | ||
1107 | s13 += carry[12] | ||
1108 | s12 -= carry[12] << 21 | ||
1109 | carry[14] = (s14 + (1 << 20)) >> 21 | ||
1110 | s15 += carry[14] | ||
1111 | s14 -= carry[14] << 21 | ||
1112 | carry[16] = (s16 + (1 << 20)) >> 21 | ||
1113 | s17 += carry[16] | ||
1114 | s16 -= carry[16] << 21 | ||
1115 | carry[18] = (s18 + (1 << 20)) >> 21 | ||
1116 | s19 += carry[18] | ||
1117 | s18 -= carry[18] << 21 | ||
1118 | carry[20] = (s20 + (1 << 20)) >> 21 | ||
1119 | s21 += carry[20] | ||
1120 | s20 -= carry[20] << 21 | ||
1121 | carry[22] = (s22 + (1 << 20)) >> 21 | ||
1122 | s23 += carry[22] | ||
1123 | s22 -= carry[22] << 21 | ||
1124 | |||
1125 | carry[1] = (s1 + (1 << 20)) >> 21 | ||
1126 | s2 += carry[1] | ||
1127 | s1 -= carry[1] << 21 | ||
1128 | carry[3] = (s3 + (1 << 20)) >> 21 | ||
1129 | s4 += carry[3] | ||
1130 | s3 -= carry[3] << 21 | ||
1131 | carry[5] = (s5 + (1 << 20)) >> 21 | ||
1132 | s6 += carry[5] | ||
1133 | s5 -= carry[5] << 21 | ||
1134 | carry[7] = (s7 + (1 << 20)) >> 21 | ||
1135 | s8 += carry[7] | ||
1136 | s7 -= carry[7] << 21 | ||
1137 | carry[9] = (s9 + (1 << 20)) >> 21 | ||
1138 | s10 += carry[9] | ||
1139 | s9 -= carry[9] << 21 | ||
1140 | carry[11] = (s11 + (1 << 20)) >> 21 | ||
1141 | s12 += carry[11] | ||
1142 | s11 -= carry[11] << 21 | ||
1143 | carry[13] = (s13 + (1 << 20)) >> 21 | ||
1144 | s14 += carry[13] | ||
1145 | s13 -= carry[13] << 21 | ||
1146 | carry[15] = (s15 + (1 << 20)) >> 21 | ||
1147 | s16 += carry[15] | ||
1148 | s15 -= carry[15] << 21 | ||
1149 | carry[17] = (s17 + (1 << 20)) >> 21 | ||
1150 | s18 += carry[17] | ||
1151 | s17 -= carry[17] << 21 | ||
1152 | carry[19] = (s19 + (1 << 20)) >> 21 | ||
1153 | s20 += carry[19] | ||
1154 | s19 -= carry[19] << 21 | ||
1155 | carry[21] = (s21 + (1 << 20)) >> 21 | ||
1156 | s22 += carry[21] | ||
1157 | s21 -= carry[21] << 21 | ||
1158 | |||
1159 | s11 += s23 * 666643 | ||
1160 | s12 += s23 * 470296 | ||
1161 | s13 += s23 * 654183 | ||
1162 | s14 -= s23 * 997805 | ||
1163 | s15 += s23 * 136657 | ||
1164 | s16 -= s23 * 683901 | ||
1165 | s23 = 0 | ||
1166 | |||
1167 | s10 += s22 * 666643 | ||
1168 | s11 += s22 * 470296 | ||
1169 | s12 += s22 * 654183 | ||
1170 | s13 -= s22 * 997805 | ||
1171 | s14 += s22 * 136657 | ||
1172 | s15 -= s22 * 683901 | ||
1173 | s22 = 0 | ||
1174 | |||
1175 | s9 += s21 * 666643 | ||
1176 | s10 += s21 * 470296 | ||
1177 | s11 += s21 * 654183 | ||
1178 | s12 -= s21 * 997805 | ||
1179 | s13 += s21 * 136657 | ||
1180 | s14 -= s21 * 683901 | ||
1181 | s21 = 0 | ||
1182 | |||
1183 | s8 += s20 * 666643 | ||
1184 | s9 += s20 * 470296 | ||
1185 | s10 += s20 * 654183 | ||
1186 | s11 -= s20 * 997805 | ||
1187 | s12 += s20 * 136657 | ||
1188 | s13 -= s20 * 683901 | ||
1189 | s20 = 0 | ||
1190 | |||
1191 | s7 += s19 * 666643 | ||
1192 | s8 += s19 * 470296 | ||
1193 | s9 += s19 * 654183 | ||
1194 | s10 -= s19 * 997805 | ||
1195 | s11 += s19 * 136657 | ||
1196 | s12 -= s19 * 683901 | ||
1197 | s19 = 0 | ||
1198 | |||
1199 | s6 += s18 * 666643 | ||
1200 | s7 += s18 * 470296 | ||
1201 | s8 += s18 * 654183 | ||
1202 | s9 -= s18 * 997805 | ||
1203 | s10 += s18 * 136657 | ||
1204 | s11 -= s18 * 683901 | ||
1205 | s18 = 0 | ||
1206 | |||
1207 | carry[6] = (s6 + (1 << 20)) >> 21 | ||
1208 | s7 += carry[6] | ||
1209 | s6 -= carry[6] << 21 | ||
1210 | carry[8] = (s8 + (1 << 20)) >> 21 | ||
1211 | s9 += carry[8] | ||
1212 | s8 -= carry[8] << 21 | ||
1213 | carry[10] = (s10 + (1 << 20)) >> 21 | ||
1214 | s11 += carry[10] | ||
1215 | s10 -= carry[10] << 21 | ||
1216 | carry[12] = (s12 + (1 << 20)) >> 21 | ||
1217 | s13 += carry[12] | ||
1218 | s12 -= carry[12] << 21 | ||
1219 | carry[14] = (s14 + (1 << 20)) >> 21 | ||
1220 | s15 += carry[14] | ||
1221 | s14 -= carry[14] << 21 | ||
1222 | carry[16] = (s16 + (1 << 20)) >> 21 | ||
1223 | s17 += carry[16] | ||
1224 | s16 -= carry[16] << 21 | ||
1225 | |||
1226 | carry[7] = (s7 + (1 << 20)) >> 21 | ||
1227 | s8 += carry[7] | ||
1228 | s7 -= carry[7] << 21 | ||
1229 | carry[9] = (s9 + (1 << 20)) >> 21 | ||
1230 | s10 += carry[9] | ||
1231 | s9 -= carry[9] << 21 | ||
1232 | carry[11] = (s11 + (1 << 20)) >> 21 | ||
1233 | s12 += carry[11] | ||
1234 | s11 -= carry[11] << 21 | ||
1235 | carry[13] = (s13 + (1 << 20)) >> 21 | ||
1236 | s14 += carry[13] | ||
1237 | s13 -= carry[13] << 21 | ||
1238 | carry[15] = (s15 + (1 << 20)) >> 21 | ||
1239 | s16 += carry[15] | ||
1240 | s15 -= carry[15] << 21 | ||
1241 | |||
1242 | s5 += s17 * 666643 | ||
1243 | s6 += s17 * 470296 | ||
1244 | s7 += s17 * 654183 | ||
1245 | s8 -= s17 * 997805 | ||
1246 | s9 += s17 * 136657 | ||
1247 | s10 -= s17 * 683901 | ||
1248 | s17 = 0 | ||
1249 | |||
1250 | s4 += s16 * 666643 | ||
1251 | s5 += s16 * 470296 | ||
1252 | s6 += s16 * 654183 | ||
1253 | s7 -= s16 * 997805 | ||
1254 | s8 += s16 * 136657 | ||
1255 | s9 -= s16 * 683901 | ||
1256 | s16 = 0 | ||
1257 | |||
1258 | s3 += s15 * 666643 | ||
1259 | s4 += s15 * 470296 | ||
1260 | s5 += s15 * 654183 | ||
1261 | s6 -= s15 * 997805 | ||
1262 | s7 += s15 * 136657 | ||
1263 | s8 -= s15 * 683901 | ||
1264 | s15 = 0 | ||
1265 | |||
1266 | s2 += s14 * 666643 | ||
1267 | s3 += s14 * 470296 | ||
1268 | s4 += s14 * 654183 | ||
1269 | s5 -= s14 * 997805 | ||
1270 | s6 += s14 * 136657 | ||
1271 | s7 -= s14 * 683901 | ||
1272 | s14 = 0 | ||
1273 | |||
1274 | s1 += s13 * 666643 | ||
1275 | s2 += s13 * 470296 | ||
1276 | s3 += s13 * 654183 | ||
1277 | s4 -= s13 * 997805 | ||
1278 | s5 += s13 * 136657 | ||
1279 | s6 -= s13 * 683901 | ||
1280 | s13 = 0 | ||
1281 | |||
1282 | s0 += s12 * 666643 | ||
1283 | s1 += s12 * 470296 | ||
1284 | s2 += s12 * 654183 | ||
1285 | s3 -= s12 * 997805 | ||
1286 | s4 += s12 * 136657 | ||
1287 | s5 -= s12 * 683901 | ||
1288 | s12 = 0 | ||
1289 | |||
1290 | carry[0] = (s0 + (1 << 20)) >> 21 | ||
1291 | s1 += carry[0] | ||
1292 | s0 -= carry[0] << 21 | ||
1293 | carry[2] = (s2 + (1 << 20)) >> 21 | ||
1294 | s3 += carry[2] | ||
1295 | s2 -= carry[2] << 21 | ||
1296 | carry[4] = (s4 + (1 << 20)) >> 21 | ||
1297 | s5 += carry[4] | ||
1298 | s4 -= carry[4] << 21 | ||
1299 | carry[6] = (s6 + (1 << 20)) >> 21 | ||
1300 | s7 += carry[6] | ||
1301 | s6 -= carry[6] << 21 | ||
1302 | carry[8] = (s8 + (1 << 20)) >> 21 | ||
1303 | s9 += carry[8] | ||
1304 | s8 -= carry[8] << 21 | ||
1305 | carry[10] = (s10 + (1 << 20)) >> 21 | ||
1306 | s11 += carry[10] | ||
1307 | s10 -= carry[10] << 21 | ||
1308 | |||
1309 | carry[1] = (s1 + (1 << 20)) >> 21 | ||
1310 | s2 += carry[1] | ||
1311 | s1 -= carry[1] << 21 | ||
1312 | carry[3] = (s3 + (1 << 20)) >> 21 | ||
1313 | s4 += carry[3] | ||
1314 | s3 -= carry[3] << 21 | ||
1315 | carry[5] = (s5 + (1 << 20)) >> 21 | ||
1316 | s6 += carry[5] | ||
1317 | s5 -= carry[5] << 21 | ||
1318 | carry[7] = (s7 + (1 << 20)) >> 21 | ||
1319 | s8 += carry[7] | ||
1320 | s7 -= carry[7] << 21 | ||
1321 | carry[9] = (s9 + (1 << 20)) >> 21 | ||
1322 | s10 += carry[9] | ||
1323 | s9 -= carry[9] << 21 | ||
1324 | carry[11] = (s11 + (1 << 20)) >> 21 | ||
1325 | s12 += carry[11] | ||
1326 | s11 -= carry[11] << 21 | ||
1327 | |||
1328 | s0 += s12 * 666643 | ||
1329 | s1 += s12 * 470296 | ||
1330 | s2 += s12 * 654183 | ||
1331 | s3 -= s12 * 997805 | ||
1332 | s4 += s12 * 136657 | ||
1333 | s5 -= s12 * 683901 | ||
1334 | s12 = 0 | ||
1335 | |||
1336 | carry[0] = s0 >> 21 | ||
1337 | s1 += carry[0] | ||
1338 | s0 -= carry[0] << 21 | ||
1339 | carry[1] = s1 >> 21 | ||
1340 | s2 += carry[1] | ||
1341 | s1 -= carry[1] << 21 | ||
1342 | carry[2] = s2 >> 21 | ||
1343 | s3 += carry[2] | ||
1344 | s2 -= carry[2] << 21 | ||
1345 | carry[3] = s3 >> 21 | ||
1346 | s4 += carry[3] | ||
1347 | s3 -= carry[3] << 21 | ||
1348 | carry[4] = s4 >> 21 | ||
1349 | s5 += carry[4] | ||
1350 | s4 -= carry[4] << 21 | ||
1351 | carry[5] = s5 >> 21 | ||
1352 | s6 += carry[5] | ||
1353 | s5 -= carry[5] << 21 | ||
1354 | carry[6] = s6 >> 21 | ||
1355 | s7 += carry[6] | ||
1356 | s6 -= carry[6] << 21 | ||
1357 | carry[7] = s7 >> 21 | ||
1358 | s8 += carry[7] | ||
1359 | s7 -= carry[7] << 21 | ||
1360 | carry[8] = s8 >> 21 | ||
1361 | s9 += carry[8] | ||
1362 | s8 -= carry[8] << 21 | ||
1363 | carry[9] = s9 >> 21 | ||
1364 | s10 += carry[9] | ||
1365 | s9 -= carry[9] << 21 | ||
1366 | carry[10] = s10 >> 21 | ||
1367 | s11 += carry[10] | ||
1368 | s10 -= carry[10] << 21 | ||
1369 | carry[11] = s11 >> 21 | ||
1370 | s12 += carry[11] | ||
1371 | s11 -= carry[11] << 21 | ||
1372 | |||
1373 | s0 += s12 * 666643 | ||
1374 | s1 += s12 * 470296 | ||
1375 | s2 += s12 * 654183 | ||
1376 | s3 -= s12 * 997805 | ||
1377 | s4 += s12 * 136657 | ||
1378 | s5 -= s12 * 683901 | ||
1379 | s12 = 0 | ||
1380 | |||
1381 | carry[0] = s0 >> 21 | ||
1382 | s1 += carry[0] | ||
1383 | s0 -= carry[0] << 21 | ||
1384 | carry[1] = s1 >> 21 | ||
1385 | s2 += carry[1] | ||
1386 | s1 -= carry[1] << 21 | ||
1387 | carry[2] = s2 >> 21 | ||
1388 | s3 += carry[2] | ||
1389 | s2 -= carry[2] << 21 | ||
1390 | carry[3] = s3 >> 21 | ||
1391 | s4 += carry[3] | ||
1392 | s3 -= carry[3] << 21 | ||
1393 | carry[4] = s4 >> 21 | ||
1394 | s5 += carry[4] | ||
1395 | s4 -= carry[4] << 21 | ||
1396 | carry[5] = s5 >> 21 | ||
1397 | s6 += carry[5] | ||
1398 | s5 -= carry[5] << 21 | ||
1399 | carry[6] = s6 >> 21 | ||
1400 | s7 += carry[6] | ||
1401 | s6 -= carry[6] << 21 | ||
1402 | carry[7] = s7 >> 21 | ||
1403 | s8 += carry[7] | ||
1404 | s7 -= carry[7] << 21 | ||
1405 | carry[8] = s8 >> 21 | ||
1406 | s9 += carry[8] | ||
1407 | s8 -= carry[8] << 21 | ||
1408 | carry[9] = s9 >> 21 | ||
1409 | s10 += carry[9] | ||
1410 | s9 -= carry[9] << 21 | ||
1411 | carry[10] = s10 >> 21 | ||
1412 | s11 += carry[10] | ||
1413 | s10 -= carry[10] << 21 | ||
1414 | |||
1415 | s[0] = byte(s0 >> 0) | ||
1416 | s[1] = byte(s0 >> 8) | ||
1417 | s[2] = byte((s0 >> 16) | (s1 << 5)) | ||
1418 | s[3] = byte(s1 >> 3) | ||
1419 | s[4] = byte(s1 >> 11) | ||
1420 | s[5] = byte((s1 >> 19) | (s2 << 2)) | ||
1421 | s[6] = byte(s2 >> 6) | ||
1422 | s[7] = byte((s2 >> 14) | (s3 << 7)) | ||
1423 | s[8] = byte(s3 >> 1) | ||
1424 | s[9] = byte(s3 >> 9) | ||
1425 | s[10] = byte((s3 >> 17) | (s4 << 4)) | ||
1426 | s[11] = byte(s4 >> 4) | ||
1427 | s[12] = byte(s4 >> 12) | ||
1428 | s[13] = byte((s4 >> 20) | (s5 << 1)) | ||
1429 | s[14] = byte(s5 >> 7) | ||
1430 | s[15] = byte((s5 >> 15) | (s6 << 6)) | ||
1431 | s[16] = byte(s6 >> 2) | ||
1432 | s[17] = byte(s6 >> 10) | ||
1433 | s[18] = byte((s6 >> 18) | (s7 << 3)) | ||
1434 | s[19] = byte(s7 >> 5) | ||
1435 | s[20] = byte(s7 >> 13) | ||
1436 | s[21] = byte(s8 >> 0) | ||
1437 | s[22] = byte(s8 >> 8) | ||
1438 | s[23] = byte((s8 >> 16) | (s9 << 5)) | ||
1439 | s[24] = byte(s9 >> 3) | ||
1440 | s[25] = byte(s9 >> 11) | ||
1441 | s[26] = byte((s9 >> 19) | (s10 << 2)) | ||
1442 | s[27] = byte(s10 >> 6) | ||
1443 | s[28] = byte((s10 >> 14) | (s11 << 7)) | ||
1444 | s[29] = byte(s11 >> 1) | ||
1445 | s[30] = byte(s11 >> 9) | ||
1446 | s[31] = byte(s11 >> 17) | ||
1447 | } | ||
1448 | |||
1449 | // Input: | ||
1450 | // s[0]+256*s[1]+...+256^63*s[63] = s | ||
1451 | // | ||
1452 | // Output: | ||
1453 | // s[0]+256*s[1]+...+256^31*s[31] = s mod l | ||
1454 | // where l = 2^252 + 27742317777372353535851937790883648493. | ||
1455 | func ScReduce(out *[32]byte, s *[64]byte) { | ||
1456 | s0 := 2097151 & load3(s[:]) | ||
1457 | s1 := 2097151 & (load4(s[2:]) >> 5) | ||
1458 | s2 := 2097151 & (load3(s[5:]) >> 2) | ||
1459 | s3 := 2097151 & (load4(s[7:]) >> 7) | ||
1460 | s4 := 2097151 & (load4(s[10:]) >> 4) | ||
1461 | s5 := 2097151 & (load3(s[13:]) >> 1) | ||
1462 | s6 := 2097151 & (load4(s[15:]) >> 6) | ||
1463 | s7 := 2097151 & (load3(s[18:]) >> 3) | ||
1464 | s8 := 2097151 & load3(s[21:]) | ||
1465 | s9 := 2097151 & (load4(s[23:]) >> 5) | ||
1466 | s10 := 2097151 & (load3(s[26:]) >> 2) | ||
1467 | s11 := 2097151 & (load4(s[28:]) >> 7) | ||
1468 | s12 := 2097151 & (load4(s[31:]) >> 4) | ||
1469 | s13 := 2097151 & (load3(s[34:]) >> 1) | ||
1470 | s14 := 2097151 & (load4(s[36:]) >> 6) | ||
1471 | s15 := 2097151 & (load3(s[39:]) >> 3) | ||
1472 | s16 := 2097151 & load3(s[42:]) | ||
1473 | s17 := 2097151 & (load4(s[44:]) >> 5) | ||
1474 | s18 := 2097151 & (load3(s[47:]) >> 2) | ||
1475 | s19 := 2097151 & (load4(s[49:]) >> 7) | ||
1476 | s20 := 2097151 & (load4(s[52:]) >> 4) | ||
1477 | s21 := 2097151 & (load3(s[55:]) >> 1) | ||
1478 | s22 := 2097151 & (load4(s[57:]) >> 6) | ||
1479 | s23 := (load4(s[60:]) >> 3) | ||
1480 | |||
1481 | s11 += s23 * 666643 | ||
1482 | s12 += s23 * 470296 | ||
1483 | s13 += s23 * 654183 | ||
1484 | s14 -= s23 * 997805 | ||
1485 | s15 += s23 * 136657 | ||
1486 | s16 -= s23 * 683901 | ||
1487 | s23 = 0 | ||
1488 | |||
1489 | s10 += s22 * 666643 | ||
1490 | s11 += s22 * 470296 | ||
1491 | s12 += s22 * 654183 | ||
1492 | s13 -= s22 * 997805 | ||
1493 | s14 += s22 * 136657 | ||
1494 | s15 -= s22 * 683901 | ||
1495 | s22 = 0 | ||
1496 | |||
1497 | s9 += s21 * 666643 | ||
1498 | s10 += s21 * 470296 | ||
1499 | s11 += s21 * 654183 | ||
1500 | s12 -= s21 * 997805 | ||
1501 | s13 += s21 * 136657 | ||
1502 | s14 -= s21 * 683901 | ||
1503 | s21 = 0 | ||
1504 | |||
1505 | s8 += s20 * 666643 | ||
1506 | s9 += s20 * 470296 | ||
1507 | s10 += s20 * 654183 | ||
1508 | s11 -= s20 * 997805 | ||
1509 | s12 += s20 * 136657 | ||
1510 | s13 -= s20 * 683901 | ||
1511 | s20 = 0 | ||
1512 | |||
1513 | s7 += s19 * 666643 | ||
1514 | s8 += s19 * 470296 | ||
1515 | s9 += s19 * 654183 | ||
1516 | s10 -= s19 * 997805 | ||
1517 | s11 += s19 * 136657 | ||
1518 | s12 -= s19 * 683901 | ||
1519 | s19 = 0 | ||
1520 | |||
1521 | s6 += s18 * 666643 | ||
1522 | s7 += s18 * 470296 | ||
1523 | s8 += s18 * 654183 | ||
1524 | s9 -= s18 * 997805 | ||
1525 | s10 += s18 * 136657 | ||
1526 | s11 -= s18 * 683901 | ||
1527 | s18 = 0 | ||
1528 | |||
1529 | var carry [17]int64 | ||
1530 | |||
1531 | carry[6] = (s6 + (1 << 20)) >> 21 | ||
1532 | s7 += carry[6] | ||
1533 | s6 -= carry[6] << 21 | ||
1534 | carry[8] = (s8 + (1 << 20)) >> 21 | ||
1535 | s9 += carry[8] | ||
1536 | s8 -= carry[8] << 21 | ||
1537 | carry[10] = (s10 + (1 << 20)) >> 21 | ||
1538 | s11 += carry[10] | ||
1539 | s10 -= carry[10] << 21 | ||
1540 | carry[12] = (s12 + (1 << 20)) >> 21 | ||
1541 | s13 += carry[12] | ||
1542 | s12 -= carry[12] << 21 | ||
1543 | carry[14] = (s14 + (1 << 20)) >> 21 | ||
1544 | s15 += carry[14] | ||
1545 | s14 -= carry[14] << 21 | ||
1546 | carry[16] = (s16 + (1 << 20)) >> 21 | ||
1547 | s17 += carry[16] | ||
1548 | s16 -= carry[16] << 21 | ||
1549 | |||
1550 | carry[7] = (s7 + (1 << 20)) >> 21 | ||
1551 | s8 += carry[7] | ||
1552 | s7 -= carry[7] << 21 | ||
1553 | carry[9] = (s9 + (1 << 20)) >> 21 | ||
1554 | s10 += carry[9] | ||
1555 | s9 -= carry[9] << 21 | ||
1556 | carry[11] = (s11 + (1 << 20)) >> 21 | ||
1557 | s12 += carry[11] | ||
1558 | s11 -= carry[11] << 21 | ||
1559 | carry[13] = (s13 + (1 << 20)) >> 21 | ||
1560 | s14 += carry[13] | ||
1561 | s13 -= carry[13] << 21 | ||
1562 | carry[15] = (s15 + (1 << 20)) >> 21 | ||
1563 | s16 += carry[15] | ||
1564 | s15 -= carry[15] << 21 | ||
1565 | |||
1566 | s5 += s17 * 666643 | ||
1567 | s6 += s17 * 470296 | ||
1568 | s7 += s17 * 654183 | ||
1569 | s8 -= s17 * 997805 | ||
1570 | s9 += s17 * 136657 | ||
1571 | s10 -= s17 * 683901 | ||
1572 | s17 = 0 | ||
1573 | |||
1574 | s4 += s16 * 666643 | ||
1575 | s5 += s16 * 470296 | ||
1576 | s6 += s16 * 654183 | ||
1577 | s7 -= s16 * 997805 | ||
1578 | s8 += s16 * 136657 | ||
1579 | s9 -= s16 * 683901 | ||
1580 | s16 = 0 | ||
1581 | |||
1582 | s3 += s15 * 666643 | ||
1583 | s4 += s15 * 470296 | ||
1584 | s5 += s15 * 654183 | ||
1585 | s6 -= s15 * 997805 | ||
1586 | s7 += s15 * 136657 | ||
1587 | s8 -= s15 * 683901 | ||
1588 | s15 = 0 | ||
1589 | |||
1590 | s2 += s14 * 666643 | ||
1591 | s3 += s14 * 470296 | ||
1592 | s4 += s14 * 654183 | ||
1593 | s5 -= s14 * 997805 | ||
1594 | s6 += s14 * 136657 | ||
1595 | s7 -= s14 * 683901 | ||
1596 | s14 = 0 | ||
1597 | |||
1598 | s1 += s13 * 666643 | ||
1599 | s2 += s13 * 470296 | ||
1600 | s3 += s13 * 654183 | ||
1601 | s4 -= s13 * 997805 | ||
1602 | s5 += s13 * 136657 | ||
1603 | s6 -= s13 * 683901 | ||
1604 | s13 = 0 | ||
1605 | |||
1606 | s0 += s12 * 666643 | ||
1607 | s1 += s12 * 470296 | ||
1608 | s2 += s12 * 654183 | ||
1609 | s3 -= s12 * 997805 | ||
1610 | s4 += s12 * 136657 | ||
1611 | s5 -= s12 * 683901 | ||
1612 | s12 = 0 | ||
1613 | |||
1614 | carry[0] = (s0 + (1 << 20)) >> 21 | ||
1615 | s1 += carry[0] | ||
1616 | s0 -= carry[0] << 21 | ||
1617 | carry[2] = (s2 + (1 << 20)) >> 21 | ||
1618 | s3 += carry[2] | ||
1619 | s2 -= carry[2] << 21 | ||
1620 | carry[4] = (s4 + (1 << 20)) >> 21 | ||
1621 | s5 += carry[4] | ||
1622 | s4 -= carry[4] << 21 | ||
1623 | carry[6] = (s6 + (1 << 20)) >> 21 | ||
1624 | s7 += carry[6] | ||
1625 | s6 -= carry[6] << 21 | ||
1626 | carry[8] = (s8 + (1 << 20)) >> 21 | ||
1627 | s9 += carry[8] | ||
1628 | s8 -= carry[8] << 21 | ||
1629 | carry[10] = (s10 + (1 << 20)) >> 21 | ||
1630 | s11 += carry[10] | ||
1631 | s10 -= carry[10] << 21 | ||
1632 | |||
1633 | carry[1] = (s1 + (1 << 20)) >> 21 | ||
1634 | s2 += carry[1] | ||
1635 | s1 -= carry[1] << 21 | ||
1636 | carry[3] = (s3 + (1 << 20)) >> 21 | ||
1637 | s4 += carry[3] | ||
1638 | s3 -= carry[3] << 21 | ||
1639 | carry[5] = (s5 + (1 << 20)) >> 21 | ||
1640 | s6 += carry[5] | ||
1641 | s5 -= carry[5] << 21 | ||
1642 | carry[7] = (s7 + (1 << 20)) >> 21 | ||
1643 | s8 += carry[7] | ||
1644 | s7 -= carry[7] << 21 | ||
1645 | carry[9] = (s9 + (1 << 20)) >> 21 | ||
1646 | s10 += carry[9] | ||
1647 | s9 -= carry[9] << 21 | ||
1648 | carry[11] = (s11 + (1 << 20)) >> 21 | ||
1649 | s12 += carry[11] | ||
1650 | s11 -= carry[11] << 21 | ||
1651 | |||
1652 | s0 += s12 * 666643 | ||
1653 | s1 += s12 * 470296 | ||
1654 | s2 += s12 * 654183 | ||
1655 | s3 -= s12 * 997805 | ||
1656 | s4 += s12 * 136657 | ||
1657 | s5 -= s12 * 683901 | ||
1658 | s12 = 0 | ||
1659 | |||
1660 | carry[0] = s0 >> 21 | ||
1661 | s1 += carry[0] | ||
1662 | s0 -= carry[0] << 21 | ||
1663 | carry[1] = s1 >> 21 | ||
1664 | s2 += carry[1] | ||
1665 | s1 -= carry[1] << 21 | ||
1666 | carry[2] = s2 >> 21 | ||
1667 | s3 += carry[2] | ||
1668 | s2 -= carry[2] << 21 | ||
1669 | carry[3] = s3 >> 21 | ||
1670 | s4 += carry[3] | ||
1671 | s3 -= carry[3] << 21 | ||
1672 | carry[4] = s4 >> 21 | ||
1673 | s5 += carry[4] | ||
1674 | s4 -= carry[4] << 21 | ||
1675 | carry[5] = s5 >> 21 | ||
1676 | s6 += carry[5] | ||
1677 | s5 -= carry[5] << 21 | ||
1678 | carry[6] = s6 >> 21 | ||
1679 | s7 += carry[6] | ||
1680 | s6 -= carry[6] << 21 | ||
1681 | carry[7] = s7 >> 21 | ||
1682 | s8 += carry[7] | ||
1683 | s7 -= carry[7] << 21 | ||
1684 | carry[8] = s8 >> 21 | ||
1685 | s9 += carry[8] | ||
1686 | s8 -= carry[8] << 21 | ||
1687 | carry[9] = s9 >> 21 | ||
1688 | s10 += carry[9] | ||
1689 | s9 -= carry[9] << 21 | ||
1690 | carry[10] = s10 >> 21 | ||
1691 | s11 += carry[10] | ||
1692 | s10 -= carry[10] << 21 | ||
1693 | carry[11] = s11 >> 21 | ||
1694 | s12 += carry[11] | ||
1695 | s11 -= carry[11] << 21 | ||
1696 | |||
1697 | s0 += s12 * 666643 | ||
1698 | s1 += s12 * 470296 | ||
1699 | s2 += s12 * 654183 | ||
1700 | s3 -= s12 * 997805 | ||
1701 | s4 += s12 * 136657 | ||
1702 | s5 -= s12 * 683901 | ||
1703 | s12 = 0 | ||
1704 | |||
1705 | carry[0] = s0 >> 21 | ||
1706 | s1 += carry[0] | ||
1707 | s0 -= carry[0] << 21 | ||
1708 | carry[1] = s1 >> 21 | ||
1709 | s2 += carry[1] | ||
1710 | s1 -= carry[1] << 21 | ||
1711 | carry[2] = s2 >> 21 | ||
1712 | s3 += carry[2] | ||
1713 | s2 -= carry[2] << 21 | ||
1714 | carry[3] = s3 >> 21 | ||
1715 | s4 += carry[3] | ||
1716 | s3 -= carry[3] << 21 | ||
1717 | carry[4] = s4 >> 21 | ||
1718 | s5 += carry[4] | ||
1719 | s4 -= carry[4] << 21 | ||
1720 | carry[5] = s5 >> 21 | ||
1721 | s6 += carry[5] | ||
1722 | s5 -= carry[5] << 21 | ||
1723 | carry[6] = s6 >> 21 | ||
1724 | s7 += carry[6] | ||
1725 | s6 -= carry[6] << 21 | ||
1726 | carry[7] = s7 >> 21 | ||
1727 | s8 += carry[7] | ||
1728 | s7 -= carry[7] << 21 | ||
1729 | carry[8] = s8 >> 21 | ||
1730 | s9 += carry[8] | ||
1731 | s8 -= carry[8] << 21 | ||
1732 | carry[9] = s9 >> 21 | ||
1733 | s10 += carry[9] | ||
1734 | s9 -= carry[9] << 21 | ||
1735 | carry[10] = s10 >> 21 | ||
1736 | s11 += carry[10] | ||
1737 | s10 -= carry[10] << 21 | ||
1738 | |||
1739 | out[0] = byte(s0 >> 0) | ||
1740 | out[1] = byte(s0 >> 8) | ||
1741 | out[2] = byte((s0 >> 16) | (s1 << 5)) | ||
1742 | out[3] = byte(s1 >> 3) | ||
1743 | out[4] = byte(s1 >> 11) | ||
1744 | out[5] = byte((s1 >> 19) | (s2 << 2)) | ||
1745 | out[6] = byte(s2 >> 6) | ||
1746 | out[7] = byte((s2 >> 14) | (s3 << 7)) | ||
1747 | out[8] = byte(s3 >> 1) | ||
1748 | out[9] = byte(s3 >> 9) | ||
1749 | out[10] = byte((s3 >> 17) | (s4 << 4)) | ||
1750 | out[11] = byte(s4 >> 4) | ||
1751 | out[12] = byte(s4 >> 12) | ||
1752 | out[13] = byte((s4 >> 20) | (s5 << 1)) | ||
1753 | out[14] = byte(s5 >> 7) | ||
1754 | out[15] = byte((s5 >> 15) | (s6 << 6)) | ||
1755 | out[16] = byte(s6 >> 2) | ||
1756 | out[17] = byte(s6 >> 10) | ||
1757 | out[18] = byte((s6 >> 18) | (s7 << 3)) | ||
1758 | out[19] = byte(s7 >> 5) | ||
1759 | out[20] = byte(s7 >> 13) | ||
1760 | out[21] = byte(s8 >> 0) | ||
1761 | out[22] = byte(s8 >> 8) | ||
1762 | out[23] = byte((s8 >> 16) | (s9 << 5)) | ||
1763 | out[24] = byte(s9 >> 3) | ||
1764 | out[25] = byte(s9 >> 11) | ||
1765 | out[26] = byte((s9 >> 19) | (s10 << 2)) | ||
1766 | out[27] = byte(s10 >> 6) | ||
1767 | out[28] = byte((s10 >> 14) | (s11 << 7)) | ||
1768 | out[29] = byte(s11 >> 1) | ||
1769 | out[30] = byte(s11 >> 9) | ||
1770 | out[31] = byte(s11 >> 17) | ||
1771 | } | ||