7

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?

andrew.z
  • 1,039
  • 3
  • 15
  • 24
  • The 'Related' list over on the right has a number of similar qs, it seems – AakashM Jan 12 '12 at 10:26
  • By definition, a reversible obfuscating function is a "cipher". Not being able to compute `enc(k+1)` from `enc(k)` is pretty much required for a good cipher, since if you could then a known plaintext/cipher pair would give you as many ciphertexts of nearby plaintexts as you had time to compute. I think the question then, is how "bad" (or expensive-to-compute) a cipher are you willing to accept in order to get short cipher texts, whether you're going to use salt or not, and whether you need a streaming mode. – Steve Jessop Jan 12 '12 at 11:45
  • Streaming modes are important and not entirely trivial, because even if your cipher makes it infeasible to reverse the representation of a single number, an attacker who can see a long series of numbers and knows a little bit about the likely distribution of the plaintext data might be able to perform frequency analysis, Markov chain analysis etc, to identify the ciphered values of specific common plaintext values. See http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation#Electronic_codebook_.28ECB.29 for an example of a streaming mode failing. – Steve Jessop Jan 12 '12 at 11:54
  • if you ignore requirements 1 and 3, then the obvious solution is bijective base 10: https://en.wikipedia.org/wiki/Bijective_numeration#The_bijective_base-10_system – Norill Tempest Sep 18 '17 at 22:35

5 Answers5

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.

Tikhon Jelvis
  • 67,485
  • 18
  • 177
  • 214
1

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()
Daniel Fischer
  • 181,706
  • 17
  • 308
  • 431
1

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!

Michael J. Barber
  • 24,518
  • 9
  • 68
  • 88
0

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.

Chowlett
  • 45,935
  • 20
  • 116
  • 150
0

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
dmeister
  • 34,704
  • 19
  • 73
  • 95