]>
Commit | Line | Data |
---|---|---|
bae9f6d2 JC |
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 | } |