crypto/curve25519/make_curve25519_tables.py - boringssl.git - Git at Google

 #!/usr/bin/env python
 # coding=utf-8
 # Copyright (c) 2020, Google Inc.
 #
 # Permission to use, copy, modify, and/or distribute this software for any
 # purpose with or without fee is hereby granted, provided that the above
 # copyright notice and this permission notice appear in all copies.
 #
 # THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 # WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 # MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 # SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 # WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
 # OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 # CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

 import StringIO
 import subprocess

 # Base field Z_p
 p = 2**255 - 19

 def modp_inv(x):
     return pow(x, p-2, p)

 # Square root of -1
 modp_sqrt_m1 = pow(2, (p-1) // 4, p)

 # Compute corresponding x-coordinate, with low bit corresponding to
 # sign, or return None on failure
 def recover_x(y, sign):
     if y >= p:
         return None
     x2 = (y*y-1) * modp_inv(d*y*y+1)
     if x2 == 0:
         if sign:
             return None
         else:
             return 0

     # Compute square root of x2
     x = pow(x2, (p+3) // 8, p)
     if (x*x - x2) % p != 0:
         x = x * modp_sqrt_m1 % p
     if (x*x - x2) % p != 0:
         return None

     if (x & 1) != sign:
         x = p - x
     return x

 # Curve constant
 d = -121665 * modp_inv(121666) % p

 # Base point
 g_y = 4 * modp_inv(5) % p
 g_x = recover_x(g_y, 0)

 # Points are represented as affine tuples (x, y).

 def point_add(P, Q):
     x1, y1 = P
     x2, y2 = Q
     x3 = ((x1*y2 + y1*x2) * modp_inv(1 + d*x1*x2*y1*y2)) % p
     y3 = ((y1*y2 + x1*x2) * modp_inv(1 - d*x1*x2*y1*y2)) % p
     return (x3, y3)

 # Computes Q = s * P
 def point_mul(s, P):
     Q = (0, 1)  # Neutral element
     while s > 0:
         if s & 1:
             Q = point_add(Q, P)
         P = point_add(P, P)
         s >>= 1
     return Q

 def to_bytes(x):
     ret = bytearray(32)
     for i in range(len(ret)):
         ret[i] = x % 256
         x >>= 8
     assert x == 0
     return ret

 def to_ge_precomp(P):
     # typedef struct {
     #   fe_loose yplusx;
     #   fe_loose yminusx;
     #   fe_loose xy2d;
     # } ge_precomp;
     x, y = P
     return ((y + x) % p, (y - x) % p, (x * y * 2 * d) % p)

 def to_base_25_5(x):
     limbs = (26, 25, 26, 25, 26, 25, 26, 25, 26, 25)
     ret = []
     for l in limbs:
         ret.append(x & ((1<<l) - 1))
         x >>= l
     assert x == 0
     return ret

 def to_base_51(x):
     ret = []
     for _ in range(5):
         ret.append(x & ((1<<51) - 1))
         x >>= 51
     assert x == 0
     return ret

 def to_literal(x):
     ret = "{{\n#if defined(BORINGSSL_CURVE25519_64BIT)\n"
     ret += ", ".join(map(str, to_base_51(x)))
     ret += "\n#else\n"
     ret += ", ".join(map(str, to_base_25_5(x)))
     ret += "\n#endif\n}}"
     return ret

 def main():
     d2 = (2 * d) % p

     small_precomp = bytearray()
     for i in range(1, 16):
         s = (i&1) | ((i&2) << (64-1)) | ((i&4) << (128-2)) | ((i&8) << (192-3))
         P = point_mul(s, (g_x, g_y))
         small_precomp += to_bytes(P[0])
         small_precomp += to_bytes(P[1])

     large_precomp = []
     for i in range(32):
         large_precomp.append([])
         for j in range(8):
             P = point_mul((j + 1) << (i * 8), (g_x, g_y))
             large_precomp[-1].append(to_ge_precomp(P))

     bi_precomp = []
     for i in range(8):
         P = point_mul(2*i + 1, (g_x, g_y))
         bi_precomp.append(to_ge_precomp(P))


     buf = StringIO.StringIO()
     buf.write("""/* Copyright (c) 2020, Google Inc.
  *
  * Permission to use, copy, modify, and/or distribute this software for any
  * purpose with or without fee is hereby granted, provided that the above
  * copyright notice and this permission notice appear in all copies.
  *
  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
  * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
  * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */

 // This file is generated from
 //    ./make_curve25519_tables.py > curve25519_tables.h


 static const fe d = """)
     buf.write(to_literal(d))
     buf.write(""";

 static const fe sqrtm1 = """)
     buf.write(to_literal(modp_sqrt_m1))
     buf.write(""";

 static const fe d2 = """)
     buf.write(to_literal(d2))
     buf.write(""";

 #if defined(OPENSSL_SMALL)

 // This block of code replaces the standard base-point table with a much smaller
 // one. The standard table is 30,720 bytes while this one is just 960.
 //
 // This table contains 15 pairs of group elements, (x, y), where each field
 // element is serialised with |fe_tobytes|. If |i| is the index of the group
 // element then consider i+1 as a four-bit number: (i₀, i₁, i₂, i₃) (where i₀
 // is the most significant bit). The value of the group element is then:
 // (i₀×2^192 + i₁×2^128 + i₂×2^64 + i₃)G, where G is the generator.
 static const uint8_t k25519SmallPrecomp[15 * 2 * 32] = {""")
     for i, b in enumerate(small_precomp):
         buf.write("0x%02x, " % b)
     buf.write("""
 };

 #else

 // k25519Precomp[i][j] = (j+1)*256^i*B
 static const ge_precomp k25519Precomp[32][8] = {
 """)
     for child in large_precomp:
         buf.write("{\n")
         for val in child:
             buf.write("{\n")
             for term in val:
                 buf.write(to_literal(term) + ",\n")
             buf.write("},\n")
         buf.write("},\n")
     buf.write("""};

 #endif  // OPENSSL_SMALL

 // Bi[i] = (2*i+1)*B
 static const ge_precomp Bi[8] = {
 """)
     for val in bi_precomp:
         buf.write("{\n")
         for term in val:
                 buf.write(to_literal(term) + ",\n")
         buf.write("},\n")
     buf.write("""};
 """)

     proc = subprocess.Popen(["clang-format"], stdin=subprocess.PIPE)
     proc.communicate(buf.getvalue())

 if __name__ == "__main__":
     main()
	#!/usr/bin/env python
	# coding=utf-8
	# Copyright (c) 2020, Google Inc.
	#
	# Permission to use, copy, modify, and/or distribute this software for any
	# purpose with or without fee is hereby granted, provided that the above
	# copyright notice and this permission notice appear in all copies.
	#
	# THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	# WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	# MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
	# SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	# WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
	# OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
	# CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

	import StringIO
	import subprocess

	# Base field Z_p
	p = 2**255 - 19

	def modp_inv(x):
	return pow(x, p-2, p)

	# Square root of -1
	modp_sqrt_m1 = pow(2, (p-1) // 4, p)

	# Compute corresponding x-coordinate, with low bit corresponding to
	# sign, or return None on failure
	def recover_x(y, sign):
	if y >= p:
	return None
	x2 = (yy-1) modp_inv(dyy+1)
	if x2 == 0:
	if sign:
	return None
	else:
	return 0

	# Compute square root of x2
	x = pow(x2, (p+3) // 8, p)
	if (x*x - x2) % p != 0:
	x = x * modp_sqrt_m1 % p
	if (x*x - x2) % p != 0:
	return None

	if (x & 1) != sign:
	x = p - x
	return x

	# Curve constant
	d = -121665 * modp_inv(121666) % p

	# Base point
	g_y = 4 * modp_inv(5) % p
	g_x = recover_x(g_y, 0)

	# Points are represented as affine tuples (x, y).

	def point_add(P, Q):
	x1, y1 = P
	x2, y2 = Q
	x3 = ((x1y2 + y1x2) * modp_inv(1 + dx1x2y1y2)) % p
	y3 = ((y1y2 + x1x2) * modp_inv(1 - dx1x2y1y2)) % p
	return (x3, y3)

	# Computes Q = s * P
	def point_mul(s, P):
	Q = (0, 1) # Neutral element
	while s > 0:
	if s & 1:
	Q = point_add(Q, P)
	P = point_add(P, P)
	s >>= 1
	return Q

	def to_bytes(x):
	ret = bytearray(32)
	for i in range(len(ret)):
	ret[i] = x % 256
	x >>= 8
	assert x == 0
	return ret

	def to_ge_precomp(P):
	# typedef struct {
	# fe_loose yplusx;
	# fe_loose yminusx;
	# fe_loose xy2d;
	# } ge_precomp;
	x, y = P
	return ((y + x) % p, (y - x) % p, (x * y * 2 * d) % p)

	def to_base_25_5(x):
	limbs = (26, 25, 26, 25, 26, 25, 26, 25, 26, 25)
	ret = []
	for l in limbs:
	ret.append(x & ((1<<l) - 1))
	x >>= l
	assert x == 0
	return ret

	def to_base_51(x):
	ret = []
	for _ in range(5):
	ret.append(x & ((1<<51) - 1))
	x >>= 51
	assert x == 0
	return ret

	def to_literal(x):
	ret = "{{\n#if defined(BORINGSSL_CURVE25519_64BIT)\n"
	ret += ", ".join(map(str, to_base_51(x)))
	ret += "\n#else\n"
	ret += ", ".join(map(str, to_base_25_5(x)))
	ret += "\n#endif\n}}"
	return ret

	def main():
	d2 = (2 * d) % p

	small_precomp = bytearray()
	for i in range(1, 16):
	s = (i&1) \| ((i&2) << (64-1)) \| ((i&4) << (128-2)) \| ((i&8) << (192-3))
	P = point_mul(s, (g_x, g_y))
	small_precomp += to_bytes(P[0])
	small_precomp += to_bytes(P[1])

	large_precomp = []
	for i in range(32):
	large_precomp.append([])
	for j in range(8):
	P = point_mul((j + 1) << (i * 8), (g_x, g_y))
	large_precomp[-1].append(to_ge_precomp(P))

	bi_precomp = []
	for i in range(8):
	P = point_mul(2*i + 1, (g_x, g_y))
	bi_precomp.append(to_ge_precomp(P))


	buf = StringIO.StringIO()
	buf.write("""/* Copyright (c) 2020, Google Inc.
	*
	* Permission to use, copy, modify, and/or distribute this software for any
	* purpose with or without fee is hereby granted, provided that the above
	* copyright notice and this permission notice appear in all copies.
	*
	* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
	* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
	* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
	* SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
	* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
	* OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
	* CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */

	// This file is generated from
	// ./make_curve25519_tables.py > curve25519_tables.h


	static const fe d = """)
	buf.write(to_literal(d))
	buf.write(""";

	static const fe sqrtm1 = """)
	buf.write(to_literal(modp_sqrt_m1))
	buf.write(""";

	static const fe d2 = """)
	buf.write(to_literal(d2))
	buf.write(""";

	#if defined(OPENSSL_SMALL)

	// This block of code replaces the standard base-point table with a much smaller
	// one. The standard table is 30,720 bytes while this one is just 960.
	//
	// This table contains 15 pairs of group elements, (x, y), where each field
	// element is serialised with \|fe_tobytes\|. If \|i\| is the index of the group
	// element then consider i+1 as a four-bit number: (i₀, i₁, i₂, i₃) (where i₀
	// is the most significant bit). The value of the group element is then:
	// (i₀×2^192 + i₁×2^128 + i₂×2^64 + i₃)G, where G is the generator.
	static const uint8_t k25519SmallPrecomp[15 * 2 * 32] = {""")
	for i, b in enumerate(small_precomp):
	buf.write("0x%02x, " % b)
	buf.write("""
	};

	#else

	// k25519Precomp[i][j] = (j+1)256^iB
	static const ge_precomp k25519Precomp[32][8] = {
	""")
	for child in large_precomp:
	buf.write("{\n")
	for val in child:
	buf.write("{\n")
	for term in val:
	buf.write(to_literal(term) + ",\n")
	buf.write("},\n")
	buf.write("},\n")
	buf.write("""};

	#endif // OPENSSL_SMALL

	// Bi[i] = (2i+1)B
	static const ge_precomp Bi[8] = {
	""")
	for val in bi_precomp:
	buf.write("{\n")
	for term in val:
	buf.write(to_literal(term) + ",\n")
	buf.write("},\n")
	buf.write("""};
	""")

	proc = subprocess.Popen(["clang-format"], stdin=subprocess.PIPE)
	proc.communicate(buf.getvalue())

	if __name__ == "__main__":
	main()