Symmetric Bijective Algorithm for Integers

Question

I need an algorithm that can do a one-to-one mapping (ie. no collision) of a 32-bit signed integer onto another 32-bit signed integer.

My real concern is enough entropy so that the output of the function appears to be random. Basically I am looking for a cipher similar to XOR Cipher but that can generate more arbitrary-looking outputs. Security is not my real concern, although obscurity is.

Edit for clarification purpose:

1. The algorithm must be symetric, so that I can reverse the operation without a keypair.
2. The algorithm must be bijective, every 32-bit input number must generate a 32-bit unique number.
3. The output of the function must be obscure enough, adding only one to the input should result big effect on the output.

Example expected result:

F(100) = 98456
F(101) = -758
F(102) = 10875498
F(103) = 986541
F(104) = 945451245
F(105) = -488554

Just like MD5, changing one thing may change lots of things.

I am looking for a mathmetical function, so manually mapping integers is not a solution for me. For those who are asking, algorithm speed is not very important.

Answer 1

The following paper gives you 4 or 5 mapping examples, giving you functions rather than building mapped sets: www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf

Answer 2

Here is my simple idea: You can move around the bits of the number, as PeterK proposed, but you can have a different permutation of bits for each number, and still be able to decipher it.

The cipher goes like this: Treat the input number as an array of bits I[0..31], and the output as O[0..31]. Prepare an array K[0..63] of 64 randomly generated numbers. This will be your key. Take the bit of input number from position determined by the first random number (I[K[0] mod 32]) and place it at the beginning of your result (O[0]). Now to decide which bit to place at O[1], use the previously used bit. If it is 0, use K[1] to generate position in I from which to take, it it is 1, use K[2] (which simply means skip one random number).

Now this will not work well, as you may take the same bit twice. In order to avoid it, renumber the bits after each iteration, omitting the used bits. To generate the position from which to take O[1] use I[K[p] mod 31], where p is 1 or 2, depending on the bit O[0], as there are 31 bits left, numbered from 0 to 30.

To illustrate this, I'll give an example:

We have a 4-bit number, and 8 random numbers: 25, 5, 28, 19, 14, 20, 0, 18.

I: 0111    O: ____
    _

25 mod 4 = 1, so we'll take bit whose position is 1 (counting from 0)

I: 0_11    O: 1___
     _

We've just taken a bit of value 1, so we skip one random number and use 28. There are 3 bits left, so to count position we take 28 mod 3 = 1. We take the first (counting from 0) of the remaining bits:

I: 0__1    O: 11__
   _

Again we skip one number, and take 14. 14 mod 2 = 0, so we take the 0th bit:

I: ___1    O: 110_
      _

Now it doesn't matter, but the previous bit was 0, so we take 20. 20 mod 1 = 0:

I: ____    O: 1101

And this is it.

Deciphering such a number is easy, one just has to do the same things. The position at which to place the first bit of the code is known from the key, the next positions are determined by the previously inserted bits.

This obviously has all the disadvantages of anything which just moves the bits around (for example 0 becomes 0, and MAXINT becomes MAXINT), but is seems harder to find how someone has encrypted the number without knowing the key, which has to be secret.

Answer 3

Use any 32-bit block cipher! By definition, a block cipher maps every possible input value in its range to a unique output value, in a reversible fashion, and by design, it's difficult to determine what any given value will map to without the key. Simply pick a key, keep it secret if security or obscurity is important, and use the cipher as your transformation.

For an extension of this idea to non-power-of-2 ranges, see my post on Secure Permutations with Block Ciphers.

Addressing your specific concerns:

1. The algorithm is indeed symmetric. I'm not sure what you mean by "reverse the operation without a keypair". If you don't want to use a key, hardcode a randomly generated one and consider it part of the algorithm.
2. Yup - by definition, a block cipher is bijective.
3. Yup. It wouldn't be a good cipher if that were not the case.

Answer 4

If you don't want to use proper cryptographic algorithms (perhaps for performance and complexity reasons) you can instead use a simpler cipher like the Vigenère cipher. This cipher was actually described as le chiffre indéchiffrable (French for 'the unbreakable cipher').

Here is a simple C# implementation that shifts values based on a corresponding key value:

void Main()
{
  var clearText = Enumerable.Range(0, 10);
  var key = new[] { 10, 20, Int32.MaxValue };
  var cipherText = Encode(clearText, key);
  var clearText2 = Decode(cipherText, key);
}

IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
  return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}

IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
  return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}

This algorithm does not create a big shift in the output when the input is changed slightly. However, you can use another bijective operation instead of addition to achieve that.

Answer 5

Apart from generating random lookup-tables, you can use a combination of functions:

• XOR
• symmetric bit permutation (for example shift 16 bits, or flip 0-31 to 31-0, or flip 0-3 to 3-0, 4-7 to 7-4, ...)
• more?