The present invention provides a method of securing messages steganographically embedded in media (e.g., printed or electronic objects, audio, and video). In one implementation, a message inclues a first portion and a second portion. The first portion includes a first message and a first checksum, which are encrypted with a private key. The encrypted first protion is combined with the second portion. The second portion includes a second message and a second checksum. The combined encrypted first portion and the second portion form a signature. The signature is encrypted wth a common key or universal key, perhaps after error correction coding. The private key is uniquely associated with an entity such as a document issuing jurisdiction.