Authenticated ECDH In Python using X25519

Authenticated ECDH In Python using X25519

Curve 25519 is one of the most widely used ECC (Elliptic Curve Cryptography) methods and you are likely to be using it for the connection that you have on this connection. It uses a curve of y²=x³+486662x²+x, and which is a Montgomery curve. The prime number used is 2²⁵⁵−19.

So let’s create a Python to implement X25519. This method uses Curve 25519), but only focuses on the x-axis point for the sharing of values. A weakness of the Diffie-Hellman and core ECDH (Elliptic Curve Diffie Hellman) methods is that Eve can perform an Eve-in-the-middle attack, so let’s see if we can overcome this with the usage of Bob and Alice’s long term public key.

In this case, Bob and Alice share their public keys initially, and then each session has its own key exchange, with keys created from their long-term public keys and their session keys.

When Bob and Alice are communicating over a network, they might want to create a unique encryption key for each session. 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 long-term private key of a, and Bob generates a long term private key of b.

Alice’s long public key will be:

and Bob’s long-term public key becomes:

Alice will store Bob’s long-term key, and Bob will store Alice’s long-term key, and they will use these to compute the shared key for each session. For a new session, Bob generates a random private key value of b

and Alice generates a random private key of a. Alice will then share a public key by and multiplying Bob’s long term public key by a and x:

And Bob takes Alice’s public key and multiplies by b and y:

The exchange their values, and Alice multiplies by the value received from Bob by y, and Bob multiplies the value he receives from Alice by x. They should then end up with the same value, and which should be:

and:

and which are the same values.

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

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) # (y) aG
Bob_send = multscalar(b, Bob_send) # (yb) aG

Alice_send = multscalar(x, b_pub) # (x) bG
Alice_send = multscalar(a, Alice_send) # (xa) bG

k_a = multscalar(x, Bob_send) # x (yb) aG
k_b = multscalar(y, Alice_send) # y ( xa) bG

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

# res=bytes_to_int(a)*bytes_to_int(y)*bytes_to_int(b)*bytes_to_int(x)

# k = base_point_mult(int_to_bytes(res,32))
# print ("\n\nChecking shared:\t",binascii.hexlify(k.encode()))

And here is x25519.py [demo]:

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'087e87f810e153ffb2c2ab589db4081817b68019f1f36a675b2e76d11d24759a'
Alice private:	 b'd4e51c3e0d311c9d1de33b0e68cc245a9c1f841a37555e49a5064517d8d706bb'

Bob public:	 b'c2bd242f292d0dc38b2fc2a178c3bc72c39a47c2aec3ab30c3abc28833c3bb024f59254817656ac29ac2bf55'
Alice public:	 b'2f782fc2b161c2aec39c0ac39f59c391c2b46fc3a65376c3a40e1a00c2b1c29cc295c38e3bc38dc3a470c294c2bbc28778'

Bob x value:	 b'385752103e4e0330d7af95cd61560fb0c47cc55a1e70fb0fecebd1a44fb32e6b'
Alice y value:	 b'5185474b094f769a5ad14b1d5a5076e4bd5f0582e085c9976ff10496ee21431d'

Bob send:	 b'c2b23ac285c28d24607a1030c39ec3917408c39543c38971c3b31f03c3823839c3b6176f450bc2a4c393c2803a'
Alice send:	 b'3a79c2bfc3b8c2af4f40c2a9c2adc3a7c3a43bc2a2c3a9c3a656c2b219c286c29518135ac389c280c294c3b7c3a3c3b3c383312d'

Bob shared:	 b'c39a7d77c28fc287c3a2c3b5106723c3bf19c2b067c28fc3b40bc39ec2aac3b41dc2aec2b60677c3a0c2b5c2935b5bc2a713'
Alice shared:	 b'c39a7d77c28fc287c3a2c3b5106723c3bf19c2b067c28fc3b40bc39ec2aac3b41dc2aec2b60677c3a0c2b5c2935b5bc2a713'

And the code here: