>>132
I think that would be fine. Just create a fixed universal algorithm for extracting the public key from the medium. Like a facebook profile picture. But the public key must appear arbitrary, just like how it would look if the extraction algorithm was performed on an image with no key encoded in it. And throughout every step of using the public key, there couldn't be any tell tail signs of the key working correctly. If you perform the key extraction on an arbitrary image with no actual key in it, the gibberish key should function without error, as otherwise this would provide a means of identifying images without keys, which helps identify images that contain keys.
But then what exactly would the public key be used for?