1#!/usr/bin/env python
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
17import 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    ret = bytearray(32)
80    for i in range(len(ret)):
81        ret[i] = x % 256
82        x >>= 8
83    assert x == 0
84    return ret
85
86def to_ge_precomp(P):
87    # typedef struct {
88    #   fe_loose yplusx;
89    #   fe_loose yminusx;
90    #   fe_loose xy2d;
91    # } ge_precomp;
92    x, y = P
93    return ((y + x) % p, (y - x) % p, (x * y * 2 * d) % p)
94
95def to_base_25_5(x):
96    limbs = (26, 25, 26, 25, 26, 25, 26, 25, 26, 25)
97    ret = []
98    for l in limbs:
99        ret.append(x & ((1<<l) - 1))
100        x >>= l
101    assert x == 0
102    return ret
103
104def to_base_51(x):
105    ret = []
106    for _ in range(5):
107        ret.append(x & ((1<<51) - 1))
108        x >>= 51
109    assert x == 0
110    return ret
111
112def to_literal(x):
113    ret = "{{\n#if defined(BORINGSSL_CURVE25519_64BIT)\n"
114    ret += ", ".join(map(str, to_base_51(x)))
115    ret += "\n#else\n"
116    ret += ", ".join(map(str, to_base_25_5(x)))
117    ret += "\n#endif\n}}"
118    return ret
119
120def main():
121    d2 = (2 * d) % p
122
123    small_precomp = bytearray()
124    for i in range(1, 16):
125        s = (i&1) | ((i&2) << (64-1)) | ((i&4) << (128-2)) | ((i&8) << (192-3))
126        P = point_mul(s, (g_x, g_y))
127        small_precomp += to_bytes(P[0])
128        small_precomp += to_bytes(P[1])
129
130    large_precomp = []
131    for i in range(32):
132        large_precomp.append([])
133        for j in range(8):
134            P = point_mul((j + 1) << (i * 8), (g_x, g_y))
135            large_precomp[-1].append(to_ge_precomp(P))
136
137    bi_precomp = []
138    for i in range(8):
139        P = point_mul(2*i + 1, (g_x, g_y))
140        bi_precomp.append(to_ge_precomp(P))
141
142
143    buf = StringIO.StringIO()
144    buf.write("""/* Copyright (c) 2020, Google Inc.
145 *
146 * Permission to use, copy, modify, and/or distribute this software for any
147 * purpose with or without fee is hereby granted, provided that the above
148 * copyright notice and this permission notice appear in all copies.
149 *
150 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
151 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
152 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
153 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
154 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
155 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
156 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
157
158// This file is generated from
159//    ./make_curve25519_tables.py > curve25519_tables.h
160
161
162static const fe d = """)
163    buf.write(to_literal(d))
164    buf.write(""";
165
166static const fe sqrtm1 = """)
167    buf.write(to_literal(modp_sqrt_m1))
168    buf.write(""";
169
170static const fe d2 = """)
171    buf.write(to_literal(d2))
172    buf.write(""";
173
174#if defined(OPENSSL_SMALL)
175
176// This block of code replaces the standard base-point table with a much smaller
177// one. The standard table is 30,720 bytes while this one is just 960.
178//
179// This table contains 15 pairs of group elements, (x, y), where each field
180// element is serialised with |fe_tobytes|. If |i| is the index of the group
181// element then consider i+1 as a four-bit number: (i₀, i₁, i₂, i₃) (where i₀
182// is the most significant bit). The value of the group element is then:
183// (i₀×2^192 + i₁×2^128 + i₂×2^64 + i₃)G, where G is the generator.
184static const uint8_t k25519SmallPrecomp[15 * 2 * 32] = {""")
185    for i, b in enumerate(small_precomp):
186        buf.write("0x%02x, " % b)
187    buf.write("""
188};
189
190#else
191
192// k25519Precomp[i][j] = (j+1)*256^i*B
193static const ge_precomp k25519Precomp[32][8] = {
194""")
195    for child in large_precomp:
196        buf.write("{\n")
197        for val in child:
198            buf.write("{\n")
199            for term in val:
200                buf.write(to_literal(term) + ",\n")
201            buf.write("},\n")
202        buf.write("},\n")
203    buf.write("""};
204
205#endif  // OPENSSL_SMALL
206
207// Bi[i] = (2*i+1)*B
208static const ge_precomp Bi[8] = {
209""")
210    for val in bi_precomp:
211        buf.write("{\n")
212        for term in val:
213                buf.write(to_literal(term) + ",\n")
214        buf.write("},\n")
215    buf.write("""};
216""")
217
218    proc = subprocess.Popen(["clang-format"], stdin=subprocess.PIPE)
219    proc.communicate(buf.getvalue())
220
221if __name__ == "__main__":
222    main()
223