1// Copyright (c) 2020, Google Inc. 2// 3// Permission to use, copy, modify, and/or distribute this software for any 4// purpose with or without fee is hereby granted, provided that the above 5// copyright notice and this permission notice appear in all copies. 6// 7// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 8// WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 9// MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 10// SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 11// WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 12// OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 13// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 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 (c) 2023, Google Inc. 55 * 56 * Permission to use, copy, modify, and/or distribute this software for any 57 * purpose with or without fee is hereby granted, provided that the above 58 * copyright notice and this permission notice appear in all copies. 59 * 60 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 61 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 62 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 63 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 64 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 65 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 66 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 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, "OPENSSL_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, "OPENSSL_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 = `/* 176 * Copyright 2014-2016 The OpenSSL Project Authors. All Rights Reserved. 177 * Copyright (c) 2015, Intel Inc. 178 * 179 * Licensed under the OpenSSL license (the "License"). You may not use 180 * this file except in compliance with the License. You can obtain a copy 181 * in the file LICENSE in the source distribution or at 182 * https://www.openssl.org/source/license.html 183 */ 184 185// This is the precomputed constant time access table for the code in 186// p256-nistz.c, for the default generator. The table consists of 37 187// subtables, each subtable contains 64 affine points. The affine points are 188// encoded as eight uint64's, four for the x coordinate and four for the y. 189// Both values are in little-endian order. There are 37 tables because a 190// signed, 6-bit wNAF form of the scalar is used and ceil(256/(6 + 1)) = 37. 191// Within each table there are 64 values because the 6-bit wNAF value can take 192// 64 values, ignoring the sign bit, which is implemented by performing a 193// negation of the affine point when required. We would like to align it to 2MB 194// in order to increase the chances of using a large page but that appears to 195// lead to invalid ELF files being produced. 196 197// This file is generated by make_tables.go. 198 199static const alignas(4096) PRECOMP256_ROW ecp_nistz256_precomputed[37] = ` 200 if _, err := io.WriteString(w, fileHeader); err != nil { 201 return err 202 } 203 if err := writeTables(w, curve, tables, writeBNMont); err != nil { 204 return err 205 } 206 if _, err := io.WriteString(w, ";\n"); err != nil { 207 return err 208 } 209 210 return nil 211} 212 213func writeP256Table(path string) error { 214 curve := elliptic.P256() 215 tables := [][][2]*big.Int{ 216 makeComb(curve, 64, 4, 0), 217 makeComb(curve, 64, 4, 32), 218 } 219 220 f, err := os.Create(path) 221 if err != nil { 222 return err 223 } 224 defer f.Close() 225 w := &columnWriter{w: f} 226 227 const fileHeader = `/* Copyright (c) 2020, Google Inc. 228 * 229 * Permission to use, copy, modify, and/or distribute this software for any 230 * purpose with or without fee is hereby granted, provided that the above 231 * copyright notice and this permission notice appear in all copies. 232 * 233 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 234 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 235 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 236 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 237 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 238 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 239 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 240 241// This file is generated by make_tables.go. 242 243// Base point pre computation 244// -------------------------- 245// 246// Two different sorts of precomputed tables are used in the following code. 247// Each contain various points on the curve, where each point is three field 248// elements (x, y, z). 249// 250// For the base point table, z is usually 1 (0 for the point at infinity). 251// This table has 2 * 16 elements, starting with the following: 252// index | bits | point 253// ------+---------+------------------------------ 254// 0 | 0 0 0 0 | 0G 255// 1 | 0 0 0 1 | 1G 256// 2 | 0 0 1 0 | 2^64G 257// 3 | 0 0 1 1 | (2^64 + 1)G 258// 4 | 0 1 0 0 | 2^128G 259// 5 | 0 1 0 1 | (2^128 + 1)G 260// 6 | 0 1 1 0 | (2^128 + 2^64)G 261// 7 | 0 1 1 1 | (2^128 + 2^64 + 1)G 262// 8 | 1 0 0 0 | 2^192G 263// 9 | 1 0 0 1 | (2^192 + 1)G 264// 10 | 1 0 1 0 | (2^192 + 2^64)G 265// 11 | 1 0 1 1 | (2^192 + 2^64 + 1)G 266// 12 | 1 1 0 0 | (2^192 + 2^128)G 267// 13 | 1 1 0 1 | (2^192 + 2^128 + 1)G 268// 14 | 1 1 1 0 | (2^192 + 2^128 + 2^64)G 269// 15 | 1 1 1 1 | (2^192 + 2^128 + 2^64 + 1)G 270// followed by a copy of this with each element multiplied by 2^32. 271// 272// The reason for this is so that we can clock bits into four different 273// locations when doing simple scalar multiplies against the base point, 274// and then another four locations using the second 16 elements. 275// 276// Tables for other points have table[i] = iG for i in 0 .. 16. 277 278// fiat_p256_g_pre_comp is the table of precomputed base points 279#if defined(OPENSSL_64_BIT) 280static const fiat_p256_felem fiat_p256_g_pre_comp[2][15][2] = ` 281 if _, err := io.WriteString(w, fileHeader); err != nil { 282 return err 283 } 284 if err := writeTables(w, curve, tables, writeU64Mont); err != nil { 285 return err 286 } 287 if _, err := io.WriteString(w, ";\n#else\nstatic const fiat_p256_felem fiat_p256_g_pre_comp[2][15][2] = "); err != nil { 288 return err 289 } 290 if err := writeTables(w, curve, tables, writeU32Mont); err != nil { 291 return err 292 } 293 if _, err := io.WriteString(w, ";\n#endif\n"); err != nil { 294 return err 295 } 296 297 return nil 298} 299 300// makeMultiples returns a table of the first n multiples of 2^shift * G, 301// starting from 1 * 2^shift * G. 302func makeMultiples(curve elliptic.Curve, n, shift int) [][2]*big.Int { 303 ret := make([][2]*big.Int, n) 304 x, y := curve.Params().Gx, curve.Params().Gy 305 for j := 0; j < shift; j++ { 306 x, y = curve.Double(x, y) 307 } 308 ret[1-1] = [2]*big.Int{x, y} 309 for i := 2; i <= n; i++ { 310 if i&1 == 0 { 311 x, y := curve.Double(ret[i/2-1][0], ret[i/2-1][1]) 312 ret[i-1] = [2]*big.Int{x, y} 313 } else { 314 x, y := curve.Add(ret[i-1-1][0], ret[i-1-1][1], ret[1-1][0], ret[1-1][1]) 315 ret[i-1] = [2]*big.Int{x, y} 316 } 317 } 318 return ret 319} 320 321// makeComb returns a table of 2^size - 1 points. The i-1th entry is k*G. 322// If i is represented in binary by b0*2^0 + b1*2^1 + ... bn*2^n, k is 323// b0*2^(shift + 0*stride) + b1*2^(shift + 1*stride) + ... + bn*2^(shift + n*stride). 324// The entry for i = 0 is omitted because it is always the point at infinity. 325func makeComb(curve elliptic.Curve, stride, size, shift int) [][2]*big.Int { 326 ret := make([][2]*big.Int, 1<<size-1) 327 x, y := curve.Params().Gx, curve.Params().Gy 328 for j := 0; j < shift; j++ { 329 x, y = curve.Double(x, y) 330 } 331 ret[1<<0-1] = [2]*big.Int{x, y} 332 for i := 1; i < size; i++ { 333 // Entry 2^i is entry 2^(i-1) doubled stride times. 334 x, y = ret[1<<(i-1)-1][0], ret[1<<(i-1)-1][1] 335 for j := 0; j < stride; j++ { 336 x, y = curve.Double(x, y) 337 } 338 ret[1<<i-1] = [2]*big.Int{x, y} 339 // The remaining entries with MSB 2^i are computed by adding entry 2^i 340 // to the corresponding previous entry. 341 for j := 1; j < 1<<i; j++ { 342 x, y = curve.Add(ret[1<<i-1][0], ret[1<<i-1][1], ret[j-1][0], ret[j-1][1]) 343 ret[1<<i+j-1] = [2]*big.Int{x, y} 344 } 345 } 346 return ret 347} 348 349func montgomeryR(p *big.Int, wordSize int) *big.Int { 350 // R is the bit width of p, rounded up to word size. 351 rounded := wordSize * ((p.BitLen() + wordSize - 1) / wordSize) 352 R := new(big.Int).SetInt64(1) 353 R.Lsh(R, uint(rounded)) 354 R.Mod(R, p) 355 return R 356} 357 358func montgomeryRR(p *big.Int, wordSize int) *big.Int { 359 R := montgomeryR(p, wordSize) 360 R.Mul(R, R) 361 R.Mod(R, p) 362 return R 363} 364 365func montgomeryN0(p *big.Int) uint64 { 366 two64 := new(big.Int) 367 two64 = two64.SetBit(two64, 64, 1) 368 n0 := new(big.Int).Neg(p) 369 n0 = n0.ModInverse(n0, two64) 370 if !n0.IsUint64() { 371 panic("n0 should fit in uint64") 372 } 373 return n0.Uint64() 374} 375 376// toMontgomery returns n×R mod p, where R is the Montgomery factor. 377func toMontgomery(n, p *big.Int, wordSize int) *big.Int { 378 ret := montgomeryR(p, wordSize) 379 ret.Mul(ret, n) 380 ret.Mod(ret, p) 381 return ret 382} 383 384func bigIntToU64s(curve elliptic.Curve, n *big.Int) []uint64 { 385 words := (curve.Params().BitSize + 63) / 64 386 ret := make([]uint64, words) 387 bytes := n.Bytes() 388 for i, b := range bytes { 389 i = len(bytes) - i - 1 390 ret[i/8] |= uint64(b) << (8 * (i % 8)) 391 } 392 return ret 393} 394 395func bigIntToU32s(curve elliptic.Curve, n *big.Int) []uint32 { 396 words := (curve.Params().BitSize + 31) / 32 397 ret := make([]uint32, words) 398 bytes := n.Bytes() 399 for i, b := range bytes { 400 i = len(bytes) - i - 1 401 ret[i/4] |= uint32(b) << (8 * (i % 4)) 402 } 403 return ret 404} 405 406// A columnWriter is an io.Writer that tracks the number of columns in the 407// current line. 408type columnWriter struct { 409 w io.Writer 410 column int 411} 412 413func (c *columnWriter) Write(p []byte) (n int, err error) { 414 n, err = c.w.Write(p) 415 idx := bytes.LastIndexByte(p[:n], '\n') 416 if idx < 0 { 417 c.column += n 418 } else { 419 c.column = n - idx - 1 420 } 421 return 422} 423 424func writeIndent(w io.Writer, indent int) error { 425 for i := 0; i < indent; i++ { 426 if _, err := io.WriteString(w, " "); err != nil { 427 return err 428 } 429 } 430 return nil 431} 432 433func writeWordsBraced[Word any](w *columnWriter, words []Word, format func(Word) string) error { 434 if _, err := io.WriteString(w, "{"); err != nil { 435 return err 436 } 437 if err := writeWords(w, words, format); err != nil { 438 return err 439 } 440 if _, err := io.WriteString(w, "}"); err != nil { 441 return err 442 } 443 return nil 444} 445 446func writeWords[Word any](w *columnWriter, words []Word, format func(Word) string) error { 447 indent := w.column 448 for i, word := range words { 449 str := format(word) 450 if i > 0 { 451 if w.column+1+len(str) > 80 { 452 if _, err := io.WriteString(w, ",\n"); err != nil { 453 return err 454 } 455 if err := writeIndent(w, indent); err != nil { 456 return err 457 } 458 } else { 459 if _, err := io.WriteString(w, ", "); err != nil { 460 return err 461 } 462 } 463 } 464 if _, err := io.WriteString(w, str); err != nil { 465 return err 466 } 467 } 468 return nil 469} 470 471func writeDecl(w *columnWriter, curve elliptic.Curve, bits int, decl string, n *big.Int) error { 472 if _, err := fmt.Fprintf(w, "OPENSSL_UNUSED static const uint%d_t %s[] = {\n ", bits, decl); err != nil { 473 return err 474 } 475 if bits == 32 { 476 if err := writeWords(w, bigIntToU32s(curve, n), formatU32); err != nil { 477 return err 478 } 479 } else if bits == 64 { 480 if err := writeWords(w, bigIntToU64s(curve, n), formatU64); err != nil { 481 return err 482 } 483 } else { 484 panic("unknown bit count") 485 } 486 if _, err := fmt.Fprintf(w, "};\n"); err != nil { 487 return err 488 } 489 return nil 490} 491 492func formatBN(word uint64) string { 493 return fmt.Sprintf("TOBN(0x%08x, 0x%08x)", uint32(word>>32), uint32(word)) 494} 495 496func formatU64(word uint64) string { 497 return fmt.Sprintf("0x%016x", word) 498} 499 500func formatU32(word uint32) string { 501 return fmt.Sprintf("0x%08x", word) 502} 503 504func writeBNMont(w *columnWriter, curve elliptic.Curve, n *big.Int) error { 505 n32 := toMontgomery(n, curve.Params().P, 32) 506 n64 := toMontgomery(n, curve.Params().P, 64) 507 if n32.Cmp(n64) != 0 { 508 panic(fmt.Sprintf("Montgomery form for %s is inconsistent between 32-bit and 64-bit", curve.Params().Name)) 509 } 510 return writeWordsBraced(w, bigIntToU64s(curve, n64), formatBN) 511} 512 513func writeU64Mont(w *columnWriter, curve elliptic.Curve, n *big.Int) error { 514 n = toMontgomery(n, curve.Params().P, 64) 515 return writeWordsBraced(w, bigIntToU64s(curve, n), formatU64) 516} 517 518func writeU32Mont(w *columnWriter, curve elliptic.Curve, n *big.Int) error { 519 n = toMontgomery(n, curve.Params().P, 32) 520 return writeWordsBraced(w, bigIntToU32s(curve, n), formatU32) 521} 522 523type writeBigIntFunc func(w *columnWriter, curve elliptic.Curve, n *big.Int) error 524 525func writeTable(w *columnWriter, curve elliptic.Curve, table [][2]*big.Int, writeBigInt writeBigIntFunc) error { 526 if _, err := io.WriteString(w, "{"); err != nil { 527 return err 528 } 529 indent := w.column 530 for i, point := range table { 531 if i != 0 { 532 if _, err := io.WriteString(w, ",\n"); err != nil { 533 return err 534 } 535 if err := writeIndent(w, indent); err != nil { 536 return err 537 } 538 } 539 if _, err := io.WriteString(w, "{"); err != nil { 540 return err 541 } 542 if err := writeBigInt(w, curve, point[0]); err != nil { 543 return err 544 } 545 if _, err := io.WriteString(w, ",\n"); err != nil { 546 return err 547 } 548 if err := writeIndent(w, indent+1); err != nil { 549 return err 550 } 551 if err := writeBigInt(w, curve, point[1]); err != nil { 552 return err 553 } 554 if _, err := io.WriteString(w, "}"); err != nil { 555 return err 556 } 557 } 558 if _, err := io.WriteString(w, "}"); err != nil { 559 return err 560 } 561 return nil 562} 563 564func writeTables(w *columnWriter, curve elliptic.Curve, tables [][][2]*big.Int, writeBigInt writeBigIntFunc) error { 565 if _, err := io.WriteString(w, "{\n "); err != nil { 566 return err 567 } 568 indent := w.column 569 for i, table := range tables { 570 if i != 0 { 571 if _, err := io.WriteString(w, ",\n"); err != nil { 572 return err 573 } 574 if err := writeIndent(w, indent); err != nil { 575 return err 576 } 577 } 578 if err := writeTable(w, curve, table, writeBigInt); err != nil { 579 return err 580 } 581 } 582 if _, err := io.WriteString(w, "}"); err != nil { 583 return err 584 } 585 return nil 586} 587