Public Key Infrastructures (PKIs) were developed to address the key distribution problem of asymmetric cryptography. Certificates bind an identity to a public key and are signed by a trustworthy entity, called the issuer. Although seemingly a simple concept, the setup of a PKI is not an easy task at all. Trustworthy issuers need to be guaranteed, and certificates must be issued conforming to certain standards. A correct deployment is needed to ensure the PKI is usable for the parties that rely on it. Some PKIs, like the important X.509 PKI for TLS, were criticised from early on for being poor examples with respect to these aspects. The objective of this thesis is to provide a sound analysis of important PKIs and to analyse proposals for improvements for one of them, X.509. The contributions of this thesis are threefold. In the first part of this thesis, we carry out an analysis of known criticisms of the X.509 PKI and show that they were never addressed well. The approach here is both documental as well as empirical. Furthermore, we provide a survey of incidents in the X.509 PKI, some of which brought it close to failure, and identify their root causes. This analysis allows us to formulate requirements that improvements for the X.509 PKI have to meet. The methodology here is historical-documental. In the second part of the thesis, we apply empirical methods to analyse the status quo for three representative and important PKIs that address different use cases: X.509, the OpenPGP Web of Trust, and the simple key distribution mechanism of SSH. We measure their respective strengths and weaknesses, in particular with respect to deployment, and draw conclusions about the level of security that each PKI achieves in practical use. For X.509, we carried out HTTPS scans of a large number of servers over a period of 1.5 years, including scans from globally distributed vantage points. We also monitored live TLS traffic on a high-speed link of a large network. Our analyses of the thus obtained certification data reveals that the quality of certification lacks in stringency to a degree that is truly worrisome. For OpenPGP, we conducted a graph analysis of the Web of Trust, with a focus on properties such as usefulness and robustness of certification chains. We also analysed the community structure of the Web of Trust and mapped it to social relationships. This allows us to determine for which users, and on which scale, the Web of Trust is particularly useful. For SSH, we carried out several scans over the entire IPv4 address space and collected statistics on host-keys and ciphers used. A number of keys were found to be duplicates, but not due to cryptographic weaknesses. For these, we determined in which network setups they occurred and identified both secure as well as very insecure patterns of use. In the third part of this thesis, we study five representative schemes to improve the security of X.509. In order to describe each scheme succinctly, we first develop a unified notation to capture the essential protocol flows and properties of each scheme. We then analyse its security properties with particular regard to three threat models that we defined for this purpose. A further particular focus is on the deployment properties of a scheme, i.e., which entities need to make changes to implement it. Based on our findings, we identify the two most promising candidates to reinforce X.509. However, all schemes fall short in one respect, namely automatic incident reporting and localisation of the position of an attacker. We thus developed and deployed our own solution, Crossbear, to close this gap. Crossbear allows to detect an ongoing man-in-the-middle attack and initiates a distributed but centrally coordinated hunting process to determine the location of the attacker in the network with a fair degree of confidence.