Curve25519 Diffie Hellman Key Exchange

I wanted to play with Daniel Bernstein's library function that implements a Diffie Hellman key exchange, mainly to convince myself that the magic is genuinely easy to use.

As it turns out, this library, dating from ~2005, didn't build for me. It seems to have been made for speed records rather than portability, but fortunately others have implemented it for more general use. I chose to use the implementation 'curve25519-donna' because it's a drop-in replacement for Bernstein's code, so I could follow the original documentation.

The elliptic curve keys and the shared secret are all 32-byte arrays. A private key is simply 32 random bytes with five bits manipulated to specific values. I'm using stdlib's rand() function for this example, though it's not really cryptographically safe! I suppose '/dev/urandom' is much better.

The function curve25519_donna() does all the hard work. Given a private key and a constant, it generates a public key. Given my private key and your public key, it generates our secret for me. Given your private key and my public key, it generates our secret for you.

That's pretty much it! The essence of an elliptic curve key exchange.

The code I've written (shown further down) is very simple C. Even if you don't know C, it should be simple enough to figure out, since it relates directly to Bernstein's description in the page linked above.

First, the output of the code

[kevin@ideapad]$ gcc -o test curve25519-donna.o test.c && ./test

We create a private and public key for the server...
--------------
Server Private Key:
CEA5B3EFF9BF89C7687C04830525ACC8596A34654F945920561CE254176157E5
Server Public Key:
1B37C78DC92F3C62C3578E43F20666FCAE1ACE0D039259F971A93B1D8AD64B64

Let's pretend our server is now running with these keys.

We create a private and public key for the client...
--------------
Client Private Key:
060BD400CA5EC732DACBB5DFF061A849CCDCAF1B71083BC7241D1C3C7F732185
Client Public Key:
25F4C4BB5C717FC65FDA17D9888CF0F0F09CEF11442D1A9F4756F910815A5C2A

Let's pretend our client sends it's public key to the server and
gets the server's public key in response.

The client uses the server's public key along with its own private
key to generate its copy of the shared secret.
--------------
Shared Secret (client-generated):
4AEC3CC0660435F2565FD32FAE214EB62DB3924FCE36C06AC1FE4F11F66E6D70

The server uses the client's public key along with its own private
key to generate its copy of the shared secret.
--------------
Shared Secret (Server Generated):
4AEC3CC0660435F2565FD32FAE214EB62DB3924FCE36C06AC1FE4F11F66E6D70

The server and the client now both know a secret that nobody else
knows. This is a 32-byte number that can be used with a cipher to
encrypt and decrypt messages between them.

Now the code itself

I've tried to write the code to be as self-documenting as possible. It's mostly printf() calls. Of course, it all runs in a single process, so the most important thing to observe is that the server's curve25519_donna() calls don't make any use of client-private data, and vice-versa.

The code compiles to a 26K binary. The library itself is 14K. To give some perspective, it could compile for a $2 PIC microcontroller, or an 8-bit micro, or easily for an ESP32.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

extern void curve25519_donna(unsigned char *output, const unsigned char *a,
                             const unsigned char *b);

int main(int argc, char *argv[]) {

    const unsigned char basepoint[32] = {9};
    unsigned char serverprv[32];
    unsigned char serverpub[32];

    // Seed the random number generator
    srand(time(0));

    int i;

    printf("\nWe create a private and public key for the server...\n");
    printf("--------------\n");
    printf("Server Private Key:\n");
    for(i=0; i<32; i++) {
        serverprv[i] = (rand() & 0xff);
        printf("%02X", serverprv[i]);
    }
    putchar('\n');

    // This makes our 32 random bytes into an curve25519 private key.
    serverprv[0] &= 248; serverprv[31] &= 127; serverprv[31] |= 64;

    // Generate server's public key from private key
    curve25519_donna(serverpub, serverprv, basepoint);

    printf("Server Public Key:\n");
    for(i=0; i<32; i++) printf("%02X", serverpub[i]); putchar('\n');

    printf(
      "\nLet's pretend our server is now running with these keys.\n");

    unsigned char clientprv[32];
    unsigned char clientpub[32];

    printf("\nWe create a private and public key for the client...\n");
    printf("--------------\n");
    printf("Client Private Key:\n");
    for(i=0; i<32; i++) {
        clientprv[i] = (rand() & 0xff);
        printf("%02X", clientprv[i]);
    }
    putchar('\n');

    // This makes our 32 random bytes into a curve25519 private key
    clientprv[0] &= 248; clientprv[31] &= 127; clientprv[31] |= 64;
    
    // Generate public key for client
    curve25519_donna(clientpub, clientprv, basepoint);

    printf("Client Public Key:\n");
    for(i=0; i<32; i++) printf("%02X", clientpub[i]); putchar('\n');

    printf(
      "\nLet's pretend our client sends it's public key to the server and\n"
      "gets the server's public key in response.\n");

    printf(
      "\nThe client uses the server's public key along with its own private\n"
      "key to generate its copy of the shared secret.\n");
    printf("--------------\n");

    unsigned char secret_c[32];

    curve25519_donna(secret_c, clientprv, serverpub);
    
    printf("Shared Secret (client-generated):\n");
    for(i=0; i<32; i++) printf("%02X", secret_c[i]); putchar('\n');

    printf(
      "\nThe server uses the client's public key along with its own private\n"
      "key to generate its copy of the shared secret.\n");
    printf("--------------\n");

    unsigned char secret_s[32];

    curve25519_donna(secret_s, serverprv, clientpub);

    printf("Shared Secret (Server Generated):\n");
    for(i=0; i<32; i++) printf("%02X", secret_s[i]); putchar('\n');

    printf(
      "\nThe server and the client now both know a secret that nobody else\n"
      "knows. This is a 32-byte number that can be used with a cipher to\n"
      "encrypt and decrypt messages between them.\n"); 

    return 0;
}

Errata

I print the private key data prematurely. I should really have printed them *after* modifying the bytes, not while generating the random numbers. It's not a private key until those five bits are clear/set appropriately. It doesn't affect the actual key exchange.


Source: gemini://gemini.susa.net/curve25519_dh_example.gmi

This page was originally taken from my Gemini server. Gemini is an Internet technology specifically designed for simple text publishing, free from intrusive advertising and tracking. You can read more about Gemini here.