Lehmer随机数发生器密码-寻找微分

Question

我在寻找我的玩具加密方案的区别。我什么都找不到。

让我们考虑线性同余生成器：

X_{k+1} = a \cdot X_{k} \mod 2^{128}

因此，a是一个数字，在从0到2^{128}-1的每128位输入中，就会给出从0到2^{128}-1的不同的输出X_{k+1}。所以这里有双射(我们可以找到许多这样的奇数a)。现在，假设我们随机选择这样的128位a_{1},a_{2}, ..., a_{10}作为密钥。我们对10进行这样的一轮加密：

1. a_{1} \cdot INPUT \mod 2^{128}
2. 反向128-bit块。
3. a_{2} \cdot (2^{128}-INPUT) \mod 2^{128}
4. a_{3} \cdot INPUT \mod 2^{128}
5. 反向128-bit块。
6. a_{4} \cdot (2^{128}-INPUT) \mod 2^{128}

等等..。

你看到这里有什么区别吗？让我们跳过零块的加密问题-它可以很容易解决，例如，如果我们将使用xoring在每一轮。当然，它只是带模的Lehmer随机数发生器，它是2的幂，这样的发生器有低比特的问题，但是在这种情况下，我不能用它来寻找微分。

Answer 1

你看到这里有什么区别吗？

是的，考虑一个微分，其中一边是值X，另一边是值2^{127}-X。

您的密码包括三个操作：

• 将当前值乘以奇数a_i模2^{128}

这个操作保留了概率1的微分；一边计算为a_i \cdot X，另一边计算为a_i \cdot (2^{127} - X) = a_i \cdot 2^{127} - a_i \cdot X = 2^{127} - a_i \cdot X。

• 否定当前值(作为第2-10轮的一部分完成)

此操作保留了概率为1的差分；这是因为-(2^{127} - X) = 2^{127} - (-X)

• 反转当前值中的位

这个操作保留了概率为0.5的微分，即，如果X的lsbit (等价地，2^{127} - X)是1。这是因为，当lsbit是1时，这种关系等价于X \oplus (2^{127}-X) = 2^{127}-2的关系。后一种关系在你反转比特的时候被保留下来，因此前一种也是一样的。

这给了你一个差分，概率2^{-10}，通过十轮密码。