1#!/usr/bin/env python3
2# coding=utf-8
3# Copyright 2020 The BoringSSL Authors
4#
5# Licensed under the Apache License, Version 2.0 (the "License");
6# you may not use this file except in compliance with the License.
7# You may obtain a copy of the License at
8#
9#     https://www.apache.org/licenses/LICENSE-2.0
10#
11# Unless required by applicable law or agreed to in writing, software
12# distributed under the License is distributed on an "AS IS" BASIS,
13# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14# See the License for the specific language governing permissions and
15# limitations under the License.
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 2020 The BoringSSL Authors
143//
144// Licensed under the Apache License, Version 2.0 (the "License");
145// you may not use this file except in compliance with the License.
146// You may obtain a copy of the License at
147//
148//     https://www.apache.org/licenses/LICENSE-2.0
149//
150// Unless required by applicable law or agreed to in writing, software
151// distributed under the License is distributed on an "AS IS" BASIS,
152// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
153// See the License for the specific language governing permissions and
154// limitations under the License.
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