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?

Improve this question
4
  • The 'Related' list over on the right has a number of similar qs, it seems Commented Jan 12, 2012 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. Commented Jan 12, 2012 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 en.wikipedia.org/wiki/… for an example of a streaming mode failing. Commented Jan 12, 2012 at 11:54
  • if you ignore requirements 1 and 3, then the obvious solution is bijective base 10: en.wikipedia.org/wiki/… Commented Sep 18, 2017 at 22:35

5 Answers 5

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Vigenere cipher was my first idea. Just trying to get confident that I didn't skip something more trivial...
Heh, always nice when somebody else has the same idea as me :)
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()
Improve this answer

Comments

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!

Improve this answer

Comments

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.

Improve this answer

1 Comment

He wanted the opposite--guessing x + 1 should be nontrivial.
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
Improve this answer

1 Comment

Why p.1 & p.3 are contradicting? And your solution violates p.3 for sure.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.