The report is outlined as follows. In chapter 2, we give an overview of, and a background to, Cryptography, Public Key Infrastructure (PKI), DNS and Secure Messaging, which is used throughout this report. In chapter 3 we demonstrate our implementation of a secure mail application and of a certificate publishing application. In chapter 4 we compare LDAP and DNS for certificate locating and retrieval purposes. In chapter 5 we discuss privacy threats due to Secure DNS and present a possible remedy. In the final chapter we present our conclusions and suggest topics for further investigations