dateKeys-dart/tool/gen_primitive_vectors.go

//go:build ignore

// gen_primitive_vectors writes test/vectors/primitives.json: the vectors of
// the primitives of stage 2 of datekeys-dart, every expected value computed
// here with the Go libraries that datekeys-go and filippo.io/age use, never
// written by hand. The inputs are those of the RFCs (5869, 7748, 7914, 8032,
// 8439), taken from the tests and test data of Go and golang.org/x/crypto in
// the module cache where they are there, plus edge cases and seeded random
// ones.
//
// It needs the module context of datekeys-go, for golang.org/x/crypto
// v0.57.0 and the codec/bech32 and profile packages, and changes nothing
// there:
//
//	cd ../datekeys-go && go run ../datekeys-dart/tool/gen_primitive_vectors.go -out ../datekeys-dart/test/vectors
//
// The output is deterministic: running it again writes the same bytes.
package main

import (
	"bufio"
	"bytes"
	"compress/gzip"
	"crypto/ed25519"
	"crypto/hmac"
	"crypto/sha256"
	"encoding/base64"
	"encoding/hex"
	"encoding/json"
	"flag"
	"fmt"
	"io"
	"log"
	"math/big"
	"math/rand/v2"
	"os"
	"os/exec"
	"path/filepath"
	"regexp"
	"runtime"
	"slices"
	"strconv"
	"strings"

	"golang.org/x/crypto/chacha20"
	"golang.org/x/crypto/chacha20poly1305"
	"golang.org/x/crypto/curve25519"
	"golang.org/x/crypto/hkdf"
	"golang.org/x/crypto/pbkdf2"
	"golang.org/x/crypto/poly1305"
	"golang.org/x/crypto/scrypt"

	"g.activething.com/go/DateKeys/codec/bech32"
	"g.activething.com/go/DateKeys/profile"
)

type obj = map[string]any

var rng = rand.New(rand.NewChaCha8([32]byte([]byte("datekeys-dart stage 2 primitives"))))

func randBytes(n int) []byte {
	b := make([]byte, n)
	for i := range b {
		b[i] = byte(rng.Uint32())
	}
	return b
}

func seq(from, n int) []byte {
	b := make([]byte, n)
	for i := range b {
		b[i] = byte(from + i)
	}
	return b
}

func h(b []byte) string { return hex.EncodeToString(b) }

func mustHex(s string) []byte {
	b, err := hex.DecodeString(s)
	if err != nil {
		log.Fatal(err)
	}
	return b
}

func modDir(path string) string {
	out, err := exec.Command("go", "list", "-m", "-f", "{{.Dir}}", path).Output()
	if err != nil {
		log.Fatalf("go list %s: %v", path, err)
	}
	return strings.TrimSpace(string(out))
}

// byteArrays returns the [32]byte or []byte literals {0x.., ...} after the
// first occurrence of marker in a Go source file.
func byteArrays(src, marker, end string) [][]byte {
	i := strings.Index(src, marker)
	if i < 0 {
		log.Fatalf("marker %q not found", marker)
	}
	src = src[i:]
	if j := strings.Index(src, end); j >= 0 {
		src = src[:j]
	}
	var out [][]byte
	for _, m := range regexp.MustCompile(`\{(0x[0-9a-fA-F]+(?:,\s*0x[0-9a-fA-F]+)*),?\s*\}`).FindAllStringSubmatch(src, -1) {
		var b []byte
		for _, f := range strings.Split(m[1], ",") {
			v, err := strconv.ParseUint(strings.TrimSpace(f), 0, 8)
			if err != nil {
				log.Fatal(err)
			}
			b = append(b, byte(v))
		}
		out = append(out, b)
	}
	return out
}

