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 symmetric, 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 mathematical function, so manually mapping integers is not a solution for me. For those who are asking, algorithm speed is not very important.

Talie

How fast do you want your algorithm to run ? – Doom

@Scorpi0 Encoding does not matter, decoding should be faster, generally a speed close to public key cryptography acceptable. – Talie

@eyazici: If the algorithm is symmetric, encoding and decoding are the same. Now you say decoding should be faster. Do you really need a symmetric algorithm? – Asthenosphere

@Scorpi0: Algorithm must be symetric so that I can reverse the process. I give PKI speed as a measure. – Talie

@eyaici: The process is reversible if the encoding function is bijective. But do the encoding and decoding function have to be the same function? That's how I would understand the term "symetric". If you mean something else by "symetric algorithm", please clarify. – Asthenosphere

@nikie: I mean the key used for encoding should be same for decoding by saying "symetric", I do not want to deal with keypairs. – Talie

Duplicate or near-duplicate at sci-comp SE has a nice answer: Random access random permutations. Wikipedia has articles on pseudorandom permutations and permutation polynomials which have some other ideas. If you're interested in obscurity and "looking shuffled" than security, – Regality

Answer 1

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.

Thirtieth

Yes the algorithm is symetric, I mean I do not want a solution that uses asymetric (if any), asymetric ciphers use different keys for encoding and decoding that are together named "keypair". I found a 32-bit block cipher (perhaps the only one on the web) with the help of your suggestions and I am poritng it another language now, it seems good enough: qualcomm.com.au/PublicationsDocs/skip32.c – Talie

Ah, understood. As my post indicates, it's possible to shorten existing ciphers; TEA is amenable to being modified for a 32 bit blocklength. I wouldn't rely on such a modification for cryptographic security, but you don't appear to be concerned about that. :) – Thirtieth

Of course, a rainbow table for a 32-bit key is only 16 GB in size and can be generated at first run, so this is probably not going to ever be cryptographically secure on modern hardware. – Zootechnics

Some possible ciphers for this in no particular order: Hasty Pudding cipher, GDES, Simon, Speck, RC5. There are probably many more. – Chromatography

Answer 2

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

Comptroller

Answer 3

If your goal is simply to get a seemingly random permutation of numbers of a roughly defined size, then there is another possible way: reduce the set of numbers to a prime number.

Then you can use a mapping of the form

f(i) = (i * a + b) % p

and if p is indeed a prime, this will be a bijection for all a != 0 and all b. It will look fairly random for larger a and b.

For example, in my case for which I stumbled on this question, I used 1073741789 as a prime for the range of numbers smaller than 1 << 30. That makes me lose only 35 numbers, which is fine in my case.

My encoding is then

((n + 173741789) * 507371178) % 1073741789

and the decoding is

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Note that 507371178 * 233233408 % 1073741789 == 1, so those two numbers are inverse the field of numbers modulo 1073741789 (you can figure out inverse numbers in such fields with the extended euclidean algorithm).

I chose a and b fairly arbitrarily, I merely made sure they are roughly half the size of p.

Shortening

Don't "reduce the set of numbers to a prime number", so having to cut numbers out of the set, instead increase the set of numbers to a prime number! This messes up your bijection in 2 ways: some i in your original range have image f(i)=j outside the range, whereas some k in your original range have pre-image f(j)=k where j is outside the range... but these 2 problems exactly cancel out! Just iterate f until you are within the desired range. In my example, f(f(i))=k so we can ignore j entirely. We may need to do f(f(f(f(i)))) but we'll get back in range eventually! – Regality

That's because permutations have cycles so it's guaranteed we can just ride along a cycle until back in the original range (worst case, we get back to i). This stitches together those i whose image goes out of range, with those k whose preimage was out of range. This is a similar idea to making the number up to a power of 2 so you can apply (repeatedly, if needed) a block cipher - see this sci-comp SE post – Regality

@Regality Interesting, thanks for sharing. – Shortening

Answer 4

I will try to explain my solution to this on a much simpler example, which then can be easily extended for your large one.

Say i have a 4 bit number. There are 16 distinct values. Look at it as if it was a four dimensional cube:
_{(source: ams.org)}
.

Every vertex represents one of those numbers, every bit represents one dimension. So its basicaly XYZW, where each of the dimensions can have only values 0 or 1. Now imagine you use a different order of dimensions. For example XZYW. Each of the vertices now changed its number!

You can do this for any number of dimensions, just permute those dimensions. If security is not your concern this could be a nice fast solution for you. On the other hand, i dont know if the output will be "obscure" enough for your needs and certainly after a large amount of mapping done, the mapping can be reversed (which may be an advantage or disadvantage, depending on your needs.)

Viridi

Is this not equivalent to simply switching around the individual bits of the number to a given pattern? Hypercube is cool, regardless. – Oof

Yes, it is. The hypercube example was added just for explanation since i thought it would be nice to actually understand what swapping bits "does" in multidimensional space. – Viridi

I see. I've never really seen multidimensional been used as an analogy for a 32 bit integer before, but it's interesting indeed. – Oof

