← Back to branch summary

~juju-qa/ubuntu/xenial/juju/2.0-rc2

« back to all changes in this revision

Viewing changes to src/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go

  • Committer: Nicholas Skaggs
  • Date: 2016-09-30 14:39:30 UTC
  • mfrom: (1.8.1)
  • Revision ID: nicholas.skaggs@canonical.com-20160930143930-vwwhrefh6ftckccy
import upstream

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/golang.org/x/crypto/ed25519/internal/edwards25519/edwards25519.go
 
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
}