func main() {
	outDir := flag.String("out", "", "directory of the vectors")
	testdata := flag.String("testdata", "../datekeys-dart/testdata", "the testdata/ of datekeys-dart, synced from datekeys-go")
	flag.Parse()
	if *outDir == "" {
		log.Fatal("-out is required")
	}
	xcrypto := modDir("golang.org/x/crypto")

	doc := obj{
		"description": "Vectors of the primitives of stage 2 of datekeys-dart. Every expected value is computed by tool/gen_primitive_vectors.go with Go " + runtime.Version() + ", golang.org/x/crypto v0.57.0 and codec/bech32 of datekeys-go; the inputs are those of the RFCs, taken from the tests of Go and x/crypto where they are, plus edge cases and seeded random ones. Binary values are lowercase hex. `node` marks the cases cheap enough to run compiled to JavaScript.",
		"generator":   "tool/gen_primitive_vectors.go",
	}

	// SHA-256 and HMAC-SHA256: around the block and padding boundaries.
	var shaCases, hmacCases []obj
	for _, n := range []int{0, 1, 3, 55, 56, 57, 63, 64, 65, 119, 120, 128, 1000} {
		m := randBytes(n)
		d := sha256.Sum256(m)
		shaCases = append(shaCases, obj{"message": h(m), "digest": h(d[:])})
	}
	for _, kn := range []int{0, 1, 20, 32, 63, 64, 65, 131} {
		for _, mn := range []int{0, 32, 100} {
			k, m := randBytes(kn), randBytes(mn)
			mac := hmac.New(sha256.New, k)
			mac.Write(m)
			hmacCases = append(hmacCases, obj{"key": h(k), "message": h(m), "mac": h(mac.Sum(nil))})
		}
	}
	doc["sha256"] = shaCases
	doc["hmac_sha256"] = hmacCases

	// HKDF-SHA256: RFC 5869 A.1 to A.3 (the inputs of hkdf_test.go of
	// x/crypto), a nil salt, and the age labels.
	hkdfInputs := []struct {
		name            string
		ikm, salt, info []byte
		length          int
	}{
		{"RFC 5869 A.1", bytes.Repeat([]byte{0x0b}, 22), seq(0x00, 13), seq(0xf0, 10), 42},
		{"RFC 5869 A.2", seq(0x00, 80), seq(0x60, 80), seq(0xb0, 80), 82},
		{"RFC 5869 A.3", bytes.Repeat([]byte{0x0b}, 22), []byte{}, []byte{}, 42},
		{"nil salt, age header label", randBytes(16), nil, []byte("header"), 32},
		{"age payload label", randBytes(16), randBytes(16), []byte("payload"), 32},
		{"255 blocks", randBytes(32), randBytes(32), randBytes(10), 255 * 32},
	}
	var hkdfCases []obj
	for _, c := range hkdfInputs {
		out := make([]byte, c.length)
		if _, err := io.ReadFull(hkdf.New(sha256.New, c.ikm, c.salt, c.info), out); err != nil {
			log.Fatal(err)
		}
		salt := any(h(c.salt))
		if c.salt == nil {
			salt = nil
		}
		hkdfCases = append(hkdfCases, obj{"name": c.name, "ikm": h(c.ikm), "salt": salt, "info": h(c.info), "length": c.length, "okm": h(out)})
	}
	doc["hkdf_sha256"] = hkdfCases

	// PBKDF2-HMAC-SHA256: the inputs of RFC 6070 (written for SHA-1) with
	// SHA-256, a password longer than a block, and the word key of spec
	// §38.1 with 600 000 iterations.
	qn := profile.Quicknet()
	wordSalt := "DateKeys llave de palabras v2|" + qn.ChainHashHex() + "|1000|000102030405060708090a0b0c0d0e0f"
	pbkdf2Inputs := []struct {
		name, password, salt string
		iter, length         int
		node                 bool
	}{
		{"RFC 6070 inputs, c = 1", "password", "salt", 1, 32, true},
		{"RFC 6070 inputs, c = 2", "password", "salt", 2, 32, true},
		{"RFC 6070 inputs, c = 4096", "password", "salt", 4096, 32, true},
		{"RFC 6070 inputs, 40 bytes", "passwordPASSWORDpassword", "saltSALTsaltSALTsaltSALTsaltSALTsalt", 4096, 40, true},
		{"RFC 6070 inputs, NUL", "pass\x00word", "sa\x00lt", 4096, 16, true},
		{"a password of 100 bytes, 3 blocks", strings.Repeat("0123456789", 10), "salt", 3, 70, true},
		{"spec §38.1: perro luna casa verde tren mar", "perro luna casa verde tren mar", wordSalt, 600000, 32, false},
	}
	var pbkdf2Cases []obj
	for _, c := range pbkdf2Inputs {
		k := pbkdf2.Key([]byte(c.password), []byte(c.salt), c.iter, c.length, sha256.New)
		pbkdf2Cases = append(pbkdf2Cases, obj{"name": c.name, "password": h([]byte(c.password)), "salt": h([]byte(c.salt)), "iterations": c.iter, "length": c.length, "key": h(k), "node": c.node})
	}
	doc["pbkdf2_sha256"] = pbkdf2Cases

	// scrypt: RFC 7914 §12 (the inputs of scrypt_test.go of x/crypto, but
	// for N = 2^20, 1 GiB), and the parameters of age with logN 10 and 16.
	scryptInputs := []struct {
		name, password, salt string
		n, r, p, length      int
		node                 bool
	}{
		{"RFC 7914 §12, N = 16", "", "", 16, 1, 1, 64, true},
		{"RFC 7914 §12, N = 1024, p = 16", "password", "NaCl", 1024, 8, 16, 64, true},
		{"RFC 7914 §12, N = 16384", "pleaseletmein", "SodiumChloride", 16384, 8, 1, 64, true},
		{"N = 2, r = 1, p = 1", "p", "s", 2, 1, 1, 32, true},
		{"N = 4, r = 2, p = 3", "password", "salt", 4, 2, 3, 70, true},
		{"age, logN = 10", "passphrase", "age-encryption.org/v1/scrypt" + string(seq(0, 16)), 1 << 10, 8, 1, 32, true},
		{"age, logN = 16 (spec §29.12)", "passphrase", "age-encryption.org/v1/scrypt" + string(seq(16, 16)), 1 << 16, 8, 1, 32, false},
	}
	var scryptCases []obj
	for _, c := range scryptInputs {
		k, err := scrypt.Key([]byte(c.password), []byte(c.salt), c.n, c.r, c.p, c.length)
		if err != nil {
			log.Fatal(err)
		}
		scryptCases = append(scryptCases, obj{"name": c.name, "password": h([]byte(c.password)), "salt": h([]byte(c.salt)), "n": c.n, "r": c.r, "p": c.p, "length": c.length, "key": h(k), "node": c.node})
	}
	var scryptErrors []obj
	for _, c := range []struct{ n, r, p int }{{1, 8, 1}, {0, 8, 1}, {3, 8, 1}, {1 << 10, 0, 1}, {1 << 10, 8, 0}, {1 << 10, 1 << 20, 1 << 10}} {
		_, err := scrypt.Key([]byte("p"), []byte("s"), c.n, c.r, c.p, 32)
		scryptErrors = append(scryptErrors, obj{"n": c.n, "r": c.r, "p": c.p, "error": err.Error()})
	}
	doc["scrypt"] = scryptCases
	doc["scrypt_errors"] = scryptErrors

	// ChaCha20 (RFC 8439 2.3.2 and 2.4.2), Poly1305 (2.5.2 and edge keys)
	// and ChaCha20-Poly1305 (2.8.2 and seeded random cases).
	vecSrc, err := os.ReadFile(filepath.Join(xcrypto, "chacha20poly1305", "chacha20poly1305_vectors_test.go"))
	if err != nil {
		log.Fatal(err)
	}
	// The plaintext of RFC 8439 2.4.2 and 2.8.2, as the vectors of x/crypto
	// hold it.
	m := regexp.MustCompile(`"(4c616469657320616e642047656e746c656d656e[0-9a-f]*)"`).FindSubmatch(vecSrc)
	if m == nil {
		log.Fatal("the sunscreen plaintext is not in the vectors of x/crypto")
	}
	sunscreen := mustHex(string(m[1]))
	var chachaCases []obj
	for _, c := range []struct {
		name       string
		key, nonce []byte
		counter    uint32
		length     int
		plaintext  []byte
	}{
		{"RFC 8439 2.3.2", seq(0, 32), mustHex("000000090000004a00000000"), 1, 64, nil},
		{"RFC 8439 2.4.2", seq(0, 32), mustHex("000000000000004a00000000"), 1, 0, sunscreen},
		{"counter 0, 3 blocks and a half", randBytes(32), randBytes(12), 0, 224, nil},
		{"counter near 2^32", randBytes(32), randBytes(12), 0xfffffffe, 128, nil},
	} {
		s, err := chacha20.NewUnauthenticatedCipher(c.key, c.nonce)
		if err != nil {
			log.Fatal(err)
		}
		s.SetCounter(c.counter)
		in := c.plaintext
		if in == nil {
			in = make([]byte, c.length)
		}
		out := make([]byte, len(in))
		s.XORKeyStream(out, in)
		chachaCases = append(chachaCases, obj{"name": c.name, "key": h(c.key), "nonce": h(c.nonce), "counter": c.counter, "input": h(in), "output": h(out)})
	}
	doc["chacha20"] = chachaCases

	var polyCases []obj
	addPoly := func(name string, key, msg []byte) {
		var k [32]byte
		copy(k[:], key)
		var tag [16]byte
		poly1305.Sum(&tag, msg, &k)
		polyCases = append(polyCases, obj{"name": name, "key": h(key), "message": h(msg), "tag": h(tag[:])})
	}
	addPoly("RFC 8439 2.5.2", mustHex("85d6be7857556d337f4452fe42d506a80103808afb0db2fd4abff6af4149f51b"), []byte("Cryptographic Forum Research Group"))
	ff := bytes.Repeat([]byte{0xff}, 32)
	for _, n := range []int{0, 1, 15, 16, 17, 31, 32, 33, 64, 100, 257} {
		addPoly(fmt.Sprintf("r and s all ones, %d bytes of 0xff", n), ff, bytes.Repeat([]byte{0xff}, n))
	}
	for _, n := range []int{16, 48} {
		// The largest r that clamping leaves, with s zero; and r zero with s
		// all ones.
		k := append(bytes.Repeat([]byte{0xff}, 16), make([]byte, 16)...)
		addPoly(fmt.Sprintf("s zero, %d bytes of 0xff", n), k, bytes.Repeat([]byte{0xff}, n))
		addPoly(fmt.Sprintf("s all ones, %d zero bytes", n), append(make([]byte, 16), bytes.Repeat([]byte{0xff}, 16)...), make([]byte, n))
	}
	// r = 1 and s = 0: the tag is the sum of the blocks, so that blocks of
	// 0xff take h across p.
	r1 := append([]byte{1}, make([]byte, 31)...)
	for _, n := range []int{1, 2, 3} {
		addPoly(fmt.Sprintf("r = 1, %d blocks of 0xff", n), r1, bytes.Repeat([]byte{0xff}, 16*n))
	}
	for i := 0; i < 24; i++ {
		addPoly(fmt.Sprintf("random %d", i), randBytes(32), randBytes(int(rng.Uint32()%200)))
	}
	// Messages whose sums of limb products pass 2^32 in the 13-bit limbs of
	// datekeys-dart, where a carry taken with a shift instead of a division
	// would be truncated to 32 bits on the web. They are found by simulating
	// that arithmetic (polyMaxSums) with the largest r that clamping allows
	// and blocks of 0xff, with a generator of their own so that the other
	// vectors do not change; Go's poly1305 gives their tags.
	srng := rand.New(rand.NewChaCha8([32]byte([]byte("datekeys-dart poly1305 carries.."))))
	found := map[int]int{}
	for attempt := 0; attempt < 20000 && found[0]+found[1]+found[2] < 6; attempt++ {
		key := bytes.Repeat([]byte{0xff}, 32)
		for j := 16; j < 32; j++ {
			key[j] = byte(srng.Uint32())
		}
		// A random first block, then blocks of 0xff, whose limbs are all
		// ones: the largest that can be added to h.
		msg := bytes.Repeat([]byte{0xff}, 1024)
		for j := range 16 {
			msg[j] = byte(srng.Uint32())
		}
		maxD := polyMaxSums(key, msg)
		for limb := 2; limb >= 0; limb-- {
			if maxD[limb] >= 1<<32 && found[limb] < 2 {
				found[limb]++
				addPoly(fmt.Sprintf("a sum of products of limb %d reaches %d, past 2^32", limb, maxD[limb]), key, msg)
				break
			}
		}
	}
	if found[0] == 0 {
		log.Fatal("no message takes a sum of products past 2^32")
	}
	fmt.Printf("poly1305: messages past 2^32 for limbs 0, 1, 2: %d, %d, %d\n", found[0], found[1], found[2])
	doc["poly1305"] = polyCases

	var aeadCases []obj
	addAEAD := func(name string, key, nonce, aad, pt []byte) {
		a, err := chacha20poly1305.New(key)
		if err != nil {
			log.Fatal(err)
		}
		aeadCases = append(aeadCases, obj{"name": name, "key": h(key), "nonce": h(nonce), "aad": h(aad), "plaintext": h(pt), "ciphertext": h(a.Seal(nil, nonce, pt, aad))})
	}
	addAEAD("RFC 8439 2.8.2", seq(0x80, 32), mustHex("070000004041424344454647"), mustHex("50515253c0c1c2c3c4c5c6c7"), sunscreen)
	addAEAD("age: a file key under a zero nonce", randBytes(32), make([]byte, 12), nil, randBytes(16))
	for _, n := range []int{0, 1, 15, 16, 17, 63, 64, 65, 127, 128, 129, 300, 1000} {
		addAEAD(fmt.Sprintf("random, %d bytes", n), randBytes(32), randBytes(12), randBytes(int(rng.Uint32()%40)), randBytes(n))
	}
	doc["chacha20poly1305"] = aeadCases

	// X25519: RFC 7748 5.2 and 6.1, the iterated function from u = 9, the
	// BoringSSL vectors and the points of low order of x/crypto's tests.
	cvSrc, err := os.ReadFile(filepath.Join(xcrypto, "curve25519", "vectors_test.go"))
	if err != nil {
		log.Fatal(err)
	}
	src := string(cvSrc)
	lowOrder := byteArrays(src, "var lowOrderPoints", "// testVectors")
	tv := byteArrays(src, "var testVectors", "\n}\n")
	if len(lowOrder) != 7 || len(tv)%3 != 0 || len(tv) == 0 {
		log.Fatalf("unexpected vectors: %d low order, %d arrays", len(lowOrder), len(tv))
	}
	var xCases []obj
	addX := func(name string, scalar, u []byte) {
		out, err := curve25519.X25519(scalar, u)
		c := obj{"name": name, "scalar": h(scalar), "u": h(u)}
		if err != nil {
			c["error"] = err.Error()
			// The value of the function itself, before the check.
			var dst, s, p [32]byte
			copy(s[:], scalar)
			copy(p[:], u)
			curve25519.ScalarMult(&dst, &s, &p)
			c["output"] = h(dst[:])
		} else {
			c["output"] = h(out)
		}
		xCases = append(xCases, c)
	}
	addX("RFC 7748 5.2, first", mustHex("a546e36bf0527c9d3b16154b82465edd62144c0ac1fc5a18506a2244ba449ac4"), mustHex("e6db6867583030db3594c1a424b15f7c726624ec26b3353b10a903a6d0ab1c4c"))
	addX("RFC 7748 5.2, second", mustHex("4b66e9d4d1b4673c5ad22691957d6af5c11b6421e0ea01d42ca4169e7918ba0d"), mustHex("e5210f12786811d3f4b7959d0538ae2c31dbe7106fc03c3efc4cd549c715a493"))
	alice := mustHex("77076d0a7318a57d3c16c17251b26645df4c2f87ebc0992ab177fba51db92c2a")
	addX("RFC 7748 6.1, Alice's public key", alice, curve25519.Basepoint)
	addX("RFC 7748 6.1, the shared secret", alice, mustHex("de9edb7d7b7dc1b4d35b61c2ece435373f8343c85b78674dadfc7e146f882b4f"))
	for i := 0; i < len(tv); i += 3 {
		addX(fmt.Sprintf("BoringSSL %d", i/3), tv[i], tv[i+1])
	}
	for i, lo := range lowOrder {
		addX(fmt.Sprintf("low order %d", i), randBytes(32), lo)
		hi := slices.Clone(lo)
		hi[31] |= 0x80
		addX(fmt.Sprintf("low order %d, bit 255 set", i), randBytes(32), hi)
	}
	// u not below p: reduced, and bit 255 ignored.
	for _, d := range []int{0, 1, 2, 18, 19, 20, 30} {
		p := new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 255), big.NewInt(19))
		v := new(big.Int).Add(p, big.NewInt(int64(d)))
		v.Mod(v, new(big.Int).Lsh(big.NewInt(1), 255))
		le := make([]byte, 32)
		v.FillBytes(le)
		slices.Reverse(le)
		addX(fmt.Sprintf("u = p + %d mod 2^255", d), randBytes(32), le)
	}
	for i := 0; i < 8; i++ {
		addX(fmt.Sprintf("random %d", i), randBytes(32), randBytes(32))
	}
	doc["x25519"] = xCases

	iter := func(n int) string {
		k := append([]byte{9}, make([]byte, 31)...)
		u := slices.Clone(k)
		for i := 0; i < n; i++ {
			out, err := curve25519.X25519(k, u)
			if err != nil {
				log.Fatal(err)
			}
			u, k = k, out
		}
		return h(k)
	}
	doc["x25519_iterated"] = obj{"description": "RFC 7748 5.2: k = u = 9, then k, u = X25519(k, u), k n times", "1": iter(1), "1000": iter(1000)}

	// Ed25519: the first 64 lines of sign.input of Go's crypto/ed25519 (SUPERCOP;
	// the first three are RFC 8032 7.1 TEST 1 to 3), checked here with
	// crypto/ed25519 and the strict profile.
	f, err := os.Open(filepath.Join(runtime.GOROOT(), "src", "crypto", "ed25519", "testdata", "sign.input.gz"))
	if err != nil {
		log.Fatal(err)
	}
	gz, err := gzip.NewReader(f)
	if err != nil {
		log.Fatal(err)
	}
	var edCases []obj
	sc := bufio.NewScanner(gz)
	sc.Buffer(make([]byte, 1<<20), 1<<20)
	for line := 0; line < 64 && sc.Scan(); line++ {
		parts := strings.Split(sc.Text(), ":")
		pub, msg, sm := mustHex(parts[1]), mustHex(parts[2]), mustHex(parts[3])
		sig := sm[:64]
		priv := ed25519.NewKeyFromSeed(mustHex(parts[0])[:32])
		if !bytes.Equal(ed25519.Sign(priv, msg), sig) || !ed25519.Verify(pub, msg, sig) {
			log.Fatalf("sign.input line %d does not verify", line)
		}
		edCases = append(edCases, obj{"name": fmt.Sprintf("sign.input line %d", line), "public_key": h(pub), "message": h(msg), "signature": h(sig), "valid": strictVerify(pub, msg, sig), "stdlib": true})
		if line%8 == 0 {
			// Mutations of every eighth line: the result of the strict
			// profile and of crypto/ed25519.
			for _, mut := range []struct {
				what  string
				which int
				pos   int
			}{{"R", 1, 0}, {"S", 1, 32}, {"S top byte", 1, 63}, {"A", 0, 5}, {"message", 2, 0}} {
				p2, m2, s2 := slices.Clone(pub), slices.Clone(msg), slices.Clone(sig)
				target := [][]byte{p2, s2, m2}[mut.which]
				if len(target) == 0 {
					continue
				}
				target[mut.pos%len(target)] ^= 1 << (line % 8)
				edCases = append(edCases, obj{"name": fmt.Sprintf("sign.input line %d, %s changed", line, mut.what), "public_key": h(p2), "message": h(m2), "signature": h(s2), "valid": strictVerify(p2, m2, s2), "stdlib": ed25519.Verify(p2, m2, s2)})
			}
		}
	}
	if err := sc.Err(); err != nil {
		log.Fatal(err)
	}
	// The copy of the strict profile below gives the results of
	// testdata/vectors/ed25519_strict.json, in the copy of datekeys-dart.
	var strictFile struct {
		Vectors []struct {
			Name, Message, PublicKey, Signature string
			Valid                               bool
		}
	}
	raw, err := os.ReadFile(filepath.Join(*testdata, "vectors", "ed25519_strict.json"))
	if err != nil {
		log.Fatal(err)
	}
	if err := json.Unmarshal(bytes.ReplaceAll(raw, []byte(`"public_key"`), []byte(`"publickey"`)), &strictFile); err != nil {
		log.Fatal(err)
	}
	for _, v := range strictFile.Vectors {
		if strictVerify(mustHex(v.PublicKey), mustHex(v.Message), mustHex(v.Signature)) != v.Valid {
			log.Fatalf("the copy of ed25519strict disagrees on %q", v.Name)
		}
	}
	if len(strictFile.Vectors) == 0 {
		log.Fatal("no vectors in ed25519_strict.json")
	}
	// S + ℓ and S + 2^253 on a valid signature, and keys of small order.
	l := new(big.Int).Add(new(big.Int).Lsh(big.NewInt(1), 252), mustBig("27742317777372353535851937790883648493"))
	seed := randBytes(32)
	priv := ed25519.NewKeyFromSeed(seed)
	pub := priv.Public().(ed25519.PublicKey)
	msg := []byte("DateKeys")
	sig := ed25519.Sign(priv, msg)
	for _, add := range []*big.Int{l, new(big.Int).Lsh(big.NewInt(1), 253), new(big.Int).Lsh(l, 1)} {
		s := leBig(sig[32:])
		s.Add(s, add)
		if s.BitLen() > 256 {
			continue
		}
		s2 := slices.Clone(sig)
		copy(s2[32:], leBytes(s, 32))
		edCases = append(edCases, obj{"name": "S + " + add.String(), "public_key": h(pub), "message": h(msg), "signature": h(s2), "valid": strictVerify(pub, msg, s2), "stdlib": ed25519.Verify(pub, msg, s2)})
	}
	for i, so := range smallOrder {
		// R = the identity and S = 0: [0]B - [k]A = -[k]A, the identity when
		// A has an order that divides k.
		s2 := make([]byte, 64)
		s2[0] = 1
		for j := 0; j < 4; j++ {
			m2 := []byte{byte(i), byte(j)}
			edCases = append(edCases, obj{"name": fmt.Sprintf("small order point %d, R = identity, S = 0, message %d", i, j), "public_key": h(so[:]), "message": h(m2), "signature": h(s2), "valid": strictVerify(so[:], m2, s2), "stdlib": ed25519.Verify(so[:], m2, s2)})
		}
	}
	doc["ed25519"] = edCases

	// The encodings of points: Canonical, OnCurve and SmallOrder of the
	// strict profile.
	var encCases []obj
	addEnc := func(name string, a []byte) {
		encCases = append(encCases, obj{"name": name, "encoding": h(a), "canonical": canonical(a), "on_curve": onCurve(a), "small_order": isSmallOrder(a)})
	}
	pBig := new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 255), big.NewInt(19))
	for d := 0; d < 20; d++ {
		for _, sign := range []byte{0, 0x80} {
			v := new(big.Int).Add(pBig, big.NewInt(int64(d)))
			e := leBytes(v, 32)
			e[31] |= sign
			addEnc(fmt.Sprintf("y = p + %d, sign %d", d, sign>>7), e)
			e2 := leBytes(big.NewInt(int64(d)), 32)
			e2[31] |= sign
			addEnc(fmt.Sprintf("y = %d, sign %d", d, sign>>7), e2)
		}
	}
	v := new(big.Int).Sub(pBig, big.NewInt(1))
	for _, sign := range []byte{0, 0x80} {
		e := leBytes(v, 32)
		e[31] |= sign
		addEnc(fmt.Sprintf("y = p - 1, sign %d", sign>>7), e)
	}
	for i, so := range smallOrder {
		addEnc(fmt.Sprintf("small order %d", i), so[:])
		e := slices.Clone(so[:])
		e[31] ^= 0x80
		addEnc(fmt.Sprintf("small order %d, sign flipped", i), e)
	}
	for i := 0; i < 24; i++ {
		addEnc(fmt.Sprintf("random %d", i), randBytes(32))
	}
	addEnc("a public key", pub)
	doc["ed25519_encodings"] = encCases

	// Base64 as Go decodes it, with the offsets of its errors, in the
	// encodings that the protocol uses.
	encodings := []struct {
		name                string
		enc                 *base64.Encoding
		url, padded, strict bool
	}{
		{"std raw strict (age)", base64.RawStdEncoding.Strict(), false, false, true},
		{"std padded strict", base64.StdEncoding.Strict(), false, true, true},
		{"url raw strict", base64.RawURLEncoding.Strict(), true, false, true},
		{"std padded", base64.StdEncoding, false, true, false},
		{"url raw", base64.RawURLEncoding, true, false, false},
	}
	inputs := []string{"", "A", "AA", "AB", "AAA", "AAB", "AAAA", "AA==", "AAA=", "A===", "AB==", "AAB=", "=", "==", "AA=", "AA=A", "AA==A", "AA\n", "A\nA", "AA\r\n", "\nAAAA", "Zm9v", "Zm9", "Zm8", "Zm", "Zg", "Zh", "Z", "Zm9v=", "Zm\x80v", " Zm9v", "Zm-v", "Zm_v", "Zm+v", "Zm/v", "Zm9vYmFy", "Zm9vYmFyZm9v!mFy", "Zm9vYmFyZm9vYmF", "Zm9vYmFyZm9vYmE", "Zm9vYmFyZm9vYmE=", "Zm9vYmFyZm9vYm==", "Zm9vYmFyZm9vYm", "Zm9vYmFyZm9vYmFyZm9vYmFyZm9vYmFyZm9vYmFy*", "AAAA\x00AAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA", "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB"}
	var b64Cases []obj
	for _, e := range encodings {
		for _, in := range inputs {
			c := obj{"encoding": e.name, "url": e.url, "padded": e.padded, "strict": e.strict, "input": h([]byte(in))}
			out, err := e.enc.DecodeString(in)
			if err != nil {
				c["error"] = err.Error()
			} else {
				c["output"] = h(out)
			}
			b64Cases = append(b64Cases, c)
		}
	}
	doc["base64"] = b64Cases

	// Bech32 as age's internal/bech32, copied by datekeys-go as codec/bech32.
	var bechCases []obj
	addDecode := func(s string) {
		hrp, data, err := bech32.Decode(s)
		c := obj{"op": "decode", "input": s}
		if err != nil {
			c["error"] = err.Error()
		} else {
			c["hrp"], c["data"] = hrp, h(data)
		}
		bechCases = append(bechCases, c)
	}
	addEncode := func(hrp string, data []byte) {
		s, err := bech32.Encode(hrp, data)
		c := obj{"op": "encode", "hrp": hrp, "data": h(data)}
		if err != nil {
			c["error"] = err.Error()
		} else {
			c["output"] = s
		}
		bechCases = append(bechCases, c)
	}
	key := randBytes(32)
	id, _ := bech32.Encode("AGE-SECRET-KEY-", key)
	rec, _ := bech32.Encode("age", randBytes(32))
	for _, d := range [][]byte{nil, {0}, {0xff}, randBytes(5), key, randBytes(60)} {
		addEncode("age", d)
		addEncode("AGE-SECRET-KEY-", d)
	}
	addEncode("", key)
	addEncode("Age", key)
	addEncode("a b", key)
	addEncode("é", key)
	for _, s := range []string{id, strings.ToLower(id), rec, strings.ToUpper(rec), id[:len(id)-1] + "Q", id[:len(id)-1], id + "q", strings.Replace(id, "1", "", 1), "1" + id[16:], "A1QQQQQQ", "a1qqqqqq", "a1qqqqq", "a1qqqqqb", "a1qqqqqqqq", "\x7f1qqqqqq", "x1Ẁqqqqqq", "é1qqqqqq", "AGE-SECRET-KEY-1Qa", rec[:4] + "B" + rec[5:], "age1" + strings.Repeat("q", 100), "age1qyqszqgpqyqszqgpqyqszqgpqyqszqgpqyqszqgpqyqszqgpqyqszqgpqyqszqgpqyqszqgp"} {
		addDecode(s)
	}
	// Non-zero padding and illegal zero padding, with a valid checksum.
	for _, data := range [][]byte{{1}, {0, 1}, {0, 0, 1}, {31, 31}} {
		values := data
		s := "age1"
		for _, v := range values {
			s += string("qpzry9x8gf2tvdw0s3jn54khce6mua7l"[v])
		}
		s += checksum("age", values)
		addDecode(s)
	}
	doc["bech32"] = bechCases

	path := filepath.Join(*outDir, "primitives.json")
	var buf bytes.Buffer
	enc := json.NewEncoder(&buf)
	enc.SetEscapeHTML(false)
	enc.SetIndent("", " ")
	if err := enc.Encode(doc); err != nil {
		log.Fatal(err)
	}
	if err := os.WriteFile(path, buf.Bytes(), 0o644); err != nil {
		log.Fatal(err)
	}
	fmt.Printf("wrote %s, %d bytes\n", path, buf.Len())
	// The same JSON as a Dart constant, for the tests compiled to
	// JavaScript, which cannot read files.
	if bytes.Contains(buf.Bytes(), []byte("'''")) {
		log.Fatal("the JSON holds three quotes")
	}
	dart := "// Generated by tool/gen_primitive_vectors.go from primitives.json, for the\n" +
		"// tests that also run compiled to JavaScript, where no file can be read. Do\n" +
		"// not edit.\n\n" +
		"/// The text of test/vectors/primitives.json.\n" +
		"const primitivesJson = r'''\n" + buf.String() + "''';\n"
	dpath := filepath.Join(*outDir, "primitives.g.dart")
	if err := os.WriteFile(dpath, []byte(dart), 0o644); err != nil {
		log.Fatal(err)
	}
	fmt.Printf("wrote %s\n", dpath)
}

