是什么使Mersenne Twister回火功能具有可逆性? [英] What makes the Mersenne Twister Tempering function reversible?

问题描述

众所周知，可以逆转MT回火功能.可以在线获取源代码来执行此操作此处.我试图弄清楚它是如何工作的，以及如何以编程方式解决这个问题和类似问题.

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.

我正在努力的是，对有限大小的变量进行移位操作会导致不可逆的数据丢失.同样，按位AND运算也应导致永久性数据丢失，但是提供的示例代码可以将任何值恢复为原始预调状态！

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.

推荐答案

请考虑 Feistel网络.基本的操作原理是将数据分为两部分，然后将一个部分散列为掩码以进行异或，或者将其散列为另一部分.即使哈希本身不是，这也是可逆的.在解密期间，使用相同的(可能具有破坏性的)哈希操作来生成与以前相同的掩码，并且该掩码与其他部分异或，从而将其恢复为原始值.可以用不同的拆分方式重复执行此操作，以便所有位都有机会影响所有其他位并受到其他位的影响，并且只需反序重放该链即可对其解密.

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表示取k的高21位，然后对k的低21位进行异或运算. k的高11位保持不变，我们可以使用它们通过再次对k的后11位进行异或来恢复k的后11位.然后，我们可以使用这些新发现的k原始位来恢复k其余部分的原始值.

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.

这篇关于是什么使Mersenne Twister回火功能具有可逆性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！