ECDH with Curve25519 with Python

Daniel J. Bernstein introduced the curve25519 to the world in 2006. Curve25519 is a montgomery curve, in which 25519 indicates that the characteristic of the lower main number field on which the elliptic curve depends is ²²⁵⁵-19.

Motivated by performance, he designed Curve25519 to be faster and use shorter keys than standard curves. But Curve25519 also brings safety benefits because, unlike NIST curves, it has no suspicious constants and can use the same unified formula to add separate points or double a point. Curve 25519 is one of the most widely used ECC methods. It uses a curve of which is a Montgomery curve.

Desmos | Calculatrice graphique

The prime number used is 2²⁵⁵-19. This page implements ECDH, which is the method used in Tor to exchange the key. In this case we will use Python to implement X25519 (and which uses the 25519 curve), but uses only the point on the x-axis for value sharing. In this case, Bob and Alice first share their public keys, and then each session has its own key exchange, with keys created from their long term public keys and their session keys.

X25519 and ECDH

Based on Curve25519, Bernstein built the Diffie-Hellman X25519 key exchange protocol. Compared to the ECDH key exchange protocol, the most notable feature of the X25519 protocol is that it depends only on the x-coordinate of the point on the elliptic curve. The idea of constructing a ECDH key exchange protocol using only x co-ordinates came from Victor Millier’s 1985 article, “The Use of Elliptic Curves in Cryptography”, which was considered the cornerstone of the field.

Calculation based solely on the x-coordinate can be constructed on elliptic curves of various shapes, but using the algebraic structure of the group of points (the presence of the 4th order point) on the Montgomery curve is less computationally intensive with the montgomery ladder algorithm and is easier to implement in constant time. This is why Bernstein chose the Montgomery curve. In addition to the design of the underlying mathematical structure, the X25519 key exchange protocol also takes into account problems often encountered in actual deployment and, based on the Montgomery curve, has ingeniously circumvented these problems, simplifying the implementation and deployment of the X25519 application.

When Bob and Alice communicate over a network, they may want to create a unique encryption key for each session. This is often done using X25519, and uses ECDH (Elliptic Curve Diffie Hellman). With this, we select a point with x base G coordinates, then Bob and Alice generate random values and determine their public keys.

Curve25519 use cases

One of the uses of curve25519 is Tor routing. The web traces a wide range of information, including user details from cookies, IP addresses, and even user behavior (including the user’s fingerprints). This information is used to target marketing to users, and also provides a rich set of information for crime detection and investigation. The Tor network has long been targeted by law enforcement and defense agencies because it protects the identity of users and the location of their source, and is generally known as the “black web” because it is not accessible to major search engines such as Google. Obviously Tor can be used to link to a server, so the server only talks to a client that has been routed through the Tor network, meaning that search engines will not be able to find the content on them. This is the closed model of creating a web that can only be accessed by Internet users, and only by those who use Tor. If users make transactions on the black web servers with Bitcoins, there will be little record of their transactions.

Code in python

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))

So here is a basic Python program to implement using X25519:

import os
import binascii
from x25519 import base_point_mult,multscalar
a = os.urandom(32)
b = os.urandom(32)
a_pub = base_point_mult(a)
b_pub = base_point_mult(b)
x = os.urandom(32)
y = os.urandom(32)
Bob_send = multscalar(y, a_pub)
Bob_send = multscalar(b, Bob_send)
Alice_send = multscalar(x, b_pub)
Alice_send = multscalar(a, Alice_send) 
k_a = multscalar(x, Bob_send) 
k_b = multscalar(y, Alice_send) 
print ("Bob private:\t",binascii.hexlify(a))
print ("Alice private:\t",binascii.hexlify(b))
print ("\n\nBob public:\t",binascii.hexlify(b_pub.encode()))
print ("Alice public:\t",binascii.hexlify(a_pub.encode()))
print ("\nBob x value:\t",binascii.hexlify(x))
print ("Alice y value:\t",binascii.hexlify(y))
print ("\n\nBob send:\t",binascii.hexlify(Bob_send.encode()))
print ("Alice send:\t",binascii.hexlify(Alice_send.encode()))
print ("\n\nBob shared:\t",binascii.hexlify(k_b.encode()))
print ("Alice shared:\t",binascii.hexlify(k_a.encode()))

A sample is :

For more details on Curve25519, the X25519 protocol policy and operating rules, and a detailed analysis of the X25519 application in Tendermint Core, please click here.