func mustBig(s string) *big.Int {
	v, ok := new(big.Int).SetString(s, 10)
	if !ok {
		log.Fatal(s)
	}
	return v
}

func leBig(b []byte) *big.Int {
	be := slices.Clone(b)
	slices.Reverse(be)
	return new(big.Int).SetBytes(be)
}

func leBytes(v *big.Int, n int) []byte {
	b := make([]byte, n)
	v.FillBytes(b)
	slices.Reverse(b)
	return b
}

// polyMaxSums simulates the Poly1305 of datekeys-dart, ten limbs of 13 bits,
// and returns for each limb the largest sum of products, carry included,
// that it takes over the blocks of msg.
func polyMaxSums(key, msg []byte) (maxD [10]uint64) {
	limbs := func(b []byte) (l [10]uint64) {
		for i := range 10 {
			bit := 13 * i
			o := bit >> 3
			v := uint64(b[o]) | uint64(b[o+1])<<8 | uint64(b[o+2])<<16
			l[i] = v >> (bit & 7) & 0x1fff
		}
		return
	}
	var rb [20]byte
	copy(rb[:16], key[:16])
	rb[3] &= 15
	rb[7] &= 15
	rb[11] &= 15
	rb[15] &= 15
	rb[4] &= 252
	rb[8] &= 252
	rb[12] &= 252
	r := limbs(rb[:])
	var h [10]uint64
	for off := 0; off < len(msg); off += 16 {
		var blk [20]byte
		n := copy(blk[:16], msg[off:min(off+16, len(msg))])
		blk[n] = 1
		m := limbs(blk[:])
		for i := range 10 {
			h[i] += m[i]
		}
		var d [10]uint64
		var c uint64
		for i := range 10 {
			sum := c
			for j := 0; j <= i; j++ {
				sum += h[j] * r[i-j]
			}
			for j := i + 1; j < 10; j++ {
				sum += h[j] * 5 * r[i-j+10]
			}
			maxD[i] = max(maxD[i], sum)
			c = sum >> 13
			d[i] = sum & 0x1fff
		}
		v := d[0] + c*5
		h[0] = v & 0x1fff
		h[1] = d[1] + v>>13
		for i := 2; i < 10; i++ {
			h[i] = d[i]
		}
	}
	return
}

