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

Question

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

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

Проблемы:

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

Одно из решений:Я мог бы создать массив длиной 256 ^ 4 байта и заполнить его, в сопоставлении один к одному, это сработало бы, но есть проблемы:это означает, что я должен искать график размером 256 ^ 8 из-за необходимости поиска свободных чисел для каждого значения (следует отметить, что распределение должно быть sudo random на основе массива 64 * 64 байт).Это решение также имеет НЕЗНАЧИТЕЛЬНУЮ (lol) проблему с потребностью в 8 ГБ оперативной памяти, что делает это решение бессмысленным.

Область ввода совпадает с областью вывода, другими словами, каждый вход имеет уникальный результат:сопоставление один к одному.Как я отмечал в разделе "одно решение", это очень возможно, и я использовал этот метод, когда речь шла о меньшем домене (всего 256).Дело в том, что по мере увеличения чисел этот метод становится чрезвычайно неэффективным, недостатком дельты было O(n^5) и омега был O(n^8) с таким же дерьмовым использованием памяти.

Мне было интересно, есть ли какой-нибудь умный способ сделать это.В двух словах, это взаимно однозначное отображение домена (4 байта или 256 ^ 4).О, и такие простые вещи, как N + 1, не могут быть использованы, они должны быть выведены из массива 64 * 64 байтовых значений, которые являются sudo случайными, но могут быть воссозданы для обратных преобразований.

Answer 1

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

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

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

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

Учитывая такое g, мы определяем 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, мы получим 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).Если a изменится, то изменится и a^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 2

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

Кто знал?

Answer 3

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

У вас есть четыре байта, a_1, a_2, a_3, a_4, который мы будем рассматривать как вектор a с 4 компонентами, каждый из которых представляет собой номер mod 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 быть обратимым?Поскольку мы рассматриваем его mod 256, нам просто нужен его определяющий фактор быть обратимым mod 256;то есть его определитель должен быть нечетным.

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

Answer 4

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

Побитовый эксклюзив Или является вашим другом.

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

Answer 5

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

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

Answer 6

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

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

Например:

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

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

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

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

Answer 7

Что вы подразумеваете под "линейным" преобразованием?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)

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

Answer 8

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

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

Answer 9

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

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