Symmetric Bijective Algorithm for Integers

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. 是的。It wouldn't be a good cipher if that were not the case.

我将尝试在一个更简单的例子上解释我的解决方案,然后可以很容易地扩展到您的大例子中。

假设我有一个4位的数字。有16个不同的值。把它看成是一个四维立方体: 4 dimensional cube http://www.ams.org/featurecolumn/images/january2009/klee8.jpg .

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 不同顺序 尺寸的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.)

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

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

• 异或
• 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, ...)
• 更多?

If your goal is simply to get a seemingly random permutation of numbers of a 粗略地 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).

我选择A和B相当随意,我只是确定它们大约是P的一半。

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.

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.

如此

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

W00它工作!

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

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〕 使用 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:

我们有一个4位数字和8个随机数:25、5、28、19、14、20、0、18。

I: 0111    O: ____
    _

25 mod 4=1,所以我们取位置为1的位(从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

就是这样。

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.

如果你不想使用适当的密码算法(也许是出于性能和复杂性的原因),你可以使用一个更简单的密码,比如 Vigenère cipher . This cipher was actually described as L.CHIFRE工业株式会社 (法语为“牢不可破的密码”)。

这里是一个简单的C实现,它根据相应的键值移位值:

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]));
}

当输入稍微改变时,该算法不会在输出中产生大的移位。但是,您可以使用另一个双射操作而不是加法来实现这一点。

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 下面的评论:如果你只对纸旋转卡片,那么方法和你抱怨的一样简单。但是,当您翻转卡片时,映射不等于 (x+m) mod MAXINT 对于任何 m . 例如,如果你离开卡不旋转,并将它围绕直径0翻转(在时钟表面的顶部),那么1被映射到-1, 2到-2,等等。 (x+m) mod MAXINT corresponds to rotations of the card only.

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 你结束了 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.