Method and apparatus for enabling authentication of on-line communications. In some embodiments, a message code is embedded in an e-mail, where the message code can be used by the recipient to verify the authenticity of the e-mail or of a Web site. In some embodiments, this code can be created for a particular e-mail message; in other embodiments, the code is created as a watermark for use by a customer or other a specific user or recipient. The message code is associated with both the e-mail message and the recipient. In the case of a message-specific code, a recipient can verify the e-mail message by inputting the code via a Web server to be looked up in the database. Provision is also made for including stenographic information in graphical or other codes as further authentication when accessing a Web site.