функция линейного преобразования

Question

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

Но подождите, это еще не все: он также должен быть распределительным, поэтому изменение одного байта на входе должно повлиять на все 4 выходных байта.

Вопросы:

• если я использую умножение, оно не будет обратимым после того, как оно модифицировано 255 через хранилище в виде байта (и его необходимо оставить как байт)
• если я использую сложение, оно не может быть обратимым и распределительным

Одно из решений: Я мог бы создать массив байтов длиной 256 ^ 4 и заполнить его в сопоставлении один к одному, это сработало бы, но есть проблемы: это означает, что мне приходится искать график размером 256 ^ 8 из-за необходимости поиска для свободных чисел для каждого значения (следует отметить, что дистрибутивность должна быть случайной на основе массива байтов 64 * 64). Это решение также имеет проблему MINOR (смеется), требующую 8 ГБ ОЗУ, что делает это решение бессмысленным.

Есть хорошие идеи? Мне не нужен код, просто идея.

РЕДАКТИРОВАТЬ: ОК, извините за описание; Я постараюсь сделать это немного яснее. Домен ввода совпадает с доменом вывода, каждый вход имеет уникальный выход, другими словами: отображение один в один. Как я отметил в «одном решении», это очень возможно, и я использовал этот метод, когда речь шла о меньшем домене (всего 256). Дело в том, что по мере того как числа становятся большими, метод становится необычайно неэффективным, дельта-недостаток был O (n ^ 5), а omega был O (n ^ 8) с аналогичной хреновостью в использовании памяти. Мне было интересно, если есть умный способ сделать это. Короче говоря, это сопоставление домена один к одному (4 байта или 256 ^ 4). Да, и такие простые вещи, как N + 1, не могут быть использованы, он должен быть выделен из массива байтовых значений размером 64 * 64, которые являются sudo случайными, но восстанавливаемыми для обратных преобразований.

Надеюсь, я что-то понял.

Answer 1

Сбалансированные блочные смесители - это именно то, что вы ищете.

Кто знал?

Answer 2

Редактировать! не возможно, если вы действительно хотите линейное преобразование. Вот математическое решение:

У вас есть четыре байта, a_1, a_2, a_3, a_4, которые мы будем рассматривать как вектор a с 4 компонентами, каждый из которых является числовым модом 256. Линейное преобразование - это просто матрица 4x4 M, элементы которой также являются числами mod 256. У вас есть два условия:

1. Из Ma мы можем вывести a (это означает, что M является обратимой матрицей).
2. Если a и a' отличаются одной координатой, то Ma и Ma' должны отличаться каждой координатой.

Условие (2) немного сложнее, но вот что это значит. Поскольку M является линейным преобразованием, мы знаем, что

M (a - a) = Ma - Ma'

Слева, поскольку a и a' отличаются одной координатой, a - a имеет ровно одну ненулевую координату. Справа, поскольку Ma и Ma' должны различаться по каждой координате, Ma - Ma' должен иметь каждые ненулевая координата.

Таким образом, матрица M должна принимать вектор с одной ненулевой координатой к одному со всеми ненулевыми координатами. Таким образом, нам просто нужно, чтобы каждая запись M была ненулевым делителем mod 256, т.е. быть нечетной.

Возвращаясь к условию (1), что означает для M обратимость? Поскольку мы рассматриваем его мод 256, нам нужно, чтобы его определитель был обратимым модом 256; то есть его определитель должен быть нечетным.

Итак, вам нужна матрица 4x4 с нечетными записями мод 256, чей определитель нечетен. Но это невозможно! Зачем? Определитель вычисляется путем суммирования различных произведений записей. Для матрицы 4х4 их 4! = 24 различных слагаемых, и каждое из них, являющееся произведением нечетных записей, является нечетным. Но сумма 24 нечетных чисел четна, поэтому определитель такой матрицы должен быть четным!

Answer 3

Вот ваши требования, как я их понимаю:

1. Пусть B будет пространством байтов. Вам нужна функция «один к одному» (и, следовательно, на) f: B^4 -> B^4.
2. Если вы измените какой-либо один входной байт, то все выходные байты изменятся.

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

Хорошо, во-первых, нам нужна функция g: B -> B, которая принимает один байт и возвращает один байт. Эта функция должна иметь два свойства: g (x) обратимо и x ^ g (x) обратимо. [Примечание: ^ - это оператор XOR.] Подойдет любой такой g, но позже я определю конкретный.

