Introduction

New with go1.20 is a package devoted to making easy use of elliptic curve Diffie-Hellman key exchange: crypto/ECDH (Elliptic Curve Diffie-Hellman).

The remarkable way that ECDH works is that two parties can exchange public keys (i.e. unencrypted, open-text keys), and from those keys derive a common shared secret key that they can subsequently use to encrypt messages they can exchange with each other. Using any of the standard stream ciphers (for example Chacha20/Poly1305), they can rest assured that their messages cannot be deciphered or read by third parties. This is true, even if the two parties have never met or previously exchanged any messages or data. A key part of the process in ECDH is the use of elliptic curve cryptography. With elliptic curves it is possible to construct one-way functions that are unfeasible to invert. By unfeasible, think millions of years to crack on a conventional supercomputer.

The principal elliptic curve operations used by ECDH are ScalarBaseMult and ScalarMult. ScalarBaseMult “multiplies” a scalar number by a special point on the elliptic curve called the base point.  ScalarMult is similar to ScalarBaseMult, but works for any point on the curve. Here, “multiply”  is not standard multiplication, but multiple addition in the elliptic curve’s algebraic group — operations that are always modulus a large prime number. It’s a significant computation.

ECDH - a graphic example

Consider Bob and Alice. For simplicity, we’ll assume that they have already agreed on which elliptic curve they will use for their communication. (If they hadn’t, it would be simple enough for them to send the curve information with their public key). Here is a graphic explaining how they each get a shared private key. First each picks a random private key. This will be a within the range of 1 to a very large number known as the scalar order of the curve. For example for the popular curve known as P256 , the random number will be between 1 and 115792089210356248762697446949407573529996955224135760342422259061068512044369. That’s 79 decimal digits. As you can see, it would very hard for an outside party to correctly guess the chosen random number. After choosing the private random key, each computes the ScalarBaseMult of the random key. That is their public key for the ECDH exchange. Each can transmit their key unencrypted to the world knowing that no one else can use it to guess or reverse-engineer what their private key was — the mathematical properties of elliptic curve cryptography make that a practical impossibility. However, here’s where the magic happens: when Alice multiples Bob’s public key (using ScalarMult) by her private random key, she gets a number which is the same as the number Bob gets when he multiplies Alice's public key by his private key. Voilà: Bob and Alice have a shared secret. Understand that Bob and Alice may be strangers. They may not trust each other, or even like each other, but with ECDH they can acquire a shared secret which they can use for encrypting messages they subsequently send back and forth to each other.

The Code

Here is an example of using crypto/ecdh:

func main() {
	curve := ecdh.P256()
	myKey, err := curve.GenerateKey(rand.Reader)
	if err != nil {
		fmt.Println("Unable to generate private key:", err)
		return
	}
	fmt.Println("My public key", myKey.PublicKey().Bytes())
	key := readPublicKey()
	theirPK, err := curve.NewPublicKey(key)
	if err != nil {
		fmt.Println("Problem with remote key:", err)
		return
	}
	mySecret, err := myKey.ECDH(theirPK)
	if err != nil {
		fmt.Println("ECDH Failed:", err)
		return
	}
	fmt.Println("\nMy secret:", mySecret)
}

It's a short program so let's go through it step by step. I'll leave out discussion of the error handling, as those errors will not occur in regular use.

curve := ecdh.P256()
For this example we will choose the curve known as P256. It's a curve with a 256 bit prime, and is reasonably secure for transient communication such is this, as well as being fast. It will not be secure against large quantum computers of the future, but sufficiently large quantum computers don't exist yet, so we are safe for now.

myKey, err := curve.GenerateKey(rand.Reader)
Here's where we choose a random private key. The GenerateKey method will ensure that the random number lies between 1 and the scalar order of the curve (it will retry rand.Reader until it gets a good one).

fmt.Println("My public key", myKey.PublicKey().Bytes())
The real work in this line is myKey.PublicKey(). This method call performs ScalarBaseMult on the random private key myKey. The result is a point on the curve which can be shared publicly (hence the name). Here we are also transforming the result into a byte slice and printing it. Later we will do a simple copy/paste to transfer the public keys between our two participants.

key := readPublicKey()
This line uses the readPublicKey method (shown below — not part of the ECDH package) to read characters from the terminal and produce a byte slice. It will be the byte-slice for the public key of the other participant.

theirPK, err := curve.NewPublicKey(key)
This line takes the byte slice returned from readPublicKey and morphs it into a first class PublicKey as defined in the ecdh package. The main value-add of NewPublicKey is that it checks that the provided byte-slice does indeed represent a point on the chosen elliptic curve.

mySecret, err := myKey.ECDH(theirPK)
Finally, ECDH does ScalarMult of the original randomly chosen key with the public key of the other correspondent. Note that the public key is a point on the curve, and ScalarMult multiplies it by the scalar random number that is the original private key. Both Bob and Alice will do this and they will, both wind up with the same value of mySecret.

