Federated Space Public Key Infrastructure (PKI) can offer a scalable foundation for secure and interoperable communications in collaborative space missions. Yet, its deployment faces challenges stemming from resource-constrained assets, architectural complexity, and the transition to post-quantum (PQ) cryptography. Current CCSDS space guidelines rely on the Internet X.509 profile, whose extensive feature set—if left unrestricted—can increase implementation complexity, certificate size (especially under PQ algorithms), and the risk of interoperability issues. In parallel, the IETF C509 Certificates draft emerges as a streamlined subset of X.509 with a compact encoding specifically tailored for constrained environments. This paper provides an empirical comparison between X.509 and C509 to inform space mission designers about the associated advantages and costs of each, specifically when PQ cryptography is incorporated into space PKIs. To help pave the way for interoperability in federated space missions, a minimal certificate profile for space PKI is proposed.

In addition, the work introduces the first open-source native C509 toolkit that supports PQ algorithms and evaluates open-source and proprietary certificate parsers. While the IETF C509 draft proposal reports a size reduction of over 50%, our evaluation confirms approximately 40% savings for classical certificates generated according to our proposed minimal certificate profile. For PQ certificates, the savings plateau at around 200 bytes, rendering the size gains negligible. However, revocation lists consistently achieve a 60% reduction for 30,000 entries, independent of the cryptographic scheme (PQ or traditional). To quantify and compare the software implementation complexity of X.509 and C509, we conduct software complexity analysis using well-established heuristic metrics (e.g., cyclomatic complexity, Halstead metrics, logical lines of code). The findings further highlight the relative simplicity of the C509 parser implementation in software. Defining a standardised certificate profile for federated space would advance interoperability; however, adopting C509 requires carefully balancing modest PQ size savings against software simplification and the uncertainties associated with a draft standard.