Integrating fault tolerance and security is crucial for building trustworthy on-line services. Such integration is studied in this dissertation through the design and implementation of COCA (Cornell On-line Certification Authority), a fault-tolerant and secure on-line certification authority. COCA maintains a service private key to sign the responses it sends to clients, and achieves availability using replicated servers that employ threshold cryptography and store shares of the service private key. Periodic share refreshing, coupled with periodic recovery of server states, defends against so-called mobile adversaries which move from one server to another. COCA is designed for a weak system model: no assumptions are made about server speed or message delay, and communications are assumed to employ links that are intermittent. The result is a service with reduced vulnerability to attacks because, by their nature, weaker assumptions are more difficult for adversaries to invalidate. COCA further employs an array of defense mechanisms specific to denial of service attacks. COCA runs both on a local area network and on the Internet. Performance measurements of COCA under simulated denial of service attacks demonstrate the effectiveness of COCA's defenses.