This algorithm is then called the Fletcher-16 checksum. Usually, the second sum will be multiplied by 256 and added to the simple checksum, effectively stacking the sums side-by-side in a 16-bit word with the simple checksum at the least significant end. When the data word is divided into 8-bit blocks, as in the example above, two 8-bit sums result and are combined into a 16-bit Fletcher checksum. The 16 and 32 bits versions (Fletcher-32 and -64) have been derived from the original case and studied in subsequent specifications or papers. While there is an infinity of parameters, the original paper only studies the case K=8 (word length) with modulus 255 and 256.
Overview of the different algorithm parameters In our example, the two sums, each with 255 possible values, result in 65025 possible values for the combined checksum.
The universe of possible checksum values is now the square of the value for the simple checksum. The final value of the first sum will be the same, but the second sum will be different, detecting the change to the message. If, for example, two adjacent blocks become exchanged, the one that was originally first will be added to the second sum one fewer times and the one that was originally second will be added to the second sum one more time. Sensitivity to the order of blocks is introduced because once a block is added to the first sum, it is then repeatedly added to the second sum along with every block after it. At the end of the data word, the modulus operator is applied and the two values are combined to form the Fletcher checksum value. Both sums start with the value zero (or some other known value). So, for each block of the data word, taken in sequence, the block's value is added to the first sum and the new value of the first sum is then added to the second sum. This is the modular sum of the values taken by the simple checksum as each block of the data word is added to it. In our example, there are only 255 possible checksum values, so it is easy to see that even random data has about a 0.4% probability of having the same checksum as our message.įletcher addresses both of these weaknesses by computing a second value along with the simple checksum. The second weakness is that the universe of checksum values is small, being equal to the chosen modulus. If the order is changed, the checksum value will be the same and the change will not be detected. The first weakness of the simple checksum is that it is insensitive to the order of the blocks (bytes) in the data word (message). The receiver of the message can re-compute the checksum and compare it to the value received to determine whether the message has been altered by the transmission process. (In practice, the modulo operation is performed during the summation to control the size of the result.) The checksum value is transmitted with the message, increasing its length to 137 bytes, or 1096 bits.
So, the simple checksum is computed by adding together all the 8-bit bytes of the message, dividing by 255 and keeping only the remainder. Similarly, a convenient modulus would be 255, although, again, others could be chosen. A convenient block size would be 8 bits, although this is not required. The data to be protected, in its entirety, is referred to as a "word", and the pieces into which it is divided are referred to as "blocks".)Īs an example, the data may be a message to be transmitted consisting of 136 characters, each stored as an 8-bit byte, making a data word of 1088 bits in total. (Note that the terminology used in this domain can be confusing. The algorithm Review of simple checksums Īs with simpler checksum algorithms, the Fletcher checksum involves dividing the binary data word to be protected from errors into short "blocks" of bits and computing the modular sum of those blocks.
0 kommentar(er)
