Некоторые вопросы по построению перестановок из логических функций
Я видел несколько примеров использования логических функций в качестве перестановок.
Например, функция Keccak Chi: 2.3.1 :
из https://keccak.team/figures.html
Или как формула: для $i=\{0..4\}$ $A_i=a_i \oplus (\neg a_{i+1} \wedge a_{i+2})$ с индексами, рассчитанными по модулю 5
Первый вопрос: каково обоснование (или доказательство) того, почему это перестановка?
Второй, связанный с этим вопрос: каковы свойства, чтобы логическая функция удовлетворяла тому, что она приводит к перестановке?
А теперь по поводу обратной такой перестановки.
Существуют ли какие-либо общие методы / алгоритмы для поиска обратного такой конструкции?
Кроме того, каковы основные факторы, способствующие сложности обратного (количество переменных, алгебраическая степень и т. Д.)?
И если такой метод применяется к большему входу - скажем, $i=\{0..127\}$, труднее ли вычислить обратное, если функция имеет только несколько (например, 3 для Chi) или много, скажем 128, входных переменных?
Любые ответы / указатели приветствуются.
Ответы
Общий алгебраический вопрос многогранен и может быть довольно сложным. Некоторые зависят от векторного пространства, некоторые - от свойств поля расширения.
Как упоминалось в комментариях, проверка свойства может быть проще.
Я ответил на связанный вопрос Примеры многоуровневых сбалансированных логических функций с несколькими выходами
Упомянутые там статьи Ниберга
К. Ниберг, Дифференциально однородные отображения для криптографии , 1993 и
К. Ниберг, Совершенные нелинейные S-блоки , 1992
оба легко найти в Google Scholar.
Изменить : keccak$\chi$ карты $\{0,1\}^5$ себе.
я буду использовать $a_i$ в качестве ввода и $A_i$ как выходные переменные, как в отредактированном вопросе.
Подсчет индексов по модулю 5, если нет $i$ такой, что $(a_i,a_{i+2})=(0,1)$ тогда $\chi$имеет фиксированную точку для этого входа. Позволять$W=\{i: (a_i,a_{i+2})=(0,1)\},$ то общее отображение просто инвертирует биты, принадлежащие $i.$
Обратите внимание, что наборы $J_i,J_j$ где $J_i=\{i,i+2\}$ не пересекаются, кроме случаев, когда $j=i+2$ или же $i=j+2.$Таким образом, нет двусмысленности в определении обратного, если только мы не находимся в этом особом случае, поэтому обратное существует, кроме этого особого случая. Но даже в этом случае узоры$(a_i,a_{i+2},a_{i+4})$ которые приводят к однозначным битовым переворотам.
Если $(a_i,a_{i+2},a_{i+4})=(1,0,0)$ тогда $a_{i+1}$ будет перевернут, но не $a_{i+3}$. Так$A_{i+1}=1\oplus a_{i+1},$ а также $A_{i+3}=a_{i+3}.$
Если $(a_i,a_{i+2},a_{i+4})=(1,0,1)$ тогда $a_{i+1}$ будет перевернут, но не обязательно $a_{i+3}$, что будет зависеть от значения $a_{i+6}=a_{i+1}$. Но предыдущий аргумент не влияет на этот бит, поскольку$J_i$ а также $J_j$ не пересекаются, если $i=j+1\pmod 2.$
Итак, существует уникальное обратное отображение.
Замечание : В общем, переход между "независимыми от базиса" формулировками перестановок полей расширения и "зависимыми от базиса" перестановками битовых векторов нелегко. Я не вижу непосредственной базисно-независимой формулировки поля расширения для этой перестановки, и, как указано в комментариях к вопросу, такие формулировки, полученные (скажем) с помощью интерполяции Лагранжа, могут быть довольно сложными и высокой степенью.
В $\chi$функция определена и проанализирована в Джоан Дэемен, доктор философии. Тезис
- Стратегии проектирования шифров и хеш-функций на основе линейного и дифференциального криптоанализа, 1995 г.
Глава 6: Преобразования с инвариантным сдвигом (SIT) - это место, где упоминается теория. Я покажу это (множество определений и результатов).
Свойства SIT, делающие их полезными;
- Аппаратно эти преобразования могут быть реализованы в виде взаимосвязанного массива идентичных 1-битных выходных «процессоров».
- Инвариантность к сдвигу обеспечивает оптимальное распределение вычислительной нагрузки.
- В программном обеспечении их регулярность позволяет эффективно реализовывать их с помощью поразрядных логических операций.
- Более того, двоичные инвариантные к сдвигу преобразования могут быть заданы одной булевой функцией.
SIT очень связаны с конечными клеточными автоматами, которые фокусируются на долгосрочной структуре и паттернах с течением времени, эта работа концентрируется на краткосрочных аспектах обратимости и локальных свойств распространения и корреляции.
Определение 6.1: Преобразование$\phi: \mathcal{A} \to \mathcal{A}$является инвариантным относительно сдвиг , если
$$\forall a \in \mathcal{A}, \forall r\in\mathbb{Z}: \phi(\tau_r(a)) = \tau(\phi(a))$$ где $\mathcal{A}$ есть все возможные состояния.
Затем он определил локальные карты, где изображение зависит только от некоторых входных данных.
Теорема 6.1 (Д. Ричардсон) Если преобразование$\phi$ с конечным $\nu$ обратимо, то обратное $\phi^{−1}$ инвариантное к сдвигу преобразование с конечным $\nu$.
Где $\nu$определяет окрестность, см. 6.3 Локальные карты . Эта теорема не дает явного построения обратного.
Раздел 6.6. Нелинейные преобразования с конечным $\nu$ здесь начинается действие.
Здесь карта местности определяется набором паттернов, называемых дополняющими ландшафтами (CL). Значение компонента дополняется, если его окружение принимает один из этих шаблонов. Пейзаж - это узор, состоящий из символов.$1, 0$, а также $\textbf{-}$ обозначающий «безразлично», расположенный относительно источника, обозначаемый $∗$. В этом контексте состояние «все нули» будет обозначаться как$0^*$ и единое государство $1^*$.
Обратное $\chi$обсуждается в разделах о локальной и глобальной обратимости, которые требуют более глубокого изучения теории. Приятное чтение, чтобы узнать, если хотите.
Итак, как я сказал в комментариях, можно либо искать все возможные перестановки, чтобы увидеть желаемое свойство, либо смотреть в теории, как это сделал Дэмен. Они использовали эту теорию много лет спустя в конструкции Sponge, где$\chi$ это единственная нелинейная часть SHA-3.
Поскольку на мой первый вопрос был дан подробный ответ в ответах kodlu и kelalaka, я хотел поделиться результатами, которые я собрал по второму вопросу с момента публикации:
Какие свойства должна удовлетворять логическая функция, чтобы она приводила к перестановке?
Во время множества дополнительных чтений я обнаружил, что это, кажется, хорошо (но не широко) известное свойство. Например, заявлено и доказано в главе 2.3.1 « Векторные булевы функции для криптографии» как Предложение 2:
(N, m) -функция сбалансирована тогда и только тогда, когда ее составляющие функции сбалансированы, то есть тогда и только тогда, когда для любого ненулевого v ∈ $F^2_m$, булева функция v · F сбалансирована.
с дополнительным фактом из главы 2.3:
сбалансированные (n, n) -функции - это перестановки на $F^2_n$
Итак, (n, n) -функция является перестановкой, если и только если она сбалансирована согласно приведенному выше определению.
Другими словами, должна быть сбалансирована каждая функция компонента, а также любая возможная комбинация функций компонента, в т.ч. все функции одновременно, должны быть сбалансированы.
Между прочим, это свойство также заявлено, менее очевидно, в Стратегиях проектирования шифров и хэш-функций, основанных на линейном и дифференциальном криптоанализе, Теорема 5.1 1995 г.
Это также означает, что проверка этого свойства в общем случае для более крупных функций, например шириной 64 бита (n = 64), неосуществима, так как это потребует проверки сбалансированности для 2 ^ 64 - 1 различных комбинаций (для 2 ^ 64 возможных входов каждая). . Так что, скорее всего, потребуются некоторые уловки или ярлыки.