>>126
The trick is to not require a private key, although I suppose a symmetric cipher with a plain text random key prepended to the message would do.
You
can do public-key steganography, as long as you have some way to render the public key bits indistinguishable from random data.