Linearize x509 certificates where partial order is derived from issuing authority

examples__main.go

package main

import (
	"crypto"
	crand "crypto/rand"
	"crypto/rsa"
	"crypto/x509"
	"crypto/x509/pkix"
	"math/big"
	mrand "math/rand"
	"time"

	"github.com/amitkgupta/x509utils"
)

func main() {
	a, aKey := generate(true, "a", nil, nil)
	b, bKey := generate(true, "b", nil, nil)
	c, _ := generate(true, "c", nil, nil)
	a1, a1Key := generate(true, "a1", a, aKey)
	a2, a2Key := generate(true, "a2", a, aKey)
	a3, _ := generate(false, "a3", a, aKey)
	b1, b1Key := generate(true, "b1", b, bKey)
	b2, _ := generate(false, "b2", b, bKey)
	a1i, _ := generate(true, "a1i", a1, a1Key)
	a1ii, _ := generate(false, "a1ii", a1, a1Key)
	a2i, _ := generate(false, "a2i", a2, a2Key)
	a2ii, _ := generate(false, "a2ii", a2, a2Key)
	b1i, _ := generate(false, "b1i", b1, b1Key)
	b1ii, b1iiKey := generate(true, "b1ii", b1, b1Key)
	b1iiA, _ := generate(false, "b1iiA", b1ii, b1iiKey)

	list := []*x509.Certificate{b1iiA, a2i, b1, a, b1ii, a1ii, a3, b2, c, b, a2ii, a2, a1, a1i, b1i}
	for _, cert := range list {
		println(cert.Subject.CommonName)
	}

	x509utils.SortByDepth(list)
	for _, cert := range list {
		println(cert.Subject.CommonName)
	}
}

func generate(isCA bool, commonName string, issuer *x509.Certificate, issuerSigningKey crypto.Signer) (*x509.Certificate, crypto.Signer) {
	key, err := rsa.GenerateKey(crand.Reader, 2048)
	if err != nil {
		panic(err)
	}

	template := &x509.Certificate{
		BasicConstraintsValid: true,
		IsCA:         isCA,
		Subject:      pkix.Name{CommonName: commonName},
		SerialNumber: big.NewInt(mrand.Int63()),
		NotBefore:    time.Now().Add(-time.Hour),
		NotAfter:     time.Now().Add(time.Hour),
	}

	var parent *x509.Certificate
	if issuer == nil {
		parent = template
	} else {
		parent = issuer
	}

	var signingKey crypto.Signer
	if issuerSigningKey == nil {
		signingKey = key
	} else {
		signingKey = issuerSigningKey
	}

	certBytes, err := x509.CreateCertificate(crand.Reader, template, parent, key.Public(), signingKey)
	if err != nil {
		panic(err)
	}

	cert, err := x509.ParseCertificate(certBytes)
	if err != nil {
		panic(err)
	}

	return cert, key
}

sortbydepth.go

package x509utils

import (
	"crypto/x509"
	"sort"
)

type certWithParent struct {
	cert   *x509.Certificate
	parent *certWithParent
}

type byDepth []*certWithParent

func (bd byDepth) Len() int           { return len(bd) }
func (bd byDepth) Swap(i, j int)      { bd[i], bd[j] = bd[j], bd[i] }
func (bd byDepth) Less(i, j int) bool { return depth(bd[i]) < depth(bd[j]) }

func depth(cwp *certWithParent) int {
	if cwp.parent == nil {
		return 0
	} else {
		return 1 + depth(cwp.parent)
	}
}

func SortByDepth(certs []*x509.Certificate) {
	cwps := make(byDepth, len(certs))

	for i, cert := range certs {
		cwps[i] = &certWithParent{
			cert:   cert,
			parent: findParent(cert, remove(certs, i)),
		}
	}

	sort.Sort(cwps)

	for i, cwp := range cwps {
		certs[i] = cwp.cert
	}
}

func findParent(cert *x509.Certificate, possibleCAs []*x509.Certificate) *certWithParent {
	for j, possibleCA := range possibleCAs {
		roots := x509.NewCertPool()
		roots.AddCert(possibleCA)

		if _, err := cert.Verify(x509.VerifyOptions{Roots: roots, KeyUsages: []x509.ExtKeyUsage{x509.ExtKeyUsageAny}}); err == nil {
			return &certWithParent{
				cert:   possibleCA,
				parent: findParent(possibleCA, remove(possibleCAs, j)),
			}
		}
	}

	return nil
}

func remove(certs []*x509.Certificate, i int) []*x509.Certificate {
	result := make([]*x509.Certificate, i)
	copy(result, certs[:i])
	return append(result, certs[i+1:]...)
}