2

假设我有一个长度为 32 的 Java 字符串，例如

String s = "Y7yEdfjQ2qmpGZbPYswKIdxYVo6KnR9M";

我正在寻找具有以下属性的字符串 t ：如果在 t 上执行以下循环，则生成的字符串为 s：

char[] tArr = t.toCharArray();
for (int i = 1; i < 32; i++) {
    tArr[i] = (char) (tArr[i] ^ tArr[i * 123456 % 31] & 31);
}

请注意，在 Java 中，数组运算符 [] 具有最高优先级，并且在按位 XOR 之前计算位与。

为了获得 t，必须对 s 进行反向操作。XOR 的逆运算是 XOR，但逻辑 AND 显然没有逆运算。

字符串 t 可以在没有暴力破解的情况下恢复吗？

4

2 回答 2

3

31 是 11111b

因此该算法采用任何字符的最低 5 位，这使您无法恢复初始字符串 - 您可能会发现一些导致相同哈希的字符串

蛮力是这里唯一的选择

于 2014-07-02T19:16:11.793 回答
3

您的循环在每次迭代中接受两个字符，并将第一个字符与另一个字符的最低 5 位进行异或。这意味着前 3 位保持不变。他们不会迷路。实际上 的 前 3 位t[i]等于 的 前 3 位s[i], 我们只需要找到原始字符串中字符的最低 5 位t.

现在，让我们计算i * 123456 % 31一下，看看循环在每次迭代中实际做了什么：

t[1] = t[1] ^ (t[14]&31)
t[2] = t[2] ^ (t[28]&31)
t[3] = t[3] ^ (t[11]&31)
t[4] = t[4] ^ (t[25]&31)
t[5] = t[5] ^ (t[8]&31)
t[6] = t[6] ^ (t[22]&31)
t[7] = t[7] ^ (t[5]&31)
t[8] = t[8] ^ (t[19]&31)
t[9] = t[9] ^ (t[2]&31)
t[10] = t[10] ^ (t[16]&31)
t[11] = t[11] ^ (t[30]&31)
t[12] = t[12] ^ (t[13]&31)
t[13] = t[13] ^ (t[27]&31)
t[14] = t[14] ^ (t[10]&31)
t[15] = t[15] ^ (t[24]&31)
t[16] = t[16] ^ (t[7]&31)
t[17] = t[17] ^ (t[21]&31)
t[18] = t[18] ^ (t[4]&31)
t[19] = t[19] ^ (t[18]&31)
t[20] = t[20] ^ (t[1]&31)
t[21] = t[21] ^ (t[15]&31)
t[22] = t[22] ^ (t[29]&31)
t[23] = t[23] ^ (t[12]&31)
t[24] = t[24] ^ (t[26]&31)
t[25] = t[25] ^ (t[9]&31)
t[26] = t[26] ^ (t[23]&31)
t[27] = t[27] ^ (t[6]&31)
t[28] = t[28] ^ (t[20]&31)
t[29] = t[29] ^ (t[3]&31)
t[30] = t[30] ^ (t[17]&31)
t[31] = t[31] ^ (t[0]&31)

我们知道，在最后一次迭代之后，数组已经从t（我们不知道）转换为s（我们知道 - “Y7yEdfjQ2qmpGZbPYswKIdxYVo6KnR9M”）。

现在，由于t[0]从未修改，我们知道s[0]=t[0]='Y'（或二进制的 01011001）。

这t[31]很容易给我们：

t[0]&31 = 00011001
s[31] = 'M' = 01001101 = t[31] ^ 00011001

两边异或，得到：

t[31] = 01001101 ^ 00011001 = 01010100

其他角色不太容易。

循环的迭代形成两个循环：

1->14->10->16->7->5->8->19->18->4->25->9->2->28->20->1

3->11->30->17->21->15->24->26->23->12->13->27->6->22->29->3

现在，让我们尝试查找 的其他字符t：

t[30] = t[30] ^ (t[17]&31)

在此分配之后，t[30]变为s[30]，即 '9' 或 00111001。

我们知道001 11001 = 001 ????? ^ 000 xxxxx

在哪里 ？？？？？是 的最低 5 位，t[30]xxxxxx 是 的最低 5 位t[17]。但实际上，它不是原版的t[17]。到我们分配的时候t[30]，t[17]已经更新到它的最终值，我们知道（它是s[17]- 's' 或01110011）。

因此001 11001 = 001 ????? ^ 000 10011。

如果我们两边异或，001 11001 ^ 000 10011 = 001 01010

所以原来t[30]是00101010。

到目前为止，我t[0]发现t[30]和t[31]。我相信（虽然我还没有真正检查过），我可以继续以t这种方式找到所有其他角色。

计算时要注意的重要一点t[i]是，如果t[i]依赖于t[j]这样i<j，它依赖于t[j]（未知数）的原始值，而如果i>j，它依赖于t[j]（s[j]即我们知道的）的最终值。

于 2014-07-02T20:53:00.513 回答