Black Lives Matter. Support the Equal Justice Initiative.

Source file src/vendor/golang.org/x/crypto/curve25519/curve25519_generic.go

Documentation: vendor/golang.org/x/crypto/curve25519

     1  // Copyright 2013 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 curve25519
     6  
     7  import "encoding/binary"
     8  
     9  // This code is a port of the public domain, "ref10" implementation of
    10  // curve25519 from SUPERCOP 20130419 by D. J. Bernstein.
    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  func feZero(fe *fieldElement) {
    19  	for i := range fe {
    20  		fe[i] = 0
    21  	}
    22  }
    23  
    24  func feOne(fe *fieldElement) {
    25  	feZero(fe)
    26  	fe[0] = 1
    27  }
    28  
    29  func feAdd(dst, a, b *fieldElement) {
    30  	for i := range dst {
    31  		dst[i] = a[i] + b[i]
    32  	}
    33  }
    34  
    35  func feSub(dst, a, b *fieldElement) {
    36  	for i := range dst {
    37  		dst[i] = a[i] - b[i]
    38  	}
    39  }
    40  
    41  func feCopy(dst, src *fieldElement) {
    42  	for i := range dst {
    43  		dst[i] = src[i]
    44  	}
    45  }
    46  
    47  // feCSwap replaces (f,g) with (g,f) if b == 1; replaces (f,g) with (f,g) if b == 0.
    48  //
    49  // Preconditions: b in {0,1}.
    50  func feCSwap(f, g *fieldElement, b int32) {
    51  	b = -b
    52  	for i := range f {
    53  		t := b & (f[i] ^ g[i])
    54  		f[i] ^= t
    55  		g[i] ^= t
    56  	}
    57  }
    58  
    59  // load3 reads a 24-bit, little-endian value from in.
    60  func load3(in []byte) int64 {
    61  	var r int64
    62  	r = int64(in[0])
    63  	r |= int64(in[1]) << 8
    64  	r |= int64(in[2]) << 16
    65  	return r
    66  }
    67  
    68  // load4 reads a 32-bit, little-endian value from in.
    69  func load4(in []byte) int64 {
    70  	return int64(binary.LittleEndian.Uint32(in))
    71  }
    72  
    73  func feFromBytes(dst *fieldElement, src *[32]byte) {
    74  	h0 := load4(src[:])
    75  	h1 := load3(src[4:]) << 6
    76  	h2 := load3(src[7:]) << 5
    77  	h3 := load3(src[10:]) << 3
    78  	h4 := load3(src[13:]) << 2
    79  	h5 := load4(src[16:])
    80  	h6 := load3(src[20:]) << 7
    81  	h7 := load3(src[23:]) << 5
    82  	h8 := load3(src[26:]) << 4
    83  	h9 := (load3(src[29:]) & 0x7fffff) << 2
    84  
    85  	var carry [10]int64
    86  	carry[9] = (h9 + 1<<24) >> 25
    87  	h0 += carry[9] * 19
    88  	h9 -= carry[9] << 25
    89  	carry[1] = (h1 + 1<<24) >> 25
    90  	h2 += carry[1]
    91  	h1 -= carry[1] << 25
    92  	carry[3] = (h3 + 1<<24) >> 25
    93  	h4 += carry[3]
    94  	h3 -= carry[3] << 25
    95  	carry[5] = (h5 + 1<<24) >> 25
    96  	h6 += carry[5]
    97  	h5 -= carry[5] << 25
    98  	carry[7] = (h7 + 1<<24) >> 25
    99  	h8 += carry[7]
   100  	h7 -= carry[7] << 25
   101  
   102  	carry[0] = (h0 + 1<<25) >> 26
   103  	h1 += carry[0]
   104  	h0 -= carry[0] << 26
   105  	carry[2] = (h2 + 1<<25) >> 26
   106  	h3 += carry[2]
   107  	h2 -= carry[2] << 26
   108  	carry[4] = (h4 + 1<<25) >> 26
   109  	h5 += carry[4]
   110  	h4 -= carry[4] << 26
   111  	carry[6] = (h6 + 1<<25) >> 26
   112  	h7 += carry[6]
   113  	h6 -= carry[6] << 26
   114  	carry[8] = (h8 + 1<<25) >> 26
   115  	h9 += carry[8]
   116  	h8 -= carry[8] << 26
   117  
   118  	dst[0] = int32(h0)
   119  	dst[1] = int32(h1)
   120  	dst[2] = int32(h2)
   121  	dst[3] = int32(h3)
   122  	dst[4] = int32(h4)
   123  	dst[5] = int32(h5)
   124  	dst[6] = int32(h6)
   125  	dst[7] = int32(h7)
   126  	dst[8] = int32(h8)
   127  	dst[9] = int32(h9)
   128  }
   129  
   130  // feToBytes marshals h to s.
   131  // Preconditions:
   132  //   |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
   133  //
   134  // Write p=2^255-19; q=floor(h/p).
   135  // Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
   136  //
   137  // Proof:
   138  //   Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
   139  //   Also have |h-2^230 h9|<2^230 so |19 2^(-255)(h-2^230 h9)|<1/4.
   140  //
   141  //   Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
   142  //   Then 0<y<1.
   143  //
   144  //   Write r=h-pq.
   145  //   Have 0<=r<=p-1=2^255-20.
   146  //   Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
   147  //
   148  //   Write x=r+19(2^-255)r+y.
   149  //   Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
   150  //
   151  //   Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
   152  //   so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q.
   153  func feToBytes(s *[32]byte, h *fieldElement) {
   154  	var carry [10]int32
   155  
   156  	q := (19*h[9] + (1 << 24)) >> 25
   157  	q = (h[0] + q) >> 26
   158  	q = (h[1] + q) >> 25
   159  	q = (h[2] + q) >> 26
   160  	q = (h[3] + q) >> 25
   161  	q = (h[4] + q) >> 26
   162  	q = (h[5] + q) >> 25
   163  	q = (h[6] + q) >> 26
   164  	q = (h[7] + q) >> 25
   165  	q = (h[8] + q) >> 26
   166  	q = (h[9] + q) >> 25
   167  
   168  	// Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20.
   169  	h[0] += 19 * q
   170  	// Goal: Output h-2^255 q, which is between 0 and 2^255-20.
   171  
   172  	carry[0] = h[0] >> 26
   173  	h[1] += carry[0]
   174  	h[0] -= carry[0] << 26
   175  	carry[1] = h[1] >> 25
   176  	h[2] += carry[1]
   177  	h[1] -= carry[1] << 25
   178  	carry[2] = h[2] >> 26
   179  	h[3] += carry[2]
   180  	h[2] -= carry[2] << 26
   181  	carry[3] = h[3] >> 25
   182  	h[4] += carry[3]
   183  	h[3] -= carry[3] << 25
   184  	carry[4] = h[4] >> 26
   185  	h[5] += carry[4]
   186  	h[4] -= carry[4] << 26
   187  	carry[5] = h[5] >> 25
   188  	h[6] += carry[5]
   189  	h[5] -= carry[5] << 25
   190  	carry[6] = h[6] >> 26
   191  	h[7] += carry[6]
   192  	h[6] -= carry[6] << 26
   193  	carry[7] = h[7] >> 25
   194  	h[8] += carry[7]
   195  	h[7] -= carry[7] << 25
   196  	carry[8] = h[8] >> 26
   197  	h[9] += carry[8]
   198  	h[8] -= carry[8] << 26
   199  	carry[9] = h[9] >> 25
   200  	h[9] -= carry[9] << 25
   201  	// h10 = carry9
   202  
   203  	// Goal: Output h[0]+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
   204  	// Have h[0]+...+2^230 h[9] between 0 and 2^255-1;
   205  	// evidently 2^255 h10-2^255 q = 0.
   206  	// Goal: Output h[0]+...+2^230 h[9].
   207  
   208  	s[0] = byte(h[0] >> 0)
   209  	s[1] = byte(h[0] >> 8)
   210  	s[2] = byte(h[0] >> 16)
   211  	s[3] = byte((h[0] >> 24) | (h[1] << 2))
   212  	s[4] = byte(h[1] >> 6)
   213  	s[5] = byte(h[1] >> 14)
   214  	s[6] = byte((h[1] >> 22) | (h[2] << 3))
   215  	s[7] = byte(h[2] >> 5)
   216  	s[8] = byte(h[2] >> 13)
   217  	s[9] = byte((h[2] >> 21) | (h[3] << 5))
   218  	s[10] = byte(h[3] >> 3)
   219  	s[11] = byte(h[3] >> 11)
   220  	s[12] = byte((h[3] >> 19) | (h[4] << 6))
   221  	s[13] = byte(h[4] >> 2)
   222  	s[14] = byte(h[4] >> 10)
   223  	s[15] = byte(h[4] >> 18)
   224  	s[16] = byte(h[5] >> 0)
   225  	s[17] = byte(h[5] >> 8)
   226  	s[18] = byte(h[5] >> 16)
   227  	s[19] = byte((h[5] >> 24) | (h[6] << 1))
   228  	s[20] = byte(h[6] >> 7)
   229  	s[21] = byte(h[6] >> 15)
   230  	s[22] = byte((h[6] >> 23) | (h[7] << 3))
   231  	s[23] = byte(h[7] >> 5)
   232  	s[24] = byte(h[7] >> 13)
   233  	s[25] = byte((h[7] >> 21) | (h[8] << 4))
   234  	s[26] = byte(h[8] >> 4)
   235  	s[27] = byte(h[8] >> 12)
   236  	s[28] = byte((h[8] >> 20) | (h[9] << 6))
   237  	s[29] = byte(h[9] >> 2)
   238  	s[30] = byte(h[9] >> 10)
   239  	s[31] = byte(h[9] >> 18)
   240  }
   241  
   242  // feMul calculates h = f * g
   243  // Can overlap h with f or g.
   244  //
   245  // Preconditions:
   246  //    |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
   247  //    |g| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
   248  //
   249  // Postconditions:
   250  //    |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
   251  //
   252  // Notes on implementation strategy:
   253  //
   254  // Using schoolbook multiplication.
   255  // Karatsuba would save a little in some cost models.
   256  //
   257  // Most multiplications by 2 and 19 are 32-bit precomputations;
   258  // cheaper than 64-bit postcomputations.
   259  //
   260  // There is one remaining multiplication by 19 in the carry chain;
   261  // one *19 precomputation can be merged into this,
   262  // but the resulting data flow is considerably less clean.
   263  //
   264  // There are 12 carries below.
   265  // 10 of them are 2-way parallelizable and vectorizable.
   266  // Can get away with 11 carries, but then data flow is much deeper.
   267  //
   268  // With tighter constraints on inputs can squeeze carries into int32.
   269  func feMul(h, f, g *fieldElement) {
   270  	f0 := f[0]
   271  	f1 := f[1]
   272  	f2 := f[2]
   273  	f3 := f[3]
   274  	f4 := f[4]
   275  	f5 := f[5]
   276  	f6 := f[6]
   277  	f7 := f[7]
   278  	f8 := f[8]
   279  	f9 := f[9]
   280  	g0 := g[0]
   281  	g1 := g[1]
   282  	g2 := g[2]
   283  	g3 := g[3]
   284  	g4 := g[4]
   285  	g5 := g[5]
   286  	g6 := g[6]
   287  	g7 := g[7]
   288  	g8 := g[8]
   289  	g9 := g[9]
   290  	g1_19 := 19 * g1 // 1.4*2^29
   291  	g2_19 := 19 * g2 // 1.4*2^30; still ok
   292  	g3_19 := 19 * g3
   293  	g4_19 := 19 * g4
   294  	g5_19 := 19 * g5
   295  	g6_19 := 19 * g6
   296  	g7_19 := 19 * g7
   297  	g8_19 := 19 * g8
   298  	g9_19 := 19 * g9
   299  	f1_2 := 2 * f1
   300  	f3_2 := 2 * f3
   301  	f5_2 := 2 * f5
   302  	f7_2 := 2 * f7
   303  	f9_2 := 2 * f9
   304  	f0g0 := int64(f0) * int64(g0)
   305  	f0g1 := int64(f0) * int64(g1)
   306  	f0g2 := int64(f0) * int64(g2)
   307  	f0g3 := int64(f0) * int64(g3)
   308  	f0g4 := int64(f0) * int64(g4)
   309  	f0g5 := int64(f0) * int64(g5)
   310  	f0g6 := int64(f0) * int64(g6)
   311  	f0g7 := int64(f0) * int64(g7)
   312  	f0g8 := int64(f0) * int64(g8)
   313  	f0g9 := int64(f0) * int64(g9)
   314  	f1g0 := int64(f1) * int64(g0)
   315  	f1g1_2 := int64(f1_2) * int64(g1)
   316  	f1g2 := int64(f1) * int64(g2)
   317  	f1g3_2 := int64(f1_2) * int64(g3)
   318  	f1g4 := int64(f1) * int64(g4)
   319  	f1g5_2 := int64(f1_2) * int64(g5)
   320  	f1g6 := int64(f1) * int64(g6)
   321  	f1g7_2 := int64(f1_2) * int64(g7)
   322  	f1g8 := int64(f1) * int64(g8)
   323  	f1g9_38 := int64(f1_2) * int64(g9_19)
   324  	f2g0 := int64(f2) * int64(g0)
   325  	f2g1 := int64(f2) * int64(g1)
   326  	f2g2 := int64(f2) * int64(g2)
   327  	f2g3 := int64(f2) * int64(g3)
   328  	f2g4 := int64(f2) * int64(g4)
   329  	f2g5 := int64(f2) * int64(g5)
   330  	f2g6 := int64(f2) * int64(g6)
   331  	f2g7 := int64(f2) * int64(g7)
   332  	f2g8_19 := int64(f2) * int64(g8_19)
   333  	f2g9_19 := int64(f2) * int64(g9_19)
   334  	f3g0 := int64(f3) * int64(g0)
   335  	f3g1_2 := int64(f3_2) * int64(g1)
   336  	f3g2 := int64(f3) * int64(g2)
   337  	f3g3_2 := int64(f3_2) * int64(g3)
   338  	f3g4 := int64(f3) * int64(g4)
   339  	f3g5_2 := int64(f3_2) * int64(g5)
   340  	f3g6 := int64(f3) * int64(g6)
   341  	f3g7_38 := int64(f3_2) * int64(g7_19)
   342  	f3g8_19 := int64(f3) * int64(g8_19)
   343  	f3g9_38 := int64(f3_2) * int64(g9_19)
   344  	f4g0 := int64(f4) * int64(g0)
   345  	f4g1 := int64(f4) * int64(g1)
   346  	f4g2 := int64(f4) * int64(g2)
   347  	f4g3 := int64(f4) * int64(g3)
   348  	f4g4 := int64(f4) * int64(g4)
   349  	f4g5 := int64(f4) * int64(g5)
   350  	f4g6_19 := int64(f4) * int64(g6_19)
   351  	f4g7_19 := int64(f4) * int64(g7_19)
   352  	f4g8_19 := int64(f4) * int64(g8_19)
   353  	f4g9_19 := int64(f4) * int64(g9_19)
   354  	f5g0 := int64(f5) * int64(g0)
   355  	f5g1_2 := int64(f5_2) * int64(g1)
   356  	f5g2 := int64(f5) * int64(g2)
   357  	f5g3_2 := int64(f5_2) * int64(g3)
   358  	f5g4 := int64(f5) * int64(g4)
   359  	f5g5_38 := int64(f5_2) * int64(g5_19)
   360  	f5g6_19 := int64(f5) * int64(g6_19)
   361  	f5g7_38 := int64(f5_2) * int64(g7_19)
   362  	f5g8_19 := int64(f5) * int64(g8_19)
   363  	f5g9_38 := int64(f5_2) * int64(g9_19)
   364  	f6g0 := int64(f6) * int64(g0)
   365  	f6g1 := int64(f6) * int64(g1)
   366  	f6g2 := int64(f6) * int64(g2)
   367  	f6g3 := int64(f6) * int64(g3)
   368  	f6g4_19 := int64(f6) * int64(g4_19)
   369  	f6g5_19 := int64(f6) * int64(g5_19)
   370  	f6g6_19 := int64(f6) * int64(g6_19)
   371  	f6g7_19 := int64(f6) * int64(g7_19)
   372  	f6g8_19 := int64(f6) * int64(g8_19)
   373  	f6g9_19 := int64(f6) * int64(g9_19)
   374  	f7g0 := int64(f7) * int64(g0)
   375  	f7g1_2 := int64(f7_2) * int64(g1)
   376  	f7g2 := int64(f7) * int64(g2)
   377  	f7g3_38 := int64(f7_2) * int64(g3_19)
   378  	f7g4_19 := int64(f7) * int64(g4_19)
   379  	f7g5_38 := int64(f7_2) * int64(g5_19)
   380  	f7g6_19 := int64(f7) * int64(g6_19)
   381  	f7g7_38 := int64(f7_2) * int64(g7_19)
   382  	f7g8_19 := int64(f7) * int64(g8_19)
   383  	f7g9_38 := int64(f7_2) * int64(g9_19)
   384  	f8g0 := int64(f8) * int64(g0)
   385  	f8g1 := int64(f8) * int64(g1)
   386  	f8g2_19 := int64(f8) * int64(g2_19)
   387  	f8g3_19 := int64(f8) * int64(g3_19)
   388  	f8g4_19 := int64(f8) * int64(g4_19)
   389  	f8g5_19 := int64(f8) * int64(g5_19)
   390  	f8g6_19 := int64(f8) * int64(g6_19)
   391  	f8g7_19 := int64(f8) * int64(g7_19)
   392  	f8g8_19 := int64(f8) * int64(g8_19)
   393  	f8g9_19 := int64(f8) * int64(g9_19)
   394  	f9g0 := int64(f9) * int64(g0)
   395  	f9g1_38 := int64(f9_2) * int64(g1_19)
   396  	f9g2_19 := int64(f9) * int64(g2_19)
   397  	f9g3_38 := int64(f9_2) * int64(g3_19)
   398  	f9g4_19 := int64(f9) * int64(g4_19)
   399  	f9g5_38 := int64(f9_2) * int64(g5_19)
   400  	f9g6_19 := int64(f9) * int64(g6_19)
   401  	f9g7_38 := int64(f9_2) * int64(g7_19)
   402  	f9g8_19 := int64(f9) * int64(g8_19)
   403  	f9g9_38 := int64(f9_2) * int64(g9_19)
   404  	h0 := f0g0 + f1g9_38 + f2g8_19 + f3g7_38 + f4g6_19 + f5g5_38 + f6g4_19 + f7g3_38 + f8g2_19 + f9g1_38
   405  	h1 := f0g1 + f1g0 + f2g9_19 + f3g8_19 + f4g7_19 + f5g6_19 + f6g5_19 + f7g4_19 + f8g3_19 + f9g2_19
   406  	h2 := f0g2 + f1g1_2 + f2g0 + f3g9_38 + f4g8_19 + f5g7_38 + f6g6_19 + f7g5_38 + f8g4_19 + f9g3_38
   407  	h3 := f0g3 + f1g2 + f2g1 + f3g0 + f4g9_19 + f5g8_19 + f6g7_19 + f7g6_19 + f8g5_19 + f9g4_19
   408  	h4 := f0g4 + f1g3_2 + f2g2 + f3g1_2 + f4g0 + f5g9_38 + f6g8_19 + f7g7_38 + f8g6_19 + f9g5_38
   409  	h5 := f0g5 + f1g4 + f2g3 + f3g2 + f4g1 + f5g0 + f6g9_19 + f7g8_19 + f8g7_19 + f9g6_19
   410  	h6 := f0g6 + f1g5_2 + f2g4 + f3g3_2 + f4g2 + f5g1_2 + f6g0 + f7g9_38 + f8g8_19 + f9g7_38
   411  	h7 := f0g7 + f1g6 + f2g5 + f3g4 + f4g3 + f5g2 + f6g1 + f7g0 + f8g9_19 + f9g8_19
   412  	h8 := f0g8 + f1g7_2 + f2g6 + f3g5_2 + f4g4 + f5g3_2 + f6g2 + f7g1_2 + f8g0 + f9g9_38
   413  	h9 := f0g9 + f1g8 + f2g7 + f3g6 + f4g5 + f5g4 + f6g3 + f7g2 + f8g1 + f9g0
   414  	var carry [10]int64
   415  
   416  	// |h0| <= (1.1*1.1*2^52*(1+19+19+19+19)+1.1*1.1*2^50*(38+38+38+38+38))
   417  	//   i.e. |h0| <= 1.2*2^59; narrower ranges for h2, h4, h6, h8
   418  	// |h1| <= (1.1*1.1*2^51*(1+1+19+19+19+19+19+19+19+19))
   419  	//   i.e. |h1| <= 1.5*2^58; narrower ranges for h3, h5, h7, h9
   420  
   421  	carry[0] = (h0 + (1 << 25)) >> 26
   422  	h1 += carry[0]
   423  	h0 -= carry[0] << 26
   424  	carry[4] = (h4 + (1 << 25)) >> 26
   425  	h5 += carry[4]
   426  	h4 -= carry[4] << 26
   427  	// |h0| <= 2^25
   428  	// |h4| <= 2^25
   429  	// |h1| <= 1.51*2^58
   430  	// |h5| <= 1.51*2^58
   431  
   432  	carry[1] = (h1 + (1 << 24)) >> 25
   433  	h2 += carry[1]
   434  	h1 -= carry[1] << 25
   435  	carry[5] = (h5 + (1 << 24)) >> 25
   436  	h6 += carry[5]
   437  	h5 -= carry[5] << 25
   438  	// |h1| <= 2^24; from now on fits into int32
   439  	// |h5| <= 2^24; from now on fits into int32
   440  	// |h2| <= 1.21*2^59
   441  	// |h6| <= 1.21*2^59
   442  
   443  	carry[2] = (h2 + (1 << 25)) >> 26
   444  	h3 += carry[2]
   445  	h2 -= carry[2] << 26
   446  	carry[6] = (h6 + (1 << 25)) >> 26
   447  	h7 += carry[6]
   448  	h6 -= carry[6] << 26
   449  	// |h2| <= 2^25; from now on fits into int32 unchanged
   450  	// |h6| <= 2^25; from now on fits into int32 unchanged
   451  	// |h3| <= 1.51*2^58
   452  	// |h7| <= 1.51*2^58
   453  
   454  	carry[3] = (h3 + (1 << 24)) >> 25
   455  	h4 += carry[3]
   456  	h3 -= carry[3] << 25
   457  	carry[7] = (h7 + (1 << 24)) >> 25
   458  	h8 += carry[7]
   459  	h7 -= carry[7] << 25
   460  	// |h3| <= 2^24; from now on fits into int32 unchanged
   461  	// |h7| <= 2^24; from now on fits into int32 unchanged
   462  	// |h4| <= 1.52*2^33
   463  	// |h8| <= 1.52*2^33
   464  
   465  	carry[4] = (h4 + (1 << 25)) >> 26
   466  	h5 += carry[4]
   467  	h4 -= carry[4] << 26
   468  	carry[8] = (h8 + (1 << 25)) >> 26
   469  	h9 += carry[8]
   470  	h8 -= carry[8] << 26
   471  	// |h4| <= 2^25; from now on fits into int32 unchanged
   472  	// |h8| <= 2^25; from now on fits into int32 unchanged
   473  	// |h5| <= 1.01*2^24
   474  	// |h9| <= 1.51*2^58
   475  
   476  	carry[9] = (h9 + (1 << 24)) >> 25
   477  	h0 += carry[9] * 19
   478  	h9 -= carry[9] << 25
   479  	// |h9| <= 2^24; from now on fits into int32 unchanged
   480  	// |h0| <= 1.8*2^37
   481  
   482  	carry[0] = (h0 + (1 << 25)) >> 26
   483  	h1 += carry[0]
   484  	h0 -= carry[0] << 26
   485  	// |h0| <= 2^25; from now on fits into int32 unchanged
   486  	// |h1| <= 1.01*2^24
   487  
   488  	h[0] = int32(h0)
   489  	h[1] = int32(h1)
   490  	h[2] = int32(h2)
   491  	h[3] = int32(h3)
   492  	h[4] = int32(h4)
   493  	h[5] = int32(h5)
   494  	h[6] = int32(h6)
   495  	h[7] = int32(h7)
   496  	h[8] = int32(h8)
   497  	h[9] = int32(h9)
   498  }
   499  
   500  // feSquare calculates h = f*f. Can overlap h with f.
   501  //
   502  // Preconditions:
   503  //    |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
   504  //
   505  // Postconditions:
   506  //    |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
   507  func feSquare(h, f *fieldElement) {
   508  	f0 := f[0]
   509  	f1 := f[1]
   510  	f2 := f[2]
   511  	f3 := f[3]
   512  	f4 := f[4]
   513  	f5 := f[5]
   514  	f6 := f[6]
   515  	f7 := f[7]
   516  	f8 := f[8]
   517  	f9 := f[9]
   518  	f0_2 := 2 * f0
   519  	f1_2 := 2 * f1
   520  	f2_2 := 2 * f2
   521  	f3_2 := 2 * f3
   522  	f4_2 := 2 * f4
   523  	f5_2 := 2 * f5
   524  	f6_2 := 2 * f6
   525  	f7_2 := 2 * f7
   526  	f5_38 := 38 * f5 // 1.31*2^30
   527  	f6_19 := 19 * f6 // 1.31*2^30
   528  	f7_38 := 38 * f7 // 1.31*2^30
   529  	f8_19 := 19 * f8 // 1.31*2^30
   530  	f9_38 := 38 * f9 // 1.31*2^30
   531  	f0f0 := int64(f0) * int64(f0)
   532  	f0f1_2 := int64(f0_2) * int64(f1)
   533  	f0f2_2 := int64(f0_2) * int64(f2)
   534  	f0f3_2 := int64(f0_2) * int64(f3)
   535  	f0f4_2 := int64(f0_2) * int64(f4)
   536  	f0f5_2 := int64(f0_2) * int64(f5)
   537  	f0f6_2 := int64(f0_2) * int64(f6)
   538  	f0f7_2 := int64(f0_2) * int64(f7)
   539  	f0f8_2 := int64(f0_2) * int64(f8)
   540  	f0f9_2 := int64(f0_2) * int64(f9)
   541  	f1f1_2 := int64(f1_2) * int64(f1)
   542  	f1f2_2 := int64(f1_2) * int64(f2)
   543  	f1f3_4 := int64(f1_2) * int64(f3_2)
   544  	f1f4_2 := int64(f1_2) * int64(f4)
   545  	f1f5_4 := int64(f1_2) * int64(f5_2)
   546  	f1f6_2 := int64(f1_2) * int64(f6)
   547  	f1f7_4 := int64(f1_2) * int64(f7_2)
   548  	f1f8_2 := int64(f1_2) * int64(f8)
   549  	f1f9_76 := int64(f1_2) * int64(f9_38)
   550  	f2f2 := int64(f2) * int64(f2)
   551  	f2f3_2 := int64(f2_2) * int64(f3)
   552  	f2f4_2 := int64(f2_2) * int64(f4)
   553  	f2f5_2 := int64(f2_2) * int64(f5)
   554  	f2f6_2 := int64(f2_2) * int64(f6)
   555  	f2f7_2 := int64(f2_2) * int64(f7)
   556  	f2f8_38 := int64(f2_2) * int64(f8_19)
   557  	f2f9_38 := int64(f2) * int64(f9_38)
   558  	f3f3_2 := int64(f3_2) * int64(f3)
   559  	f3f4_2 := int64(f3_2) * int64(f4)
   560  	f3f5_4 := int64(f3_2) * int64(f5_2)
   561  	f3f6_2 := int64(f3_2) * int64(f6)
   562  	f3f7_76 := int64(f3_2) * int64(f7_38)
   563  	f3f8_38 := int64(f3_2) * int64(f8_19)
   564  	f3f9_76 := int64(f3_2) * int64(f9_38)
   565  	f4f4 := int64(f4) * int64(f4)
   566  	f4f5_2 := int64(f4_2) * int64(f5)
   567  	f4f6_38 := int64(f4_2) * int64(f6_19)
   568  	f4f7_38 := int64(f4) * int64(f7_38)
   569  	f4f8_38 := int64(f4_2) * int64(f8_19)
   570  	f4f9_38 := int64(f4) * int64(f9_38)
   571  	f5f5_38 := int64(f5) * int64(f5_38)
   572  	f5f6_38 := int64(f5_2) * int64(f6_19)
   573  	f5f7_76 := int64(f5_2) * int64(f7_38)
   574  	f5f8_38 := int64(f5_2) * int64(f8_19)
   575  	f5f9_76 := int64(f5_2) * int64(f9_38)
   576  	f6f6_19 := int64(f6) * int64(f6_19)
   577  	f6f7_38 := int64(f6) * int64(f7_38)
   578  	f6f8_38 := int64(f6_2) * int64(f8_19)
   579  	f6f9_38 := int64(f6) * int64(f9_38)
   580  	f7f7_38 := int64(f7) * int64(f7_38)
   581  	f7f8_38 := int64(f7_2) * int64(f8_19)
   582  	f7f9_76 := int64(f7_2) * int64(f9_38)
   583  	f8f8_19 := int64(f8) * int64(f8_19)
   584  	f8f9_38 := int64(f8) * int64(f9_38)
   585  	f9f9_38 := int64(f9) * int64(f9_38)
   586  	h0 := f0f0 + f1f9_76 + f2f8_38 + f3f7_76 + f4f6_38 + f5f5_38
   587  	h1 := f0f1_2 + f2f9_38 + f3f8_38 + f4f7_38 + f5f6_38
   588  	h2 := f0f2_2 + f1f1_2 + f3f9_76 + f4f8_38 + f5f7_76 + f6f6_19
   589  	h3 := f0f3_2 + f1f2_2 + f4f9_38 + f5f8_38 + f6f7_38
   590  	h4 := f0f4_2 + f1f3_4 + f2f2 + f5f9_76 + f6f8_38 + f7f7_38
   591  	h5 := f0f5_2 + f1f4_2 + f2f3_2 + f6f9_38 + f7f8_38
   592  	h6 := f0f6_2 + f1f5_4 + f2f4_2 + f3f3_2 + f7f9_76 + f8f8_19
   593  	h7 := f0f7_2 + f1f6_2 + f2f5_2 + f3f4_2 + f8f9_38
   594  	h8 := f0f8_2 + f1f7_4 + f2f6_2 + f3f5_4 + f4f4 + f9f9_38
   595  	h9 := f0f9_2 + f1f8_2 + f2f7_2 + f3f6_2 + f4f5_2
   596  	var carry [10]int64
   597  
   598  	carry[0] = (h0 + (1 << 25)) >> 26
   599  	h1 += carry[0]
   600  	h0 -= carry[0] << 26
   601  	carry[4] = (h4 + (1 << 25)) >> 26
   602  	h5 += carry[4]
   603  	h4 -= carry[4] << 26
   604  
   605  	carry[1] = (h1 + (1 << 24)) >> 25
   606  	h2 += carry[1]
   607  	h1 -= carry[1] << 25
   608  	carry[5] = (h5 + (1 << 24)) >> 25
   609  	h6 += carry[5]
   610  	h5 -= carry[5] << 25
   611  
   612  	carry[2] = (h2 + (1 << 25)) >> 26
   613  	h3 += carry[2]
   614  	h2 -= carry[2] << 26
   615  	carry[6] = (h6 + (1 << 25)) >> 26
   616  	h7 += carry[6]
   617  	h6 -= carry[6] << 26
   618  
   619  	carry[3] = (h3 + (1 << 24)) >> 25
   620  	h4 += carry[3]
   621  	h3 -= carry[3] << 25
   622  	carry[7] = (h7 + (1 << 24)) >> 25
   623  	h8 += carry[7]
   624  	h7 -= carry[7] << 25
   625  
   626  	carry[4] = (h4 + (1 << 25)) >> 26
   627  	h5 += carry[4]
   628  	h4 -= carry[4] << 26
   629  	carry[8] = (h8 + (1 << 25)) >> 26
   630  	h9 += carry[8]
   631  	h8 -= carry[8] << 26
   632  
   633  	carry[9] = (h9 + (1 << 24)) >> 25
   634  	h0 += carry[9] * 19
   635  	h9 -= carry[9] << 25
   636  
   637  	carry[0] = (h0 + (1 << 25)) >> 26
   638  	h1 += carry[0]
   639  	h0 -= carry[0] << 26
   640  
   641  	h[0] = int32(h0)
   642  	h[1] = int32(h1)
   643  	h[2] = int32(h2)
   644  	h[3] = int32(h3)
   645  	h[4] = int32(h4)
   646  	h[5] = int32(h5)
   647  	h[6] = int32(h6)
   648  	h[7] = int32(h7)
   649  	h[8] = int32(h8)
   650  	h[9] = int32(h9)
   651  }
   652  
   653  // feMul121666 calculates h = f * 121666. Can overlap h with f.
   654  //
   655  // Preconditions:
   656  //    |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
   657  //
   658  // Postconditions:
   659  //    |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
   660  func feMul121666(h, f *fieldElement) {
   661  	h0 := int64(f[0]) * 121666
   662  	h1 := int64(f[1]) * 121666
   663  	h2 := int64(f[2]) * 121666
   664  	h3 := int64(f[3]) * 121666
   665  	h4 := int64(f[4]) * 121666
   666  	h5 := int64(f[5]) * 121666
   667  	h6 := int64(f[6]) * 121666
   668  	h7 := int64(f[7]) * 121666
   669  	h8 := int64(f[8]) * 121666
   670  	h9 := int64(f[9]) * 121666
   671  	var carry [10]int64
   672  
   673  	carry[9] = (h9 + (1 << 24)) >> 25
   674  	h0 += carry[9] * 19
   675  	h9 -= carry[9] << 25
   676  	carry[1] = (h1 + (1 << 24)) >> 25
   677  	h2 += carry[1]
   678  	h1 -= carry[1] << 25
   679  	carry[3] = (h3 + (1 << 24)) >> 25
   680  	h4 += carry[3]
   681  	h3 -= carry[3] << 25
   682  	carry[5] = (h5 + (1 << 24)) >> 25
   683  	h6 += carry[5]
   684  	h5 -= carry[5] << 25
   685  	carry[7] = (h7 + (1 << 24)) >> 25
   686  	h8 += carry[7]
   687  	h7 -= carry[7] << 25
   688  
   689  	carry[0] = (h0 + (1 << 25)) >> 26
   690  	h1 += carry[0]
   691  	h0 -= carry[0] << 26
   692  	carry[2] = (h2 + (1 << 25)) >> 26
   693  	h3 += carry[2]
   694  	h2 -= carry[2] << 26
   695  	carry[4] = (h4 + (1 << 25)) >> 26
   696  	h5 += carry[4]
   697  	h4 -= carry[4] << 26
   698  	carry[6] = (h6 + (1 << 25)) >> 26
   699  	h7 += carry[6]
   700  	h6 -= carry[6] << 26
   701  	carry[8] = (h8 + (1 << 25)) >> 26
   702  	h9 += carry[8]
   703  	h8 -= carry[8] << 26
   704  
   705  	h[0] = int32(h0)
   706  	h[1] = int32(h1)
   707  	h[2] = int32(h2)
   708  	h[3] = int32(h3)
   709  	h[4] = int32(h4)
   710  	h[5] = int32(h5)
   711  	h[6] = int32(h6)
   712  	h[7] = int32(h7)
   713  	h[8] = int32(h8)
   714  	h[9] = int32(h9)
   715  }
   716  
   717  // feInvert sets out = z^-1.
   718  func feInvert(out, z *fieldElement) {
   719  	var t0, t1, t2, t3 fieldElement
   720  	var i int
   721  
   722  	feSquare(&t0, z)
   723  	for i = 1; i < 1; i++ {
   724  		feSquare(&t0, &t0)
   725  	}
   726  	feSquare(&t1, &t0)
   727  	for i = 1; i < 2; i++ {
   728  		feSquare(&t1, &t1)
   729  	}
   730  	feMul(&t1, z, &t1)
   731  	feMul(&t0, &t0, &t1)
   732  	feSquare(&t2, &t0)
   733  	for i = 1; i < 1; i++ {
   734  		feSquare(&t2, &t2)
   735  	}
   736  	feMul(&t1, &t1, &t2)
   737  	feSquare(&t2, &t1)
   738  	for i = 1; i < 5; i++ {
   739  		feSquare(&t2, &t2)
   740  	}
   741  	feMul(&t1, &t2, &t1)
   742  	feSquare(&t2, &t1)
   743  	for i = 1; i < 10; i++ {
   744  		feSquare(&t2, &t2)
   745  	}
   746  	feMul(&t2, &t2, &t1)
   747  	feSquare(&t3, &t2)
   748  	for i = 1; i < 20; i++ {
   749  		feSquare(&t3, &t3)
   750  	}
   751  	feMul(&t2, &t3, &t2)
   752  	feSquare(&t2, &t2)
   753  	for i = 1; i < 10; i++ {
   754  		feSquare(&t2, &t2)
   755  	}
   756  	feMul(&t1, &t2, &t1)
   757  	feSquare(&t2, &t1)
   758  	for i = 1; i < 50; i++ {
   759  		feSquare(&t2, &t2)
   760  	}
   761  	feMul(&t2, &t2, &t1)
   762  	feSquare(&t3, &t2)
   763  	for i = 1; i < 100; i++ {
   764  		feSquare(&t3, &t3)
   765  	}
   766  	feMul(&t2, &t3, &t2)
   767  	feSquare(&t2, &t2)
   768  	for i = 1; i < 50; i++ {
   769  		feSquare(&t2, &t2)
   770  	}
   771  	feMul(&t1, &t2, &t1)
   772  	feSquare(&t1, &t1)
   773  	for i = 1; i < 5; i++ {
   774  		feSquare(&t1, &t1)
   775  	}
   776  	feMul(out, &t1, &t0)
   777  }
   778  
   779  func scalarMultGeneric(out, in, base *[32]byte) {
   780  	var e [32]byte
   781  
   782  	copy(e[:], in[:])
   783  	e[0] &= 248
   784  	e[31] &= 127
   785  	e[31] |= 64
   786  
   787  	var x1, x2, z2, x3, z3, tmp0, tmp1 fieldElement
   788  	feFromBytes(&x1, base)
   789  	feOne(&x2)
   790  	feCopy(&x3, &x1)
   791  	feOne(&z3)
   792  
   793  	swap := int32(0)
   794  	for pos := 254; pos >= 0; pos-- {
   795  		b := e[pos/8] >> uint(pos&7)
   796  		b &= 1
   797  		swap ^= int32(b)
   798  		feCSwap(&x2, &x3, swap)
   799  		feCSwap(&z2, &z3, swap)
   800  		swap = int32(b)
   801  
   802  		feSub(&tmp0, &x3, &z3)
   803  		feSub(&tmp1, &x2, &z2)
   804  		feAdd(&x2, &x2, &z2)
   805  		feAdd(&z2, &x3, &z3)
   806  		feMul(&z3, &tmp0, &x2)
   807  		feMul(&z2, &z2, &tmp1)
   808  		feSquare(&tmp0, &tmp1)
   809  		feSquare(&tmp1, &x2)
   810  		feAdd(&x3, &z3, &z2)
   811  		feSub(&z2, &z3, &z2)
   812  		feMul(&x2, &tmp1, &tmp0)
   813  		feSub(&tmp1, &tmp1, &tmp0)
   814  		feSquare(&z2, &z2)
   815  		feMul121666(&z3, &tmp1)
   816  		feSquare(&x3, &x3)
   817  		feAdd(&tmp0, &tmp0, &z3)
   818  		feMul(&z3, &x1, &z2)
   819  		feMul(&z2, &tmp1, &tmp0)
   820  	}
   821  
   822  	feCSwap(&x2, &x3, swap)
   823  	feCSwap(&z2, &z3, swap)
   824  
   825  	feInvert(&z2, &z2)
   826  	feMul(&x2, &x2, &z2)
   827  	feToBytes(out, &x2)
   828  }
   829  

View as plain text