# How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher?

I'll probably get shot for asking this, but I've got some kids (aged 8-10) in my neighbourhood that I've been showing/teaching the simple pen-and-paper Caesar cipher and they're successfully playing with it for more than a week now.

Silly me thought it would be great to now show them the concept of message authentication and how it practically works; especially that it can be used to show if the message has been modified by someone along the way or not. So the plan was set and the promise made as it suddenly dawned upon me that I never used anything else but computational power to calculate (H)MACs… and that's not exactly a pen-and-paper solution for the kids.

Now, the good thing is that they don't need a national-security-level encryption, which means I could use any simple (read: improvised) hashing method as long as it works using pen-and-paper. But such simple hashes are obviously hard to find. So currently, I am thinking of simply replacing the usual hashing with an addition-based checksum thing. That could work, but I'm not so sure that that's really the best option.

Keeping in mind that I need to explain MAC to kids aged 8-10 so they can practically do it themselves using nothing but pen-and-paper, do you have a better idea? How would you encrypt-then-MAC when using pen-and-paper and a Caesar cipher to practically show them a working message authentication?

-

One option would be to get them to select a one-time MAC of the form:

$mac(m,k_0, k_1) = (k_0 \times m + k_1) \mod p$

You would select $p$ to be something like 29. $k_0$ and $k_1$ would be chosen at random from the values 0-29. $k_0$ has the additional restriction that it can't be 0.

You can aid the computation by giving them a 29x29 matrix of all multiplications mod 29 and a similar table for all additions mod 29.

You'd then work through the message a letter at the time. Suppose these were the letters were numbered: $m_0 \dots m_i$. You'd start at $m_0$, computing the mac equation above. Then you'd feed the mac output in to the $k_1$ position for the next message block:

$mac(m_1, k_0, mac(m_0, k_0, k_1))$

and so on and so on:

$mac(m_i, k_0, mac(m_{i-1}, k_0, \dots))$

The final result is simply the output of the MAC.

Even though it isn't secure it demonstrates at least the idea of a MAC. It also gives them a design that can be trivially extended in to a secure MAC with small alterations.

-
I really like this option for both it's simplicity as well as practical demonstration purposes. [+1] and accepted. Thanks - also in the name of the little buggers. Hope you don't mind me telling them that "Simon" helped me? ;) –  e-sushi Nov 1 '13 at 15:40
Don't mind at all. :) –  Simon Johnson Nov 1 '13 at 15:45