Algorithm Implementation/Checksums

From Wikibooks, open books for an open world
Jump to: navigation, search

Some people view checksums as a kind of hashing but take note that most will have no guarantee not to generate collisions (different inputs, same result).

A programmer writing a checksum algorithm should use one's complement addition if one is willing to sacrifice error detection effectiveness for speed, Fletcher-32 checksum for a balance of speed and error detection, CRC-32 for better error detection.[1] A programmer should use a MAC or digital signature—typically involving a cryptographically secure hash such as SHA-256 or SHA-3 -- if one is willing to run a little slower in order to detect malicious alterations to data. Such hashes are covered in a later chapter, Hashing.

Cyclic Redundancy Checks[edit]

  • CRC16 XModem
  • CRC32 / FCS32 - commonly used in Ethernet and PKZip-compatible archiving

Further reading[edit]

  1. Theresa C. Maxino. "The Effectiveness of Checksums for Embedded Networks" compares the error detection effectiveness of commonly used checksums: exclusive or (XOR), two's complement addition, ones' complement addition, Fletcher checksum, Adler checksum, and cyclic redundancy codes (CRC) ... briefly mentions that "weighted sum codes" might be just as good as CRC in error detection but with lower computational cost ... discusses common misconceptions about error check codes.