Curve 25519 is one of the most widely used ECC methods. It uses a curve of \(y^2 = x^3 + 486662 x^2 + x\) [plot], and which is a Montgomery curve. The prime number used is \(2^{255}-19\). This page implements ECDH, and which is the method used in Tor to exchange the key. In this case we will use Python to implement X25519 (and which uses Curve 25519), but only uses the x-axis point for the sharing of values. The base point \(G\) on Curve 25519 is (9,1478161944 ... 7755586237401)[here] and the paramaters based by on RFC 7748 [here].
ECDH with Curve 25519 using Python |
X2519 and ECDH
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 \)
and Bob’s public key becomes:
\(B=bG \)
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 \)
So here is a basic Python program to implement [X448]:
import os import binascii from x25519 import base_point_mult,multscalar,bytes_to_int,int_to_bytes a = os.urandom(32) b = os.urandom(32) # a = int_to_bytes(10,32) # just for testing a=10 (32 bytes - 256 bits) # b = int_to_bytes(12,32) # just for testing b=12 (32 bytes - 256 bits) 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 x25519.py:
P = 2 ** 255 - 19 A24 = 121665 def bytes_to_int(bytes): result = 0 for b in bytes: result = result * 256 + int(b) return result def int_to_bytes(value, length): result = [] for i in range(0, length): result.append(value >> (i * 8) & 0xff) return result 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) # Based on https://tools.ietf.org/html/rfc7748 def X25519(k, u): x_1 = u x_2 = 1 z_2 = 0 x_3 = u z_3 = 1 swap = 0 for t in reversed(range(255)): 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 decodeScalar25519(k): k_list = [(b) for b in k] k_list[0] &= 248 k_list[31] &= 127 k_list[31] |= 64 return decodeLittleEndian(k_list) def decodeLittleEndian(b): return sum([b[i] << 8*i for i in range( 32 )]) def unpack2(s): if len(s) != 32: raise ValueError('Invalid Curve25519 scalar (len=%d)' % len(s)) t = sum((ord(s[i]) ) << (8 * i) for i in range(31)) t += (((ord(s[31]) ) & 0x7f) << 248) return t def pack(n): return ''.join([chr((n >> (8 * i)) & 255) for i in range(32)]) def clamp(n): n &= ~7 n &= ~(128 << 8 * 31) n |= 64 << 8 * 31 return n # Return nP def multscalar(n, p): n = clamp(decodeScalar25519(n)) p = unpack2(p) return pack(X25519(n, p)) # Start at x=9. Find point n times x-point def base_point_mult(n): n = clamp(decodeScalar25519(n)) return pack(X25519(n, 9))
A sample run is:
Bob private (b): 6264934114294864108155832116589512190769343449440305564703770308573812778654 Alice private (a): 37570614652735813404148591764780940380697332455226489257781080469443589954301 Bob public (bG): b'4245c38470c2b1c38720c2827dc2a1783e4fc391260043c397c3970cc385c2bd1a0c50c29859c3a8c2a4164316' Alice public (aG): b'c2ab6c0339c28931c38d5b1fc2a17cc39935c38ec39671c28876c2bc16c2884f6dc2833c48c3bd251858c39b7c' Bob shared (b)aG: b'c38524654c26c2b2c3b12ac39bc2a7c28778c2a5c29ac3b1c384c3afc28a241c1e67c389227e695b2850c2bfc3a249' Alice shared (a)bG: b'c38524654c26c2b2c3b12ac39bc2a7c28778c2a5c29ac3b1c384c3afc28a241c1e67c389227e695b2850c2bfc3a249'