delphi - 线性变换函数

Question

我需要编写一个以 4 个字节作为输入的函数，对此执行可逆线性变换，并将其作为 4 个字节返回。

但是等等，还有更多：它还必须是可分配的，因此在输入上更改一个字节应该会影响所有 4 个输出字节。

问题：

• 如果我使用乘法，它在通过存储作为字节修改 255 后将不可逆（并且它需要保持为字节）
• 如果我使用加法，它就不能可逆和分配

一种解决方案：我可以创建一个长度为 256^4 的字节数组并以一对一的映射方式填充它，这会起作用，但是存在问题：这意味着我必须搜索大小为 256^8 的图形，因为必须为每个值搜索免费数字（应注意分配性应该是基于 64*64 字节数组的 sudo 随机数）。该解决方案还存在需要 8GB RAM 的次要 (lol) 问题，这使得该解决方案毫无意义。

输入的域与输出的域相同，每个输入都有一个唯一的输出，换句话说：一对一映射。正如我在“一个解决方案”中指出的那样，这是很有可能的，当有一个较小的域（只有 256 个）存在问题时，我使用了该方法。事实是，随着数字变大，该方法变得异常低效，delta 缺陷O(n^5)和 omegaO(n^8)在内存使用方面也有类似的缺陷。

我想知道是否有一个聪明的方法来做到这一点。简而言之，它是域的一对一映射（4 字节或 256^4）。哦，像 N+1 这样简单的东西不能使用，它必须是一个 64*64 字节值数组，这些字节值是 sudo 随机的，但可以重新创建以进行反向转换。

Answer 1

平衡块混合器正是您正在寻找的。

谁知道？

Answer 2

编辑！如果您确实想要线性变换，这是不可能的。这是数学解决方案：

您有四个字节，a_1, a_2, a_3, a_4我们将其视为a具有 4 个分量的向量，每个分量都是一个模 256 的数字。线性变换只是一个 4x4 矩阵M，其元素也是模 256 的数字。您有两个条件：

1. 从Ma，我们可以推断a（这意味着它M是一个可逆矩阵）。
2. 如果a和a'在单个坐标上不同，那么Ma和Ma'必须在每个坐标上都不同。

条件 (2) 有点棘手，但这就是它的含义。由于M是线性变换，我们知道

M( a- a) = Ma-Ma'

在左边，因为a和a'在单个坐标上不同，所以a-a恰好有一个非零坐标。在右边，因为Ma和Ma'必须在每个坐标上不同，Ma-Ma'必须使每个坐标都非零。

因此，矩阵M必须将具有单个非零坐标的向量变为具有所有非零坐标的向量。所以我们只需要 的每个条目M都是一个非零除数模 256，即奇数。

回到条件（1），M可逆是什么意思？由于我们正在考虑它 mod 256，我们只需要它的行列式是可逆 mod 256；也就是说，它的行列式必须是奇数。

因此，您需要一个 4x4 矩阵，其中包含奇数项 mod 256，其行列式是奇数。但这是不可能的！为什么？通过对条目的各种乘积求和来计算行列式。对于 4x4 矩阵，有 4 个！= 24 个不同的加数，每个加数都是奇数项的乘积，都是奇数。但是24个奇数的和是偶数，所以这样的矩阵的行列式一定是偶数！

Answer 3

我不确定我是否理解你的问题，但我想我明白你想要做什么。

Bitwise Exclusive Or 是您的朋友。

如果 R = A XOR B，则 R XOR A 给出 B 并且 R XOR B 返回 A。所以这是一个可逆的转换，假设你知道结果和输入之一。

Answer 4

据我了解，这是您的要求：

1. 设B为字节空间。你想要一个一对一（因此也就是）函数f: B^4 -> B^4。
2. 如果您更改任何单个输入字节，则所有输出字节都会更改。

这是我迄今为止最简单的解决方案。我有一段时间避免发帖，因为我一直在尝试提出更好的解决方案，但我没有想到任何事情。

好的，首先，我们需要一个g: B -> B接收单个字节并返回单个字节的函数。这个函数必须有两个性质：g(x) 是可逆的，x^g(x) 是可逆的。[注意：^ 是 XOR 运算符。] 任何这样的 g 都可以，但我稍后会定义一个特定的。

给定这样的 ag，我们定义 f 为 f(a,b,c,d) = (a^b^c^d, g(a)^b^c^d, a^g(b)^c^d, a^b^g(c)^d)。让我们检查您的要求：

