Two-way hashing of fixed range numbers

Question

I need to create a function which takes a single integer as argument in the range 0-N and returns a seemingly random number in the same range.

Each input number should always have exactly one output and it should always be the same.

Such a function would produce something like this:

f(1) = 4
f(2) = 1
f(3) = 5
f(4) = 2
f(5) = 3

I believe this could be accomplished by some kind of a hashing algorithm? I don't need anything complex, just not something too simple like f(1) = 2, f(2) = 3 etc.

The biggest issue is that I need this to be reversible. E.g. the above table should be true left-to-right as well as right-to-left, using a different function for the right-to-left conversion is fine.

I know the easiest way is to create an array, shuffle it and just store the relations in a db or something, but as I need N to be quite large I'd like to avoid this if possible.

Edit: For my particular case N is a specific number, it's exactly 16777216 (64^4).

Answer 1

If the range is always a power of two -- like [0,16777216) -- then you can use exclusive-or just as @MarkBaker suggested. It just doesn't work so easily if your range is not a power of two.

You can use addition and subtraction modulo N, although these alone are too obvious, so you have to combine it with something else.

You can also do multiplication modulo-N, but reversing that is complicated. To make it simpler, we can isolate the bottom eight bits and multiply those and add them in a way that doesn't interfere with those bits so we can use them again to reverse the operation.

I don't know PHP so I'm going to give an example in C, instead. Maybe it's the same.

int enc(int x) {
  x = x + 4799 * 256 * (x % 256);
  x = x + 8896843;
  x = x ^ 4777277;
  return (x + 1073741824) % 16777216;
}

And to decode, play the operations back in reverse order:

int dec(int x) {
  x = x + 1073741824;
  x = x ^ 4777277;
  x = x - 8896843;
  x = x - 4799 * 256 * (x % 256);
  return x % 16777216;
}

That 1073741824 must be a multiple of N, and 256 must be a factor of N, and if N is not a power of two then you can't (necessarily) use exclusive-or (^ is exclusive-or in C and I assume in PHP too). The other numbers you can fiddle with, and add and remove stages, at your leisure.

The addition of 1073741824 in both functions is to ensure that x stays positive; this is so that the modulo operation doesn't ever give a negative result, even after we've subtracted values from x which might have made it go negative in the interim.

Answer 2

I offered to describe how I "randomly" scramble up 9-digit SSNs when producing research data sets. This does not replace or hash an SSN. It re-orders the digits. It is difficult to put the digits back in the correct order if you don't know the order in which they were scrambled. I have a gut feeling that this is not what the questioner really wants. So, I am happy to delete this answer if it is deemed off-topic.

I know that I have 9 digits. So, I start with an array that has 9 index values in order:

$a = array(0,1,2,3,4,5,6,7,8);

Now, I need to turn a key that I can remember into a way to shuffle the array. The shuffling has to be the same order for the same key every time. I use a couple tricks. I use crc32 to turn a word into a number. I use srand/rand to get a predictable order of random values. Note: mt_rand no longer produces the same sequence of random digits with the same seed, so I have to use rand.

srand(crc32("My secret key"));
usort($a, function($a, $b) { return rand(-1,1); });

The array $a still has the digits 0 through 8, but they are shuffled. If I use the same keyword I will get the same shuffled order every time. That lets me repeat this every month and get the same result. Then, with a shuffled array, I can pick the digits off the SSN. First, I ensure it has 9 characters (some SSNs are sent as integers and a leading 0 is omitted). Then, I build a masked SSN by picking the digits using $a.

$ssn = str_pad($ssn, 9, '0', STR_PAD_LEFT);
$masked_ssn = '';
foreach($a as $i) $masked_ssn.= $ssn{$i};

$masked_ssn will now have all the digits in $ssn, but in a different order. Technically, there are keywords that make $a become the original ordered array after shuffling, but that is very very rare.

Hopefully this makes sense. If so, you can do it all much faster. If you turn the original string into an array of characters, you can shuffle the array of characters. You just need to reseed rand every time.

$ssn = "111223333"; // Assume I'm using a proper 9-digit SSN
$a = str_split($ssn);
srand(crc32("My secret key"));
usort($a, function($a, $b) { return rand(-1,1); });
$masked_ssn = implode('', $a);

This is not really faster in a runtime way because rand is a rather expensive function and you run rand a hell of lot more here. If you are masking thousands of values as I do, you will want to use an index array that is shuffled just once, not a shuffling for every value.

Now, how do I undo it? Assume I'm using the first method with the index array. It will be something like $a = {5, 3, 6, 1, 0, 2, 7, 8, 4}. Those are the indexes for the original SSN in the masked order. So, I can easily build the original SSN.

$ssn = '000000000'; // I like to define all 9 characters before I start
foreach($a as $i=>$j) $ssn[$j] = $masked_ssn{$i};

As you can see, $i counts from 0 to 8 across the masked SSN. $j counts 5, 3, 6... and puts each value from the masked SSN in the correct place in the original SSN.

Answer 3

Looks like you've got good answer, but still there is an alternative. Linear Congruential Generator (LCG) could provide 1-to-1 mapping and it is known to be a reversible using Euclid's algorithm. For 24bit

Xi = [(A * Xi-1) + C] Mod M
where M = 2^24 = 16,777,216

A = 16,598,013
C = 12,820,163

For LCG reversability take a look at Reversible pseudo-random sequence generator