Cryptanalysis
做什麼(a+b)模256(一個+b)反對256(a+b) bmod{256}和一個一個a異或bbb透露一下甲,乙一個,ba, b?
說 $ a $ 和 $ b $ 是一些均勻隨機的 $ 8 $ 位使得熵 $ a $ 和 $ b $ 每個是 8 位。
如果我給你看 $ (a+b) \bmod{256} $ 和 $ a $ 異或 $ b $ , 那你能說什麼 $ a $ 和 $ b $ ? 或者他們的熵減少了多少？
我假設位串通過大端符號被同化為整數， $ a $ 和 $ b $ 是 $ k $ -位與 $ k=8 $ 在問題中，它給出了兩個 $ k $ 位數量 $ s:=a+b\bmod{2^k} $ 和 $ x:=a\oplus b $ .
$ s $ 和 $ x $ 不是獨立的：它們的低位是相同的。因此揭示 $ (s,x) $ 最多暴露 $ 2k-1 $ 位資訊，因此最多導致 $ 2k-1 $ 熵的位減少。
既然給了 $ a $ 和 $ x $ 我們可以計算 $ b=a\oplus x $ ， 揭示 $ (s,x) $ 導致至少一個 $ k $ 熵的位減少。
熵的實際減少在這些界限之間變化：
- 和 $ x=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 $ 一點點的熵。
- 和 $ x=s=1 $ 有4個解決方案： $ (a,b)\in{(0,1),(1,0),(2^{k-1},2^{k-1}+1),(2^{k-1}+1,2^{k-1})} $ ，因此還有 $ \log_2(4)=2 $ 最初的熵 $ 2k $ , 損失 $ 2k-2 $ 一點點的熵。
- 和 $ x=s=2^{k-1} $ 有 $ 2^k $ 形式的解決方案 $ (a,2^k-1-a) $ ，因此還有 $ k $ 最初的熵 $ 2k $ , 損失 $ k $ 一點點的熵。
我在沒有證據的情況下斷言 $ i\in[0,k) $ 熵損失是 $ 2k-1-i $ 有機率的位 $ {k-1\choose i}/2^{k-1} $ ，並且它遵循預期的熵損失是 $ (3k-1)/2 $ 少量。