Учитывая такое ag, мы определяем f как f (a, b, c, d) = (a ^ b ^ c ^ d, g (a) ^ b ^ c ^ d, a ^ g (b) ^ c ^ d, a ^ b ^ g (c) ^ d). Давайте проверим ваши требования:

1. Обратимый: да. Если мы XOR первые два выходных байта, мы получаем ^ g (a), но по второму свойству g мы можем восстановить a. Аналогично для б и в. Мы можем восстановить d после получения a, b и c, XORing первый байт с (a ^ b ^ c).
2. Распределительный: да. Предположим, что b, c и d фиксированы. Тогда функция принимает вид f (a, b, c, d) = (a ^ const, g (a) ^ const, a ^ const, a ^ const). Если изменения, то так же будет ^ const; Точно так же, если a изменится, то будет и g (a), и, следовательно, то же самое произойдет с g (a) ^ const. (Тот факт, что g (a) изменяется, если a делает, является первым свойством g; если это не так, то g (x) не будет обратимым.) То же самое верно для b и c. Для d это даже проще, потому что тогда f (a, b, c, d) = (d ^ const, d ^ const, d ^ const, d ^ const), поэтому, если d изменяется, меняется каждый байт.

Наконец, мы строим такую ​​функцию g. Пусть T будет пространством двухбитовых значений, а h : T -> T функция такая, что h (0) = 0, h (1) = 2, h (2) = 3 и h (3) = 1. Эта функция имеет два требуемых свойства g, а именно h (x) является обратимым, как и x ^ h (x). (Для последнего проверьте, что 0 ^ h (0) = 0, 1 ^ h (1) = 3, 2 ^ h (2) = 1 и 3 ^ h (3) = 2.) Итак, наконец, вычислить g (x), разделить x на четыре группы по два бита и взять h каждого квартала отдельно. Поскольку h удовлетворяет двум желаемым свойствам и между четвертями нет взаимодействия, то и g.

Answer 4

Я не уверен, что понимаю ваш вопрос, но мне кажется, я понимаю, что вы пытаетесь сделать.

Побитовый Эксклюзив Или твой друг.

Если R = A XOR B, R XOR A возвращает B, а R XOR B возвращает A. Так что это обратимое преобразование, если вы знаете результат и один из входных данных.

Answer 5

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

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

Answer 6

Вы можете переназначить биты. Давайте использовать ii для ввода и oo для вывода:

oo[0] = (ii[0] & 0xC0) | (ii[1] & 0x30) | (ii[2] & 0x0C) | (ii[3] | 0x03)
oo[1] = (ii[0] & 0x30) | (ii[1] & 0x0C) | (ii[2] & 0x03) | (ii[3] | 0xC0)
oo[2] = (ii[0] & 0x0C) | (ii[1] & 0x03) | (ii[2] & 0xC0) | (ii[3] | 0x30)
oo[3] = (ii[0] & 0x03) | (ii[1] & 0xC0) | (ii[2] & 0x30) | (ii[3] | 0x0C)

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

Answer 7

Вставьте все байты в 32-битное число, а затем выполните shl или shr (сдвиг влево или вправо) на один, два или три. Затем разбить его обратно на байты (можно использовать вариант записи). Это переместит биты из каждого байта в соседний байт.

Здесь есть несколько хороших предложений (XOR и т. Д.), Я бы предложил объединить их.

Answer 8

Я собираюсь выбросить идею, которая может или не может работать.

Используйте набор линейных функций мод 256 с нечетными простыми коэффициентами.

Например:

b0 = 3 * a0 + 5 * a1 + 7 * a2 + 11 * a3;
b1 = 13 * a0 + 17 * a1 + 19 * a2 + 23 * a3;

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

Это, я считаю, обратимая трансформация. Это линейно, в этом af (x) mod 256 = f (ax) и f (x) + f (y) mod 256 = f (x + y). Очевидно, что изменение одного входного байта изменит все выходные байты.

Итак, посмотрите китайскую теорему об остатках и посмотрите, работает ли она.

Answer 9

Что вы подразумеваете под «линейным» преобразованием? O (n) или функция f с f (c * (a + b)) = c * f (a) + c * f (b)?

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

РЕДАКТИРОВАТЬ: Мое решение будет следующим:

b0 = (a0 ^ a1 ^ a2 ^ a3)
b1 = a1 + b0 ( mod 256)
b2 = a2 + b0 ( mod 256)
b3 = a3 + b0 ( mod 256)

Это было бы обратимо (просто вычтите первый байт из другого, а затем XOR 3 результирующих байта на первом), и изменение одного бита будет изменять каждый байт (так как b0 является результатом всех байтов и воздействий все остальные).