Filippo Valsorda | fe70532 | 2019-11-07 16:06:22 -0500 | [diff] [blame] | 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 | } |