Bijective “Integer <-> String” function

问题:

Here's a problem I'm trying to create the best solution for. I have a finite set of non-negative integers in the range of [0...N]. I need to be able to represent each number in this set as a string and be able to convert such string backwards to original number. So this should be a bijective function.

Additional requirements are:

1. String representation of a number should obfuscate original number at least to some degree. So primitive solution like f(x) = x.toString() will not work.
2. String length is important: the less the better.
3. If one knows the string representation of K, I would like it to be non-trivial (to some degree) to guess the string representation of K+1.

For p.1 & p.2 the obvious solution is to use something like Base64 (or whatever BaseXXX to fit all the values) notation. But can we fit into p.3 with minimal additional effort? Common sense tells me that I additionally need a bijective "String <-> String" function for BaseXXX values. Any suggestions? Or maybe there's something better than BaseXXX to use to fit all 3 requirements?

回答1:

If you do not need this to be too secure, you can just use a simple symmetric cipher after encoding in BaseXXX. For example you can choose a key sequence of integers [n₁, n₂, n₃...] and then use a Vigenere cipher.

The basic idea behind the cipher is simple--encode each character C as C + K (mod 26) where K is an element from the key. As you go along, just get the next number from the key for the next character, wrapping around once you run out of values in the key.

You really have two options here: you can first convert a number to a string in baseXXX and then encrypt, or you can use the same idea to just encrypt each number as a single character. In that case, you would want to change it from mod 26 to mod N + 1.

Come to think of it, an even simpler option would be to just xor the element from the key and the value. (As opposed to using the Vigenere formula.) I think this would work just as well for obfuscation.

回答2:

This method meets requirements 1-3, but it is perhaps a bit too computationally expensive:

1. find a prime p > N+2, not too much larger
2. find a primitive root g modulo p, that is, a number whose multiplicative order modulo p is p-1
3. for 0 <= k <= N, let enc(k) = min {j > 0 : g^j == (k+2) (mod p)}
4. f(k) = enc(k).toString()

回答3:

Construct a table of length M. This table should map the numbers 0 through M-1 to distinct short strings with a random ordering. Express the integer as a base-M number, using the strings from the table to represent the digits in the number. Decode with a straightforward reversal.

With M=26, you could just use a letter for each of the digits. Or take M=256 and use a byte for each digit.

Not even remotely a good cryptographic approach!

回答4:

So you need a string that obfuscates the original number, but allows one to determine str(K+1) when str(K) is known?

How about just doing f(x) = (x + a).toString(), where a is secret? Then an outside user can't determine x from f(x), but they can be confident that if they have a string "1234", say, for an unknown x then "1235" maps to x+1.

回答5:

p. 1 and p. 3 are slightly contradicting and a bit vague, too.

I would propose using hex representation of the integer numbers.

17 => 0x11
123123 => 1E0F3