线性变换函数
我需要编写一个函数，它接受 4 个字节作为输入，对其执行可逆线性变换，并将其返回为 4 个字节。
但是等等，还有更多：它还必须是分布式的，因此更改输入上的一个字节应该会影响所有 4 个输出字节。
问题：
- 如果我使用乘法，它在通过存储作为字节修改 255 后将不可逆（并且它需要保持为一个字节），
- 如果我使用加法，它就不能可逆和分配
一个解决方案： 我可以创建一个长度为 256^4 的字节数组并将其填充，在一对一映射中，这可以工作，但是存在问题：这意味着我必须搜索大小为 256^8 的图形，因为必须搜索对于每个值的免费数字（应注意分布性应是基于 64*64 字节数组的 sudo random）。 这个解决方案还有一个小问题（笑），即需要 8GB RAM，这使得这个解决方案毫无意义。
输入的域与输出的域相同，每个输入都有唯一的输出，换句话说：一对一的映射。 正如我在“一个解决方案”中指出的那样，这是很有可能的，并且当涉及较小的域（仅 256）时我已经使用了该方法。 事实是，随着数字变大，该方法变得异常低效，Delta 缺陷为 O(n^5)，omega 为 O(n^8)，具有类似的蹩脚性能在内存使用方面。
我想知道是否有一种聪明的方法可以做到这一点。 简而言之，它是域（4 字节或 256^4）的一对一映射。 哦，像 N+1 这样简单的东西不能使用，它必须关闭 64*64 的字节值数组，这些字节值是 sudo 随机的，但可重新创建以进行反向转换。
I need to write a function that takes 4 bytes as input, performs a reversible linear transformation on this, and returns it as 4 bytes.
But wait, there is more: it also has to be distributive, so changing one byte on the input should affect all 4 output bytes.
The issues:
- if I use multiplication it won't be reversible after it is modded 255 via the storage as a byte (and its needs to stay as a byte)
- if I use addition it can't be reversible and distributive
One solution:
I could create an array of bytes 256^4 long and fill it in, in a one to one mapping, this would work, but there are issues: this means I have to search a graph of size 256^8 due to having to search for free numbers for every value (should note distributivity should be sudo random based on a 64*64 array of byte). This solution also has the MINOR (lol) issue of needing 8GB of RAM, making this solution nonsense.
The domain of the input is the same as the domain of the output, every input has a unique output, in other words: a one to one mapping. As I noted on "one solution" this is very possible and I have used that method when a smaller domain (just 256) was in question. The fact is, as numbers get big that method becomes extraordinarily inefficient, the delta flaw was O(n^5) and omega was O(n^8) with similar crappiness in memory usage.
I was wondering if there was a clever way to do it. In a nutshell, it's a one to one mapping of domain (4 bytes or 256^4). Oh, and such simple things as N+1 can't be used, it has to be keyed off a 64*64 array of byte values that are sudo random but recreatable for reverse transformations.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
平衡块混合器正是您所寻找的。
谁知道？
Balanced Block Mixers are exactly what you're looking for.
Who knew?
编辑！ 如果您确实想要线性变换，这是不可能的。 这是数学解决方案：
您有四个字节，
a_1、a_2、a_3、a_4，我们将其视为向量a有 4 个分量，每个分量都是一个数字 mod 256。线性变换只是一个 4x4 矩阵M，其元素也是数字 mod 256。您有两个条件：Ma，我们可以推导出a（这意味着M是一个可逆矩阵）。a和a'在单个坐标上不同，则Ma和Ma'的每个坐标都必须不同。条件 (2) 有点棘手，但它的含义如下。 由于
M是一个线性变换，我们知道在左侧，从
a和a'在单个坐标上不同，a- < strong>a恰好有一个非零坐标。 在右侧，由于Ma和Ma'< /strong> 每个坐标都必须不同，Ma-Ma'< /code>每个坐标必须非零。因此，矩阵 M 必须将具有单个非零坐标的向量转换为具有所有非零坐标的向量。 因此，我们只需要
M的每个条目都是一个非零除数 mod 256，即奇数。回到条件(1)，
M可逆意味着什么？ 由于我们考虑的是 mod 256，我们只需要它的 行列式 是可逆的 mod 256； 也就是说，它的行列式必须是奇数。因此，您需要一个具有奇数项 mod 256 且行列式为奇数的 4x4 矩阵。 但这是不可能的！ 为什么？ 行列式是通过对各个条目的乘积求和来计算的。 对于 4x4 矩阵，有 4！ = 24 个不同的被加数，每一个都是奇数项的乘积，因此都是奇数。 但24个奇数之和是偶数，所以这样的矩阵的行列式一定是偶数！
Edit! It is not possible, if you indeed want a linear transformation. Here's the mathy solution:
You've got four bytes,
a_1, a_2, a_3, a_4, which we'll think of as a vectorawith 4 components, each of which is a number mod 256. A linear transformation is just a 4x4 matrixMwhose elements are also numbers mod 256. You have two conditions:Ma, we can deducea(this means thatMis an invertible matrix).aanda'differ in a single coordinate, thenMaandMa'must differ in every coordinate.Condition (2) is a little trickier, but here's what it means. Since
Mis a linear transformation, we know thatOn the left, since
aanda'differ in a single coordinate,a-ahas exactly one nonzero coordinate. On the right, sinceMaandMa'must differ in every coordinate,Ma-Ma'must have every coordinate nonzero.So the matrix
Mmust take a vector with a single nonzero coordinate to one with all nonzero coordinates. So we just need every entry ofMto be a non-zero-divisor mod 256, i.e., to be odd.Going back to condition (1), what does it mean for
Mto be invertible? Since we're considering it mod 256, we just need its determinant to be invertible mod 256; that is, its determinant must be odd.So you need a 4x4 matrix with odd entries mod 256 whose determinant is odd. But this is impossible! Why? The determinant is computed by summing various products of entries. For a 4x4 matrix, there are 4! = 24 different summands, and each one, being a product of odd entries, is odd. But the sum of 24 odd numbers is even, so the determinant of such a matrix must be even!
以下是我理解的您的要求：
B为字节空间。 您想要一个一对一（从而到）函数f: B^4 -> B^4。这是迄今为止我拥有的最简单的解决方案。 我已经有一段时间避免发帖了，因为我一直在尝试想出更好的解决方案，但我什么也没想到。
好吧，首先我们需要一个函数
g: B -> B接受一个字节并返回一个字节。 这个函数必须有两个性质：g(x)是可逆的，x^g(x)是可逆的。 [注：^ 是 XOR 运算符。] 任何这样的 g 都可以，但稍后我将定义一个特定的 g。给定这样的 ag，我们通过 f(a,b,c,d) = (a^b^c^d, g(a)^b^c^d, a^g(b)^c^d, a^b^g(c)^d)。 让我们检查一下您的要求：
最后，我们构造这样一个函数g。 令T为两位值的空间，并且h : T -> h : T -> h : T -> h : 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 也满足。
Here are your requirements as I understand them:
Bbe the space of bytes. You want a one-to-one (and thus onto) functionf: B^4 -> B^4.Here's the simplest solution I have thusfar. I have avoided posting for a while because I kept trying to come up with a better solution, but I haven't thought of anything.
Okay, first of all, we need a function
g: B -> Bwhich takes a single byte and returns a single byte. This function must have two properties: g(x) is reversible, and x^g(x) is reversible. [Note: ^ is the XOR operator.] Any such g will do, but I will define a specific one later.Given such a g, we define f by f(a,b,c,d) = (a^b^c^d, g(a)^b^c^d, a^g(b)^c^d, a^b^g(c)^d). Let's check your requirements:
Finally, we construct such a function g. Let T be the space of two-bit values, and
h : T -> Tthe function such that h(0) = 0, h(1) = 2, h(2) = 3, and h(3) = 1. This function has the two desired properties of g, namely h(x) is reversible and so is x^h(x). (For the latter, check that 0^h(0) = 0, 1^h(1) = 3, 2^h(2) = 1, and 3^h(3) = 2.) So, finally, to compute g(x), split x into four groups of two bits, and take h of each quarter separately. Because h satisfies the two desired properties, and there's no interaction between the quarters, so does g.我不确定我是否理解你的问题，但我想我明白你想要做什么。
按位异或是你的朋友。
如果 R = A XOR B，则 R XOR A 给出 B，R XOR B 给出 A。 所以这是一个可逆的转换，假设您知道结果和输入之一。
I'm not sure I understand your question, but I think I get what you're trying to do.
Bitwise Exclusive Or is your friend.
If R = A XOR B, R XOR A gives B and R XOR B gives A back. So it's a reversible transformation, assuming you know the result and one of the inputs.
假设我明白你想要做什么，我认为任何 块密码 都可以完成这项工作.
分组密码采用比特块（例如 128）并将它们可逆地映射到具有相同大小的不同块。
此外，如果您使用 OFB 模式，您可以使用分组密码来生成无限流伪随机位。 将这些位与位流进行异或将为您提供任意长度数据的转换。
Assuming I understood what you're trying to do, I think any block cipher will do the job.
A block cipher takes a block of bits (say 128) and maps them reversibly to a different block with the same size.
Moreover, if you're using OFB mode you can use a block cipher to generate an infinite stream of pseudo-random bits. XORing these bits with your stream of bits will give you a transformation for any length of data.
我将抛出一个可能行得通也可能行不通的想法。
使用一组具有奇素数系数的 mod 256 线性函数。
例如：
如果我没记错中国剩余定理，并且我已经很多年没有看过它了，那么 ax 可以从 bx 中恢复。 甚至可能有一种快速的方法来做到这一点。
我相信，这是一个可逆的转变。 它是线性的，即 af(x) mod 256 = f(ax) 和 f(x) + f(y) mod 256 = f(x + y)。 显然，更改一个输入字节将更改所有输出字节。
所以，去查一下中国剩余定理，看看这是否有效。
I'm going to throw out an idea that may or may not work.
Use a set of linear functions mod 256, with odd prime coefficients.
For example:
If I remember the Chinese Remainder Theorem correctly, and I haven't looked at it in years, the ax are recoverable from the bx. There may even be a quick way to do it.
This is, I believe, a reversible transformation. It's linear, in that af(x) mod 256 = f(ax) and f(x) + f(y) mod 256 = f(x + y). Clearly, changing one input byte will change all the output bytes.
So, go look up the Chinese Remainder Theorem and see if this works.
“线性”变换是什么意思？
O(n)，或者函数 f 且 f(c * (a+b)) = c * f(a) + c * f(b)？
一个简单的方法是旋转位移（不确定这是否满足上述数学定义）。 它是可逆的，每个字节都可以改变。 但这样并不强制每个字节都被改变。
编辑：我的解决方案是这样的：
它将是可逆的（只需从另一个字节中减去第一个字节，然后对第一个字节进行 XOR 3 个结果字节），并且一位的更改将更改每个字节（因为 b0 是结果所有字节并影响所有其他字节）。
What you mean by "linear" transformation?
O(n), or a function f with f(c * (a+b)) = c * f(a) + c * f(b)?
An easy approach would be a rotating bitshift (not sure if this fullfils the above math definition). Its reversible and every byte can be changed. But with this it does not enforce that every byte is changed.
EDIT: My solution would be this:
It would be reversible (just subtract the first byte from the other, and then XOR the 3 resulting bytes on the first), and a change in one bit would change every byte (as b0 is the result of all bytes and impacts all others).
将所有字节粘贴到 32 位数字中，然后执行 shl 或 shr（左移或右移）1、2 或 3。 然后将其拆分回字节（可以使用变体记录）。 这会将每个字节中的位移动到相邻字节中。
这里有很多好的建议（异或等），我建议将它们结合起来。
Stick all of the bytes into 32-bit number and then do a shl or shr (shift left or shift right) by one, two or three. Then split it back into bytes (could use a variant record). This will move bits from each byte into the adjacent byte.
There are a number of good suggestions here (XOR, etc.) I would suggest combining them.
您可以重新映射这些位。 让我们使用 ii 表示输入，使用 oo 表示输出：
它不是线性的，但显着更改输入中的一个字节将影响输出中的所有字节。 我不认为你可以进行可逆的转换，例如更改输入中的一位会影响输出的所有四个字节，但我没有证据。
You could remap the bits. Let's use ii for input and oo for output:
It's not linear, but significantly changing one byte in the input will affect all the bytes in the output. I don't think you can have a reversible transformation such as changing one bit in the input will affect all four bytes of the output, but I don't have a proof.