A secure electronic mail distribution system for a network, e.g. Encrypted Internet E-Mail transmitted between interactive display terminals. The system offers a solution to the disclosed problems by providing a display interface at a receiving terminal including the conventional mechanisms of access of an E-Mail distribution server by an E-Mail client; but in addition provides an automatic encryption mechanism that responds to a key request to generate a public key/private key pair enabling a user of the E-Mail distribution system to send secured messages and to have the recipient receive a cleartext version of an encrypted message transmission. The system automatically generates the pair, most preferably at the consuming message recipient though key pairs may be created/issued centrally using machine-derived data so the user does not participate in the key generation and the key pairs are preferably single use meaning that the user does not need to have a passphrase or worry about passwords or other management of the key pair. When they are multiple use, it is preferred that the server maintain the key information and provide the SENDER with the public key and the CLIENT with the private key used for a specific message. The invention further provides, in some implementations, a mechanism to initiate various tests to confirm access and availability of the secure system before sending. This invention is applicable to enable an secure communications between users of virtually any device participating in the communications network (e.g., desktop, laptop, wireless computing systems and wireless devices including cellular telephones and personal digital assistants and other portable messaging systems like Blackberry PDAs).