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