Jul 15, 2023

ECDH encryption using ed25519 keys

Elliptic-curve Diffie-Hellman (ECDH) is a key agreement protocol that allows two parties, each having an elliptic public-private key pair to establish a shared secret over an insecure channel. Ed25519 is an elliptic curve signing algorithm using EdDSA and Curve25519. This tutorial will explain in detail how the ECDH works and has also some code examples in golang.

TL;DR

You can find the full source code and examples at github.com/gabihodoroaga/ecdh.

How ECDH encryption works

ECDH is based on the following property of EC points:

(a * G) * b = (b * G) * a

If we have two secret numbers a and b (two private keys, belonging to Alice and Bob) and an ECC elliptic curve with generator point G, we can exchange over an insecure channel the values (a * G) and (b * G) (the public keys of Alice and Bob) and then we can derive a shared secret: secret = (a * G) * b = (b * G) * a. Pretty simple. The above equation takes the following form:

alicePubKey * bobPrivKey = bobPubKey * alicePrivKey = secret

The ECDH algorithm (Elliptic Curve Diffie-Hellman Key Exchange) goes like this:

  • Alice generates a random ECC key pair: alicePrivKey, alicePubKey
  • Bob generates a random ECC key pair: bobPrivKey, bobPubKey
  • Alice and Bob exchange their public keys through the insecure channel (e.g. over Internet)
  • Alice calculates sharedKey = bobPubKey * alicePrivKey
  • Bob calculates sharedKey = alicePubKey * bobPrivKey
  • Now both Alice and Bob have the same sharedKey == bobPubKey * alicePrivKey == alicePubKey * bobPrivKey

How to get shared secret using ed25519 keys

For encryption, the ed25519 signing keys cannot be used directly and in order to achieve the above we need to convert the ed25519 key to X25519 keys.

There is an excellent article from Fillipo Valsorada Using Ed25519 signing keys for encryption that explains all the mathematics behind. And in fact some of the code used here is copied from the Age, a simple, modern and secure file encryption tool, format, and Go library.

There are 2 functions that we need in order to convert the ed25519 key into x25519 keys

import (
	"crypto/ed25519"
	"crypto/rand"
	"crypto/sha512"

	"filippo.io/edwards25519"
	"golang.org/x/crypto/curve25519"
)

// ed25519PrivateKeyToCurve25519 converts a ed25519 private key in X25519 equivalent
// source: https://github.com/FiloSottile/age/blob/980763a16e30ea5c285c271344d2202fcb18c33b/agessh/agessh.go#L287
func ed25519PrivateKeyToCurve25519(pk ed25519.PrivateKey) []byte {
	h := sha512.New()
	h.Write(pk.Seed())
	out := h.Sum(nil)
	return out[:curve25519.ScalarSize]
}

// ed25519PublicKeyToCurve25519 converts a ed25519 public key in X25519 equivalent
// source: https://github.com/FiloSottile/age/blob/main/agessh/agessh.go#L190
func ed25519PublicKeyToCurve25519(pk ed25519.PublicKey) ([]byte, error) {
	// See https://blog.filippo.io/using-ed25519-keys-for-encryption and
	// https://pkg.go.dev/filippo.io/edwards25519#Point.BytesMontgomery.
	p, err := new(edwards25519.Point).SetBytes(pk)
	if err != nil {
		return nil, err
	}
	return p.BytesMontgomery(), nil
}

And we can wrap everything together in a public function in order to get the shared secret

func SharedSecret(pub, priv []byte, decrypt bool) ([]byte, error) {

	pkPriv := ed25519.PrivateKey(priv)
	xPriv := ed25519PrivateKeyToCurve25519(pkPriv)

	xPub, err := ed25519PublicKeyToCurve25519(pub)
	if err != nil {
		return nil, err
	}

	secret, err := curve25519.X25519(xPriv, xPub)
	if err != nil {
		return nil, err
	}

	return secret, nil
}

Next we should test if our implementation works as expected.

First let’s generate some key pairs and for this we can use a tool from Parity called subkey.

docker run -it --rm parity/subkey generate --scheme Ed25519

