The presented messaging protocol uses three new public keys in a signed and encrypted message to achieve backward security and recovery in an environment where an attacker now and then obtains the security parameters in exposed, decrypted form. Backward security is understood to mean that an adversary cannot decrypt those captured encrypted messages that the user has decrypted prior the exposure. The recovery of the protocol means that the attacker at some point of time after the exposure cannot any more decrypt messages created after the exposure. The invention can be used e.g. in encrypted email communication. New to the current state of the art is that a message contains history data: a list of recently used public keys and their Diffie-Hellman counterparts. Also new is the usage of a stored and pseudorandomly changing data used together with a just computed Diffie-Hellman shared secret to provide a value that an attacker cannot produce if he does not have a proper exposed security data and the private key required to compute the Diffie-Hellman shared secret.