Регистрация Войти
Рейтинг:2
caveman avatar Crypto

Что $(a+b) \bmod{256}$ и $a$ XOR $b$ раскрывают относительно $a, b$?

флаг in
caveman

Сказать $а$ и $b$ некоторые равномерные случайные $8$ битов так, что энтропия $а$ и $b$ составляет 8 бит каждый.

если я покажу тебе $(а+б) \bmod{256}$ и $а$ исключающее ИЛИ $b$, то что вы можете сказать о $а$ и $b$? Или насколько уменьшается их энтропия?

202
0 + 0
xor
Рейтинг:5
poncho avatar Crypto
флаг my
poncho

fgrieu анализирует средний случай; мы также можем рассмотреть наихудший случай — сколько энтропии у нас гарантированно останется.

Один «худший случай» происходит, если $a+b = 0 \pmod {256}$ и $а \оплюс б = 0$; в этом случае единственными возможными решениями являются $а=б=0$ и $а=б=128$; следовательно, мы уменьшили энтропию до 1 бита.

В более общем случае этот худший случай происходит, если $а \оплюс б = 0$ или же $а\оплюс б = 128$; всякий раз, когда это происходит, есть только два возможных решения, а именно (в случае $а \оплюс б = 0$, у нас есть либо $a = b = сумма/2$ (куда $сумма$ это опубликованная сумма, которая всегда будет четной) или $a = b = сумма/2 + 128$; в случае $а\оплюс б = 128$, у нас есть $a, b = сумма/2, сумма/2 + 128$ в некотором порядке.

Отметим, что для любого $а, б$, альтернативные значения $a \oplus 128, b \oplus 128$ всегда дают один и тот же xor и сумму, поэтому всегда есть как минимум два решения - следовательно, этот плохой случай - худший случай.

0 + 0
Рейтинг:4
avatar Crypto
флаг cn
j.p.

Поскольку я еще не видел, чтобы это упоминалось: $a + b = (a\oplus b) + ((a\&b)<<1) \bmod 256$ (куда $<<$ обозначает сдвиг влево), поэтому полученная вами информация эквивалентна знанию $а\оплюс б$ и - кроме старшего бита - $а\&б$.

Все функции $а+б$, $а\оплюс б$ и $а\&б$ симметричны в $а$ и $б$. Для фиксированной позиции бита $я$ поэтому вы можете самое большее знать, сколько из двух битов $a_i$ и $b_i$ 1, но если это только один, то вы не знаете, какой именно.

Для всех, кроме самых высоких битов, которые вы знаете $a_i\&b_i$ и $a_i\oplus b_i$, которые являются просто двоичными цифрами $a_i+b_i$, поэтому у вас есть для каждой битовой позиции (кроме самой высокой) ровно 0/1-счетчик. Для старшей битовой позиции у вас просто есть $a_7\oplus b_7$.

Из этого вы сможете получить результаты пончо и фгрие.

0 + 0
Рейтинг:4
fgrieu avatar Crypto
флаг ng
fgrieu

Я предполагаю, что битовые строки уподобляются целым числам с помощью записи с обратным порядком байтов, $а$ и $b$ находятся $к$-биты с $к=8$ в вопросе, и ему дано два $к$-битные количества $s:=a+b\bmod{2^k}$ и $х:=а\оплюс б$.

$s$ и $х$ не являются независимыми: их младший бит одинаков. Поэтому выявление $(с,х)$ показывает в большинстве $2k-1$ бит информации, таким образом вызывая в большинстве а $2k-1$ битовое уменьшение энтропии.

Поскольку дано $а$ и $х$ мы можем вычислить $b=а\оплюс х$, выявление $(с,х)$ причина по меньшей мере а $к$ битовое уменьшение энтропии.

Фактическое уменьшение энтропии варьируется в следующих пределах:

  • С $х=0$ и $s$ даже решения есть $(a,b)\in\{(s/2,s/2),(s/2+2^{k-1},s/2+2^{k-1})\}$, таким образом остается $\log_2(2)=1$ немного энтропии из начального $2k$, потеря $2k-1$ биты энтропии.
  • С $х=s=1$ есть 4 решения: $(a,b)\in\{(0,1),(1,0),(2^{k-1},2^{k-1}+1),(2^{k-1} +1,2^{к-1})\}$, таким образом остается $\log_2(4)=2$ немного энтропии из начального $2k$, потеря $2k-2$ биты энтропии.
  • С $х=s=2^{к-1}$ Есть $2^к$ решения вида $(а,2^к-1-а)$, таким образом остается $к$ немного энтропии из начального $2k$, потеря $к$ биты энтропии.

Я бездоказательно утверждаю, что для $i\in[0,k)$ потеря энтропии $2k-1-i$ бит с вероятностью ${k-1\выберите i}/2^{k-1}$, и из этого следует, что ожидаемая потеря энтропии равна $(3k-1)/2$ кусочек.

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

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

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