1#!/usr/bin/env python3 2# coding=utf-8 3# Copyright (c) 2020, Google Inc. 4# 5# Permission to use, copy, modify, and/or distribute this software for any 6# purpose with or without fee is hereby granted, provided that the above 7# copyright notice and this permission notice appear in all copies. 8# 9# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 12# SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 14# OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 15# CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 17from io import StringIO 18import subprocess 19 20# Base field Z_p 21p = 2**255 - 19 22 23def modp_inv(x): 24 return pow(x, p-2, p) 25 26# Square root of -1 27modp_sqrt_m1 = pow(2, (p-1) // 4, p) 28 29# Compute corresponding x-coordinate, with low bit corresponding to 30# sign, or return None on failure 31def recover_x(y, sign): 32 if y >= p: 33 return None 34 x2 = (y*y-1) * modp_inv(d*y*y+1) 35 if x2 == 0: 36 if sign: 37 return None 38 else: 39 return 0 40 41 # Compute square root of x2 42 x = pow(x2, (p+3) // 8, p) 43 if (x*x - x2) % p != 0: 44 x = x * modp_sqrt_m1 % p 45 if (x*x - x2) % p != 0: 46 return None 47 48 if (x & 1) != sign: 49 x = p - x 50 return x 51 52# Curve constant 53d = -121665 * modp_inv(121666) % p 54 55# Base point 56g_y = 4 * modp_inv(5) % p 57g_x = recover_x(g_y, 0) 58 59# Points are represented as affine tuples (x, y). 60 61def point_add(P, Q): 62 x1, y1 = P 63 x2, y2 = Q 64 x3 = ((x1*y2 + y1*x2) * modp_inv(1 + d*x1*x2*y1*y2)) % p 65 y3 = ((y1*y2 + x1*x2) * modp_inv(1 - d*x1*x2*y1*y2)) % p 66 return (x3, y3) 67 68# Computes Q = s * P 69def point_mul(s, P): 70 Q = (0, 1) # Neutral element 71 while s > 0: 72 if s & 1: 73 Q = point_add(Q, P) 74 P = point_add(P, P) 75 s >>= 1 76 return Q 77 78def to_bytes(x): 79 return x.to_bytes(32, "little") 80 81def to_ge_precomp(P): 82 # typedef struct { 83 # fe_loose yplusx; 84 # fe_loose yminusx; 85 # fe_loose xy2d; 86 # } ge_precomp; 87 x, y = P 88 return ((y + x) % p, (y - x) % p, (x * y * 2 * d) % p) 89 90def to_base_25_5(x): 91 limbs = (26, 25, 26, 25, 26, 25, 26, 25, 26, 25) 92 ret = [] 93 for l in limbs: 94 ret.append(x & ((1<<l) - 1)) 95 x >>= l 96 assert x == 0 97 return ret 98 99def to_base_51(x): 100 ret = [] 101 for _ in range(5): 102 ret.append(x & ((1<<51) - 1)) 103 x >>= 51 104 assert x == 0 105 return ret 106 107def to_bytes_literal(x): 108 return "{" + ", ".join(map(hex, to_bytes(x))) + "}" 109 110def to_literal(x): 111 ret = "{{\n#if defined(OPENSSL_64_BIT)\n" 112 ret += ", ".join(map(str, to_base_51(x))) 113 ret += "\n#else\n" 114 ret += ", ".join(map(str, to_base_25_5(x))) 115 ret += "\n#endif\n}}" 116 return ret 117 118def main(): 119 d2 = (2 * d) % p 120 121 small_precomp = bytearray() 122 for i in range(1, 16): 123 s = (i&1) | ((i&2) << (64-1)) | ((i&4) << (128-2)) | ((i&8) << (192-3)) 124 P = point_mul(s, (g_x, g_y)) 125 small_precomp += to_bytes(P[0]) 126 small_precomp += to_bytes(P[1]) 127 128 large_precomp = [] 129 for i in range(32): 130 large_precomp.append([]) 131 for j in range(8): 132 P = point_mul((j + 1) << (i * 8), (g_x, g_y)) 133 large_precomp[-1].append(to_ge_precomp(P)) 134 135 bi_precomp = [] 136 for i in range(8): 137 P = point_mul(2*i + 1, (g_x, g_y)) 138 bi_precomp.append(to_ge_precomp(P)) 139 140 141 buf = StringIO() 142 buf.write("""/* Copyright (c) 2020, Google Inc. 143 * 144 * Permission to use, copy, modify, and/or distribute this software for any 145 * purpose with or without fee is hereby granted, provided that the above 146 * copyright notice and this permission notice appear in all copies. 147 * 148 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 149 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 150 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY 151 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 152 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION 153 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN 154 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */ 155 156// This file is generated from 157// ./make_curve25519_tables.py > curve25519_tables.h 158 159 160static const fe d = """) 161 buf.write(to_literal(d)) 162 buf.write("""; 163 164static const fe sqrtm1 = """) 165 buf.write(to_literal(modp_sqrt_m1)) 166 buf.write("""; 167 168static const fe d2 = """) 169 buf.write(to_literal(d2)) 170 buf.write("""; 171 172#if defined(OPENSSL_SMALL) 173 174// This block of code replaces the standard base-point table with a much smaller 175// one. The standard table is 30,720 bytes while this one is just 960. 176// 177// This table contains 15 pairs of group elements, (x, y), where each field 178// element is serialised with |fe_tobytes|. If |i| is the index of the group 179// element then consider i+1 as a four-bit number: (i₀, i₁, i₂, i₃) (where i₀ 180// is the most significant bit). The value of the group element is then: 181// (i₀×2^192 + i₁×2^128 + i₂×2^64 + i₃)G, where G is the generator. 182static const uint8_t k25519SmallPrecomp[15 * 2 * 32] = {""") 183 for i, b in enumerate(small_precomp): 184 buf.write("0x%02x, " % b) 185 buf.write(""" 186}; 187 188#else 189 190// k25519Precomp[i][j] = (j+1)*256^i*B 191static const uint8_t k25519Precomp[32][8][3][32] = { 192""") 193 for child in large_precomp: 194 buf.write("{\n") 195 for val in child: 196 buf.write("{\n") 197 for term in val: 198 buf.write(to_bytes_literal(term) + ",\n") 199 buf.write("},\n") 200 buf.write("},\n") 201 buf.write("""}; 202 203#endif // OPENSSL_SMALL 204 205// Bi[i] = (2*i+1)*B 206static const ge_precomp Bi[8] = { 207""") 208 for val in bi_precomp: 209 buf.write("{\n") 210 for term in val: 211 buf.write(to_literal(term) + ",\n") 212 buf.write("},\n") 213 buf.write("""}; 214""") 215 216 proc = subprocess.Popen(["clang-format"], stdin=subprocess.PIPE) 217 proc.communicate(buf.getvalue().encode("utf8")) 218 219if __name__ == "__main__": 220 main() 221