Home | History | Annotate | Download | only in fiat 
      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