înregistrare Logare
Puncte:2
caveman avatar Crypto

Ce dezvăluie $(a+b) \bmod{256}$ și $a$ XOR $b$ despre $a, b$?

drapel in
caveman

Spune $a$ și $b$ sunt unele aleatorii uniforme $8$ biți astfel încât entropia de $a$ și $b$ este de 8 biți fiecare.

Daca iti arat $(a+b) \bmod{256}$ și $a$ XOR $b$, atunci despre ce poți spune $a$ și $b$? Sau cât de mult din entropia lor este redusă?

202
0 + 0
xor
Puncte:5
poncho avatar Crypto
drapel my
poncho

fgrieu analizeaza cazul mediu; putem lua în considerare, de asemenea, cel mai rău caz - cât de mult entropia ne este garantat că ne rămâne.

Un „caz mai rău” se întâmplă dacă $a+b = 0 \pmod {256}$ și $a \oplus b = 0$; în acest caz, singurele soluții posibile sunt $a=b=0$ și $a=b=128$; prin urmare, am redus entropia la 1 bit.

Mai general, acest caz mai grav se întâmplă dacă $a \oplus b = 0$ sau $a \oplus b = 128$; ori de câte ori se întâmplă acest lucru, există doar două soluții posibile, și anume (în cazul $a \oplus b = 0$, avem fie $a = b = suma/2$ (Unde $sum$ este suma publicată, care va fi întotdeauna pare) sau $a = b = suma/2 + 128$; În cazul în care $a \oplus b = 128$, avem $a, b = suma/2, suma/2 + 128$ într-o oarecare ordine.

Remarcăm că, pentru orice $a, b$, valorile alternative $a \oplus 128, b \oplus 128$ dați întotdeauna același xor și sumă, deci există întotdeauna cel puțin două soluții - de aceea acest caz prost este cel mai rău caz.

0 + 0
Puncte:4
fgrieu avatar Crypto
drapel ng
fgrieu

Voi presupune că șirurile de biți sunt asimilate numerelor întregi prin notație big-endian, $a$ și $b$ sunt $k$-biti cu $k=8$ în întrebare și i se dă două $k$-cantități de biți $s:=a+b\bmod{2^k}$ și $x:=a\oplus b$.

$s$ și $x$ nu sunt independente: bitul lor de ordin inferior este același. De aceea revelatoare $(s,x)$ dezvăluie cel mult $2k-1$ un pic de informație, deci cauza cel mult A $2k-1$ reducerea pe biți a entropiei.

De când dat $a$ și $x$ putem calcula $b=a\oplus x$, revelatoare $(s,x)$ cauză macar A $k$ reducerea pe biți a entropiei.

Reducerea reală a entropiei variază între aceste limite:

  • Cu $x=0$ și $s$ chiar și, soluțiile sunt $(a,b)\in\{(s/2,s/2),(s/2+2^{k-1},s/2+2^{k-1})\}$, deci rămâne $\log_2(2)=1$ un pic de entropie din inițială 2k$, o pierdere de $2k-1$ biți de entropie.
  • Cu $x=s=1$ sunt 4 solutii: $(a,b)\in\{(0,1),(1,0),(2^{k-1},2^{k-1}+1),(2^{k-1} +1,2^{k-1})\}$, deci rămâne $\log_2(4)=2$ un pic de entropie din inițială 2k$, o pierdere de $2k-2$ biți de entropie.
  • Cu $x=s=2^{k-1}$ Sunt $2^k$ solutii de forma $(a,2^k-1-a)$, deci rămâne $k$ un pic de entropie din inițială 2k$, o pierdere de $k$ biți de entropie.

Afirm fără dovezi că pt $i\în[0,k)$ pierderea de entropie este $2k-1-i$ bit cu probabilitate ${k-1\alegeți i}/2^{k-1}$, și că urmează pierderea de entropie așteptată este $(3k-1)/2$ pic.

0 + 0
Puncte:4
avatar Crypto
drapel cn
j.p.

Cum nu am vazut inca mentionat: $a + b = (a\oplus b) + ((a\&b)<<1) \bmod 256$ (Unde $<<$ denotă deplasarea la stânga), astfel încât informațiile care vi se oferă este echivalentă cu cunoașterea $a\oplus b$ și - cu excepția bitului cel mai înalt - $a\&b$.

Toate funcțiile $a+b$, $a\oplus b$ și $a\&b$ sunt simetrice în $a$ și $b$. Pentru o poziție fixă ​​a biților $i$ puteți deci să știți cel mult câți dintre cei doi biți $a_i$ și $b_i$ sunt 1, dar dacă este doar unul, atunci nu știi care.

Pentru toate, cu excepția celor mai înalte părți pe care le cunoașteți $a_i\&b_i$ și $a_i\oplus b_i$, care sunt doar cifrele binare ale $a_i+b_i$, deci aveți pentru fiecare poziție de bit (dar cea mai mare) exact numărul 0/1. Pentru cea mai înaltă poziție de biți pe care o aveți $a_7\oplus b_7$.

Din aceasta ar trebui să puteți obține rezultatele poncho și fgrieu.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.