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.
7 import "encoding/binary"
9 // This code is a port of the public domain, “ref10” implementation of ed25519
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
16 type FieldElement [10]int32
20 func FeZero(fe *FieldElement) {
24 func FeOne(fe *FieldElement) {
29 func FeAdd(dst, a, b *FieldElement) {
42 func FeSub(dst, a, b *FieldElement) {
55 func FeCopy(dst, src *FieldElement) {
59 // Replace (f,g) with (g,g) if b == 1;
60 // replace (f,g) with (f,g) if b == 0.
62 // Preconditions: b in {0,1}.
63 func FeCMove(f, g *FieldElement, b int32) {
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])
77 func load3(in []byte) int64 {
80 r |= int64(in[1]) << 8
81 r |= int64(in[2]) << 16
85 func load4(in []byte) int64 {
88 r |= int64(in[1]) << 8
89 r |= int64(in[2]) << 16
90 r |= int64(in[3]) << 24
94 func FeFromBytes(dst *FieldElement, src *[32]byte) {
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
106 FeCombine(dst, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9)
109 // FeToBytes marshals h to s.
111 // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
113 // Write p=2^255-19; q=floor(h/p).
114 // Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
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.
120 // Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
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.
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.
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.
132 func FeToBytes(s *[32]byte, h *FieldElement) {
135 q := (19*h[9] + (1 << 24)) >> 25
147 // Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20.
149 // Goal: Output h-2^255 q, which is between 0 and 2^255-20.
151 carry[0] = h[0] >> 26
153 h[0] -= carry[0] << 26
154 carry[1] = h[1] >> 25
156 h[1] -= carry[1] << 25
157 carry[2] = h[2] >> 26
159 h[2] -= carry[2] << 26
160 carry[3] = h[3] >> 25
162 h[3] -= carry[3] << 25
163 carry[4] = h[4] >> 26
165 h[4] -= carry[4] << 26
166 carry[5] = h[5] >> 25
168 h[5] -= carry[5] << 25
169 carry[6] = h[6] >> 26
171 h[6] -= carry[6] << 26
172 carry[7] = h[7] >> 25
174 h[7] -= carry[7] << 25
175 carry[8] = h[8] >> 26
177 h[8] -= carry[8] << 26
178 carry[9] = h[9] >> 25
179 h[9] -= carry[9] << 25
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].
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)
221 func FeIsNegative(f *FieldElement) byte {
227 func FeIsNonZero(f *FieldElement) int32 {
231 for _, b := range s {
243 // |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
246 // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
247 func FeNeg(h, f *FieldElement) {
260 func 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
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
270 c0 = (h0 + (1 << 25)) >> 26
273 c4 = (h4 + (1 << 25)) >> 26
278 /* |h1| <= 1.51*2^58 */
279 /* |h5| <= 1.51*2^58 */
281 c1 = (h1 + (1 << 24)) >> 25
284 c5 = (h5 + (1 << 24)) >> 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 */
292 c2 = (h2 + (1 << 25)) >> 26
295 c6 = (h6 + (1 << 25)) >> 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 */
303 c3 = (h3 + (1 << 24)) >> 25
306 c7 = (h7 + (1 << 24)) >> 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 */
314 c4 = (h4 + (1 << 25)) >> 26
317 c8 = (h8 + (1 << 25)) >> 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 */
325 c9 = (h9 + (1 << 24)) >> 25
328 /* |h9| <= 2^24; from now on fits into int32 unchanged */
329 /* |h0| <= 1.8*2^37 */
331 c0 = (h0 + (1 << 25)) >> 26
334 /* |h0| <= 2^25; from now on fits into int32 unchanged */
335 /* |h1| <= 1.01*2^24 */
349 // FeMul calculates h = f * g
350 // Can overlap h with f or g.
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.
357 // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
359 // Notes on implementation strategy:
361 // Using schoolbook multiplication.
362 // Karatsuba would save a little in some cost models.
364 // Most multiplications by 2 and 19 are 32-bit precomputations;
365 // cheaper than 64-bit postcomputations.
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.
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.
375 // With tighter constraints on inputs, can squeeze carries into int32.
376 func FeMul(h, f, g *FieldElement) {
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])
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])
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
426 FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9)
429 func feSquare(f *FieldElement) (h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 int64) {
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
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
468 // FeSquare calculates h = f*f. Can overlap h with f.
471 // |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
474 // |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
475 func 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)
480 // FeSquare2 sets h = 2 * f * f
482 // Can overlap h with f.
485 // |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
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.
490 func FeSquare2(h, f *FieldElement) {
491 h0, h1, h2, h3, h4, h5, h6, h7, h8, h9 := feSquare(f)
504 FeCombine(h, h0, h1, h2, h3, h4, h5, h6, h7, h8, h9)
507 func FeInvert(out, z *FieldElement) {
508 var t0, t1, t2, t3 FieldElement
511 FeSquare(&t0, z) // 2^1
512 FeSquare(&t1, &t0) // 2^2
513 for i = 1; i < 2; i++ { // 2^3
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
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
529 FeMul(&t2, &t2, &t1) // 19..0
530 FeSquare(&t3, &t2) // 20..1
531 for i = 1; i < 20; i++ { // 39..20
534 FeMul(&t2, &t3, &t2) // 39..0
535 FeSquare(&t2, &t2) // 40..1
536 for i = 1; i < 10; i++ { // 49..10
539 FeMul(&t1, &t2, &t1) // 49..0
540 FeSquare(&t2, &t1) // 50..1
541 for i = 1; i < 50; i++ { // 99..50
544 FeMul(&t2, &t2, &t1) // 99..0
545 FeSquare(&t3, &t2) // 100..1
546 for i = 1; i < 100; i++ { // 199..100
549 FeMul(&t2, &t3, &t2) // 199..0
550 FeSquare(&t2, &t2) // 200..1
551 for i = 1; i < 50; i++ { // 249..50
554 FeMul(&t1, &t2, &t1) // 249..0
555 FeSquare(&t1, &t1) // 250..1
556 for i = 1; i < 5; i++ { // 254..5
559 FeMul(out, &t1, &t0) // 254..5,3,1,0
562 func fePow22523(out, z *FieldElement) {
563 var t0, t1, t2 FieldElement
567 for i = 1; i < 1; i++ {
571 for i = 1; i < 2; i++ {
577 for i = 1; i < 1; i++ {
582 for i = 1; i < 5; i++ {
587 for i = 1; i < 10; i++ {
592 for i = 1; i < 20; i++ {
597 for i = 1; i < 10; i++ {
602 for i = 1; i < 50; i++ {
607 for i = 1; i < 100; i++ {
612 for i = 1; i < 50; i++ {
617 for i = 1; i < 2; i++ {
623 // Group elements are members of the elliptic curve -x^2 + y^2 = 1 + d * x^2 *
624 // y^2 where d = -121665/121666.
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)
632 type ProjectiveGroupElement struct {
636 type ExtendedGroupElement struct {
637 X, Y, Z, T FieldElement
640 type CompletedGroupElement struct {
641 X, Y, Z, T FieldElement
644 type PreComputedGroupElement struct {
645 yPlusX, yMinusX, xy2d FieldElement
648 type CachedGroupElement struct {
649 yPlusX, yMinusX, Z, T2d FieldElement
652 func (p *ProjectiveGroupElement) Zero() {
658 func (p *ProjectiveGroupElement) Double(r *CompletedGroupElement) {
663 FeSquare2(&r.T, &p.Z)
664 FeAdd(&r.Y, &p.X, &p.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)
672 func (p *ProjectiveGroupElement) ToBytes(s *[32]byte) {
673 var recip, x, y FieldElement
675 FeInvert(&recip, &p.Z)
676 FeMul(&x, &p.X, &recip)
677 FeMul(&y, &p.Y, &recip)
679 s[31] ^= FeIsNegative(&x) << 7
682 func (p *ExtendedGroupElement) Zero() {
689 func (p *ExtendedGroupElement) Double(r *CompletedGroupElement) {
690 var q ProjectiveGroupElement
695 func (p *ExtendedGroupElement) ToCached(r *CachedGroupElement) {
696 FeAdd(&r.yPlusX, &p.Y, &p.X)
697 FeSub(&r.yMinusX, &p.Y, &p.X)
699 FeMul(&r.T2d, &p.T, &d2)
702 func (p *ExtendedGroupElement) ToProjective(r *ProjectiveGroupElement) {
708 func (p *ExtendedGroupElement) ToBytes(s *[32]byte) {
709 var recip, x, y FieldElement
711 FeInvert(&recip, &p.Z)
712 FeMul(&x, &p.X, &recip)
713 FeMul(&y, &p.Y, &recip)
715 s[31] ^= FeIsNegative(&x) << 7
718 func (p *ExtendedGroupElement) FromBytes(s *[32]byte) bool {
719 var u, v, v3, vxx, check FieldElement
725 FeSub(&u, &u, &p.Z) // y = y^2-1
726 FeAdd(&v, &v, &p.Z) // v = dy^2+1
729 FeMul(&v3, &v3, &v) // v3 = v^3
731 FeMul(&p.X, &p.X, &v)
732 FeMul(&p.X, &p.X, &u) // x = uv^7
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)
738 var tmpX, tmp2 [32]byte
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 {
748 FeMul(&p.X, &p.X, &SqrtM1)
750 FeToBytes(&tmpX, &p.X)
751 for i, v := range tmpX {
756 if FeIsNegative(&p.X) != (s[31] >> 7) {
760 FeMul(&p.T, &p.X, &p.Y)
764 func (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)
770 func (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)
777 func (p *PreComputedGroupElement) Zero() {
783 func geAdd(r *CompletedGroupElement, p *ExtendedGroupElement, q *CachedGroupElement) {
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)
799 func geSub(r *CompletedGroupElement, p *ExtendedGroupElement, q *CachedGroupElement) {
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)
815 func geMixedAdd(r *CompletedGroupElement, p *ExtendedGroupElement, q *PreComputedGroupElement) {
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)
830 func geMixedSub(r *CompletedGroupElement, p *ExtendedGroupElement, q *PreComputedGroupElement) {
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)
845 func slide(r *[256]int8, a *[32]byte) {
847 r[i] = int8(1 & (a[i>>3] >> uint(i&7)))
852 for b := 1; b <= 6 && i+b < 256; b++ {
854 if r[i]+(r[i+b]<<uint(b)) <= 15 {
855 r[i] += r[i+b] << uint(b)
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++ {
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.
879 func 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
893 for i := 0; i < 7; i++ {
894 geAdd(&t, &A2, &Ai[i])
901 for i = 255; i >= 0; i-- {
902 if aSlide[i] != 0 || bSlide[i] != 0 {
912 geAdd(&t, &u, &Ai[aSlide[i]/2])
913 } else if aSlide[i] < 0 {
915 geSub(&t, &u, &Ai[(-aSlide[i])/2])
920 geMixedAdd(&t, &u, &bi[bSlide[i]/2])
921 } else if bSlide[i] < 0 {
923 geMixedSub(&t, &u, &bi[(-bSlide[i])/2])
930 // equal returns 1 if b == c and 0 otherwise, assuming that b and c are
932 func equal(b, c int32) int32 {
935 return int32(x >> 31)
938 // negative returns 1 if b < 0 and 0 otherwise.
939 func negative(b int32) int32 {
943 func 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)
949 func selectPoint(t *PreComputedGroupElement, pos int32, b int32) {
950 var minusT PreComputedGroupElement
951 bNegative := negative(b)
952 bAbs := b - (((-bNegative) & b) << 1)
955 for i := int32(0); i < 8; i++ {
956 PreComputedGroupElementCMove(t, &base[pos][i], equal(bAbs, i+1))
958 FeCopy(&minusT.yPlusX, &t.yMinusX)
959 FeCopy(&minusT.yMinusX, &t.yPlusX)
960 FeNeg(&minusT.xy2d, &t.xy2d)
961 PreComputedGroupElementCMove(t, &minusT, bNegative)
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.
970 func GeScalarMultBase(h *ExtendedGroupElement, a *[32]byte) {
973 for i, v := range a {
974 e[2*i] = int8(v & 15)
975 e[2*i+1] = int8((v >> 4) & 15)
978 // each e[i] is between 0 and 15 and e[63] is between 0 and 7.
981 for i := 0; i < 63; i++ {
983 carry = (e[i] + 8) >> 4
987 // each e[i] is between -8 and 8.
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)
998 var s ProjectiveGroupElement
1009 for i := int32(0); i < 64; i += 2 {
1010 selectPoint(&t, i/2, int32(e[i]))
1011 geMixedAdd(&r, h, &t)
1016 // The scalars are GF(2^252 + 27742317777372353535851937790883648493).
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
1024 // s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
1025 // where l = 2^252 + 27742317777372353535851937790883648493.
1026 func 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)
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
1090 carry[0] = (s0 + (1 << 20)) >> 21
1092 s0 -= carry[0] << 21
1093 carry[2] = (s2 + (1 << 20)) >> 21
1095 s2 -= carry[2] << 21
1096 carry[4] = (s4 + (1 << 20)) >> 21
1098 s4 -= carry[4] << 21
1099 carry[6] = (s6 + (1 << 20)) >> 21
1101 s6 -= carry[6] << 21
1102 carry[8] = (s8 + (1 << 20)) >> 21
1104 s8 -= carry[8] << 21
1105 carry[10] = (s10 + (1 << 20)) >> 21
1107 s10 -= carry[10] << 21
1108 carry[12] = (s12 + (1 << 20)) >> 21
1110 s12 -= carry[12] << 21
1111 carry[14] = (s14 + (1 << 20)) >> 21
1113 s14 -= carry[14] << 21
1114 carry[16] = (s16 + (1 << 20)) >> 21
1116 s16 -= carry[16] << 21
1117 carry[18] = (s18 + (1 << 20)) >> 21
1119 s18 -= carry[18] << 21
1120 carry[20] = (s20 + (1 << 20)) >> 21
1122 s20 -= carry[20] << 21
1123 carry[22] = (s22 + (1 << 20)) >> 21
1125 s22 -= carry[22] << 21
1127 carry[1] = (s1 + (1 << 20)) >> 21
1129 s1 -= carry[1] << 21
1130 carry[3] = (s3 + (1 << 20)) >> 21
1132 s3 -= carry[3] << 21
1133 carry[5] = (s5 + (1 << 20)) >> 21
1135 s5 -= carry[5] << 21
1136 carry[7] = (s7 + (1 << 20)) >> 21
1138 s7 -= carry[7] << 21
1139 carry[9] = (s9 + (1 << 20)) >> 21
1141 s9 -= carry[9] << 21
1142 carry[11] = (s11 + (1 << 20)) >> 21
1144 s11 -= carry[11] << 21
1145 carry[13] = (s13 + (1 << 20)) >> 21
1147 s13 -= carry[13] << 21
1148 carry[15] = (s15 + (1 << 20)) >> 21
1150 s15 -= carry[15] << 21
1151 carry[17] = (s17 + (1 << 20)) >> 21
1153 s17 -= carry[17] << 21
1154 carry[19] = (s19 + (1 << 20)) >> 21
1156 s19 -= carry[19] << 21
1157 carry[21] = (s21 + (1 << 20)) >> 21
1159 s21 -= carry[21] << 21
1209 carry[6] = (s6 + (1 << 20)) >> 21
1211 s6 -= carry[6] << 21
1212 carry[8] = (s8 + (1 << 20)) >> 21
1214 s8 -= carry[8] << 21
1215 carry[10] = (s10 + (1 << 20)) >> 21
1217 s10 -= carry[10] << 21
1218 carry[12] = (s12 + (1 << 20)) >> 21
1220 s12 -= carry[12] << 21
1221 carry[14] = (s14 + (1 << 20)) >> 21
1223 s14 -= carry[14] << 21
1224 carry[16] = (s16 + (1 << 20)) >> 21
1226 s16 -= carry[16] << 21
1228 carry[7] = (s7 + (1 << 20)) >> 21
1230 s7 -= carry[7] << 21
1231 carry[9] = (s9 + (1 << 20)) >> 21
1233 s9 -= carry[9] << 21
1234 carry[11] = (s11 + (1 << 20)) >> 21
1236 s11 -= carry[11] << 21
1237 carry[13] = (s13 + (1 << 20)) >> 21
1239 s13 -= carry[13] << 21
1240 carry[15] = (s15 + (1 << 20)) >> 21
1242 s15 -= carry[15] << 21
1292 carry[0] = (s0 + (1 << 20)) >> 21
1294 s0 -= carry[0] << 21
1295 carry[2] = (s2 + (1 << 20)) >> 21
1297 s2 -= carry[2] << 21
1298 carry[4] = (s4 + (1 << 20)) >> 21
1300 s4 -= carry[4] << 21
1301 carry[6] = (s6 + (1 << 20)) >> 21
1303 s6 -= carry[6] << 21
1304 carry[8] = (s8 + (1 << 20)) >> 21
1306 s8 -= carry[8] << 21
1307 carry[10] = (s10 + (1 << 20)) >> 21
1309 s10 -= carry[10] << 21
1311 carry[1] = (s1 + (1 << 20)) >> 21
1313 s1 -= carry[1] << 21
1314 carry[3] = (s3 + (1 << 20)) >> 21
1316 s3 -= carry[3] << 21
1317 carry[5] = (s5 + (1 << 20)) >> 21
1319 s5 -= carry[5] << 21
1320 carry[7] = (s7 + (1 << 20)) >> 21
1322 s7 -= carry[7] << 21
1323 carry[9] = (s9 + (1 << 20)) >> 21
1325 s9 -= carry[9] << 21
1326 carry[11] = (s11 + (1 << 20)) >> 21
1328 s11 -= carry[11] << 21
1340 s0 -= carry[0] << 21
1343 s1 -= carry[1] << 21
1346 s2 -= carry[2] << 21
1349 s3 -= carry[3] << 21
1352 s4 -= carry[4] << 21
1355 s5 -= carry[5] << 21
1358 s6 -= carry[6] << 21
1361 s7 -= carry[7] << 21
1364 s8 -= carry[8] << 21
1367 s9 -= carry[9] << 21
1368 carry[10] = s10 >> 21
1370 s10 -= carry[10] << 21
1371 carry[11] = s11 >> 21
1373 s11 -= carry[11] << 21
1385 s0 -= carry[0] << 21
1388 s1 -= carry[1] << 21
1391 s2 -= carry[2] << 21
1394 s3 -= carry[3] << 21
1397 s4 -= carry[4] << 21
1400 s5 -= carry[5] << 21
1403 s6 -= carry[6] << 21
1406 s7 -= carry[7] << 21
1409 s8 -= carry[8] << 21
1412 s9 -= carry[9] << 21
1413 carry[10] = s10 >> 21
1415 s10 -= carry[10] << 21
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)
1452 // s[0]+256*s[1]+...+256^63*s[63] = s
1455 // s[0]+256*s[1]+...+256^31*s[31] = s mod l
1456 // where l = 2^252 + 27742317777372353535851937790883648493.
1457 func 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)
1533 carry[6] = (s6 + (1 << 20)) >> 21
1535 s6 -= carry[6] << 21
1536 carry[8] = (s8 + (1 << 20)) >> 21
1538 s8 -= carry[8] << 21
1539 carry[10] = (s10 + (1 << 20)) >> 21
1541 s10 -= carry[10] << 21
1542 carry[12] = (s12 + (1 << 20)) >> 21
1544 s12 -= carry[12] << 21
1545 carry[14] = (s14 + (1 << 20)) >> 21
1547 s14 -= carry[14] << 21
1548 carry[16] = (s16 + (1 << 20)) >> 21
1550 s16 -= carry[16] << 21
1552 carry[7] = (s7 + (1 << 20)) >> 21
1554 s7 -= carry[7] << 21
1555 carry[9] = (s9 + (1 << 20)) >> 21
1557 s9 -= carry[9] << 21
1558 carry[11] = (s11 + (1 << 20)) >> 21
1560 s11 -= carry[11] << 21
1561 carry[13] = (s13 + (1 << 20)) >> 21
1563 s13 -= carry[13] << 21
1564 carry[15] = (s15 + (1 << 20)) >> 21
1566 s15 -= carry[15] << 21
1616 carry[0] = (s0 + (1 << 20)) >> 21
1618 s0 -= carry[0] << 21
1619 carry[2] = (s2 + (1 << 20)) >> 21
1621 s2 -= carry[2] << 21
1622 carry[4] = (s4 + (1 << 20)) >> 21
1624 s4 -= carry[4] << 21
1625 carry[6] = (s6 + (1 << 20)) >> 21
1627 s6 -= carry[6] << 21
1628 carry[8] = (s8 + (1 << 20)) >> 21
1630 s8 -= carry[8] << 21
1631 carry[10] = (s10 + (1 << 20)) >> 21
1633 s10 -= carry[10] << 21
1635 carry[1] = (s1 + (1 << 20)) >> 21
1637 s1 -= carry[1] << 21
1638 carry[3] = (s3 + (1 << 20)) >> 21
1640 s3 -= carry[3] << 21
1641 carry[5] = (s5 + (1 << 20)) >> 21
1643 s5 -= carry[5] << 21
1644 carry[7] = (s7 + (1 << 20)) >> 21
1646 s7 -= carry[7] << 21
1647 carry[9] = (s9 + (1 << 20)) >> 21
1649 s9 -= carry[9] << 21
1650 carry[11] = (s11 + (1 << 20)) >> 21
1652 s11 -= carry[11] << 21
1664 s0 -= carry[0] << 21
1667 s1 -= carry[1] << 21
1670 s2 -= carry[2] << 21
1673 s3 -= carry[3] << 21
1676 s4 -= carry[4] << 21
1679 s5 -= carry[5] << 21
1682 s6 -= carry[6] << 21
1685 s7 -= carry[7] << 21
1688 s8 -= carry[8] << 21
1691 s9 -= carry[9] << 21
1692 carry[10] = s10 >> 21
1694 s10 -= carry[10] << 21
1695 carry[11] = s11 >> 21
1697 s11 -= carry[11] << 21
1709 s0 -= carry[0] << 21
1712 s1 -= carry[1] << 21
1715 s2 -= carry[2] << 21
1718 s3 -= carry[3] << 21
1721 s4 -= carry[4] << 21
1724 s5 -= carry[5] << 21
1727 s6 -= carry[6] << 21
1730 s7 -= carry[7] << 21
1733 s8 -= carry[8] << 21
1736 s9 -= carry[9] << 21
1737 carry[10] = s10 >> 21
1739 s10 -= carry[10] << 21
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)
1775 // order is the order of Curve25519 in little-endian form.
1776 var order = [4]uint64{0x5812631a5cf5d3ed, 0x14def9dea2f79cd6, 0, 0x1000000000000000}
1778 // ScMinimal returns true if the given scalar is less than the order of the
1780 func ScMinimal(scalar *[32]byte) bool {
1782 v := binary.LittleEndian.Uint64(scalar[i*8:])
1785 } else if v < order[i] {