// checksum is the Bech32 checksum of hrp and the 5-bit values.
func checksum(hrp string, values []byte) string {
	gen := []uint32{0x3b6a57b2, 0x26508e6d, 0x1ea119fa, 0x3d4233dd, 0x2a1462b3}
	var v []byte
	for _, c := range []byte(hrp) {
		v = append(v, c>>5)
	}
	v = append(v, 0)
	for _, c := range []byte(hrp) {
		v = append(v, c&31)
	}
	v = append(v, values...)
	v = append(v, 0, 0, 0, 0, 0, 0)
	chk := uint32(1)
	for _, x := range v {
		top := chk >> 25
		chk = (chk&0x1ffffff)<<5 ^ uint32(x)
		for i := range 5 {
			if top>>i&1 == 1 {
				chk ^= gen[i]
			}
		}
	}
	chk ^= 1
	s := ""
	for p := range 6 {
		s += string("qpzry9x8gf2tvdw0s3jn54khce6mua7l"[chk>>(5*(5-p))&31])
	}
	return s
}

// ---------------------------------------------------------------------------
// A verbatim copy of the functions of internal/ed25519strict of datekeys-go
// (v0.12 branch), which a program outside that module cannot import.

var smallOrder = [8][32]byte{
	{0x00},
	{31: 0x80},
	{0x01},
	{0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x05, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x02, 0x88, 0x6d, 0x53, 0xfc, 0x05},
	{0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4, 0x89, 0xf2, 0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x05, 0xd3, 0xc6, 0x33, 0x39, 0xb1, 0x38, 0x02, 0x88, 0x6d, 0x53, 0xfc, 0x85},
	{0xc7, 0x17, 0x6a, 0x70, 0x3d, 0x4d, 0xd8, 0x4f, 0xba, 0x3c, 0x0b, 0x76, 0x0d, 0x10, 0x67, 0x0f, 0x2a, 0x20, 0x53, 0xfa, 0x2c, 0x39, 0xcc, 0xc6, 0x4e, 0xc7, 0xfd, 0x77, 0x92, 0xac, 0x03, 0x7a},
	{0xc7, 0x17, 0x6a, 0x70, 0x3d, 0x4d, 0xd8, 0x4f, 0xba, 0x3c, 0x0b, 0x76, 0x0d, 0x10, 0x67, 0x0f, 0x2a, 0x20, 0x53, 0xfa, 0x2c, 0x39, 0xcc, 0xc6, 0x4e, 0xc7, 0xfd, 0x77, 0x92, 0xac, 0x03, 0xfa},
	{0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f},
}

