Регистрация Войти
Рейтинг:1
Dominic van der Zypen avatar Crypto

Обратные операции $(a,b) \mapsto a \oplus b\oplus ((a \land b) \ll 1)$ для фиксированной битовой длины

флаг br
Dominic van der Zypen

Задний план. В их бумага о криптографической схеме NORX авторы используют быстрое приближение + с помощью побитовых операций (затрачивающих меньше циклов ЦП, чем правильное сложение) по формуле $$а+б \; \приблизительно\; a \oplus b \oplus ((a \land b) \ll 1)$$ куда $\оплюс$ является побитовым XOR и $\земля$ побитовое И, и $\ll$ сдвиг влево на 1 позицию. (Цель $((а \land b) \ll 1)$ заключается в моделировании операции переноса битов.)

Формулировка вопроса. Мы можем рассматривать это как операцию $+^{n}_\sim : \{0,1\}^n\times \{0,1\}^n \to \{0,1\}^n$, определяется $(a, b) \mapsto a \oplus b \oplus ((a \land b) \ll 1)$. За $b\in \{0,1\}^n$ мы получаем карту $s^n_b: \{0,1\}^n\to \{0,1\}^n$ определяется $$a \mapsto a +^{n}_\sim b.$$

Является $s^n_b$ инъективный (и, следовательно, биективный) для всех $n\in\mathbb{N}$ и $b\in \{0,1\}^n$?

57
0 + 0
kelalaka avatar
флаг in
kelalaka
Это полусумматор. Чтобы использовать его для n-бит, вам нужен Full-adder для распространения.
0
Ответить
poncho avatar
флаг my
poncho
Это вопрос домашнего задания?
1
Ответить
kelalaka avatar
флаг in
kelalaka
На самом деле, $s_b^n$ не совсем точно определен. Что происходит с последним переносом?
0
Ответить
Рейтинг:2
Daniel S avatar Crypto
флаг ru
Daniel S

Да, чтобы увидеть эту заметку, что $а$ можно вычислить побитово, начиная с младшего бита. Мы пишем $с$ за $а+^n_\sim б$ и $x_i$ для $я$й бит $х$. Обратите внимание, что: $$a_0=b_0\oplus c_0$$ $$a_i=b_i\oplus c_i\oplus (a_{i-1}\клин b_{i-1})$$ за $1\le i\le n-1$.

К сожалению, нет хорошей побитовой обратной функции преобразования 4-бит в 1-бит. $(b,c)\mapsto$ например $a_2$ является функцией $b_0$, $b_1$, $b_2$, $c_0$ и $c_1$.

0 + 0
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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