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