func strictVerify(pub, msg, sig []byte) bool {
	if len(pub) != ed25519.PublicKeySize || len(sig) != ed25519.SignatureSize {
		return false
	}
	if !canonical(pub) || isSmallOrder(pub) {
		return false
	}
	return ed25519.Verify(ed25519.PublicKey(pub), msg, sig)
}

func canonical(a []byte) bool {
	if len(a) != 32 {
		return false
	}
	high := a[31] & 0x7f
	ones := true
	for _, b := range a[1:31] {
		if b != 0xff {
			ones = false
			break
		}
	}
	if high == 0x7f && ones && a[0] >= 0xed {
		return false
	}
	if a[31]&0x80 == 0 {
		return true
	}
	zeros := high == 0
	for _, b := range a[1:31] {
		if b != 0 {
			zeros = false
			break
		}
	}
	isOne := zeros && a[0] == 0x01
	isMinusOne := high == 0x7f && ones && a[0] == 0xec
	return !isOne && !isMinusOne
}

var curveP, curveD, halfP = func() (p, d, h *big.Int) {
	p = new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 255), big.NewInt(19))
	d = new(big.Int).ModInverse(big.NewInt(121666), p)
	d.Mul(d, big.NewInt(-121665)).Mod(d, p)
	h = new(big.Int).Rsh(new(big.Int).Sub(p, big.NewInt(1)), 1)
	return p, d, h
}()

func onCurve(a []byte) bool {
	if len(a) != 32 {
		return false
	}
	be := slices.Clone(a)
	be[31] &= 0x7f
	slices.Reverse(be)
	y := new(big.Int).SetBytes(be)
	y2 := new(big.Int).Mul(y, y)
	u := new(big.Int).Sub(y2, big.NewInt(1))
	v := new(big.Int).Mul(curveD, y2)
	v.Add(v, big.NewInt(1)).Mod(v, curveP)
	x2 := u.Mul(u, v.ModInverse(v, curveP))
	x2.Mod(x2, curveP)
	return x2.Sign() == 0 || new(big.Int).Exp(x2, halfP, curveP).Cmp(big.NewInt(1)) == 0
}

func isSmallOrder(a []byte) bool {
	if len(a) != 32 {
		return false
	}
	for _, s := range smallOrder {
		if [32]byte(a) == s {
			return true
		}
	}
	return false
}