vendor/golang.org/x/crypto/curve25519/curve25519.go

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