1. 可逆：是的。如果我们对前两个输出字节进行异或，我们得到 a^g(a)，但是通过 g 的第二个属性，我们可以恢复 a。对于 b 和 c 也是如此。在得到 a、b 和 c 后，我们可以通过用 (a^b^c) 对第一个字节进行异或来恢复 d。
2. 分配：是的。假设 b、c 和 d 是固定的。然后函数采用 f(a,b,c,d) = (a^const, g(a)^const, a^const, a^const) 的形式。如果 a 发生变化，那么 a^const; 同样，如果 a 改变，g(a) 也会改变，g(a)^const 也会改变。（如果 a 发生，g(a) 发生变化的事实是 g 的第一个属性；如果没有，则 g(x) 将不可逆。）b 和 c 也是如此。对于 d，它更容易，因为 f(a,b,c,d) = (d^const, d^const, d^const, d^const) 所以如果 d 改变，每个字节都会改变。

最后，我们构造了这样一个函数g。令 T 为两位值的空间，h : T -> T函数满足 h(0) = 0、h(1) = 2、h(2) = 3 和 h(3) = 1。该函数有两个g 的期望性质，即 h(x) 是可逆的，x^h(x) 也是可逆的。（对于后者，检查 0^h(0) = 0、1^h(1) = 3、2^h(2) = 1 和 3^h(3) = 2。）所以，最后，计算 g(x)，将 x 分成四组，每组两位，分别取每个四分之一的 h。因为 h 满足两个期望的性质，并且四等分之间没有相互作用，所以 g 也是。

Answer 5

假设我了解您要做什么，我认为任何分组密码都可以完成这项工作。
块密码采用一个比特块（比如 128）并将它们可逆地映射到具有相同大小的不同块。

此外，如果您使用的是OFB 模式，您可以使用分组密码来生成无限的伪随机位流。将这些位与您的位流进行异或运算将为您提供任何长度数据的转换。

Answer 6

您所说的“线性”转换是什么意思？O(n)，或者一个函数 f 与 f(c * (a+b)) = c * f(a) + c * f(b)？

一种简单的方法是旋转位移（不确定这是否满足上述数学定义）。它是可逆的，每个字节都可以更改。但是有了这个，它并不强制每个字节都被改变。

编辑：我的解决方案是这样的：

b0 = (a0 ^ a1 ^ a2 ^ a3)
b1 = a1 + b0 ( mod 256)
b2 = a2 + b0 ( mod 256)
b3 = a3 + b0 ( mod 256)

它是可逆的（只需从另一个字节中减去第一个字节，然后在第一个字节上对 3 个结果字节进行异或运算），并且一个位的变化会改变每个字节（因为 b0 是所有字节的结果并影响所有其他字节） .

Answer 7

我将抛出一个可能行不通的想法。

使用一组线性函数 mod 256，具有奇数素数系数。

例如：

b0 = 3 * a0 + 5 * a1 + 7 * a2 + 11 * a3;
b1 = 13 * a0 + 17 * a1 + 19 * a2 + 23 * a3;

如果我正确地记住了中国剩余定理，并且我多年没有看过它，那么斧头可以从 bx 中恢复。甚至可能有一种快速的方法来做到这一点。

我相信这是一个可逆的转变。它是线性的，因为 af(x) mod 256 = f(ax) 和 f(x) + f(y) mod 256 = f(x + y)。显然，改变一个输入字节将改变所有输出字节。

所以，去查一下中国剩余定理，看看这是否有效。

Answer 8

将所有字节粘贴到 32 位数字中，然后执行 shl 或 shr（左移或右移）一、二或三。然后将其拆分回字节（可以使用变体记录）。这会将位从每个字节移动到相邻字节。

这里有很多很好的建议（XOR 等），我建议将它们结合起来。

Answer 9

您可以重新映射这些位。让我们使用 ii 作为输入，使用 oo 作为输出：

oo[0] = (ii[0] & 0xC0) | (ii[1] & 0x30) | (ii[2] & 0x0C) | (ii[3] | 0x03)
oo[1] = (ii[0] & 0x30) | (ii[1] & 0x0C) | (ii[2] & 0x03) | (ii[3] | 0xC0)
oo[2] = (ii[0] & 0x0C) | (ii[1] & 0x03) | (ii[2] & 0xC0) | (ii[3] | 0x30)
oo[3] = (ii[0] & 0x03) | (ii[1] & 0xC0) | (ii[2] & 0x30) | (ii[3] | 0x0C)

它不是线性的，但是显着改变输入中的一个字节会影响输出中的所有字节。我不认为您可以进行可逆转换，例如更改输入中的一位会影响输出的所有四个字节，但我没有证据。