什麼是輸出符號？
我正在閱讀 Christof Paar 和 Jan Pelzl 的《理解密碼學》。在第 2 章（流密碼）中。有一節討論“從 PRNG 建構密鑰流”。
他們假設一個基於線性同餘生成器的 PRNG：
$$ S_0 = seed $$ $$ S_{i+1} \equiv AS_i + B\mod m, i=0,1,… $$
我們選擇 m 為 100 位長並且 $ S_i,A,B \in {0,1,…,m-1}. $ 請注意，如果我們仔細選擇參數，此 PRNG 可以具有出色的統計特性。模數 m 是加密方案的一部分並且是眾所周知的。密鑰包含值 (A,B) 和可能的種子 S0，每個長度為 100。這為我們提供了 200 位的密鑰長度，這足以防止暴力攻擊。由於這是一個流密碼，Alice 可以加密：
$$ y_i \equiv x_i + s_i \mod 2 $$
在哪裡 $ s_i $ 是 PRNG輸出符號的二進製表示的位 $ S_j $
但奧斯卡可以輕鬆發動攻擊。假設他知道明文的前 300 位（這只是 300/8=37.5 字節），例如文件頭資訊，或者他猜測明文的一部分。因為他當然知道密文，所以他現在可以將密鑰流的前 300 位計算為：
$$ s_i \equiv y_i + x_i \mod m , i = 1,2,…,300 $$
這 300 位立即給出PRNG的前三個輸出符號： $ S_1 = (s_1,…,s_{100}), S_2 = (s_{101},…,s_{200}) $ 和 $ S_3 = (s_{201},…,s_{300}). $
（強調我的）
我的問題是：
- 什麼是輸出符號？
- 我們如何確定輸出符號（位數等）
什麼是輸出符號？
輸出符號是 PRNG 輸出的基本“單位”。密鑰流本身由整數個符號組成。如果 PRNG 輸出位（如 LFSR），則符號是單個位。如果 PRNG 輸出八位字節（如 RC4），則符號是范圍內的整數 $ [0,255] $ .
我們如何確定輸出符號（位數等）
如果你有 $ n $ 可能的符號，則單個符號由 $ \log_2(n) $ 位。通常，PRNG 的輸出符號數是 2 的冪。情況可能並非總是如此。如果 PRNG 輸出具有 26 種不同可能性的字母數字元號，那麼每個符號將保持 $ \log_2(26) \approx 4.7 $ 位的資訊。將這樣的符號表示為範圍內的整數可能會更好 $ [0,26] $ 而不是將其表示為小數位數。
問題中的範例 PRNG 指定了符號 $ S_i \in {0,1,\dots m-1} $ 並另外指定 $ m=100 $ . 這意味著該 PRNG 的符號是一個 100 位的值，儘管它也可以表示為該範圍內的單個整數 $ [0,2^{100}) $ .