0

I am performing an operation where a function F(k,x) takes two 64bit values and returns the product of their decimal numbers. For example:

F(123,231) = 123 x 231 = 28413

The number is then converted into binary and the least significant bits are extracted. i.e. if 28413 = 0110111011111101 then we take 11111101, which is 253 in decimal.

This function is part of a Feistel network in security. When performing a type of attack (chosen plaintext) we get to the point where we have 253 and 231, but need to figure out 123.

Is there any way that is possible?

4

2 回答 2

0

你的功能正在做F(k,x) = k*x mod 256。

你的问题已经给出F(k,x)，x你能找到k吗？

当x是奇数时，有 2^56 个解，所有解都有k = x^-1 * F(k,x) mod 256. 也就是说，您计算 的倒数x mod 256，并且每个可能的解决方案都是通过将 256 的倍数F(k,x)与该值的乘积相加得出的。

何时x是偶数，您无法计算逆，但您仍然可以使用类似的技巧确定解决方案。您需要首先计算除以 的二 (2s) 的数量x，假设它是t二，然后2^t从x和中除出256，然后从那里解决问题。即k = (x/2^t)^-1 * F(k,x) mod (256/2^t)。

通常在密码设计中使用乘法是危险的，特别是由于选择明文攻击，因为攻击者可以使事物消失以简化他的攻击。你可以在我的博客上找到破解密码的例子（参见对混沌散列函数和多素数的攻击）。

于 2015-12-14T23:47:49.563 回答
-1

不。

通过丢弃最高有效位，该操作呈现为单向的。 为了恢复 123，您必须尽一切可能强制该功能，直到结果是您想要的值。

即对 x 的值运行 F(x,231)，直到 F 的结果为 253。

也就是说，知道两个输入之一和输出使得蛮力相对容易。这将取决于 x 的有效值的数量（例如，它总是一个 3 位数字吗？总是素数？总是奇数？）

可能还有其他一些捷径，具体取决于乘以 231 得到的模式，但该数字的任何给定值都会有不同的模式。例如，如果它是 9 而不是 231，您就会知道数字的总和总和为 9。

于 2015-12-14T18:06:44.140 回答