1
2
3
4
5 package edwards25519
6
7 import (
8 "crypto/subtle"
9 "encoding/binary"
10 "errors"
11 )
12
13
14
15
16
17
18
19
20
21
22
23 type Scalar struct {
24
25
26 s [32]byte
27 }
28
29 var (
30 scZero = Scalar{[32]byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
31
32 scOne = Scalar{[32]byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}
33
34 scMinusOne = Scalar{[32]byte{236, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16}}
35 )
36
37
38 func NewScalar() *Scalar {
39 return &Scalar{}
40 }
41
42
43 func (s *Scalar) MultiplyAdd(x, y, z *Scalar) *Scalar {
44 scMulAdd(&s.s, &x.s, &y.s, &z.s)
45 return s
46 }
47
48
49 func (s *Scalar) Add(x, y *Scalar) *Scalar {
50
51 scMulAdd(&s.s, &scOne.s, &x.s, &y.s)
52 return s
53 }
54
55
56 func (s *Scalar) Subtract(x, y *Scalar) *Scalar {
57
58 scMulAdd(&s.s, &scMinusOne.s, &y.s, &x.s)
59 return s
60 }
61
62
63 func (s *Scalar) Negate(x *Scalar) *Scalar {
64
65 scMulAdd(&s.s, &scMinusOne.s, &x.s, &scZero.s)
66 return s
67 }
68
69
70 func (s *Scalar) Multiply(x, y *Scalar) *Scalar {
71
72 scMulAdd(&s.s, &x.s, &y.s, &scZero.s)
73 return s
74 }
75
76
77 func (s *Scalar) Set(x *Scalar) *Scalar {
78 *s = *x
79 return s
80 }
81
82
83
84 func (s *Scalar) SetUniformBytes(x []byte) *Scalar {
85 if len(x) != 64 {
86 panic("edwards25519: invalid SetUniformBytes input length")
87 }
88 var wideBytes [64]byte
89 copy(wideBytes[:], x[:])
90 scReduce(&s.s, &wideBytes)
91 return s
92 }
93
94
95
96
97 func (s *Scalar) SetCanonicalBytes(x []byte) (*Scalar, error) {
98 if len(x) != 32 {
99 return nil, errors.New("invalid scalar length")
100 }
101 ss := &Scalar{}
102 copy(ss.s[:], x)
103 if !isReduced(ss) {
104 return nil, errors.New("invalid scalar encoding")
105 }
106 s.s = ss.s
107 return s, nil
108 }
109
110
111 func isReduced(s *Scalar) bool {
112 for i := len(s.s) - 1; i >= 0; i-- {
113 switch {
114 case s.s[i] > scMinusOne.s[i]:
115 return false
116 case s.s[i] < scMinusOne.s[i]:
117 return true
118 }
119 }
120 return true
121 }
122
123
124
125
126
127
128
129
130
131
132
133 func (s *Scalar) SetBytesWithClamping(x []byte) *Scalar {
134
135
136
137
138 if len(x) != 32 {
139 panic("edwards25519: invalid SetBytesWithClamping input length")
140 }
141 var wideBytes [64]byte
142 copy(wideBytes[:], x[:])
143 wideBytes[0] &= 248
144 wideBytes[31] &= 63
145 wideBytes[31] |= 64
146 scReduce(&s.s, &wideBytes)
147 return s
148 }
149
150
151 func (s *Scalar) Bytes() []byte {
152 buf := make([]byte, 32)
153 copy(buf, s.s[:])
154 return buf
155 }
156
157
158 func (s *Scalar) Equal(t *Scalar) int {
159 return subtle.ConstantTimeCompare(s.s[:], t.s[:])
160 }
161
162
163
164
165 func load3(in []byte) int64 {
166 r := int64(in[0])
167 r |= int64(in[1]) << 8
168 r |= int64(in[2]) << 16
169 return r
170 }
171
172 func load4(in []byte) int64 {
173 r := int64(in[0])
174 r |= int64(in[1]) << 8
175 r |= int64(in[2]) << 16
176 r |= int64(in[3]) << 24
177 return r
178 }
179
180
181
182
183
184
185
186
187
188 func scMulAdd(s, a, b, c *[32]byte) {
189 a0 := 2097151 & load3(a[:])
190 a1 := 2097151 & (load4(a[2:]) >> 5)
191 a2 := 2097151 & (load3(a[5:]) >> 2)
192 a3 := 2097151 & (load4(a[7:]) >> 7)
193 a4 := 2097151 & (load4(a[10:]) >> 4)
194 a5 := 2097151 & (load3(a[13:]) >> 1)
195 a6 := 2097151 & (load4(a[15:]) >> 6)
196 a7 := 2097151 & (load3(a[18:]) >> 3)
197 a8 := 2097151 & load3(a[21:])
198 a9 := 2097151 & (load4(a[23:]) >> 5)
199 a10 := 2097151 & (load3(a[26:]) >> 2)
200 a11 := (load4(a[28:]) >> 7)
201 b0 := 2097151 & load3(b[:])
202 b1 := 2097151 & (load4(b[2:]) >> 5)
203 b2 := 2097151 & (load3(b[5:]) >> 2)
204 b3 := 2097151 & (load4(b[7:]) >> 7)
205 b4 := 2097151 & (load4(b[10:]) >> 4)
206 b5 := 2097151 & (load3(b[13:]) >> 1)
207 b6 := 2097151 & (load4(b[15:]) >> 6)
208 b7 := 2097151 & (load3(b[18:]) >> 3)
209 b8 := 2097151 & load3(b[21:])
210 b9 := 2097151 & (load4(b[23:]) >> 5)
211 b10 := 2097151 & (load3(b[26:]) >> 2)
212 b11 := (load4(b[28:]) >> 7)
213 c0 := 2097151 & load3(c[:])
214 c1 := 2097151 & (load4(c[2:]) >> 5)
215 c2 := 2097151 & (load3(c[5:]) >> 2)
216 c3 := 2097151 & (load4(c[7:]) >> 7)
217 c4 := 2097151 & (load4(c[10:]) >> 4)
218 c5 := 2097151 & (load3(c[13:]) >> 1)
219 c6 := 2097151 & (load4(c[15:]) >> 6)
220 c7 := 2097151 & (load3(c[18:]) >> 3)
221 c8 := 2097151 & load3(c[21:])
222 c9 := 2097151 & (load4(c[23:]) >> 5)
223 c10 := 2097151 & (load3(c[26:]) >> 2)
224 c11 := (load4(c[28:]) >> 7)
225 var carry [23]int64
226
227 s0 := c0 + a0*b0
228 s1 := c1 + a0*b1 + a1*b0
229 s2 := c2 + a0*b2 + a1*b1 + a2*b0
230 s3 := c3 + a0*b3 + a1*b2 + a2*b1 + a3*b0
231 s4 := c4 + a0*b4 + a1*b3 + a2*b2 + a3*b1 + a4*b0
232 s5 := c5 + a0*b5 + a1*b4 + a2*b3 + a3*b2 + a4*b1 + a5*b0
233 s6 := c6 + a0*b6 + a1*b5 + a2*b4 + a3*b3 + a4*b2 + a5*b1 + a6*b0
234 s7 := c7 + a0*b7 + a1*b6 + a2*b5 + a3*b4 + a4*b3 + a5*b2 + a6*b1 + a7*b0
235 s8 := c8 + a0*b8 + a1*b7 + a2*b6 + a3*b5 + a4*b4 + a5*b3 + a6*b2 + a7*b1 + a8*b0
236 s9 := c9 + a0*b9 + a1*b8 + a2*b7 + a3*b6 + a4*b5 + a5*b4 + a6*b3 + a7*b2 + a8*b1 + a9*b0
237 s10 := c10 + a0*b10 + a1*b9 + a2*b8 + a3*b7 + a4*b6 + a5*b5 + a6*b4 + a7*b3 + a8*b2 + a9*b1 + a10*b0
238 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
239 s12 := a1*b11 + a2*b10 + a3*b9 + a4*b8 + a5*b7 + a6*b6 + a7*b5 + a8*b4 + a9*b3 + a10*b2 + a11*b1
240 s13 := a2*b11 + a3*b10 + a4*b9 + a5*b8 + a6*b7 + a7*b6 + a8*b5 + a9*b4 + a10*b3 + a11*b2
241 s14 := a3*b11 + a4*b10 + a5*b9 + a6*b8 + a7*b7 + a8*b6 + a9*b5 + a10*b4 + a11*b3
242 s15 := a4*b11 + a5*b10 + a6*b9 + a7*b8 + a8*b7 + a9*b6 + a10*b5 + a11*b4
243 s16 := a5*b11 + a6*b10 + a7*b9 + a8*b8 + a9*b7 + a10*b6 + a11*b5
244 s17 := a6*b11 + a7*b10 + a8*b9 + a9*b8 + a10*b7 + a11*b6
245 s18 := a7*b11 + a8*b10 + a9*b9 + a10*b8 + a11*b7
246 s19 := a8*b11 + a9*b10 + a10*b9 + a11*b8
247 s20 := a9*b11 + a10*b10 + a11*b9
248 s21 := a10*b11 + a11*b10
249 s22 := a11 * b11
250 s23 := int64(0)
251
252 carry[0] = (s0 + (1 << 20)) >> 21
253 s1 += carry[0]
254 s0 -= carry[0] << 21
255 carry[2] = (s2 + (1 << 20)) >> 21
256 s3 += carry[2]
257 s2 -= carry[2] << 21
258 carry[4] = (s4 + (1 << 20)) >> 21
259 s5 += carry[4]
260 s4 -= carry[4] << 21
261 carry[6] = (s6 + (1 << 20)) >> 21
262 s7 += carry[6]
263 s6 -= carry[6] << 21
264 carry[8] = (s8 + (1 << 20)) >> 21
265 s9 += carry[8]
266 s8 -= carry[8] << 21
267 carry[10] = (s10 + (1 << 20)) >> 21
268 s11 += carry[10]
269 s10 -= carry[10] << 21
270 carry[12] = (s12 + (1 << 20)) >> 21
271 s13 += carry[12]
272 s12 -= carry[12] << 21
273 carry[14] = (s14 + (1 << 20)) >> 21
274 s15 += carry[14]
275 s14 -= carry[14] << 21
276 carry[16] = (s16 + (1 << 20)) >> 21
277 s17 += carry[16]
278 s16 -= carry[16] << 21
279 carry[18] = (s18 + (1 << 20)) >> 21
280 s19 += carry[18]
281 s18 -= carry[18] << 21
282 carry[20] = (s20 + (1 << 20)) >> 21
283 s21 += carry[20]
284 s20 -= carry[20] << 21
285 carry[22] = (s22 + (1 << 20)) >> 21
286 s23 += carry[22]
287 s22 -= carry[22] << 21
288
289 carry[1] = (s1 + (1 << 20)) >> 21
290 s2 += carry[1]
291 s1 -= carry[1] << 21
292 carry[3] = (s3 + (1 << 20)) >> 21
293 s4 += carry[3]
294 s3 -= carry[3] << 21
295 carry[5] = (s5 + (1 << 20)) >> 21
296 s6 += carry[5]
297 s5 -= carry[5] << 21
298 carry[7] = (s7 + (1 << 20)) >> 21
299 s8 += carry[7]
300 s7 -= carry[7] << 21
301 carry[9] = (s9 + (1 << 20)) >> 21
302 s10 += carry[9]
303 s9 -= carry[9] << 21
304 carry[11] = (s11 + (1 << 20)) >> 21
305 s12 += carry[11]
306 s11 -= carry[11] << 21
307 carry[13] = (s13 + (1 << 20)) >> 21
308 s14 += carry[13]
309 s13 -= carry[13] << 21
310 carry[15] = (s15 + (1 << 20)) >> 21
311 s16 += carry[15]
312 s15 -= carry[15] << 21
313 carry[17] = (s17 + (1 << 20)) >> 21
314 s18 += carry[17]
315 s17 -= carry[17] << 21
316 carry[19] = (s19 + (1 << 20)) >> 21
317 s20 += carry[19]
318 s19 -= carry[19] << 21
319 carry[21] = (s21 + (1 << 20)) >> 21
320 s22 += carry[21]
321 s21 -= carry[21] << 21
322
323 s11 += s23 * 666643
324 s12 += s23 * 470296
325 s13 += s23 * 654183
326 s14 -= s23 * 997805
327 s15 += s23 * 136657
328 s16 -= s23 * 683901
329 s23 = 0
330
331 s10 += s22 * 666643
332 s11 += s22 * 470296
333 s12 += s22 * 654183
334 s13 -= s22 * 997805
335 s14 += s22 * 136657
336 s15 -= s22 * 683901
337 s22 = 0
338
339 s9 += s21 * 666643
340 s10 += s21 * 470296
341 s11 += s21 * 654183
342 s12 -= s21 * 997805
343 s13 += s21 * 136657
344 s14 -= s21 * 683901
345 s21 = 0
346
347 s8 += s20 * 666643
348 s9 += s20 * 470296
349 s10 += s20 * 654183
350 s11 -= s20 * 997805
351 s12 += s20 * 136657
352 s13 -= s20 * 683901
353 s20 = 0
354
355 s7 += s19 * 666643
356 s8 += s19 * 470296
357 s9 += s19 * 654183
358 s10 -= s19 * 997805
359 s11 += s19 * 136657
360 s12 -= s19 * 683901
361 s19 = 0
362
363 s6 += s18 * 666643
364 s7 += s18 * 470296
365 s8 += s18 * 654183
366 s9 -= s18 * 997805
367 s10 += s18 * 136657
368 s11 -= s18 * 683901
369 s18 = 0
370
371 carry[6] = (s6 + (1 << 20)) >> 21
372 s7 += carry[6]
373 s6 -= carry[6] << 21
374 carry[8] = (s8 + (1 << 20)) >> 21
375 s9 += carry[8]
376 s8 -= carry[8] << 21
377 carry[10] = (s10 + (1 << 20)) >> 21
378 s11 += carry[10]
379 s10 -= carry[10] << 21
380 carry[12] = (s12 + (1 << 20)) >> 21
381 s13 += carry[12]
382 s12 -= carry[12] << 21
383 carry[14] = (s14 + (1 << 20)) >> 21
384 s15 += carry[14]
385 s14 -= carry[14] << 21
386 carry[16] = (s16 + (1 << 20)) >> 21
387 s17 += carry[16]
388 s16 -= carry[16] << 21
389
390 carry[7] = (s7 + (1 << 20)) >> 21
391 s8 += carry[7]
392 s7 -= carry[7] << 21
393 carry[9] = (s9 + (1 << 20)) >> 21
394 s10 += carry[9]
395 s9 -= carry[9] << 21
396 carry[11] = (s11 + (1 << 20)) >> 21
397 s12 += carry[11]
398 s11 -= carry[11] << 21
399 carry[13] = (s13 + (1 << 20)) >> 21
400 s14 += carry[13]
401 s13 -= carry[13] << 21
402 carry[15] = (s15 + (1 << 20)) >> 21
403 s16 += carry[15]
404 s15 -= carry[15] << 21
405
406 s5 += s17 * 666643
407 s6 += s17 * 470296
408 s7 += s17 * 654183
409 s8 -= s17 * 997805
410 s9 += s17 * 136657
411 s10 -= s17 * 683901
412 s17 = 0
413
414 s4 += s16 * 666643
415 s5 += s16 * 470296
416 s6 += s16 * 654183
417 s7 -= s16 * 997805
418 s8 += s16 * 136657
419 s9 -= s16 * 683901
420 s16 = 0
421
422 s3 += s15 * 666643
423 s4 += s15 * 470296
424 s5 += s15 * 654183
425 s6 -= s15 * 997805
426 s7 += s15 * 136657
427 s8 -= s15 * 683901
428 s15 = 0
429
430 s2 += s14 * 666643
431 s3 += s14 * 470296
432 s4 += s14 * 654183
433 s5 -= s14 * 997805
434 s6 += s14 * 136657
435 s7 -= s14 * 683901
436 s14 = 0
437
438 s1 += s13 * 666643
439 s2 += s13 * 470296
440 s3 += s13 * 654183
441 s4 -= s13 * 997805
442 s5 += s13 * 136657
443 s6 -= s13 * 683901
444 s13 = 0
445
446 s0 += s12 * 666643
447 s1 += s12 * 470296
448 s2 += s12 * 654183
449 s3 -= s12 * 997805
450 s4 += s12 * 136657
451 s5 -= s12 * 683901
452 s12 = 0
453
454 carry[0] = (s0 + (1 << 20)) >> 21
455 s1 += carry[0]
456 s0 -= carry[0] << 21
457 carry[2] = (s2 + (1 << 20)) >> 21
458 s3 += carry[2]
459 s2 -= carry[2] << 21
460 carry[4] = (s4 + (1 << 20)) >> 21
461 s5 += carry[4]
462 s4 -= carry[4] << 21
463 carry[6] = (s6 + (1 << 20)) >> 21
464 s7 += carry[6]
465 s6 -= carry[6] << 21
466 carry[8] = (s8 + (1 << 20)) >> 21
467 s9 += carry[8]
468 s8 -= carry[8] << 21
469 carry[10] = (s10 + (1 << 20)) >> 21
470 s11 += carry[10]
471 s10 -= carry[10] << 21
472
473 carry[1] = (s1 + (1 << 20)) >> 21
474 s2 += carry[1]
475 s1 -= carry[1] << 21
476 carry[3] = (s3 + (1 << 20)) >> 21
477 s4 += carry[3]
478 s3 -= carry[3] << 21
479 carry[5] = (s5 + (1 << 20)) >> 21
480 s6 += carry[5]
481 s5 -= carry[5] << 21
482 carry[7] = (s7 + (1 << 20)) >> 21
483 s8 += carry[7]
484 s7 -= carry[7] << 21
485 carry[9] = (s9 + (1 << 20)) >> 21
486 s10 += carry[9]
487 s9 -= carry[9] << 21
488 carry[11] = (s11 + (1 << 20)) >> 21
489 s12 += carry[11]
490 s11 -= carry[11] << 21
491
492 s0 += s12 * 666643
493 s1 += s12 * 470296
494 s2 += s12 * 654183
495 s3 -= s12 * 997805
496 s4 += s12 * 136657
497 s5 -= s12 * 683901
498 s12 = 0
499
500 carry[0] = s0 >> 21
501 s1 += carry[0]
502 s0 -= carry[0] << 21
503 carry[1] = s1 >> 21
504 s2 += carry[1]
505 s1 -= carry[1] << 21
506 carry[2] = s2 >> 21
507 s3 += carry[2]
508 s2 -= carry[2] << 21
509 carry[3] = s3 >> 21
510 s4 += carry[3]
511 s3 -= carry[3] << 21
512 carry[4] = s4 >> 21
513 s5 += carry[4]
514 s4 -= carry[4] << 21
515 carry[5] = s5 >> 21
516 s6 += carry[5]
517 s5 -= carry[5] << 21
518 carry[6] = s6 >> 21
519 s7 += carry[6]
520 s6 -= carry[6] << 21
521 carry[7] = s7 >> 21
522 s8 += carry[7]
523 s7 -= carry[7] << 21
524 carry[8] = s8 >> 21
525 s9 += carry[8]
526 s8 -= carry[8] << 21
527 carry[9] = s9 >> 21
528 s10 += carry[9]
529 s9 -= carry[9] << 21
530 carry[10] = s10 >> 21
531 s11 += carry[10]
532 s10 -= carry[10] << 21
533 carry[11] = s11 >> 21
534 s12 += carry[11]
535 s11 -= carry[11] << 21
536
537 s0 += s12 * 666643
538 s1 += s12 * 470296
539 s2 += s12 * 654183
540 s3 -= s12 * 997805
541 s4 += s12 * 136657
542 s5 -= s12 * 683901
543 s12 = 0
544
545 carry[0] = s0 >> 21
546 s1 += carry[0]
547 s0 -= carry[0] << 21
548 carry[1] = s1 >> 21
549 s2 += carry[1]
550 s1 -= carry[1] << 21
551 carry[2] = s2 >> 21
552 s3 += carry[2]
553 s2 -= carry[2] << 21
554 carry[3] = s3 >> 21
555 s4 += carry[3]
556 s3 -= carry[3] << 21
557 carry[4] = s4 >> 21
558 s5 += carry[4]
559 s4 -= carry[4] << 21
560 carry[5] = s5 >> 21
561 s6 += carry[5]
562 s5 -= carry[5] << 21
563 carry[6] = s6 >> 21
564 s7 += carry[6]
565 s6 -= carry[6] << 21
566 carry[7] = s7 >> 21
567 s8 += carry[7]
568 s7 -= carry[7] << 21
569 carry[8] = s8 >> 21
570 s9 += carry[8]
571 s8 -= carry[8] << 21
572 carry[9] = s9 >> 21
573 s10 += carry[9]
574 s9 -= carry[9] << 21
575 carry[10] = s10 >> 21
576 s11 += carry[10]
577 s10 -= carry[10] << 21
578
579 s[0] = byte(s0 >> 0)
580 s[1] = byte(s0 >> 8)
581 s[2] = byte((s0 >> 16) | (s1 << 5))
582 s[3] = byte(s1 >> 3)
583 s[4] = byte(s1 >> 11)
584 s[5] = byte((s1 >> 19) | (s2 << 2))
585 s[6] = byte(s2 >> 6)
586 s[7] = byte((s2 >> 14) | (s3 << 7))
587 s[8] = byte(s3 >> 1)
588 s[9] = byte(s3 >> 9)
589 s[10] = byte((s3 >> 17) | (s4 << 4))
590 s[11] = byte(s4 >> 4)
591 s[12] = byte(s4 >> 12)
592 s[13] = byte((s4 >> 20) | (s5 << 1))
593 s[14] = byte(s5 >> 7)
594 s[15] = byte((s5 >> 15) | (s6 << 6))
595 s[16] = byte(s6 >> 2)
596 s[17] = byte(s6 >> 10)
597 s[18] = byte((s6 >> 18) | (s7 << 3))
598 s[19] = byte(s7 >> 5)
599 s[20] = byte(s7 >> 13)
600 s[21] = byte(s8 >> 0)
601 s[22] = byte(s8 >> 8)
602 s[23] = byte((s8 >> 16) | (s9 << 5))
603 s[24] = byte(s9 >> 3)
604 s[25] = byte(s9 >> 11)
605 s[26] = byte((s9 >> 19) | (s10 << 2))
606 s[27] = byte(s10 >> 6)
607 s[28] = byte((s10 >> 14) | (s11 << 7))
608 s[29] = byte(s11 >> 1)
609 s[30] = byte(s11 >> 9)
610 s[31] = byte(s11 >> 17)
611 }
612
613
614
615
616
617
618
619 func scReduce(out *[32]byte, s *[64]byte) {
620 s0 := 2097151 & load3(s[:])
621 s1 := 2097151 & (load4(s[2:]) >> 5)
622 s2 := 2097151 & (load3(s[5:]) >> 2)
623 s3 := 2097151 & (load4(s[7:]) >> 7)
624 s4 := 2097151 & (load4(s[10:]) >> 4)
625 s5 := 2097151 & (load3(s[13:]) >> 1)
626 s6 := 2097151 & (load4(s[15:]) >> 6)
627 s7 := 2097151 & (load3(s[18:]) >> 3)
628 s8 := 2097151 & load3(s[21:])
629 s9 := 2097151 & (load4(s[23:]) >> 5)
630 s10 := 2097151 & (load3(s[26:]) >> 2)
631 s11 := 2097151 & (load4(s[28:]) >> 7)
632 s12 := 2097151 & (load4(s[31:]) >> 4)
633 s13 := 2097151 & (load3(s[34:]) >> 1)
634 s14 := 2097151 & (load4(s[36:]) >> 6)
635 s15 := 2097151 & (load3(s[39:]) >> 3)
636 s16 := 2097151 & load3(s[42:])
637 s17 := 2097151 & (load4(s[44:]) >> 5)
638 s18 := 2097151 & (load3(s[47:]) >> 2)
639 s19 := 2097151 & (load4(s[49:]) >> 7)
640 s20 := 2097151 & (load4(s[52:]) >> 4)
641 s21 := 2097151 & (load3(s[55:]) >> 1)
642 s22 := 2097151 & (load4(s[57:]) >> 6)
643 s23 := (load4(s[60:]) >> 3)
644
645 s11 += s23 * 666643
646 s12 += s23 * 470296
647 s13 += s23 * 654183
648 s14 -= s23 * 997805
649 s15 += s23 * 136657
650 s16 -= s23 * 683901
651 s23 = 0
652
653 s10 += s22 * 666643
654 s11 += s22 * 470296
655 s12 += s22 * 654183
656 s13 -= s22 * 997805
657 s14 += s22 * 136657
658 s15 -= s22 * 683901
659 s22 = 0
660
661 s9 += s21 * 666643
662 s10 += s21 * 470296
663 s11 += s21 * 654183
664 s12 -= s21 * 997805
665 s13 += s21 * 136657
666 s14 -= s21 * 683901
667 s21 = 0
668
669 s8 += s20 * 666643
670 s9 += s20 * 470296
671 s10 += s20 * 654183
672 s11 -= s20 * 997805
673 s12 += s20 * 136657
674 s13 -= s20 * 683901
675 s20 = 0
676
677 s7 += s19 * 666643
678 s8 += s19 * 470296
679 s9 += s19 * 654183
680 s10 -= s19 * 997805
681 s11 += s19 * 136657
682 s12 -= s19 * 683901
683 s19 = 0
684
685 s6 += s18 * 666643
686 s7 += s18 * 470296
687 s8 += s18 * 654183
688 s9 -= s18 * 997805
689 s10 += s18 * 136657
690 s11 -= s18 * 683901
691 s18 = 0
692
693 var carry [17]int64
694
695 carry[6] = (s6 + (1 << 20)) >> 21
696 s7 += carry[6]
697 s6 -= carry[6] << 21
698 carry[8] = (s8 + (1 << 20)) >> 21
699 s9 += carry[8]
700 s8 -= carry[8] << 21
701 carry[10] = (s10 + (1 << 20)) >> 21
702 s11 += carry[10]
703 s10 -= carry[10] << 21
704 carry[12] = (s12 + (1 << 20)) >> 21
705 s13 += carry[12]
706 s12 -= carry[12] << 21
707 carry[14] = (s14 + (1 << 20)) >> 21
708 s15 += carry[14]
709 s14 -= carry[14] << 21
710 carry[16] = (s16 + (1 << 20)) >> 21
711 s17 += carry[16]
712 s16 -= carry[16] << 21
713
714 carry[7] = (s7 + (1 << 20)) >> 21
715 s8 += carry[7]
716 s7 -= carry[7] << 21
717 carry[9] = (s9 + (1 << 20)) >> 21
718 s10 += carry[9]
719 s9 -= carry[9] << 21
720 carry[11] = (s11 + (1 << 20)) >> 21
721 s12 += carry[11]
722 s11 -= carry[11] << 21
723 carry[13] = (s13 + (1 << 20)) >> 21
724 s14 += carry[13]
725 s13 -= carry[13] << 21
726 carry[15] = (s15 + (1 << 20)) >> 21
727 s16 += carry[15]
728 s15 -= carry[15] << 21
729
730 s5 += s17 * 666643
731 s6 += s17 * 470296
732 s7 += s17 * 654183
733 s8 -= s17 * 997805
734 s9 += s17 * 136657
735 s10 -= s17 * 683901
736 s17 = 0
737
738 s4 += s16 * 666643
739 s5 += s16 * 470296
740 s6 += s16 * 654183
741 s7 -= s16 * 997805
742 s8 += s16 * 136657
743 s9 -= s16 * 683901
744 s16 = 0
745
746 s3 += s15 * 666643
747 s4 += s15 * 470296
748 s5 += s15 * 654183
749 s6 -= s15 * 997805
750 s7 += s15 * 136657
751 s8 -= s15 * 683901
752 s15 = 0
753
754 s2 += s14 * 666643
755 s3 += s14 * 470296
756 s4 += s14 * 654183
757 s5 -= s14 * 997805
758 s6 += s14 * 136657
759 s7 -= s14 * 683901
760 s14 = 0
761
762 s1 += s13 * 666643
763 s2 += s13 * 470296
764 s3 += s13 * 654183
765 s4 -= s13 * 997805
766 s5 += s13 * 136657
767 s6 -= s13 * 683901
768 s13 = 0
769
770 s0 += s12 * 666643
771 s1 += s12 * 470296
772 s2 += s12 * 654183
773 s3 -= s12 * 997805
774 s4 += s12 * 136657
775 s5 -= s12 * 683901
776 s12 = 0
777
778 carry[0] = (s0 + (1 << 20)) >> 21
779 s1 += carry[0]
780 s0 -= carry[0] << 21
781 carry[2] = (s2 + (1 << 20)) >> 21
782 s3 += carry[2]
783 s2 -= carry[2] << 21
784 carry[4] = (s4 + (1 << 20)) >> 21
785 s5 += carry[4]
786 s4 -= carry[4] << 21
787 carry[6] = (s6 + (1 << 20)) >> 21
788 s7 += carry[6]
789 s6 -= carry[6] << 21
790 carry[8] = (s8 + (1 << 20)) >> 21
791 s9 += carry[8]
792 s8 -= carry[8] << 21
793 carry[10] = (s10 + (1 << 20)) >> 21
794 s11 += carry[10]
795 s10 -= carry[10] << 21
796
797 carry[1] = (s1 + (1 << 20)) >> 21
798 s2 += carry[1]
799 s1 -= carry[1] << 21
800 carry[3] = (s3 + (1 << 20)) >> 21
801 s4 += carry[3]
802 s3 -= carry[3] << 21
803 carry[5] = (s5 + (1 << 20)) >> 21
804 s6 += carry[5]
805 s5 -= carry[5] << 21
806 carry[7] = (s7 + (1 << 20)) >> 21
807 s8 += carry[7]
808 s7 -= carry[7] << 21
809 carry[9] = (s9 + (1 << 20)) >> 21
810 s10 += carry[9]
811 s9 -= carry[9] << 21
812 carry[11] = (s11 + (1 << 20)) >> 21
813 s12 += carry[11]
814 s11 -= carry[11] << 21
815
816 s0 += s12 * 666643
817 s1 += s12 * 470296
818 s2 += s12 * 654183
819 s3 -= s12 * 997805
820 s4 += s12 * 136657
821 s5 -= s12 * 683901
822 s12 = 0
823
824 carry[0] = s0 >> 21
825 s1 += carry[0]
826 s0 -= carry[0] << 21
827 carry[1] = s1 >> 21
828 s2 += carry[1]
829 s1 -= carry[1] << 21
830 carry[2] = s2 >> 21
831 s3 += carry[2]
832 s2 -= carry[2] << 21
833 carry[3] = s3 >> 21
834 s4 += carry[3]
835 s3 -= carry[3] << 21
836 carry[4] = s4 >> 21
837 s5 += carry[4]
838 s4 -= carry[4] << 21
839 carry[5] = s5 >> 21
840 s6 += carry[5]
841 s5 -= carry[5] << 21
842 carry[6] = s6 >> 21
843 s7 += carry[6]
844 s6 -= carry[6] << 21
845 carry[7] = s7 >> 21
846 s8 += carry[7]
847 s7 -= carry[7] << 21
848 carry[8] = s8 >> 21
849 s9 += carry[8]
850 s8 -= carry[8] << 21
851 carry[9] = s9 >> 21
852 s10 += carry[9]
853 s9 -= carry[9] << 21
854 carry[10] = s10 >> 21
855 s11 += carry[10]
856 s10 -= carry[10] << 21
857 carry[11] = s11 >> 21
858 s12 += carry[11]
859 s11 -= carry[11] << 21
860
861 s0 += s12 * 666643
862 s1 += s12 * 470296
863 s2 += s12 * 654183
864 s3 -= s12 * 997805
865 s4 += s12 * 136657
866 s5 -= s12 * 683901
867 s12 = 0
868
869 carry[0] = s0 >> 21
870 s1 += carry[0]
871 s0 -= carry[0] << 21
872 carry[1] = s1 >> 21
873 s2 += carry[1]
874 s1 -= carry[1] << 21
875 carry[2] = s2 >> 21
876 s3 += carry[2]
877 s2 -= carry[2] << 21
878 carry[3] = s3 >> 21
879 s4 += carry[3]
880 s3 -= carry[3] << 21
881 carry[4] = s4 >> 21
882 s5 += carry[4]
883 s4 -= carry[4] << 21
884 carry[5] = s5 >> 21
885 s6 += carry[5]
886 s5 -= carry[5] << 21
887 carry[6] = s6 >> 21
888 s7 += carry[6]
889 s6 -= carry[6] << 21
890 carry[7] = s7 >> 21
891 s8 += carry[7]
892 s7 -= carry[7] << 21
893 carry[8] = s8 >> 21
894 s9 += carry[8]
895 s8 -= carry[8] << 21
896 carry[9] = s9 >> 21
897 s10 += carry[9]
898 s9 -= carry[9] << 21
899 carry[10] = s10 >> 21
900 s11 += carry[10]
901 s10 -= carry[10] << 21
902
903 out[0] = byte(s0 >> 0)
904 out[1] = byte(s0 >> 8)
905 out[2] = byte((s0 >> 16) | (s1 << 5))
906 out[3] = byte(s1 >> 3)
907 out[4] = byte(s1 >> 11)
908 out[5] = byte((s1 >> 19) | (s2 << 2))
909 out[6] = byte(s2 >> 6)
910 out[7] = byte((s2 >> 14) | (s3 << 7))
911 out[8] = byte(s3 >> 1)
912 out[9] = byte(s3 >> 9)
913 out[10] = byte((s3 >> 17) | (s4 << 4))
914 out[11] = byte(s4 >> 4)
915 out[12] = byte(s4 >> 12)
916 out[13] = byte((s4 >> 20) | (s5 << 1))
917 out[14] = byte(s5 >> 7)
918 out[15] = byte((s5 >> 15) | (s6 << 6))
919 out[16] = byte(s6 >> 2)
920 out[17] = byte(s6 >> 10)
921 out[18] = byte((s6 >> 18) | (s7 << 3))
922 out[19] = byte(s7 >> 5)
923 out[20] = byte(s7 >> 13)
924 out[21] = byte(s8 >> 0)
925 out[22] = byte(s8 >> 8)
926 out[23] = byte((s8 >> 16) | (s9 << 5))
927 out[24] = byte(s9 >> 3)
928 out[25] = byte(s9 >> 11)
929 out[26] = byte((s9 >> 19) | (s10 << 2))
930 out[27] = byte(s10 >> 6)
931 out[28] = byte((s10 >> 14) | (s11 << 7))
932 out[29] = byte(s11 >> 1)
933 out[30] = byte(s11 >> 9)
934 out[31] = byte(s11 >> 17)
935 }
936
937
938
939
940 func (s *Scalar) nonAdjacentForm(w uint) [256]int8 {
941
942
943
944 if s.s[31] > 127 {
945 panic("scalar has high bit set illegally")
946 }
947 if w < 2 {
948 panic("w must be at least 2 by the definition of NAF")
949 } else if w > 8 {
950 panic("NAF digits must fit in int8")
951 }
952
953 var naf [256]int8
954 var digits [5]uint64
955
956 for i := 0; i < 4; i++ {
957 digits[i] = binary.LittleEndian.Uint64(s.s[i*8:])
958 }
959
960 width := uint64(1 << w)
961 windowMask := uint64(width - 1)
962
963 pos := uint(0)
964 carry := uint64(0)
965 for pos < 256 {
966 indexU64 := pos / 64
967 indexBit := pos % 64
968 var bitBuf uint64
969 if indexBit < 64-w {
970
971 bitBuf = digits[indexU64] >> indexBit
972 } else {
973
974 bitBuf = (digits[indexU64] >> indexBit) | (digits[1+indexU64] << (64 - indexBit))
975 }
976
977
978 window := carry + (bitBuf & windowMask)
979
980 if window&1 == 0 {
981
982
983
984
985
986
987 pos += 1
988 continue
989 }
990
991 if window < width/2 {
992 carry = 0
993 naf[pos] = int8(window)
994 } else {
995 carry = 1
996 naf[pos] = int8(window) - int8(width)
997 }
998
999 pos += w
1000 }
1001 return naf
1002 }
1003
1004 func (s *Scalar) signedRadix16() [64]int8 {
1005 if s.s[31] > 127 {
1006 panic("scalar has high bit set illegally")
1007 }
1008
1009 var digits [64]int8
1010
1011
1012 for i := 0; i < 32; i++ {
1013 digits[2*i] = int8(s.s[i] & 15)
1014 digits[2*i+1] = int8((s.s[i] >> 4) & 15)
1015 }
1016
1017
1018 for i := 0; i < 63; i++ {
1019 carry := (digits[i] + 8) >> 4
1020 digits[i] -= carry << 4
1021 digits[i+1] += carry
1022 }
1023
1024 return digits
1025 }
1026
View as plain text