What makes the Mersenne Twister Tempering function reversible?

Question

It is well known that it is possible to reverse the MT tempering function. Source code is available online to do this here. I'm trying to figure how this works and how I would approach this and similar problems in a programmatic fashion.

What I'm struggling with is that shift operations on a variable of finite size should result in irreversible data loss. Similarly, the bit-wise AND operations should also result in permanent data loss, yet the sample code provided can reverse any value to it's original pre-tempered state!

The other thing is that I find confusing, is that the un-temporing shift operations are shifting in the same direction & amount as the temporing function.

Answer 1

Consider the structure of a Feistel network. The basic operating principle is to split the data into two parts, and to hash one part into a mask to exclusive-or into the other part. This is reversible even if the hash itself is not. During decryption the same (potentially destructive) hash operation is used to generate the same mask as before and that is exclusive-ored over the other part, thereby restoring it to its original value. This operation can be repeated with different splits so that all bits get an opportunity to affect and be affected by all other bits, and the chain simply has to be replayed in reverse to decrypt it.

Similarly, the destructive shifts and bitwise ands are only used as exclusive-or masks which are used to permute a complete copy of the original value.

k ^= k >> 11 means to take the top 21 bits of k and to exclusive-or them over the bottom 21 bits of k. The top 11 bits of k are unchanged, and we can use them to restore the next 11 bits of k by exclusive-oring them over those bits again. Then we can use these newly-discovered original bits of k to restore the original value of the rest of k.