1// Copyright 2020 The BoringSSL Authors 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// https://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15//go:build ignore 16 17package main 18 19import ( 20 "bytes" 21 "crypto/elliptic" 22 "fmt" 23 "io" 24 "math/big" 25 "os" 26 "strings" 27) 28 29func main() { 30 if err := writeBuiltinCurves("builtin_curves.h"); err != nil { 31 fmt.Fprintf(os.Stderr, "Error writing builtin_curves.h: %s\n", err) 32 os.Exit(1) 33 } 34 35 if err := writeP256NistzTable("p256-nistz-table.h"); err != nil { 36 fmt.Fprintf(os.Stderr, "Error writing p256-nistz-table.h: %s\n", err) 37 os.Exit(1) 38 } 39 40 if err := writeP256Table("p256_table.h"); err != nil { 41 fmt.Fprintf(os.Stderr, "Error writing p256_table.h: %s\n", err) 42 os.Exit(1) 43 } 44} 45 46func writeBuiltinCurves(path string) error { 47 f, err := os.Create(path) 48 if err != nil { 49 return err 50 } 51 defer f.Close() 52 w := &columnWriter{w: f} 53 54 const fileHeader = `// Copyright 2023 The BoringSSL Authors 55// 56// Licensed under the Apache License, Version 2.0 (the "License"); 57// you may not use this file except in compliance with the License. 58// You may obtain a copy of the License at 59// 60// https://www.apache.org/licenses/LICENSE-2.0 61// 62// Unless required by applicable law or agreed to in writing, software 63// distributed under the License is distributed on an "AS IS" BASIS, 64// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 65// See the License for the specific language governing permissions and 66// limitations under the License. 67 68// This file is generated by make_tables.go. 69` 70 if _, err := io.WriteString(w, fileHeader); err != nil { 71 return err 72 } 73 // P-224 is the only curve where we have a non-Montgomery implementation. 74 if err := writeCurveData(w, elliptic.P224(), true); err != nil { 75 return err 76 } 77 if err := writeCurveData(w, elliptic.P256(), false); err != nil { 78 return err 79 } 80 if err := writeCurveData(w, elliptic.P384(), false); err != nil { 81 return err 82 } 83 if err := writeCurveData(w, elliptic.P521(), false); err != nil { 84 return err 85 } 86 return nil 87} 88 89func writeCurveData(w *columnWriter, curve elliptic.Curve, includeNonMontgomery bool) error { 90 params := curve.Params() 91 if _, err := fmt.Fprintf(w, "\n// %s\n", params.Name); err != nil { 92 return err 93 } 94 95 cName := strings.Replace(params.Name, "-", "", -1) 96 writeDecls := func(bits int) error { 97 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sField", cName), params.P); err != nil { 98 return err 99 } 100 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sOrder", cName), params.N); err != nil { 101 return err 102 } 103 if includeNonMontgomery { 104 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sB", cName), params.B); err != nil { 105 return err 106 } 107 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sGX", cName), params.Gx); err != nil { 108 return err 109 } 110 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sGY", cName), params.Gy); err != nil { 111 return err 112 } 113 } 114 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sFieldR", cName), montgomeryR(params.P, bits)); err != nil { 115 return err 116 } 117 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sFieldRR", cName), montgomeryRR(params.P, bits)); err != nil { 118 return err 119 } 120 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sOrderRR", cName), montgomeryRR(params.N, bits)); err != nil { 121 return err 122 } 123 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sMontB", cName), toMontgomery(params.B, params.P, bits)); err != nil { 124 return err 125 } 126 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sMontGX", cName), toMontgomery(params.Gx, params.P, bits)); err != nil { 127 return err 128 } 129 if err := writeDecl(w, curve, bits, fmt.Sprintf("k%sMontGY", cName), toMontgomery(params.Gy, params.P, bits)); err != nil { 130 return err 131 } 132 return nil 133 } 134 135 if _, err := fmt.Fprintf(w, "[[maybe_unused]] static const uint64_t k%sFieldN0 = 0x%016x;\n", cName, montgomeryN0(params.P)); err != nil { 136 return err 137 } 138 if _, err := fmt.Fprintf(w, "[[maybe_unused]] static const uint64_t k%sOrderN0 = 0x%016x;\n", cName, montgomeryN0(params.N)); err != nil { 139 return err 140 } 141 142 if _, err := io.WriteString(w, "#if defined(OPENSSL_64_BIT)\n"); err != nil { 143 return err 144 } 145 if err := writeDecls(64); err != nil { 146 return err 147 } 148 if _, err := io.WriteString(w, "#elif defined(OPENSSL_32_BIT)\n"); err != nil { 149 return err 150 } 151 if err := writeDecls(32); err != nil { 152 return err 153 } 154 if _, err := io.WriteString(w, "#else\n#error \"unknown word size\"\n#endif\n"); err != nil { 155 return err 156 } 157 return nil 158} 159 160func writeP256NistzTable(path string) error { 161 curve := elliptic.P256() 162 tables := make([][][2]*big.Int, 0, 37) 163 for shift := 0; shift < 256; shift += 7 { 164 row := makeMultiples(curve, 64, shift) 165 tables = append(tables, row) 166 } 167 168 f, err := os.Create(path) 169 if err != nil { 170 return err 171 } 172 defer f.Close() 173 w := &columnWriter{w: f} 174 175 const fileHeader = `// Copyright 2014-2016 The OpenSSL Project Authors. All Rights Reserved. 176// Copyright (c) 2015, Intel Inc. 177// 178// Licensed under the Apache License, Version 2.0 (the "License"); 179// you may not use this file except in compliance with the License. 180// You may obtain a copy of the License at 181// 182// https://www.apache.org/licenses/LICENSE-2.0 183// 184// Unless required by applicable law or agreed to in writing, software 185// distributed under the License is distributed on an "AS IS" BASIS, 186// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 187// See the License for the specific language governing permissions and 188// limitations under the License. 189 190// This is the precomputed constant time access table for the code in 191// p256-nistz.c, for the default generator. The table consists of 37 192// subtables, each subtable contains 64 affine points. The affine points are 193// encoded as eight uint64's, four for the x coordinate and four for the y. 194// Both values are in little-endian order. There are 37 tables because a 195// signed, 6-bit wNAF form of the scalar is used and ceil(256/(6 + 1)) = 37. 196// Within each table there are 64 values because the 6-bit wNAF value can take 197// 64 values, ignoring the sign bit, which is implemented by performing a 198// negation of the affine point when required. We would like to align it to 2MB 199// in order to increase the chances of using a large page but that appears to 200// lead to invalid ELF files being produced. 201 202// This file is generated by make_tables.go. 203 204alignas(4096) static const PRECOMP256_ROW ecp_nistz256_precomputed[37] = ` 205 if _, err := io.WriteString(w, fileHeader); err != nil { 206 return err 207 } 208 if err := writeTables(w, curve, tables, writeBNMont); err != nil { 209 return err 210 } 211 if _, err := io.WriteString(w, ";\n"); err != nil { 212 return err 213 } 214 215 return nil 216} 217 218func writeP256Table(path string) error { 219 curve := elliptic.P256() 220 tables := [][][2]*big.Int{ 221 makeComb(curve, 64, 4, 0), 222 makeComb(curve, 64, 4, 32), 223 } 224 225 f, err := os.Create(path) 226 if err != nil { 227 return err 228 } 229 defer f.Close() 230 w := &columnWriter{w: f} 231 232 const fileHeader = `// Copyright 2020 The BoringSSL Authors 233// 234// Licensed under the Apache License, Version 2.0 (the "License"); 235// you may not use this file except in compliance with the License. 236// You may obtain a copy of the License at 237// 238// https://www.apache.org/licenses/LICENSE-2.0 239// 240// Unless required by applicable law or agreed to in writing, software 241// distributed under the License is distributed on an "AS IS" BASIS, 242// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 243// See the License for the specific language governing permissions and 244// limitations under the License. 245 246// This file is generated by make_tables.go. 247 248// Base point pre computation 249// -------------------------- 250// 251// Two different sorts of precomputed tables are used in the following code. 252// Each contain various points on the curve, where each point is three field 253// elements (x, y, z). 254// 255// For the base point table, z is usually 1 (0 for the point at infinity). 256// This table has 2 * 16 elements, starting with the following: 257// index | bits | point 258// ------+---------+------------------------------ 259// 0 | 0 0 0 0 | 0G 260// 1 | 0 0 0 1 | 1G 261// 2 | 0 0 1 0 | 2^64G 262// 3 | 0 0 1 1 | (2^64 + 1)G 263// 4 | 0 1 0 0 | 2^128G 264// 5 | 0 1 0 1 | (2^128 + 1)G 265// 6 | 0 1 1 0 | (2^128 + 2^64)G 266// 7 | 0 1 1 1 | (2^128 + 2^64 + 1)G 267// 8 | 1 0 0 0 | 2^192G 268// 9 | 1 0 0 1 | (2^192 + 1)G 269// 10 | 1 0 1 0 | (2^192 + 2^64)G 270// 11 | 1 0 1 1 | (2^192 + 2^64 + 1)G 271// 12 | 1 1 0 0 | (2^192 + 2^128)G 272// 13 | 1 1 0 1 | (2^192 + 2^128 + 1)G 273// 14 | 1 1 1 0 | (2^192 + 2^128 + 2^64)G 274// 15 | 1 1 1 1 | (2^192 + 2^128 + 2^64 + 1)G 275// followed by a copy of this with each element multiplied by 2^32. 276// 277// The reason for this is so that we can clock bits into four different 278// locations when doing simple scalar multiplies against the base point, 279// and then another four locations using the second 16 elements. 280// 281// Tables for other points have table[i] = iG for i in 0 .. 16. 282 283// fiat_p256_g_pre_comp is the table of precomputed base points 284#if defined(OPENSSL_64_BIT) 285static const fiat_p256_felem fiat_p256_g_pre_comp[2][15][2] = ` 286 if _, err := io.WriteString(w, fileHeader); err != nil { 287 return err 288 } 289 if err := writeTables(w, curve, tables, writeU64Mont); err != nil { 290 return err 291 } 292 if _, err := io.WriteString(w, ";\n#else\nstatic const fiat_p256_felem fiat_p256_g_pre_comp[2][15][2] = "); err != nil { 293 return err 294 } 295 if err := writeTables(w, curve, tables, writeU32Mont); err != nil { 296 return err 297 } 298 if _, err := io.WriteString(w, ";\n#endif\n"); err != nil { 299 return err 300 } 301 302 return nil 303} 304 305// makeMultiples returns a table of the first n multiples of 2^shift * G, 306// starting from 1 * 2^shift * G. 307func makeMultiples(curve elliptic.Curve, n, shift int) [][2]*big.Int { 308 ret := make([][2]*big.Int, n) 309 x, y := curve.Params().Gx, curve.Params().Gy 310 for j := 0; j < shift; j++ { 311 x, y = curve.Double(x, y) 312 } 313 ret[1-1] = [2]*big.Int{x, y} 314 for i := 2; i <= n; i++ { 315 if i&1 == 0 { 316 x, y := curve.Double(ret[i/2-1][0], ret[i/2-1][1]) 317 ret[i-1] = [2]*big.Int{x, y} 318 } else { 319 x, y := curve.Add(ret[i-1-1][0], ret[i-1-1][1], ret[1-1][0], ret[1-1][1]) 320 ret[i-1] = [2]*big.Int{x, y} 321 } 322 } 323 return ret 324} 325 326// makeComb returns a table of 2^size - 1 points. The i-1th entry is k*G. 327// If i is represented in binary by b0*2^0 + b1*2^1 + ... bn*2^n, k is 328// b0*2^(shift + 0*stride) + b1*2^(shift + 1*stride) + ... + bn*2^(shift + n*stride). 329// The entry for i = 0 is omitted because it is always the point at infinity. 330func makeComb(curve elliptic.Curve, stride, size, shift int) [][2]*big.Int { 331 ret := make([][2]*big.Int, 1<<size-1) 332 x, y := curve.Params().Gx, curve.Params().Gy 333 for j := 0; j < shift; j++ { 334 x, y = curve.Double(x, y) 335 } 336 ret[1<<0-1] = [2]*big.Int{x, y} 337 for i := 1; i < size; i++ { 338 // Entry 2^i is entry 2^(i-1) doubled stride times. 339 x, y = ret[1<<(i-1)-1][0], ret[1<<(i-1)-1][1] 340 for j := 0; j < stride; j++ { 341 x, y = curve.Double(x, y) 342 } 343 ret[1<<i-1] = [2]*big.Int{x, y} 344 // The remaining entries with MSB 2^i are computed by adding entry 2^i 345 // to the corresponding previous entry. 346 for j := 1; j < 1<<i; j++ { 347 x, y = curve.Add(ret[1<<i-1][0], ret[1<<i-1][1], ret[j-1][0], ret[j-1][1]) 348 ret[1<<i+j-1] = [2]*big.Int{x, y} 349 } 350 } 351 return ret 352} 353 354func montgomeryR(p *big.Int, wordSize int) *big.Int { 355 // R is the bit width of p, rounded up to word size. 356 rounded := wordSize * ((p.BitLen() + wordSize - 1) / wordSize) 357 R := new(big.Int).SetInt64(1) 358 R.Lsh(R, uint(rounded)) 359 R.Mod(R, p) 360 return R 361} 362 363func montgomeryRR(p *big.Int, wordSize int) *big.Int { 364 R := montgomeryR(p, wordSize) 365 R.Mul(R, R) 366 R.Mod(R, p) 367 return R 368} 369 370func montgomeryN0(p *big.Int) uint64 { 371 two64 := new(big.Int) 372 two64 = two64.SetBit(two64, 64, 1) 373 n0 := new(big.Int).Neg(p) 374 n0 = n0.ModInverse(n0, two64) 375 if !n0.IsUint64() { 376 panic("n0 should fit in uint64") 377 } 378 return n0.Uint64() 379} 380 381// toMontgomery returns n×R mod p, where R is the Montgomery factor. 382func toMontgomery(n, p *big.Int, wordSize int) *big.Int { 383 ret := montgomeryR(p, wordSize) 384 ret.Mul(ret, n) 385 ret.Mod(ret, p) 386 return ret 387} 388 389func bigIntToU64s(curve elliptic.Curve, n *big.Int) []uint64 { 390 words := (curve.Params().BitSize + 63) / 64 391 ret := make([]uint64, words) 392 bytes := n.Bytes() 393 for i, b := range bytes { 394 i = len(bytes) - i - 1 395 ret[i/8] |= uint64(b) << (8 * (i % 8)) 396 } 397 return ret 398} 399 400func bigIntToU32s(curve elliptic.Curve, n *big.Int) []uint32 { 401 words := (curve.Params().BitSize + 31) / 32 402 ret := make([]uint32, words) 403 bytes := n.Bytes() 404 for i, b := range bytes { 405 i = len(bytes) - i - 1 406 ret[i/4] |= uint32(b) << (8 * (i % 4)) 407 } 408 return ret 409} 410 411// A columnWriter is an io.Writer that tracks the number of columns in the 412// current line. 413type columnWriter struct { 414 w io.Writer 415 column int 416} 417 418func (c *columnWriter) Write(p []byte) (n int, err error) { 419 n, err = c.w.Write(p) 420 idx := bytes.LastIndexByte(p[:n], '\n') 421 if idx < 0 { 422 c.column += n 423 } else { 424 c.column = n - idx - 1 425 } 426 return 427} 428 429func writeIndent(w io.Writer, indent int) error { 430 for i := 0; i < indent; i++ { 431 if _, err := io.WriteString(w, " "); err != nil { 432 return err 433 } 434 } 435 return nil 436} 437 438func writeWordsBraced[Word any](w *columnWriter, words []Word, format func(Word) string) error { 439 if _, err := io.WriteString(w, "{"); err != nil { 440 return err 441 } 442 if err := writeWords(w, words, format); err != nil { 443 return err 444 } 445 if _, err := io.WriteString(w, "}"); err != nil { 446 return err 447 } 448 return nil 449} 450 451func writeWords[Word any](w *columnWriter, words []Word, format func(Word) string) error { 452 indent := w.column 453 for i, word := range words { 454 str := format(word) 455 if i > 0 { 456 if w.column+1+len(str) > 80 { 457 if _, err := io.WriteString(w, ",\n"); err != nil { 458 return err 459 } 460 if err := writeIndent(w, indent); err != nil { 461 return err 462 } 463 } else { 464 if _, err := io.WriteString(w, ", "); err != nil { 465 return err 466 } 467 } 468 } 469 if _, err := io.WriteString(w, str); err != nil { 470 return err 471 } 472 } 473 return nil 474} 475 476func writeDecl(w *columnWriter, curve elliptic.Curve, bits int, decl string, n *big.Int) error { 477 if _, err := fmt.Fprintf(w, "[[maybe_unused]] static const uint%d_t %s[] = {\n ", bits, decl); err != nil { 478 return err 479 } 480 if bits == 32 { 481 if err := writeWords(w, bigIntToU32s(curve, n), formatU32); err != nil { 482 return err 483 } 484 } else if bits == 64 { 485 if err := writeWords(w, bigIntToU64s(curve, n), formatU64); err != nil { 486 return err 487 } 488 } else { 489 panic("unknown bit count") 490 } 491 if _, err := fmt.Fprintf(w, "};\n"); err != nil { 492 return err 493 } 494 return nil 495} 496 497func formatBN(word uint64) string { 498 return fmt.Sprintf("TOBN(0x%08x, 0x%08x)", uint32(word>>32), uint32(word)) 499} 500 501func formatU64(word uint64) string { 502 return fmt.Sprintf("0x%016x", word) 503} 504 505func formatU32(word uint32) string { 506 return fmt.Sprintf("0x%08x", word) 507} 508 509func writeBNMont(w *columnWriter, curve elliptic.Curve, n *big.Int) error { 510 n32 := toMontgomery(n, curve.Params().P, 32) 511 n64 := toMontgomery(n, curve.Params().P, 64) 512 if n32.Cmp(n64) != 0 { 513 panic(fmt.Sprintf("Montgomery form for %s is inconsistent between 32-bit and 64-bit", curve.Params().Name)) 514 } 515 return writeWordsBraced(w, bigIntToU64s(curve, n64), formatBN) 516} 517 518func writeU64Mont(w *columnWriter, curve elliptic.Curve, n *big.Int) error { 519 n = toMontgomery(n, curve.Params().P, 64) 520 return writeWordsBraced(w, bigIntToU64s(curve, n), formatU64) 521} 522 523func writeU32Mont(w *columnWriter, curve elliptic.Curve, n *big.Int) error { 524 n = toMontgomery(n, curve.Params().P, 32) 525 return writeWordsBraced(w, bigIntToU32s(curve, n), formatU32) 526} 527 528type writeBigIntFunc func(w *columnWriter, curve elliptic.Curve, n *big.Int) error 529 530func writeTable(w *columnWriter, curve elliptic.Curve, table [][2]*big.Int, writeBigInt writeBigIntFunc) error { 531 if _, err := io.WriteString(w, "{"); err != nil { 532 return err 533 } 534 indent := w.column 535 for i, point := range table { 536 if i != 0 { 537 if _, err := io.WriteString(w, ",\n"); err != nil { 538 return err 539 } 540 if err := writeIndent(w, indent); err != nil { 541 return err 542 } 543 } 544 if _, err := io.WriteString(w, "{"); err != nil { 545 return err 546 } 547 if err := writeBigInt(w, curve, point[0]); err != nil { 548 return err 549 } 550 if _, err := io.WriteString(w, ",\n"); err != nil { 551 return err 552 } 553 if err := writeIndent(w, indent+1); err != nil { 554 return err 555 } 556 if err := writeBigInt(w, curve, point[1]); err != nil { 557 return err 558 } 559 if _, err := io.WriteString(w, "}"); err != nil { 560 return err 561 } 562 } 563 if _, err := io.WriteString(w, "}"); err != nil { 564 return err 565 } 566 return nil 567} 568 569func writeTables(w *columnWriter, curve elliptic.Curve, tables [][][2]*big.Int, writeBigInt writeBigIntFunc) error { 570 if _, err := io.WriteString(w, "{\n "); err != nil { 571 return err 572 } 573 indent := w.column 574 for i, table := range tables { 575 if i != 0 { 576 if _, err := io.WriteString(w, ",\n"); err != nil { 577 return err 578 } 579 if err := writeIndent(w, indent); err != nil { 580 return err 581 } 582 } 583 if err := writeTable(w, curve, table, writeBigInt); err != nil { 584 return err 585 } 586 } 587 if _, err := io.WriteString(w, "}"); err != nil { 588 return err 589 } 590 return nil 591} 592