X448 is based on Curve 448, and is used for key exchange with ECDH (Elliptic Curve Diffie Hellman). It supports a 224-bit security level, and where we use a 448-bit (56-byte) prime number of \(P = 2^{448} - 2^{224} - 1\). It has improved security over Curve 25519, and which has a 255-bit prime number (\(P = 2^{255} - 19\)). As with X25519, in X448 we use a Montgomery curve (\(v^2 = u^3 + A \times u^2 + u\)) with scalar multiplication. In X448, we use 56-byte string values, rather than 32-byte values for X25519. Overall, X448 uses a little-endian method to store an array of bytes, and has a value of \(A = 39,081\). The base point \(G\) is at (5, 355293926785 ... 42774147268105838985595290606362) and the paramaters based by on RFC 7748 [here].
ECDH with Curve X448 using Python |
X448 and ECDH
X448 is based on Curve 448, and is used for key exchange with ECDH (Elliptic Curve Diffie Hellman). It supports a 224-bit security level, and where we use a 448-bit (56-byte) prime number of \(P = 2^{448} - 2^{224} - 1\). It has improved security over Curve 25519, and which has a 255-bit prime number (\(P = 2^{255} - 19\)). As with X25519, in X448 we use a Montgomery curve (\(v^2 = u^3 + A \times u^2 + u\)) with scalar multiplication. In X448, we use 56-byte string values, rather than 32-byte values for X25519. Overall, X448 uses a little-endian method to store an array of bytes, and has a value of \(A = 39,081\). The base point \(G\) is at (5, 355293926785 ... 42774147268105838985595290606362
We must thus create a unique encryption key for each routing host. This is often achieved by using X25519, and uses ECDH (Elliptic Curve Diffie Hellman). With this we select a base x co-ordinate point of G, and then Bob and Alice generate random values, and determine their public keys. Alice generates \(a\), and Bob generates \(b\). Alice’s public key will be:
\(A= aG \pmod p\)
and Bob’s public key becomes:
\(B=bG \pmod p\)
The exchange their values, and Alice multiplies by the value received from Bob by \(a\), and Bob multiplies the value he receives from Alice by \(b\). They should then end up with the same value, and which should be:
\(K= abG \pmod p\)
An overview is:
So here is a basic Python program to implement using X448:
import os import binascii from x448 import base_point_mult,multscalar,bytes_to_int a = os.urandom(56) b = os.urandom(56) print (f"\n\nBob private (b):\t{bytes_to_int(b)}") print (f"Alice private (a): \t{bytes_to_int(a)}") # Traditional ECDH: a_pub = base_point_mult(a) b_pub = base_point_mult(b) print ("\n\nBob public (bG):\t",binascii.hexlify(b_pub.encode())) print ("Alice public (aG):\t",binascii.hexlify(a_pub.encode())) k_a = multscalar(a, b_pub) # a (bG) k_b = multscalar(b, a_pub) # b (aG) print ("\n\nBob shared (b)aG:\t",binascii.hexlify(k_b.encode())) print ("Alice shared (a)bG:\t",binascii.hexlify(k_a.encode()))
And here is X448.py:
# X448 P = 2 ** 448 - 2 ** 224 - 1 A24 = 39081 def bytes_to_int(bytes): result = 0 for b in bytes: result = int(result * 256) + int(b) return int(result) def int_to_bytes(value, length): result = [] for i in range(0, length): result.append(value >> (i * 8) & 0xff) return result # Defined here https://tools.ietf.org/html/rfc7748 def cswap(swap, x_2, x_3): dummy = swap * ((x_2 - x_3) % P) x_2 = x_2 - dummy x_2 %= P x_3 = x_3 + dummy x_3 %= P return (x_2, x_3) # Defined here https://tools.ietf.org/html/rfc7748 def X448(k, u): x_1 = u x_2 = 1 z_2 = 0 x_3 = u z_3 = 1 swap = 0 for t in reversed(range(448)): k_t = (k >> t) & 1 swap ^= k_t x_2, x_3 = cswap(swap, x_2, x_3) z_2, z_3 = cswap(swap, z_2, z_3) swap = k_t A = x_2 + z_2 A %= P AA = A * A AA %= P B = x_2 - z_2 B %= P BB = B * B BB %= P E = AA - BB E %= P C = x_3 + z_3 C %= P D = x_3 - z_3 D %= P DA = D * A DA %= P CB = C * B CB %= P x_3 = ((DA + CB) % P)**2 x_3 %= P z_3 = x_1 * (((DA - CB) % P)**2) % P z_3 %= P x_2 = AA * BB x_2 %= P z_2 = E * ((AA + (A24 * E) % P) % P) z_2 %= P x_2, x_3 = cswap(swap, x_2, x_3) z_2, z_3 = cswap(swap, z_2, z_3) return (x_2 * pow(z_2, P - 2, P)) % P def decodeScalar448(k): k_list = [(b) for b in k] k_list[0] &= 252 k_list[55] |= 128 return decodeLittleEndian(k_list) def decodeLittleEndian(b): return sum([b[i] << 8*i for i in range( 56 )]) def unpack2(s): if len(s) != 56: raise ValueError('Invalid Curve448 scalar (len=%d)' % len(s)) return sum(ord(s[i]) << (8 * i) for i in range(56)) def pack(n): return ''.join([chr((n >> (8 * i)) & 255) for i in range(56)]) def clamp(n): n &= ~3 n |= 128 << 8 * 55 return n # Return nP def multscalar(n, p): n = clamp(decodeScalar448(n)) p = unpack2(p) return pack(X448(n, p)) # Start at x=5. Find point n times x-point def base_point_mult(n): n = clamp(decodeScalar448(n)) return pack(X448(n, 5))
A sample run is:
Bob private (b): 529664444215264135266951141469944597261153806303187710513680224127744916427240564791591137613172990921521793793133423473035184457736997 Alice private (a): 208148581958698804400347667018619697156566069342084097938799332851780319649318694500297882595406124349658988313358755473543276475259371 Bob public (bG): b'c3b9c395c393c285c38f1dc281c3bec3b56dc39f3dc2b0c396c295c28144c2a2c28644153c16c2ae1c3ac28124c3b2c2a7c3a84cc3abc2aa76c3a2c3bfc2b35b2dc294c3aec38f38c3b028c2a2c289c3aa58c3b8c2bec3b9c2834a58' Alice public (aG): b'c28cc3b61e2b64205ec3aec2bd0413c387141946580a51555e6fc381c2bdc3993e2fc29a0dc3856b0e3bc2934c0c51c3b752c38d381e31c3892ac393c2abc3983d32576b5c4f28c2adc2b2' Bob shared (b)aG: b'c28430c3b0c2b43024c3b4c3a14ec298c296252e53c38ac388c29bc2b4c3a76d7435c3a53f1764c3ab37c3a3c39fc38ec3ae53c38fc38dc2b1c29d3845c3a6c38e77c38474c380c29ac394c39616354cc3915d352327' Alice shared (a)bG: b'c28430c3b0c2b43024c3b4c3a14ec298c296252e53c38ac388c29bc2b4c3a76d7435c3a53f1764c3ab37c3a3c39fc38ec3ae53c38fc38dc2b1c29d3845c3a6c38e77c38474c380c29ac394c39616354cc3915d352327'