fmt.Println("\nMy secret:", mySecret)
Ok, after having gone to all this trouble to create a shared secret, it's a bad idea to print it out for the world to see!! However, this is a demo and I wanted you to see that, indeed, both Bob and Alice have the same secret — so here I print it.

Let's illustrate the program by running it:

Implementation and Acceleration

Now that we've had a look at how ECDH works, let's look behind the covers a little at it's implementation in Go. Looking in package crypto/ecdh we see the primary implementation is in file ecdh.go, with support for two curve types in each of nist.go and x25519.go. In this blog we will focus on the nist.go implementation, and specifically the P256 curve. In ecdh.go, a curve is defined as an interface that implements the following methods:

type Curve interface {
	GenerateKey(rand io.Reader) (*PrivateKey, error)
	NewPrivateKey(key []byte) (*PrivateKey, error)
	NewPublicKey(key []byte) (*PublicKey, error)
	ecdh(local *PrivateKey, remote *PublicKey) ([]byte, error)
	privateKeyToPublicKey(*PrivateKey) *PublicKey
}

Of these methods we use GenerateKey to create the random private key and NewPublicKey to create the public key that is shared with the world. In our code, the call myKey.PublicKey() will be implemented via the private method  privateKeyToPublicKey, and our call to ECDH will be implemented with the private ecdh method. However to get a better look at how these interface methods are implemented for NIST curves one has to look into the file nist.go. There you will find a great illustration of the power of Go generics (introduced in Go 1.18):

type nistCurve[Point nistPoint[Point]] struct {
	name        string
	newPoint    func() Point
	scalarOrder []byte
}

// nistPoint is a generic constraint for the nistec Point types.
type nistPoint[T any] interface {
	Bytes() []byte
	BytesX() ([]byte, error)
	SetBytes([]byte) (T, error)
	ScalarMult(T, []byte) (T, error)
	ScalarBaseMult([]byte) (T, error)
}

The definition of nistCurve looks like it has a recursively defined generic type: [Point nistPoint[Point]] . This is not recursive, however, as nistPoint[Point] is actually a constraint on the type of Point. This is a Go idiom which here can be read as "the type argument is constrained to denote a type that implements the methods in the nistPoint interface." Some of those methods have arguments and/or results that are defined by the generic type "Point," hence the seemingly recursive reference to Point.

In order to find the implementation of the nistPoint methods, including the crucial ScalarMult and ScalarBaseMult, you will have to look in the imported package crypto/internal/nistec. Inspecting that package you will ultimately find a file p256_asm_s390x.s. This file contains assembly code that accelerates operations on the P256 curve, including ScalarMult and ScalarBaseMult. In fact, Go on z/OS has acceleration code for many of the most used cryptographic functions. When accelerated, these functions can run many times faster than unaccelerated code.

I hope you have enjoyed this exploration of ECDH. In future blogs our hope is to further demonstrate some important cryptographic operations, and how they have been accelerated in Go on z/OS. More killer crypto in Go on z/OS!

Happy coding from Bob and Alice!!

Below find the full listing of code used in this blog.

package main

import (
	"bufio"
	"crypto/ecdh"
	"crypto/rand"
	"fmt"
	"os"
	"regexp"
	"strconv"
)

var pnum, _ = regexp.Compile(`[0-9]+`)

func readPublicKey() []byte {
	// Read the public key of the other person
	reader := bufio.NewReader(os.Stdin)
	var key []byte
READLOOP:
	for {
		fmt.Printf("Enter the public key of correspondant: ")
		line, err := reader.ReadString('\n')
		if err != nil {
			fmt.Println("Error reading strng:",err)
			continue
		}
		// extract numeric strings from the text
		charKey := pnum.FindAllString(line, -1)
		key = make([]byte, len(charKey))
		var keyi int
		for i, v := range charKey {
			keyi, err = strconv.Atoi(v)
			if err != nil || keyi > 255 {
				fmt.Println("Bad format")
				continue READLOOP
			}
			key[i] = byte(keyi)
		}
		break
	}
	return key
}

func main() {
	curve := ecdh.P256()
	myKey, err := curve.GenerateKey(rand.Reader)
	if err != nil {
		fmt.Println("Unable to generate private key:", err)
		return
	}
	fmt.Println("My public key", myKey.PublicKey().Bytes())
	key := readPublicKey()
	theirPK, err := curve.NewPublicKey(key)
	if err != nil {
		fmt.Println("Problem with remote key:", err)
		return
	}
	mySecret, err := myKey.ECDH(theirPK)
	if err != nil {
		fmt.Println("ECDH Failed:", err)
		return
	}
	fmt.Println("\nMy secret:", mySecret)
}