amd the output should be like this

Secret phrase:       force balcony plate offer dinosaur diet sort faith sell kidney edge office
  Secret seed:       0x8099218df05be91769679587124cfb3c1f6b0602805ffda193f26790c531e1eb
  Public key (hex):  0xfef1ed54588c4edc73e6c1320d7c67c886f72caeb24e2c072e4aeb1c2be1edab
  Account ID:        0xfef1ed54588c4edc73e6c1320d7c67c886f72caeb24e2c072e4aeb1c2be1edab
  Public key (SS58): 4ntgbTB6sPGMBtKp4BqLWrXU8WXXPUW6hS1LjHwM3pgSqX8P
  SS58 Address:      4ntgbTB6sPGMBtKp4BqLWrXU8WXXPUW6hS1LjHwM3pgSqX8P

and another one for Bob

Secret phrase:       giant local surge bike plunge skate arena universe brand village coffee relief
  Secret seed:       0x8ed0ce08849ef03657e0f137f15b73afbfc4ecbfcc76505e5fb5f63c998bb8a0
  Public key (hex):  0x584db3b049decbcee583e051e2d9f205ae516597b3adb3f98806a19c6c05ad62
  Account ID:        0x584db3b049decbcee583e051e2d9f205ae516597b3adb3f98806a19c6c05ad62
  Public key (SS58): 4j8BrtFpwevyuwPRSq1bAXMeoYn7Wzg4QunbmvcPVx8QtPs3
  SS58 Address:      4j8BrtFpwevyuwPRSq1bAXMeoYn7Wzg4QunbmvcPVx8QtPs3

Nex we need to create our test function

import (
	"encoding/hex"
	"testing"

	"github.com/stretchr/testify/assert"
	"github.com/stretchr/testify/require"
)

func TestSharedSecret(t *testing.T) {

	alicePrivKey,_ := hex.DecodeString("8099218df05be91769679587124cfb3c1f6b0602805ffda193f26790c531e1eb")
	alicePubKey,_ := hex.DecodeString("fef1ed54588c4edc73e6c1320d7c67c886f72caeb24e2c072e4aeb1c2be1edab")

	bobPrivKey,_ := hex.DecodeString("8ed0ce08849ef03657e0f137f15b73afbfc4ecbfcc76505e5fb5f63c998bb8a0")
	bobPubKey,_ := hex.DecodeString("584db3b049decbcee583e051e2d9f205ae516597b3adb3f98806a19c6c05ad62")

	aliceSecret, err := SharedSecret(bobPubKey, alicePrivKey, true)
	require.Nil(t, err)
	require.NotNil(t, aliceSecret)

	bobSecret, err := SharedSecret(alicePubKey, bobPrivKey, true)
	require.Nil(t, err)
	require.NotNil(t, bobSecret)

	assert.Equal(t, aliceSecret, bobSecret)
}

This is it. Now this shared secret can be used as a key to encrypt any message using a symmetric-key cipher.

In reality when you need to encrypt a message for Bob you don’t need to use the sender’s public key and it is more practical to use an ephemeral key pair and include the ephemeral public key into the final message.

  • Bob provides a public key: bobPubKey
  • A new ephemeral key is generated: ephemeralPubKey, ephemeralPrivKey
  • A shared secret is calculated: bobPubKey * ephemeralPrivKey
  • A message is encrypted with the shared secret: encryptedMessage
  • Bob will receive a message containing both ephemeralPubKey + encryptedMessage
  • When Bob wants to decrypt the message read the ephemeralPubKey and the encryptedMessage
  • Calculates the shared secret: ephemeralPubKey * bobPrivKey
  • Decrypts the message using the shared secret

For a complete example of how to do ECDHE with AES-128-CBC-HMAC-SHA1 check the example in this repository github.com/gabihodoroaga/ecdh.

References

I’m not an expert in cryptography. I’m not the actual author of all this. All I did is to copy pieces of code from the following sources and put them together in a way that makes sense to me and I hope it will make sense for someone else too.

ECDH Key Exchange by Svetlin Nakov

Using Ed25519 signing keys for encryption

Age