views:

539

answers:

9

Problem: 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.

Any good ideas? I don't need code, just an idea.

EDIT: OK, I'm sorry for my description; I'll try to make it a bit clearer. 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.

I hope I made some sense.

+2  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.

Andrei Krotkov
And doesn't fulfil the requirement of changing all four bytes if only one is touched.
David Thornley
+4  A: 

Balanced Block Mixers are exactly what you're looking for.

Who knew?

Allain Lalonde
For the two-bit version, o1 = i1, and o2 = i1 xor i2. That at least is straightforward.
David Thornley
@Allain Lalonde: No, the original problem is possible, even though the 2 groups of 1 bit is not. (2 groups of 2 bits is possible.) @David Thornley: o1 doesn't change if i2 does, violating the "distributive" property of the OP.
A. Rex
Simple proof I just thought of: if i1 changes both o1 and o2, and i2 changes both o1 and o2, then changing i1 and i2 both leaves o1 and o2 the same, and changing i1 has the exact same effect as changing i2.
David Thornley
A: 

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:

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

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).

flolo
Re. your edit: Good idea, but again it doesn't work. f(0,0,0,0) = (0,0,0,0) and f(0,0,0,128) = (128,128,128,0). Notice that the last byte doesn't change.
A. Rex
+1  A: 

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.

shoosh
A: 

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:

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

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.

David Thornley
This is a good idea, but won't work. The output bytes b0, etc., are all even. Thus you're mapping into a smaller range than the domain, and the function isn't one-to-one.
A. Rex
Why would they all be even? The rightmost bits (given that the multipliers are odd) will be 1 if there are an odd number of rightmost 1s on the input, and even otherwise.
David Thornley
Umm, yeah, sorry. If either all of the inputs are even, or all are odd, the outputs will all be even. Once again, except correctly this time, you have more inputs than outputs.
A. Rex
A: 

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.

Jim McKeeth
This wouldn't work for the inputs 0 and 1 since no matter how much you shift 3 of the bytes will always have 0s.
Allain Lalonde
Which is why I would suggest combining it with XOR or ROT13 or something. I guess it really comes down to your objective.
Jim McKeeth
A: 

You could remap the bits. Let's use ii for input and oo for output:

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)

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.

florin
+2  A: 

Here are your requirements as I understand them:

  1. Let B be the space of bytes. You want a one-to-one (and thus onto) function f: B^4 -> B^4.
  2. If you change any single input byte, then all output bytes change.

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 -> B which 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:

  1. Reversible: yes. If we XOR the first two output bytes, we get a^g(a), but by the second property of g, we can recover a. Similarly for the b and c. We can recover d after getting a,b, and c by XORing the first byte with (a^b^c).
  2. Distributive: yes. Suppose b,c, and d are fixed. Then the function takes the form f(a,b,c,d) = (a^const, g(a)^const, a^const, a^const). If a changes, then so will a^const; similarly, if a changes, so will g(a), and thus so will g(a)^const. (The fact that g(a) changes if a does is by the first property of g; if it didn't then g(x) wouldn't be reversible.) The same holds for b and c. For d, it's even easier because then f(a,b,c,d) = (d^const, d^const, d^const, d^const) so if d changes, every byte changes.

Finally, we construct such a function g. Let T be the space of two-bit values, and h : T -> T the 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.

A. Rex
+4  A: 

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 vector a with 4 components, each of which is a number mod 256. A linear transformation is just a 4x4 matrix M whose elements are also numbers mod 256. You have two conditions:

  1. From Ma, we can deduce a (this means that M is an invertible matrix).
  2. If a and a' differ in a single coordinate, then Ma and Ma' must differ in every coordinate.

Condition (2) is a little trickier, but here's what it means. Since M is a linear transformation, we know that

M(a - a) = Ma - Ma'

On the left, since a and a' differ in a single coordinate, a - a has exactly one nonzero coordinate. On the right, since Ma and Ma' must differ in every coordinate, Ma - Ma' must have every coordinate nonzero.

So the matrix M must take a vector with a single nonzero coordinate to one with all nonzero coordinates. So we just need every entry of M to be a non-zero-divisor mod 256, i.e., to be odd.

Going back to condition (1), what does it mean for M to 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!

Jesse Beder
Your analysis concluding that "every entry of M [must] be nonzero" is incorrect. For example, if some entry of M is 128 and the input byte is even, the output will be 0. We actually need every entry of M to be *odd*. But if every entry of M is odd, its determinant is even; see @David Thornley above.
A. Rex
Yes, you're right. Thanks.
Jesse Beder
Thanks for making the change. Your conclusion is correct now (any 4x4 matrix, all entries and determinant odd, should work). Unfortunately, *there are no such matrices*. For example, if you use the Leibniz formula for determinants, you have 24 odd numbers -- which sums to an even number.
A. Rex
Yeah, I realized that - check out the edit.
Jesse Beder
Great! Sorry, I responded the second time after reloading to see one edit but not the next.
A. Rex
Incidentally, this all assumes that bytes correspond to numbers modulo 256. If they correspond to elements of the finite field of order 256, then @Allain Lalonde's solution is a linear transformation. The difference is that F_256 has no zero-divisors (being a field and all ...).
A. Rex