Manual Hash Function

Question

I need a hash function, H(X), fulfilling the following:

(1) Inputs around 10 digits and outputs around 10 digits.

(2) If you change X even just by a single digit, you get a totally different H(X).

(3) Easy to calculate manually. People are going to calculate it by hand. I need them to be able to do it quickly and with no mistakes.

Thank you for your creative ideas!

edit: By "hash" I mean something in the spirit of "one-way-hash". That is - given H(X) it should be hard to find possible values for X. Hard for a human being.

edit: What is this for? This is for an exam. Students are going to do calculations and get numbers as answers. I want them to be able to know, during the test, if they got all answers right. So the idea is: concatenate all answers to one number X. Then calculate H(X). Then use H(X) to decipher some code, digit by digit, and get a short message indicating your correctness. I don't want them to be able to figure out the 4th answer after they got the first 3.

Answer 1

Hash functions such as MD5, SHA1, etc, are a combination of an encryption function (usually a block cipher) and a compression function.

As you don't really need the compression, the simplest construction would be computing the bitwise modulus of the input number and some key number. If you could use a new key for each number, your code would be unbreakable (this is called a one-time pad).

This is how the Davies–Meyer hash function works, where E is some encryption function and I is the input:

H[0] = <SOME CONSTANT>
for (i in I[1:])
   H[i] = H[i-1] mod E(H[i-1] with key I[i])

If you took each item in I to be a digit, your encryption (E) could be adding the digit to the key mod 10 and adding 1.

The base of more complex block encryption is some arrangement of substitution (replacing numbers or bit sequences with others) and permutation (swapping numbers or bit sequences within the phrase)h.

Answer 2

My best guess is, this is going to be some sort of CAPTCHA system or math puzzle. But i think it's going to be quite difficult if not impossible to construct a function obeying all three rules. If each digit should effect every other digit independently, that would make 10^2 dependencies.

Err, ok whatever, i'll still give it a try. How about this:

Prepare 10 constant numbers c_0, c_1, .. , c_9, each having 10 digits. Make them pairwise co-prime or somesuch. Choose your "hash input" number a randomly. Let the user calculate the sum of digits s of a. The last digit i of s is then used to choose one of those constants c_i. The hash result b equals a + c_i.

Example:

c_0 = 4729703658
c_1 = 5793154234
c_2 = 0362709821
...

a = 8243047067
s = 41
i = 1
b = a + c_1 = 14036201301

Change a single digit:

a = 7243047067
s = 40
i = 0
b = a + c_0 = 11972750725

It should be obvious that this system is not suited for any kind of cryptographic application. Also it's quite easy to break as CAPTCHA. I don't even think it's too difficult to reverse in most cases, even for humans. But it could be a start.

Answer 3

Each digit is the coefficient of a polynomial: ie 1234 is 1*x^3+2*x^2+3*x+4. Compute the value of the polynomial for some predetermined X, say 987654321 and truncate it to the desired number of digits.