Tham gia Đăng nhập
Điểm:2
caveman avatar Crypto

$(a+b) \bmod{256}$ và $a$ XOR $b$ tiết lộ điều gì về $a, b$?

lá cờ in
caveman

Nói $a$ và $b$ là một số thống nhất ngẫu nhiên $8$ bit sao cho entropy của $a$ và $b$ là 8 bit mỗi.

Nếu tôi chỉ cho bạn $(a+b) \bmod{256}$ và $a$ XOR $b$, sau đó bạn có thể nói gì về $a$ và $b$? Hoặc bao nhiêu entropy của họ bị giảm?

202
0 + 0
xor
Điểm:5
poncho avatar Crypto
lá cờ my
poncho

fgrieu phân tích trường hợp trung bình; chúng ta cũng có thể xem xét trường hợp xấu nhất - chúng ta đảm bảo còn lại bao nhiêu entropy.

Một 'trường hợp xấu hơn' xảy ra nếu $a+b = 0 \pmod {256}$ và $a \oplus b = 0$; trong trường hợp đó, các giải pháp khả thi duy nhất là $a=b=0$ và $a=b=128$; do đó chúng tôi đã giảm entropy xuống 1 bit.

Tổng quát hơn, trường hợp xấu hơn này xảy ra nếu $a \oplus b = 0$ hoặc $a \oplus b = 128$; bất cứ khi nào điều đó xảy ra, chỉ có hai giải pháp khả thi, cụ thể là (trong trường hợp $a \oplus b = 0$, chúng tôi có một trong hai $a = b = tổng/2$ (ở đâu $sum$ là tổng đã công bố, sẽ luôn là số chẵn) hoặc $a = b = tổng/2 + 128$; trong trường hợp $a \oplus b = 128$, chúng ta có $a, b = tổng/2, tổng/2 + 128$ theo thứ tự nào đó.

Chúng tôi lưu ý rằng, đối với bất kỳ $a, b$, các giá trị thay thế $a \oplus 128, b \oplus 128$ luôn đưa ra xor và sum giống nhau, do đó luôn có ít nhất hai giải pháp - do đó trường hợp xấu này là trường hợp xấu hơn.

0 + 0
Điểm:4
avatar Crypto
lá cờ cn
j.p.

Vì tôi chưa thấy nó được đề cập: $a + b = (a\oplus b) + ((a\&b)<<1) \bmod 256$ (ở đâu $<<$ biểu thị dịch trái), vì vậy thông tin bạn được cung cấp tương đương với việc biết $a\oplus b$ và - ngoại trừ bit cao nhất - $a\&b$.

Tất cả các chức năng $a+b$, $a\oplus b$ và $a\&b$ đối xứng trong $a$ và $b$. Đối với một vị trí bit cố định $i$ do đó, bạn nhiều nhất có thể biết có bao nhiêu trong số hai bit $a_i$ và $b_i$ là 1, nhưng nếu chỉ có một, thì bạn không biết cái nào.

Đối với tất cả trừ các bit cao nhất mà bạn biết $a_i\&b_i$ và $a_i\oplus b_i$, đó chỉ là các chữ số nhị phân của $a_i+b_i$, vì vậy bạn có cho mọi vị trí bit (nhưng cao nhất) chính xác là số đếm 0/1. Đối với vị trí bit cao nhất bạn vừa có $a_7\oplus b_7$.

Từ đó, bạn sẽ có thể rút ra kết quả của poncho và fgrieu.

0 + 0
Điểm:4
fgrieu avatar Crypto
lá cờ ng
fgrieu

Tôi sẽ cho rằng các chuỗi bit được đồng hóa với các số nguyên bằng ký hiệu big-endian, $a$ và $b$ là $k$-bit với $k=8$ trong câu hỏi, và nó được đưa ra hai $k$số lượng -bit $s:=a+b\bmod{2^k}$ và $x:=a\oplus b$.

$s$ và $x$ không độc lập: bit bậc thấp của chúng giống nhau. Do đó tiết lộ $(s,x)$ tiết lộ nhất $2k-1$ một chút thông tin, do đó gây ra nhất một $2k-1$ giảm bit của entropy.

kể từ khi đưa ra $a$ và $x$ chúng ta có thể tính toán $b=a\oplus x$, để lộ $(s,x)$ nguyên nhân ít nhất một $k$ giảm bit của entropy.

Mức giảm thực tế của entropy khác nhau giữa các giới hạn sau:

  • Với $x=0$ và $s$ thậm chí, các giải pháp là $(a,b)\in\{(s/2,s/2),(s/2+2^{k-1},s/2+2^{k-1})\}$, do đó vẫn còn $\log_2(2)=1$ một chút entropy ra khỏi ban đầu $2k$, mất mát $2k-1$ bit của entropy.
  • Với $x=s=1$ có 4 giải pháp: $(a,b)\in\{(0,1),(1,0),(2^{k-1},2^{k-1}+1),(2^{k-1} +1,2^{k-1})\}$, do đó vẫn còn $\log_2(4)=2$ một chút entropy ra khỏi ban đầu $2k$, mất mát $2k-2$ bit của entropy.
  • Với $x=s=2^{k-1}$ có $2^k$ giải pháp của hình thức $(a,2^k-1-a)$, do đó vẫn còn $k$ một chút entropy ra khỏi ban đầu $2k$, mất mát $k$ bit của entropy.

Tôi khẳng định mà không cần bằng chứng rằng đối với $i\in[0,k)$ mất mát entropi là $2k-1-i$ bit với xác suất ${k-1\choose i}/2^{k-1}$, và nó tuân theo tổn thất entropy dự kiến ​​là $(3k-1)/2$ chút.

0 + 0
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.