As the use of satellites continues to grow, new networking paradigms are emerging to support the scale and long distance communication inherent to these networks. In particular, interplanetary communication relays connect distant network segments together, but result in a sparsely connected network with long-distance links that are frequently interrupted. In this new context, traditional Public Key Infrastructure (PKI) becomes difficult to implement, due to the impossibility of low-latency queries to a central authority. This paper addresses the challenge of implementing PKI in these complex networks, identifying the essential goals and requirements. Using these requirements, we develop the KeySpace framework, comprising a set of standardized experiments and metrics for comparing PKI systems across various network topologies, evaluating their performance and security. This enables the testing of different protocols and configurations in a standard, repeatable manner, so that improvements can be more fairly tested and clearly demonstrated. We use KeySpace to test two standard PKI protocols in use in terrestrial networks (OCSP and CRLs), demonstrating for the first time that both can be effectively utilized even in interplanetary networks with high latency and frequent interruptions, provided authority is properly distributed throughout the network. Finally, we propose and evaluate a number of novel techniques extending standard OCSP to improve the overhead of connection establishment, reduce link congestion, and limit the reach of an attacker with a compromised key. Using KeySpace we validate these claims, demonstrating their improved performance over the state of the art.