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 15package main 16 17import ( 18 "crypto/elliptic" 19 "fmt" 20 "io" 21 "math/big" 22 "os" 23) 24 25func main() { 26 if err := writeP256NistzTable("p256-nistz-table.h"); err != nil { 27 fmt.Fprintf(os.Stderr, "Error writing p256-nistz-table.h: %s\n", err) 28 os.Exit(1) 29 } 30 31 if err := writeP256Table("p256_table.h"); err != nil { 32 fmt.Fprintf(os.Stderr, "Error writing p256_table.h: %s\n", err) 33 os.Exit(1) 34 } 35} 36 37func writeP256NistzTable(path string) error { 38 curve := elliptic.P256() 39 tables := make([][][2]*big.Int, 0, 37) 40 for shift := 0; shift < 256; shift += 7 { 41 row := makeMultiples(curve, 64, shift) 42 tables = append(tables, row) 43 } 44 45 f, err := os.Create(path) 46 if err != nil { 47 return err 48 } 49 defer f.Close() 50 51 const fileHeader = `/* 52 * Copyright 2014-2016 The OpenSSL Project Authors. All Rights Reserved. 53 * Copyright (c) 2015, Intel Inc. 54 * 55 * Licensed under the OpenSSL license (the "License"). You may not use 56 * this file except in compliance with the License. You can obtain a copy 57 * in the file LICENSE in the source distribution or at 58 * https://www.openssl.org/source/license.html 59 */ 60 61// This is the precomputed constant time access table for the code in 62// p256-nistz.c, for the default generator. The table consists of 37 63// subtables, each subtable contains 64 affine points. The affine points are 64// encoded as eight uint64's, four for the x coordinate and four for the y. 65// Both values are in little-endian order. There are 37 tables because a 66// signed, 6-bit wNAF form of the scalar is used and ceil(256/(6 + 1)) = 37. 67// Within each table there are 64 values because the 6-bit wNAF value can take 68// 64 values, ignoring the sign bit, which is implemented by performing a 69// negation of the affine point when required. We would like to align it to 2MB 70// in order to increase the chances of using a large page but that appears to 71// lead to invalid ELF files being produced. 72 73// This file is generated by make_tables.go. 74 75static const alignas(4096) PRECOMP256_ROW ecp_nistz256_precomputed[37] = ` 76 if _, err := f.WriteString(fileHeader); err != nil { 77 return err 78 } 79 if err := writeTables(f, curve, tables, true, 4, writeBNMont); err != nil { 80 return err 81 } 82 if _, err := f.WriteString(";\n"); err != nil { 83 return err 84 } 85 86 return nil 87} 88 89func writeP256Table(path string) error { 90 curve := elliptic.P256() 91 tables := [][][2]*big.Int{ 92 makeComb(curve, 64, 4, 0), 93 makeComb(curve, 64, 4, 32), 94 } 95 96 f, err := os.Create(path) 97 if err != nil { 98 return err 99 } 100 defer f.Close() 101 102 const fileHeader = `/* Copyright (c) 2020, Google Inc. 103 * 104 * Permission to use, copy, modify, and/or distribute this software for any 105 * purpose with or without fee is hereby granted, provided that the above 106 * copyright notice and this permission notice appear in all copies. 107 * 108 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 109 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 110 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 111 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 112 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 113 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 114 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 115 116// This file is generated by make_tables.go. 117 118// Base point pre computation 119// -------------------------- 120// 121// Two different sorts of precomputed tables are used in the following code. 122// Each contain various points on the curve, where each point is three field 123// elements (x, y, z). 124// 125// For the base point table, z is usually 1 (0 for the point at infinity). 126// This table has 2 * 16 elements, starting with the following: 127// index | bits | point 128// ------+---------+------------------------------ 129// 0 | 0 0 0 0 | 0G 130// 1 | 0 0 0 1 | 1G 131// 2 | 0 0 1 0 | 2^64G 132// 3 | 0 0 1 1 | (2^64 + 1)G 133// 4 | 0 1 0 0 | 2^128G 134// 5 | 0 1 0 1 | (2^128 + 1)G 135// 6 | 0 1 1 0 | (2^128 + 2^64)G 136// 7 | 0 1 1 1 | (2^128 + 2^64 + 1)G 137// 8 | 1 0 0 0 | 2^192G 138// 9 | 1 0 0 1 | (2^192 + 1)G 139// 10 | 1 0 1 0 | (2^192 + 2^64)G 140// 11 | 1 0 1 1 | (2^192 + 2^64 + 1)G 141// 12 | 1 1 0 0 | (2^192 + 2^128)G 142// 13 | 1 1 0 1 | (2^192 + 2^128 + 1)G 143// 14 | 1 1 1 0 | (2^192 + 2^128 + 2^64)G 144// 15 | 1 1 1 1 | (2^192 + 2^128 + 2^64 + 1)G 145// followed by a copy of this with each element multiplied by 2^32. 146// 147// The reason for this is so that we can clock bits into four different 148// locations when doing simple scalar multiplies against the base point, 149// and then another four locations using the second 16 elements. 150// 151// Tables for other points have table[i] = iG for i in 0 .. 16. 152 153// fiat_p256_g_pre_comp is the table of precomputed base points 154#if defined(BORINGSSL_NISTP256_64BIT) 155static const fiat_p256_felem fiat_p256_g_pre_comp[2][15][2] = ` 156 if _, err := f.WriteString(fileHeader); err != nil { 157 return err 158 } 159 if err := writeTables(f, curve, tables, true, 4, writeU64Mont); err != nil { 160 return err 161 } 162 if _, err := f.WriteString(";\n#else\nstatic const fiat_p256_felem fiat_p256_g_pre_comp[2][15][2] = "); err != nil { 163 return err 164 } 165 if err := writeTables(f, curve, tables, true, 4, writeU32Mont); err != nil { 166 return err 167 } 168 if _, err := f.WriteString(";\n#endif\n"); err != nil { 169 return err 170 } 171 172 return nil 173} 174 175// makeMultiples returns a table of the first n multiples of 2^shift * G, 176// starting from 1 * 2^shift * G. 177func makeMultiples(curve elliptic.Curve, n, shift int) [][2]*big.Int { 178 ret := make([][2]*big.Int, n) 179 x, y := curve.Params().Gx, curve.Params().Gy 180 for j := 0; j < shift; j++ { 181 x, y = curve.Double(x, y) 182 } 183 ret[1-1] = [2]*big.Int{x, y} 184 for i := 2; i <= n; i++ { 185 if i&1 == 0 { 186 x, y := curve.Double(ret[i/2-1][0], ret[i/2-1][1]) 187 ret[i-1] = [2]*big.Int{x, y} 188 } else { 189 x, y := curve.Add(ret[i-1-1][0], ret[i-1-1][1], ret[1-1][0], ret[1-1][1]) 190 ret[i-1] = [2]*big.Int{x, y} 191 } 192 } 193 return ret 194} 195 196// makeComb returns a table of 2^size - 1 points. The i-1th entry is k*G. 197// If i is represented in binary by b0*2^0 + b1*2^1 + ... bn*2^n, k is 198// b0*2^(shift + 0*stride) + b1*2^(shift + 1*stride) + ... + bn*2^(shift + n*stride). 199// The entry for i = 0 is omitted because it is always the point at infinity. 200func makeComb(curve elliptic.Curve, stride, size, shift int) [][2]*big.Int { 201 ret := make([][2]*big.Int, 1<<size-1) 202 x, y := curve.Params().Gx, curve.Params().Gy 203 for j := 0; j < shift; j++ { 204 x, y = curve.Double(x, y) 205 } 206 ret[1<<0-1] = [2]*big.Int{x, y} 207 for i := 1; i < size; i++ { 208 // Entry 2^i is entry 2^(i-1) doubled stride times. 209 x, y = ret[1<<(i-1)-1][0], ret[1<<(i-1)-1][1] 210 for j := 0; j < stride; j++ { 211 x, y = curve.Double(x, y) 212 } 213 ret[1<<i-1] = [2]*big.Int{x, y} 214 // The remaining entries with MSB 2^i are computed by adding entry 2^i 215 // to the corresponding previous entry. 216 for j := 1; j < 1<<i; j++ { 217 x, y = curve.Add(ret[1<<i-1][0], ret[1<<i-1][1], ret[j-1][0], ret[j-1][1]) 218 ret[1<<i+j-1] = [2]*big.Int{x, y} 219 } 220 } 221 return ret 222} 223 224// toMontgomery sets n to be n×R mod p, where R is the Montgomery factor. 225func toMontgomery(curve elliptic.Curve, n *big.Int) *big.Int { 226 params := curve.Params() 227 // R is the bit width of p, rounded up to word size. 228 rounded64 := 64 * ((params.BitSize + 63) / 64) 229 rounded32 := 32 * ((params.BitSize + 31) / 32) 230 if rounded64 != rounded32 { 231 panic(fmt.Sprintf("Montgomery form for %s is inconsistent between 32-bit and 64-bit", params.Name)) 232 } 233 R := new(big.Int).SetInt64(1) 234 R.Lsh(R, uint(rounded64)) 235 236 ret := new(big.Int).Mul(n, R) 237 ret.Mod(ret, params.P) 238 return ret 239} 240 241func bigIntToU64s(curve elliptic.Curve, n *big.Int) []uint64 { 242 words := (curve.Params().BitSize + 63) / 64 243 ret := make([]uint64, words) 244 bytes := n.Bytes() 245 for i, b := range bytes { 246 i = len(bytes) - i - 1 247 ret[i/8] |= uint64(b) << (8 * (i % 8)) 248 } 249 return ret 250} 251 252func bigIntToU32s(curve elliptic.Curve, n *big.Int) []uint64 { 253 words := (curve.Params().BitSize + 31) / 32 254 ret := make([]uint64, words) 255 bytes := n.Bytes() 256 for i, b := range bytes { 257 i = len(bytes) - i - 1 258 ret[i/4] |= uint64(b) << (8 * (i % 4)) 259 } 260 return ret 261} 262 263func writeIndent(w io.Writer, indent int) error { 264 for i := 0; i < indent; i++ { 265 if _, err := io.WriteString(w, " "); err != nil { 266 return err 267 } 268 } 269 return nil 270} 271 272func writeWords(w io.Writer, words []uint64, wrap, indent int, format func(uint64) string) error { 273 if _, err := io.WriteString(w, "{"); err != nil { 274 return err 275 } 276 for i, word := range words { 277 if i > 0 { 278 if i%wrap == 0 { 279 if _, err := io.WriteString(w, ",\n"); err != nil { 280 return err 281 } 282 if err := writeIndent(w, indent+1); err != nil { 283 return err 284 } 285 } else { 286 if _, err := io.WriteString(w, ", "); err != nil { 287 return err 288 } 289 } 290 } 291 if _, err := io.WriteString(w, format(word)); err != nil { 292 return err 293 } 294 } 295 if _, err := io.WriteString(w, "}"); err != nil { 296 return err 297 } 298 return nil 299} 300 301func writeBNMont(w io.Writer, curve elliptic.Curve, n *big.Int, indent int) error { 302 n = toMontgomery(curve, n) 303 return writeWords(w, bigIntToU64s(curve, n), 2, indent, func(word uint64) string { 304 return fmt.Sprintf("TOBN(0x%08x, 0x%08x)", uint32(word>>32), uint32(word)) 305 }) 306} 307 308func writeU64Mont(w io.Writer, curve elliptic.Curve, n *big.Int, indent int) error { 309 n = toMontgomery(curve, n) 310 return writeWords(w, bigIntToU64s(curve, n), 3, indent, func(word uint64) string { 311 return fmt.Sprintf("0x%016x", word) 312 }) 313} 314 315func writeU32Mont(w io.Writer, curve elliptic.Curve, n *big.Int, indent int) error { 316 n = toMontgomery(curve, n) 317 return writeWords(w, bigIntToU32s(curve, n), 6, indent, func(word uint64) string { 318 if word >= 1<<32 { 319 panic(fmt.Sprintf("word too large: 0x%x", word)) 320 } 321 return fmt.Sprintf("0x%08x", word) 322 }) 323} 324 325type writeBigIntFunc func(w io.Writer, curve elliptic.Curve, n *big.Int, indent int) error 326 327func writeTable(w io.Writer, curve elliptic.Curve, table [][2]*big.Int, isRoot bool, indent int, writeBigInt writeBigIntFunc) error { 328 if _, err := io.WriteString(w, "{"); err != nil { 329 return err 330 } 331 if isRoot { 332 if _, err := io.WriteString(w, "\n"); err != nil { 333 return err 334 } 335 if err := writeIndent(w, indent); err != nil { 336 return err 337 } 338 } else { 339 indent++ 340 } 341 for i, point := range table { 342 if i != 0 { 343 if _, err := io.WriteString(w, ",\n"); err != nil { 344 return err 345 } 346 if err := writeIndent(w, indent); err != nil { 347 return err 348 } 349 } 350 if _, err := io.WriteString(w, "{"); err != nil { 351 return err 352 } 353 if err := writeBigInt(w, curve, point[0], indent+1); err != nil { 354 return err 355 } 356 if _, err := io.WriteString(w, ",\n"); err != nil { 357 return err 358 } 359 if err := writeIndent(w, indent+1); err != nil { 360 return err 361 } 362 if err := writeBigInt(w, curve, point[1], indent+1); err != nil { 363 return err 364 } 365 if _, err := io.WriteString(w, "}"); err != nil { 366 return err 367 } 368 } 369 if _, err := io.WriteString(w, "}"); err != nil { 370 return err 371 } 372 return nil 373} 374 375func writeTables(w io.Writer, curve elliptic.Curve, tables [][][2]*big.Int, isRoot bool, indent int, writeBigInt writeBigIntFunc) error { 376 if _, err := io.WriteString(w, "{"); err != nil { 377 return err 378 } 379 if isRoot { 380 if _, err := io.WriteString(w, "\n"); err != nil { 381 return err 382 } 383 if err := writeIndent(w, indent); err != nil { 384 return err 385 } 386 } else { 387 indent++ 388 } 389 for i, table := range tables { 390 if i != 0 { 391 if _, err := io.WriteString(w, ",\n"); err != nil { 392 return err 393 } 394 if err := writeIndent(w, indent); err != nil { 395 return err 396 } 397 } 398 if err := writeTable(w, curve, table, false, indent, writeBigInt); err != nil { 399 return err 400 } 401 } 402 if _, err := io.WriteString(w, "}"); err != nil { 403 return err 404 } 405 return nil 406} 407