Would it be possible to create a game where one would need to decrypt a simple encryption?
Caesar cipher? Its a simple substitution cipher where you can solve with just a pen and paper.

Encryption is done by shifting each plaintext letter, x by n places the alphabet or mathematically, ENCRYPT(x) = (x + n) mod 26. Similarly, the decryption will be the reverse, DECRYPT(x) = (x - n) mod 26. (see wiki http://en.wikipedia.org/wiki/Caesar_cipher#Example)

So, you get a friend to pick a random n and compute the encryption for a randomly chosen four letter string (using free online calculators like http://online-calculators.appspot.com/caesar_ext/). You should not know both n and the plaintext. But the plaintext should be some english word or equivalent in order for it to make sense when you decrypt. 

Then, you start the decryption process by trying out all possible values of n until the decrypted plaintext is make sense. If your first two/three decrypted alphabets is not an valid word, that means your chosen n value is wrong and you should try another n.