Fair, encrypt your recipient's public key, sign with your private key.

Assume your correspondents can do the same as in, encrypt with your public key and sign with their private key