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