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

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

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

Изменить для уточнения цели:

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

Пример ожидаемого результата:

F (100) = 98456
F (101) = -758
F (102) = 10875498
F (103) = 986541
F (104) = 945451245
F (105) = -488554

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

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

Источник

11 ответов

Решение

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

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

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

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

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

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

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

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

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

Моя кодировка тогда

((n + 173741789) * 507371178) % 1073741789

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

(n * 233233408 + 1073741789 - 173741789) % 1073741789

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

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

Источник

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

Источник

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

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

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

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

Источник

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

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

Вот моя простая идея: вы можете перемещаться по битам числа, как предложил 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), но, кажется, труднее найти способ, которым кто-то зашифровал число, не зная ключа, который должен быть секретным.

Источник

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

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

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

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

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

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

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

Источник

Возьмите число, умноженное на 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

Это работает!

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

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129
Источник

Если вы не хотите использовать надлежащие криптографические алгоритмы (возможно, по соображениям производительности и сложности), вы можете вместо этого использовать более простой шифр, такой как шифр Vigenère. Этот шифр был фактически описан как 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]));
}

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

Источник

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

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

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

Источник

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

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

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

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

Источник
Другие вопросы по тегам