Paging @agl

Straightforward patch:

diff --git a/ed25519/ed25519.go b/ed25519/ed25519.go
index 4f26b49..b038979 100644
--- a/ed25519/ed25519.go
+++ b/ed25519/ed25519.go
@@ -81,6 +81,8 @@ func GenerateKey(rand io.Reader) (publicKey PublicKey, privateKey PrivateKey, er
 	var A edwards25519.ExtendedGroupElement
 	var hBytes [32]byte
 	copy(hBytes[:], digest[:])
+	// Reduce private scalar
+	hBytes = reduce(hBytes)
 	edwards25519.GeScalarMultBase(&A, &hBytes)
 	var publicKeyBytes [32]byte
 	A.ToBytes(&publicKeyBytes)
@@ -91,6 +93,14 @@ func GenerateKey(rand io.Reader) (publicKey PublicKey, privateKey PrivateKey, er
 	return publicKey, privateKey, nil
 }
 
+func reduce(scalar [32]byte) [32]byte {
+	var in [64]byte
+	copy(in[:32], scalar[:])
+	var out [32]byte
+	edwards25519.ScReduce(&out, &in)
+	return out
+}
+
 // Sign signs the message with privateKey and returns a signature. It will
 // panic if len(privateKey) is not PrivateKeySize.
 func Sign(privateKey PrivateKey, message []byte) []byte {

EDIT:
Properly reduce, i.e. after hashing.

The reference code doesn't reduce the private scalar either and, since the scalarmult is constant-time and windowed, it wouldn't speed it up, it would only slow down key generation.

Also, if the scalarmult was tweaked to exploit the fact that the top two bits are zero, it wouldn't work with private keys generated by the reference code any longer.

reference code doesn't reduce the private scalar either

Oops, fixed. What's the reason for hashing the scalar (and applying bitmasks) before use anyway?

the scalarmult is constant-time

Valid point, I'll close this PR then.

if the scalarmult was tweaked to exploit the fact that the top two bits are zero

Why would someone intend to do that? What are the benefits?

What's the reason for hashing the scalar (and applying bitmasks) before use anyway?

I think the diagram at the bottom of this post is pretty helpful for understanding what Ed25519 is doing (and the different formats that have appeared over time.)

The SHA-512 call is used to expand a 256-bit seed to a pair of 256-bit secrets. Only the first of those is used in the key generation to cache the value of the public-key. The bit masks are applied to duplicate the behaviour of X25519. The bottom three bits are cleared because the order of Ed25519 is a multiple of eight so, to make sure that nothing is leaked by points of small order, private keys are always made to be multiples of eight.

The top two bits are set to 01 because a) the order is < 2^253 so the top two bits aren't really needed but b) the Montgomery ladder (which is used in X25519, but generally not in Ed25519) is a bit simpler if you know that the first effective bit is one.

Why would someone intend to do that? What are the benefits?

I thought that you were suggesting this. (I.e. reduce the scalar in key generation and exploit that structure during the scalarmult.)

In the scalarmult you could safely try exploiting the fact that the top two bits were zero to scan less of the base-multiples table for the most-significant word of the scalar. That might result in a tiny speedup.

Thanks for your clarification, really helpful. I'll try my best to reflect what you just said in form of comments inside the code.