This disclosure relates to message encoding. One claim recites a digital watermark key generation method in which the key providing security for a plural-bit message. The method comprises: providing a plural-bit seed; randomizing the plural-bit seed; using a programmed electronic processor for encoding the randomized plural-bit seed with convolutional encoding, the encoded seed comprising a key; and transforming an independent message with the key, the independent message to be used in a digital watermark encoding process. Of course, other claims and combinations are provided too.