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

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

Побитовое исключение Или ваш друг.

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

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

Кто знал?

Что вы подразумеваете под «линейным» преобразованием? 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 является результатом всех байтов и влияет на все остальные) .

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

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

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

Используйте набор линейных функций по модулю 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). Очевидно, что изменение одного входного байта изменит все выходные байты.

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

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

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

Вы можете переназначить биты. Давайте использовать 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)

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

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

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, а ^ б ^ г (в) ^ г). Проверим ваши требования:

1. Реверсивный: да. Если мы выполним XOR первых двух выходных байтов, мы получим a ^ g (a), но по второму свойству g мы можем восстановить a. Аналогично для b и c. Мы можем восстановить d после получения a, b и c путем XOR первого байта с (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.

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

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

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

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