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

View as plain text