Winternitz Checksum

The Winternitz signature uses a checksum that’s very similar to the approach used in Merkle’s scheme.

Recall that the threat is an attacker who increments any byte(s) of the message. The checksum must ensure that the attacker cannot increment any byte of the message proper without voiding the checksum, and that they cannot maul the checksum in a way that would help them.

The solution in this case is to compute a checksum that consists of the sum of the differences between the 255 (the maximum value of a message byte) and each actual message byte being signed. The resulting sum is encoded as a base-256 integer and added to the message. Both the message and checksum are signed.

For an \ell-byte message, the exact checksum formula is:

\sum_{i=1}^{\ell} 255-M_i

Where M_i is the i^{th} byte of the message M. As an obvious example, the message (255, 255, 255, 255) would have a checksum of 0. The message (0, 0, 0, 0) would have an integer checksum of 1020, which would encode (base-256) as the bytes (3, 252).