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 5package curve25519 6 7import "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. 16type fieldElement [10]int32 17 18func feZero(fe *fieldElement) { 19 for i := range fe { 20 fe[i] = 0 21 } 22} 23 24func feOne(fe *fieldElement) { 25 feZero(fe) 26 fe[0] = 1 27} 28 29func feAdd(dst, a, b *fieldElement) { 30 for i := range dst { 31 dst[i] = a[i] + b[i] 32 } 33} 34 35func feSub(dst, a, b *fieldElement) { 36 for i := range dst { 37 dst[i] = a[i] - b[i] 38 } 39} 40 41func 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}. 50func 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. 60func 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. 69func load4(in []byte) int64 { 70 return int64(binary.LittleEndian.Uint32(in)) 71} 72 73func 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. 153func 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. 269func 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. 507func 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. 660func 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. 718func 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 779func 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