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

Question

Мне нужен алгоритм, который может выполнять взаимно-однозначное сопоставление (т. Е. Без коллизий) 32-разрядного целого числа со знаком и другого 32-разрядного целого числа со знаком.

Моя настоящая проблема - достаточно энтропиитак что вывод функции выглядит случайным.В основном я ищу шифр, похожий на XOR Cipher, но который может генерировать более произвольно выглядящие результаты.Безопасность - не моя настоящая проблема, хотя неизвестность - это.

Редактировать для уточнения:

1. Алгоритм должен быть симметричным, чтобы я мог полностью изменить операциюбез пары ключей.
2. Алгоритм должен быть биективным, каждое 32-битное входное число должно генерировать 32-битное уникальное число.
3. Вывод функции должен бытьКак ни странно, добавление только одного к входу должно сильно повлиять на вывод.

Пример ожидаемого результата:F (100) = 98456F (101) = -758F (102) = 10875498F (103) = 986541F (104) = 945451245F (105) = -488554

Так же, как MD5, изменение одной вещи может многое изменить.

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

Answer 1

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

Расширение этой идеи до диапазонов не-степени-2 см. В моем посте Безопасные перестановки с блочными шифрами .

Решение ваших конкретных задач:

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

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

Тогда моя кодировка

((n + 173741789) * 507371178) % 1073741789

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

(n * 233233408 + 1073741789 - 173741789) % 1073741789

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

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

Answer 6

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

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

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]));
}

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

Answer 7

Вот моя простая идея: вы можете перемещаться по битам числа, как предложил 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 mod1 = 0:

I: ____    O: 1101

И это все.

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

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

Answer 8

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

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

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

Редактировать: это не биекция для 0, заканчивающееся целым числом

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

Вы всегда можете добавить определенное правило, например: взять число, разделить на 10 раз, умножить на 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

Answer 9

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

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

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

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

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

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

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

Answer 10

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

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

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

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