Симметричный биективный алгоритм для целых чисел

Ответ 1

Используйте любой 32-разрядный блочный шифр! По определению блок-шифр отображает все возможные входные значения в своем диапазоне до уникального выходного значения обратимым образом, и по дизайну трудно определить, какое значение будет иметь любое заданное значение без ключа. Просто выберите ключ, держите его в секрете, если важна безопасность или неясность, и используйте шифр в качестве своей трансформации.

Для расширения этой идеи в диапазонах без полномочий 2 см. мой пост в Защищенные перестановки с блочными шифрами.

Решение ваших конкретных проблем:

• Алгоритм действительно симметричен. Я не уверен, что вы подразумеваете под "отменой операции без ключа". Если вы не хотите использовать ключ, hardcode произвольно сгенерированный и считайте его частью алгоритма.
• Yup - по определению блочный шифр является биективным.
• Угу. Это не был бы хороший шифр, если бы это было не так.

Ответ 2

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

Скажем, у меня 4-битное число. Есть 16 различных значений. Посмотрите на это, как будто это четырехмерный куб: 4-мерный куб http://www.ams.org/featurecolumn/images/january2009/klee8.jpg.

Каждая вершина представляет одно из этих чисел, каждый бит представляет одно измерение. Таким образом, его базовый XYZW, где каждый из измерений может иметь только значения 0 или 1. Теперь представьте, что вы используете размер другого порядка. Например, XZYW. Каждая из вершин теперь изменила свой номер!

Вы можете сделать это для любого количества измерений, просто переместите эти измерения. Если безопасность не является вашей проблемой, это может быть хорошим быстрым решением для вас. С другой стороны, я не знаю, будет ли результат "недостаточно понятным" для ваших нужд, и, конечно же, после выполнения большого количества картографирования отображение может быть отменено (что может быть преимуществом или недостатком в зависимости от ваших потребностей).

Ответ 3

В следующей статье приведены примеры из 4 или 5 сопоставлений, предоставляющих вам функции, а не построенные сопоставленные наборы: www.cs.auckland.ac.nz/~john-rugis/pdf/BijectiveMapping.pdf

Ответ 4

Помимо создания случайных поисковых таблиц, вы можете использовать комбинацию функций:

• XOR
• симметричная битовая перестановка (например, сдвинуть 16 бит или перевернуть от 0-31 до 31-0 или перевернуть от 0-3 до 3-0, от 4-7 до 7-4,...)
• больше?

Ответ 5

Если ваша цель - просто получить случайную перестановку чисел с примерно определенным размером, тогда существует еще один возможный способ: уменьшить число чисел до простого числа.

Тогда вы можете использовать отображение формы

f (i) = (i * a + b)% p

и если p действительно простое, это будет биекцией для всех a!= 0 и всех b. Он будет выглядеть довольно случайным для больших a и b.

Например, в моем случае, для которого я наткнулся на этот вопрос, я использовал 1073741789 как простое число для диапазона чисел меньше 1 < 30. Это заставляет меня потерять только 35 номеров, что хорошо в моем случае.

Мое кодирование тогда

((n + 173741789) * 507371178) % 1073741789

и декодирование

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Обратите внимание, что 507371178 * 233233408% 1073741789 == 1, поэтому эти два числа инвертируют поле чисел по модулю 1073741789 (вы можете найти обратные числа в таких полях с расширенным евклидовым алгоритмом).

Я выбрал a и b довольно произвольно, я просто убедился, что они примерно наполовину меньше p.

Ответ 6

Можно ли использовать случайную сгенерированную таблицу поиска? Пока случайные числа в таблице уникальны, вы получаете биективное отображение. Это не симметрично.

Одна таблица поиска 16 ГБ для всех 32-битных значений, вероятно, непрактична, но вы можете использовать две отдельные 16-разрядные таблицы поиска для слова высокого слова и низкого слова.

PS: Я думаю, вы можете создать симметричную биективную таблицу поиска, если это важно. Алгоритм должен начинаться с пустого LUT:

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Выберите первый элемент, присвойте ему случайное отображение. Чтобы сделать симметричное отображение, присвойте также и обратное:

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

Выберите следующий номер, снова назначьте случайное сопоставление, но выберите номер, который еще не был назначен. (т.е. в этом случае, не выбирайте 1 или 3). Повторяйте до завершения LUT. Это должно порождать случайное биективное симметричное отображение.

Ответ 7

Возьмите число, умножьте на 9, обратные цифры, разделите на 9.

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

Должно быть достаточно неясным!!

Изменить: это не биекция для 0 конечного целого

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

Вы всегда можете добавить определенное правило, например: Возьмите число, разделите его на 10 x раз, умножьте на 9, обратные цифры, разделите на 9, умножьте на 10 ^ x.

Итак,

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

W00t работает!

Редактирование 2: Для получения более мрачной вы можете добавить произвольное число и вычесть в конце.

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129

Ответ 8

