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