f(y) = y^(y>>11)
我有一个普遍的疑问是，每当给出了一系列说明。您有解决此类问题的方法吗？
#1 楼
快速查找函数f()是否具有逆函数的一种好方法是尝试查找初始域x和y的两个元素，以便x!=y和f(x)==f(y)。如果存在这两个元素，您无法在
f的目标域中区分它们，因此无法构建反向函数。看看您的示例：
f(x) = x^(x>>11)，我们可以将结果位向量分为三部分（第一个清零）从b31到b21的部分，第二个Xored部分，其中第一部分（因此可以恢复）从b20到b10，最后一个第三部分，可以使用第二部分的明文从b9到b0恢复）： x = (b31, ..., b0)
f(x) = (b31, ..., b21, b20^b31, b19^b30, ..., b10^b21, b9^b20, ..., b0^b11)
clear part | xored with clear part | xored with previous part
因此，实际上，没有信息丢失，因此可以构建反向功能。这是解释此反向功能原理的伪代码：
g(x)
{
/* Get the clear part */
y = (x >> 20);
/* Unmask the second part */
z = ((x << 11) >> 21) ^ y;
/* Unmask the third part */
t = ((x << 22) >> 22) ^ z;
/* Reassembling the whole thing */
return (y << 20 + z << 11 + t);
}
评论
我远远不能确定我说的是什么。因此，批评家和我的推理中出现矛盾非常令人欢迎。
–恐怖
2014年1月3日14:06
哎呀，我想我们会错过一两个信息位，因为第一个明文部分只有10位长，第二个和第三部分只有11位长...在使用此解决方案时请小心，在构建时可能会出错位的索引。
–恐怖
2014年1月3日14:36
我能看到的唯一问题是整数是否带符号而不是无符号。问题中未指定。如果签名，则结果b31将独立于b31的原始值而为0，这将导致数据丢失。对于无符号的情况，此方法可以一直推广到1位移位，这实际上更容易说明。如果您将每个位向量元素公式化为方程式系统，那么就很容易理解为什么这样做。除非我缺少任何东西。我尚未验证您的代码。
–彼得·安德森（Peter Andersson）
2014年1月3日14:42
感谢您的关注！ （伪代码仅在此处提供解码方法的概念，不应被信任）。
–恐怖
2014年1月3日14:45
没问题，我认为您重新格式化为位向量，尝试为每位公式化方程，然后反转方程组的方法通常是解决这类问题的方法。
–彼得·安德森（Peter Andersson）
2014年1月3日15:02
#2 楼
Perror已经涵盖了这个特殊情况，但是这里有一些反转相似函数的一般原则。注意：所有这些都假定整数是无符号的，或者是使用二进制补码和无符号移位进行签名的。在Java中，保证了二进制补码。在C / C ++中，这不是保证，但实际上几乎总是这样，您可以检查编译后的程序集以确保确定。
可以想到涉及xor和bitshift的一系列转换。作为（GF2）^ 32中向量的线性（或仿射，如果有常数）转换。本质上，您有一个数字为2的32元素向量，并且由于xor是加法为2，并且将其乘以矩阵。
因此，如果矩阵是可逆的，则转换是可逆的。幸运的是，通常是这种情况。 n> 0的形式为
x ^ (x >>> n)的函数是下三角矩阵，因此是可逆的。同样，x ^ (x << n)是上三角矩阵，因此也是可逆的。由于可逆矩阵的乘积是可逆的，因此此类转换的任何序列也将是可逆的。 请注意，带符号的移位（Java中的>>）不一定是可逆的。
关于实际反转，最简单的方法（尽管不一定是最快的）是只需计算变换矩阵项，然后执行Guassian消除（在有限域中没有舍入误差）。
您还会经常看到其他操作混在一起。可以将加法和乘法视为对2 ^ 32进行模环运算。使用二进制补码，无论您使用带符号的数字还是无符号的数字都没有关系。用常数加法很简单：只需减去常数即可。与任何奇数常数的乘积也是可逆的：只需乘以乘积模逆。您可以找到代码来在线进行计算，如果您使用的是Python，请直接输入
pow(c, (2**31)-1, 2**32)。乘以偶数常量会丢失信息，因此无法完全取反。同样，添加效果相同的组合也不是。例如，
x + x不可逆，因为它等效于x * 2。 x + (x<<4)是可逆的，因为它等效于x * 17。由于仿射变换的组成也是仿射，您可以通过乘以所有这些运算然后将其求逆来节省时间。一小步。
除琐碎的情况外，按位与和总是丢失信息，因此它们将不可逆。但是通常使用它们以无损方式选择部分信息进行组合，因此整体表达仍然是可逆的。例如，即使表达式的两个组成部分都是不可逆的运算，
x ^ ((x & 555) * 4)也是可逆的。您可能还会看到其他几件事。 GF（2 ^ 32）中的运算基本上与常规加法和乘法相同，只不过没有进位。通常在CRC中使用。使用与以前相同的技术，加法（仅是xor）和与任何非零数字的乘法都是可逆的。具有任何特定的结构。通常，这些表示为表查找，逆运算也带有预先计算的表。如果不是，您可以始终创建自己的逆表，并假设输入不是太大。
评论
我喜欢这个答案-如果只剩下您的最后一条评论;）
–直到
2014年1月3日在22:48
@直到抱歉，我将其删除。
–锑
2014年1月4日，2：13
#3 楼
我试着为您的问题提供一个非常肤浅的答案，因为我非常确定对此问题还有其他处理方法。函数f(y) = y^(y >> 11)的存在，因为g是一个内射函数。但是，这并不意味着我们可以轻松找到反函数，因为它可能无法计算，即在这种情况下，我们无法给出计算y = g(f(y))的算法。实际上，可能存在一些可计算的方法来“逼近”它（也许是抽象解释？）。在更严格的情况下（但可能更实际），如果f的值存储在4个字节中并且g的值存储在少于4个字节中，则由于信鸽原理，该函数通常不可逆。此外，由于执行过程中会丢失信息，因此任意指令序列的计算通常是不可逆的，因此，我们可以考虑一个示例（使用伪汇编代码）。f(y) =
mov eax, y
xor eax, eax
return eax
则
y是不可逆的，因为无论输入如何，输出始终为f(y)。但是，如果我们可以沿着指令的执行存储一些“状态值”（即不仅是输出和指令序列），那么反转是可能的，这种想法在任何地方都被提出过，例如：在GDB反向调试中或在本文中。按位互斥。评论
-1。逆很容易计算。
–锑
2014年1月3日15:24
您是完全正确的，@ perror的答案清楚地表明了这一点。实际上，在回答以上答案时，我认为运算符^是幂运算（因此，我怀疑它一般而言不可算），但实际上它是按位互斥的。
– Ta Thanh Dinh
2014年1月3日15:36
#4 楼
此python函数适用于任何值：def f_inv(x):
mask= (1<<11) - 1
a= []
while x>0:
a.append(x&mask)
x >>= 11
if not a:
return 0
z= a.pop()
while a:
z= (z<<11) | ((z&mask)^a.pop())
return z
诀窍是将数字分成11位块，然后从最高的xorring开始，与前一个（更高）块。和/或所有内容一起。
评论
您的函数在数学上是可逆的（从某种意义上说，它的左反转存在）是因为它是单调函数，但是我不知道左反转是可计算的还是不可计算的。在更严格的情况下，如果将y存储在4个字节中，而将f（y）存储在小于4个字节中，则由于鸽子洞原理，该函数不可逆。通常，任意指令序列的计算是不可逆的，因为在执行这些指令时会丢失大量信息。
@tathanhdinh也许一般而言，但是许多功能是专门设计为可逆的，例如blah在这里询问的类型。
最坏的情况是，由于y空间是有限的（4字节int），因此可以对f（y）进行详尽的搜索