Swapping bits around in an n-bit value only gives n! possibilitues. What you want is a real permutation, which gives (2^n)! possibilities. – Slipcover

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?

Monster

As I wrote in my question, I need arbitrary-looking outputs. I have already mentioned about XOR-way, haven't I? – Talie

Yes of course, but I think combining XOR with bit permutation would look relatively arbitrary. Whatever that means in your case. – Monster

Yes, trying bit permutations would solve my problem, but I am looking for a tried one that is proved instead of implenting it myself, that's why I am asking here. – Talie

Ah. In that case, I would look into block ciphers as mentioned by Nick Johnson. A bit harder to follow, but tried and true. – Monster

Answer 6

Can you use a random generated lookup-table? As long as the random numbers in the table are unique, you get a bijective mapping. It's not symmetric, though.

One 16 GB lookup-table for all 32 bit values is probably not practical, but you could use two separate 16-bit lookup tables for the high-word and the low word.

PS: I think you can generate a symmetric bijective lookup table, if that's important. The algorithm would start with an empty LUT:

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Pick the first element, assign it a random mapping. To make the mapping symmetric, assign the inverse, too:

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Pick the next number, again assign a random mapping, but pick a number that's not been assigned yet. (i.e. in this case, don't pick 1 or 3). Repeat until the LUT is complete. This should generate a random bijective symmetric mapping.

Asthenosphere

Using a lookup table is a certain solution, however I need a mathematical solution. – Talie

What do you mean by "mathematical solution"? Use a PRNG with a fixed seed (e.g. the key) and you have a mathematical solution. – Asthenosphere

I mean a more clever solution, mapping 2^32 integers is neither cost effective nor scaleable. Basically I was looking for a 32-bit block cipher (which is rare in case of 32-bit) and I have found it. – Talie

Answer 7

Take a number, multiplies by 9, inverse digits, divide by 9.

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

Should be obscure enough !!

Edit : it is not a bijection for 0 ending integer

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

You can always add a specific rule like : Take a number, divide by 10 x times, multiplies by 9, inverse digits, divide by 9, multiples by 10^x.

And so

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

W00t it works !

Edit 2 : For more obscurness, you can add an arbitrary number, and substract at the end.

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129

Doom

How do you deal with overflows? Multiplying a large 32bit number by 9 can result in a number > 2^32 – Asthenosphere

yes, little problem on the overflows, 2147483647 <> 3647263599. The algorithm guaranteed a bijection on the set 10^N, not 2^N, that is a tiny detail :p – Doom

As I write above, I am looking for a cipher that can generate arbitrary-looking outputs, but your solution generates similar outputs for sequential numbers: 123=>779, 124=>679, 125=>579... Obscurity is a must for me, but is not the only concern. I do not use simple XOR cipher or any other symetric cipher for this reason, which can generate much better results (in terms of obscurity) – Talie

I'm thinking, maybe running this algorithm twice, or even more, 10 times, on the inverted number, and the results could be fun. I will try to code something ! – Doom

Answer 8

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.

Colombes

Answer 9

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.

Chiliad

Answer 10

Draw a large circle on a large sheet of paper. Write all the integers from 0 to MAXINT clockwise from the top of the circle, equally spaced. Write all the integers from 0 to MININT anti-clockwise, equally spaced again. Observe that MININT is next to MAXINT at the bottom of the circle. Now make a duplicate of this figure on both sides of a piece of stiff card. Pin the stiff card to the circle through the centres of both. Pick an angle of rotation, any angle you like. Now you have a 1-1 mapping which meets some of your requirements, but is probably not obscure enough. Unpin the card, flip it around a diameter, any diameter. Repeat these steps (in any order) until you have a bijection you are happy with.

If you have been following closely it shouldn't be difficult to program this in your preferred language.

For Clarification following the comment: If you only rotate the card against the paper then the method is as simple as you complain. However, when you flip the card over the mapping is not equivalent to (x+m) mod MAXINT for any m. For example, if you leave the card unrotated and flip it around the diameter through 0 (which is at the top of the clock face) then 1 is mapped to -1, 2 to -2, and so forth. (x+m) mod MAXINT corresponds to rotations of the card only.

Andria

As far as I understand you mention about a function which can be defined as f(x)=(x+m) mod MAXINT where 0<m<MAXINT . However it has a very simple logic and the outputs are easily predictable. As I mentioned in my question I do not use XOR cipher which can generate much better outputs with a specially selected key. – Talie

Answer 11

Split the number in two (16 most significant bits and 16 least significant bits) and consider the bits in the two 16-bit results as cards in two decks. Mix the decks forcing one into the other.

So if your initial number is b31,b30,...,b1,b0 you end up with b15,b31,b14,b30,...,b1,b17,b0,b16. It's fast and quick to implement, as is the inverse.

If you look at the decimal representation of the results, the series looks pretty obscure.

You can manually map 0 -> maxvalue and maxvalue -> 0 to avoid them mapping onto themselves.

Broadminded