Двунаправленное хеширование номеров фиксированного диапазона

Question

Мне нужно создать функцию, которая принимает одно целое в качестве аргумента в диапазоне 0-N и возвращает случайное случайное число в том же диапазоне.

Каждый входной номер должен всегда иметь ровно один выход, и он всегда должен быть одинаковым.

Такая функция будет производить что-то вроде этого:

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

Я считаю, что это может быть достигнуто с помощью какого-то алгоритма хеширования? Мне не нужно ничего сложного, просто не слишком простое, как f(1) = 2, f(2) = 3 и т. Д.

Самая большая проблема в том, что мне нужно, чтобы это было обратимым. Например. приведенная выше таблица должна быть правдой слева направо, а также справа налево, используя другую функцию для преобразования справа налево.

Я знаю, что самый простой способ - создать массив, перетасовать его и просто сохранить отношения в db или что-то в этом роде, но поскольку мне нужно N быть довольно большим, я бы хотел избежать этого, если это возможно.

Редактировать: Для моего конкретного случая N - это конкретный номер, это точно 16777216 (64^4).

Answer 1

Если диапазон всегда равен 2 - [0,16777216), то вы можете использовать эксклюзивную или как предлагалось @MarkBaker. Он просто не работает так легко, если ваш диапазон не равен двум.

Вы можете использовать сложение и вычитание по модулю N, хотя эти только слишком очевидны, поэтому вам нужно объединить его с чем-то другим.

Вы также можете выполнять умножение по модулю-N, но перестановка в этом случае сложна. Чтобы было проще, мы можем изолировать нижние восемь бит и умножить их и добавить их таким образом, чтобы они не мешали этим битам, поэтому мы можем использовать их снова, чтобы отменить операцию.

Я не знаю PHP, поэтому я приведу пример на C. Возможно, это одно и то же.

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

И для декодирования, воспроизводить операции назад в обратном порядке:

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

То 1073741824 должно быть кратно N, и 256 должны быть фактором N, и если N не является мощность двух, то вы не можете (обязательно) использовать эксклюзивную или (^ является эксклюзивной или в C, и я тоже предполагаю на PHP). Другие номера, с которыми вы можете играть, и добавлять и удалять сцены, на досуге.

В обеих функциях добавляется 1073741824, чтобы х оставалось положительным; это так, что операция modulo никогда не дает отрицательного результата даже после того, как мы вычтем значения из x, которые могли бы сделать это отрицательным в промежуточный период.

Answer 2

Я предложил описать, как я «случайно» скремлю 9-значные SSN при создании наборов данных исследований. Это не заменит или не будет содержать SSN. Он переупорядочивает цифры. Трудно вернуть цифры в правильном порядке, если вы не знаете порядок, в котором они были скремблированы. У меня есть ощущение, что это не то, что действительно хочет расспрашивать. Поэтому я счастлив удалить этот ответ, если он считается вне темы.

Я знаю, что у меня 9 цифр. Итак, я начинаю с массивом, который имеет 9 значений индекса в порядке:

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

Теперь мне нужно повернуть ключ, который я помню в способ для воспроизведения в массиве. Перетасовка должна быть одинаковым для одного и того же ключа каждый раз. Я использую пару трюков. Я использую crc32, чтобы превратить слово в число. Я использую srand/rand для получения предсказуемого порядка случайных значений. Примечание: mt_rand больше не производит такую ​​же последовательность случайных цифр с одним и тем же семенем, поэтому мне нужно использовать rand.

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

Массив $ a по-прежнему имеет цифры от 0 до 8, но они перетасовываются. Если я использую одно и то же ключевое слово, я получаю тот же перетасованный порядок каждый раз. Это позволяет мне повторять это каждый месяц и получать тот же результат. Затем, с перетасованным массивом, я могу выбрать цифры из SSN. Во-первых, я гарантирую, что он имеет 9 символов (некоторые SSN отправляются как целые числа, а ведущее 0 опущено). Затем я создаю маскированный SSN, выбирая цифры, используя $ a.

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

$ masked_ssn теперь будет иметь все цифры в $ ССН, но в другом порядке. Технически есть ключевые слова, которые заставляют $ a стать исходным упорядоченным массивом после перетасовки, но это очень редко.

Надеюсь, это имеет смысл. Если это так, вы можете сделать все это намного быстрее. Если вы превратите исходную строку в массив символов, вы можете перетасовать массив символов. Вам просто нужно каждый раз подбирать rand.

$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); 

Это не действительно быстрее в пути, потому что во время выполнения рэнд является довольно дорогой и функция запуска рандов чертовски много больше здесь. Если вы маскируете тысячи значений, как я, вам нужно использовать массив индексов, который перетасовывается только один раз, а не перетасовка для каждого значения.

Теперь, как мне его отменить? Предположим, что я использую первый метод с массивом индексов. Это будет что-то вроде $ a = {5, 3, 6, 1, 0, 2, 7, 8, 4}. Это индексы для исходного SSN в замаскированном порядке. Таким образом, я могу легко создать оригинальный SSN.

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

Как вы можете видеть, $ i рассчитывает от 0 до 8 через маскированный SSN. $ j рассчитывает 5, 3, 6 ... и помещает каждое значение из маскированного SSN в правильное место в исходном SSN.

Answer 3

Похоже, у вас есть хороший ответ, но все же есть альтернатива. Линейный конгруэнтный генератор (LCG) может обеспечивать отображение 1-к-1 и, как известно, является обратимым с использованием алгоритма Евклида. Для 24bit

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

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

Для LCG reversability взглянуть на Reversible pseudo-random sequence generator