A method implementing a public key steganography system has been proposed. Remember the Prisoners' Problem scenario we discussed in Chapter 2? We will assume Alice wants to pass a secret message to Bob, but they did not have the opportunity to exchange a steganographic key before passing the message. If Bob possesses a public key (a PGP key, for example) and Alice knows it, she can encrypt the secret message with Bob's public key, embed the ciphertext in a cover file, and send the resulting stego file to Bob. Bob can extract the ciphertext from the stego file and decrypt it with his private key.
For PKI steganography to work, everyone needs to know how to extract the ciphertext from a stego file. This extraction algorithm can be applied to any cover file and to files without hidden ciphertext. It does not matter if a file actually contains a hidden ciphertext; the result will always be a random-looking bit string, which only a person with the public key will be able to decrypt successfully. To speed up this process in practice, a session key for a symmetric encryption algorithm could be encrypted with the public key and this session key could be used to actually encrypt and decrypt the hidden message.
The drawback is that everyone who receives a stego file will have to extract the potential ciphertext and try to decrypt it with a private key.