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

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

Расширение этой идеи для диапазонов, отличных от степени двойки, см. в моем сообщении на Безопасные перестановки с помощью блочных шифров.

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

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

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

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

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

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

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

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

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

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

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

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.

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

Одна 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

W00t это работает!

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

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

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

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