Вот моя простая идея: Вы можете перемещать биты числа, как это предлагал PeterK, но вы можете иметь другую перестановку бит для каждого номера и все еще иметь возможность расшифровать его.

Шифр ​​выглядит следующим образом: Обработать входной номер как массив бит I[0..31], а вывод - как O[0..31]. Подготовьте массив K[0..63] из 64 случайно сгенерированных чисел. Это будет ваш ключ. Возьмите бит номера входа из положения, определяемого первым случайным числом (I[K[0] mod 32]), и поместите его в начале вашего результата (O[0]). Теперь, чтобы решить, какой бит разместить в O[1], используйте ранее использованный бит. Если это 0, используйте K [1] для создания позиции в I, из которой нужно взять, это 1, используйте K [2] (что просто означает пропустить одно случайное число).

Теперь это не сработает, так как вы можете взять тот же бит дважды. Чтобы избежать этого, перенумеруйте бит после каждой итерации, опуская использованные биты. Чтобы создать позицию, из которой следует взять O[1], используйте I[K[p] mod 31], где p равно 1 или 2, в зависимости от бит O[0], поскольку осталось 31 бит, пронумерованный от 0 до 30.

Чтобы проиллюстрировать это, я приведу пример:

У нас есть 4-битное число и 8 случайных чисел: 25, 5, 28, 19, 14, 20, 0, 18.

I: 0111    O: ____
    _

25 mod 4 = 1, поэтому мы возьмем бит, положение которого равно 1 (считая от 0)

I: 0_11    O: 1___
     _

Мы только что взяли немного значения 1, поэтому мы пропустим одно случайное число и используем 28. Осталось 3 бита, поэтому для подсчета позиции берем 28 mod 3 = 1. Возьмем первый (считая от 0 ) оставшихся бит:

I: 0__1    O: 11__
   _

Снова пропустим одно число и возьмем 14. 14 mod 2 = 0, поэтому возьмем 0-й бит:

I: ___1    O: 110_
      _

Теперь это не имеет значения, но предыдущий бит был 0, поэтому мы берем 20. 20 mod 1 = 0:

I: ____    O: 1101

И это он.

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

Это, очевидно, имеет все недостатки всего, что просто перемещает биты (например, 0 становится 0, а MAXINT становится MAXINT), но кажется сложнее найти, как кто-то зашифровал номер, не зная ключа, который должен быть секретным.

Ответ 9

Если вы не хотите использовать правильные криптографические алгоритмы (возможно, по соображениям производительности и сложности), вместо этого вы можете использовать более простой шифр, например шифр Vigenère. Этот шифр был фактически описан как le chiffre indéchiffrable (французский для "нерушимого шифра" ).

Вот простая реализация С#, которая сдвигает значения на основе соответствующего значения ключа:

void Main()
{
  var clearText = Enumerable.Range(0, 10);
  var key = new[] { 10, 20, Int32.MaxValue };
  var cipherText = Encode(clearText, key);
  var clearText2 = Decode(cipherText, key);
}

IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
  return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}

IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
  return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}

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

Ответ 10

Нарисуйте большой круг на большом листе бумаги. Напишите все целые числа от 0 до MAXINT по часовой стрелке от вершины круга, равномерно распределенные. Запишите все целые числа от 0 до MININT против часовой стрелки, снова на равном расстоянии. Обратите внимание, что MININT находится рядом с MAXINT в нижней части круга. Теперь сделайте дубликат этого рисунка с обеих сторон куска жесткой карты. Прикрепите жесткую карту к кругу через центры обоих. Выберите угол поворота, любой угол, который вам нравится. Теперь у вас есть сопоставление 1-1, которое отвечает некоторым вашим требованиям, но, вероятно, недостаточно мало. Отвинтите карту, поверните ее вокруг диаметра и любого диаметра. Повторите эти шаги (в любом порядке), пока у вас не будет биекция, которой вы довольны.

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

Для уточнения, следующего за комментарием: если вы только поворачиваете карту против бумаги, то метод такой же простой, как вы жалуетесь. Однако, когда вы переворачиваете карту по карте, она не эквивалентна (x+m) mod MAXINT для любого m. Например, если вы не открыли карту и повернули ее вокруг диаметра на 0 (что находится в верхней части лицевой стороны), тогда 1 отображается на -1, от 2 до -2 и т.д. (x+m) mod MAXINT соответствует только поворотам карты.

Ответ 11

Разделите число на два (16 наиболее значимых бит и 16 младших значащих бит) и рассмотрите бит в двух 16-битных результатах как карты в двух колодах. Смешайте колоды, заставляя их друг друга.

Итак, если ваше начальное число b31,b30,...,b1,b0, вы получите b15,b31,b14,b30,...,b1,b17,b0,b16. Он быстро и быстро реализуется, как и обратный.

Если вы посмотрите на десятичное представление результатов, серия выглядит довольно неясной.

Вы можете вручную сопоставить 0 → maxvalue и maxvalue → 0, чтобы избежать их отображения на себя.