如何計算位操作中的 CPA 攻擊複雜度
我們的日常設備中使用了以下前向糾錯 FEC。但我添加了一個潛在的安全措施。
在 FEC 系統之一中，輸入是 $ K $ 位和輸出程式碼是 $ M $ 位在哪裡 $ M=3K $ . 另一端的合法使用者使用FEC解碼器得到正確的 $ K $ 位。
建議的安全性是，如果只有 $ N $ 在……之外 $ M $ 位被選擇以相同的順序進行傳輸 $ M $ 在某種程度上，接收器仍然可以成功解碼。的數量 $ N $ 位和那裡的位置 $ M $ 由具有非線性結構的偽隨機數生成器生成，由一個改變每個塊的鍵驅動 $ K $ .
FEC 解碼器只有在以下情況下才能解碼 $ N $ 並且位置是已知的，因此發送者處未選擇的位置由 $ M-N $ 少量 $ 0 $ 解碼前。攻擊者不知道密鑰，所以 $ N $ 所以他不會知道 $ M $ 和 $ K $ . 在這個系統中 $ K>500 $ 位和 PRNG 的長度 $ n=100 $ .
我們如何在這裡計算 CPA 攻擊可能性的數量？
答案將取決於一組比特的熵 $ M $ . 比方說 $ M $ 是一組全零位；在那種情況下，只有 $ 1 $ 您可以選擇的可能的位集 - 每個位置的每個位都為零。但是，如果您有一組隨機位 $ M $ 你會接近理想的安全性；理想的安全意義 $ m, P, (n-(n/2)) $ 暴力破解的可能關鍵。
我們如何計算理想的安全性：
我們知道為什麼要使用置換函式，但為什麼要使用 $ n-(n/2) $ ? 假設我們有一組隨機的字節，每個字節都是唯一的；我們的集合中少於 256 個字節，因此我們可以避免重複。可能的獨特狀態將變為 $ \infty $ 意義 $ m, P, (n-(n/\infty))=m, P, n $ . 但是，如果我們兩次獲取每個字節，我們最終會得到一半可能的唯一選擇集——對於我選擇的每個字節，我也可以選擇另一個字節並獲得相同的結果。因此，對於 $ n $ 重複的位將由 $ n / 2 $ 因為有 $ 2 $ 每個位的唯一可能狀態。對於字節集，它將定義為 $ n/256 $ 這意味著複雜性會我 $ m, P, (n-(n/256)) $ . 這是因為重複的頻率是基於可能的非重複狀態的數量。
因此，如果您希望該方案是安全的，您應該 $ M $ 盡可能隨機。非隨機值 $ M $ ，或者一個特別選擇為弱的值會削弱整個系統；如果 $ M $ 是全零，實際上是一個以 1 為基礎的系統，這意味著每個（只有一個狀態的位狀事物）只有 $ 1 $ 可能的狀態，給我 $ m, P, (n-(n/1))=m, P, 0=1 $ 可能的關鍵。
CPA 攻擊可能性：
如果攻擊者可以找到該值 $ N $ 對於 1 個街區，他們現在知道 $ n $ 位內 $ M $ . 如果他們對多個塊重複此操作，他們最終將獲得足夠的位來暴力破解其餘部分；所以註冊會計師的難度歸結為價值是否 $ N $ 可以從明文-密文關係中找出，這取決於您的 FEC 的具體情況。這同樣適用於已知明文攻擊。因此，如果（當且僅當）它對已知明文攻擊是安全的，您的系統將不會受到選擇明文攻擊。
更新：
我注意到一個錯誤，我忘記解釋重複位本身可以排列的事實。這顯著降低了可能狀態的數量。我已經相應地更新了公式，現在資訊應該是正確的。