Integrity components

How do we tell if a message has changed in transit?
Simplest answer: use a checksum.
For example, add up all the bytes of a message
The last digits of serial numbers (credit card, ISBN, etc.) are usually checksums.
Alice computes the checksum of the message, and sticks it at the end before encrypting it to Bob.  When Bob receives the message and checksum, he verifies that the checksum is correct.
This doesn't work!
With most checksum methods, Mallory can easily change the message in such a way that the checksum stays the same.
We need a "cryptographic" checksum
It should be hard for Mallory to find a second message with the same checksum as any given one.