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

Question

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

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

Редактировать для разъяснения Цель:

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

Пример Ожидаемый результат:

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

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

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

Answer 1

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

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

Обращаясь к вашим конкретным проблемам:

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

Answer 2

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

Скажем, у меня есть 4-битный номер. Есть 16 различных ценностей. Посмотрите на это, как будто это был четырехмерный куб:
_{(источник: ams.org.)}
.

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

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

Answer 3

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

Answer 4

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

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

Answer 5

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

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

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

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

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

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

((n + 173741789) * 507371178) % 1073741789

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

(n * 233233408 + 1073741789 - 173741789) % 1073741789

Примечание.

Я выбрал A и B справедливо произвольно, я просто убедился, что они примерно половина размера с.

Answer 6

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

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

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

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

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

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

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

Answer 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 ^ х.

И так

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 8

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

Шифр идет так: лечить номер ввода как массив битов 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 мод 4 = 1, поэтому мы займемся, чья позиция 1 (подсчет от 0)

I: 0_11    O: 1___
     _

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

I: 0__1    O: 11__
   _

Опять же, мы пропускаем один номер и возьму 14. 14 мод 2 = 0, поэтому мы берем 0-й бит:

I: ___1    O: 110_
      _

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

I: ____    O: 1101

И это это.

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

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

Answer 9

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

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

Answer 10

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

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

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

Answer 11

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

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

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

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