How do I sign a curve25519 key in golang?

Question

I am trying to implement the X3DH algorithm from Signal in Go. However, I got stuck on how to sign the Public Signed PreKey.

Per the specifications it is supposed to be an X25519 key. In looking at previous implementations on Github they generated a [32]byte key from the curve25519 package and then converted it to an ed25519 key and then signed it.

However, the packages they used for the conversion are deprecated (github.com/agl/ed25519). Therefore, I either need to be able to convert the keys to ed25519 so I can sign them with the current ed25519 package (golang.org/x/crypto/25519) or implement a sign and verify function for curve25519 keys.

Answer 1

Ed25519 keys can be converted to X25519 keys easily, the twisted Edwards curve used by Ed25519 and the Montgomery curve used by X25519 are birationally equivalent.

Points on the Edwards curve are usually referred to as (x, y), while points on the Montgomery curve are usually referred to as (u, v).

You don't need a library to do the conversion, it's really simple...

(u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
(x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))

Here is a great blog by Filippo Valsorda, the Golang security lead at Google, discussing this topic.

Answer 2

This takes in a public curve25519 key and converts it to an ed25519 public key. I did not write this code but appears to be doing what Woodstock above is stating. Further information would be welcomed:

func Verify(publicKey [32]byte, message []byte, signature *[64]byte) bool {

publicKey[31] &= 0x7F

/* Convert the Curve25519 public key into an Ed25519 public key.  In
particular, convert Curve25519's "montgomery" x-coordinate into an
Ed25519 "edwards" y-coordinate:
ed_y = (mont_x - 1) / (mont_x + 1)
NOTE: mont_x=-1 is converted to ed_y=0 since fe_invert is mod-exp
Then move the sign bit into the pubkey from the signature.
*/

var edY, one, montX, montXMinusOne, montXPlusOne FieldElement
FeFromBytes(&montX, &publicKey)
FeOne(&one)
FeSub(&montXMinusOne, &montX, &one)
FeAdd(&montXPlusOne, &montX, &one)
FeInvert(&montXPlusOne, &montXPlusOne)
FeMul(&edY, &montXMinusOne, &montXPlusOne)

var A_ed [32]byte
FeToBytes(&A_ed, &edY)

A_ed[31] |= signature[63] & 0x80
signature[63] &= 0x7F

var sig = make([]byte, 64)
var aed = make([]byte, 32)

copy(sig, signature[:])
copy(aed, A_ed[:])

return ed25519.Verify(aed, message, sig)

This uses functions from "golang.org/x/crypto/ed25519/internal"