Toy cryptographic hash function for education purposes?

Question

I'm teaching some high school students about number theory and cryptography, and I'd like a hash function (or ideally, a family of hash functions) that I can use as simple demonstration for cryptographic hash functions. The students have learned everything involved in a simple implementation of RSA.

It will be used for inputs that are numbers in decimal format between 8 and 12 digits long.

• Can be worked out fairly quickly and easily with paper and a scientific calculator for decimal inputs of around 8-12 digits
• A short digest (say around 4 digits)
• Digest should change significantly with small modifications to the input
• It should seem difficult (at least on paper) to find an input that produces a given digest
• It should seem difficult to see a way to modify an input without modifying its digest
• It should seem difficult to find two inputs that will have the same digest

Not all of these properties are required but the more it has the better it will be for demonstration purposes. It's okay if it's reversible, so long as it isn't obvious at first glance how to do that.

Any ideas?

Answer 1

I'm looking in my algorithms textbook now for information on hash functions. For positive integers $n$, it says that the most common hash function is to simply take $n\pmod{p}$ for some prime $p$. This doesn't really fit the requirement of "large changes in output for small changes in input."

However, things get a bit more interesting if you don't use the hash function for numbers, but rather for text. For example, my textbook (by Sedgewick and Wayne) says an example process to hash a string is to:

hash = 0
for each character c in the string:
  hash = (R*hash + c) % p

...Where R is some number that is greater than the numeric value of any character, and p is a prime (e.g. $31$ seems to be used often). You'd need some way of converting characters to numbers, which could be as simple as $A\mapsto 1, \ldots, Z\mapsto 26$

This doesn't fit your exact input/output requirements, but it would be a fairly straightforward example to teach high schoolers.