LFSR 夠用嗎？
考慮以下實驗：
假設有一台機器執行（即連續計時）一個大小（即位數）的LFSR $ b $ ，有一個按鈕，當按下時，提取下一個 $ t $ 來自 LFSR 的位，將它們列印到紙質票上，將票存入一個密封的、不透明的甕中，並補充 LFSR 中的每一位（為了爭論，忽略 LFSR 重置為全零的情況）；之後機器繼續正常執行。
現在把這台機器放在一個房間裡，與外界完全隔離，並有一個編號（比如 $ n $ ) 的玩家排成一列，一個一個地走進房間並按下按鈕。畢竟 $ n $ 他們完成了，取回密封的骨灰盒。
LFSR 的回饋多項式、初始狀態和時鐘頻率是公共參數，數字也是 $ b $ 和 $ t $ .
現在有一個攻擊者，其目的是將骨灰盒中的至少一張票與其中一名玩家匹配。攻擊者可以訪問所有公共參數，知道玩家排隊的順序，可以測量每個人**進入房間的時間（但顯然不能準確知道玩家何時按下按鈕，因為這發生在孤立的房間），並且可能與一小部分玩家勾結以實現其目標。
那麼，問題是：
- 哪些參數（即。 $ b $ , $ t $ , $ q $ ，時鐘頻率有點棘手）可以確保攻擊者沒有比猜測更多的成功機會嗎？
- 用 ASG 替換 LFSR 會更好嗎？更糟？
**關於時鐘頻率的說明：**由於技術原因，時鐘頻率被迫相對較低，例如不超過 2kHz（即每千分之二秒一個時鐘脈衝）。
**關於共謀以及玩家可以做什麼和不可以做什麼的說明：**可以假設玩家擁有他們選擇的計時設備，並具有他們認為合適的準確性（如果這被證明是一個過於強大的優勢，一個非常感謝有限制的分析！）；玩家看不到他們得到的數字（他們實際上並沒有得到它本身，因為數字進入了骨灰盒）。
這一切背後的基本原理是，我們試圖從 LFSR 生成真正的隨機數：要利用的隨機變數是按下按鈕的時間，LFSR 只是為了混淆生成的值; 如果使用自實驗開始以來的秒數，攻擊者可以輕鬆地將門票與玩家匹配；如果在沒有補充的情況下使用 LFSR，攻擊者可以根據 LFSR（所有參數都是公開的）生成它們的順序來比較它們；我相信（絕對沒有根據！）每次提取後進行補充可以解決問題。
英語不是我的母語，如果我說得不夠清楚，我很抱歉，如果需要，請務必要求澄清。
這不是家庭作業，看起來很艱難：）
**編輯：**在答案中不止一次提到知道這麼多並且能夠做這麼多，給了攻擊者太多的權力，所以我決定將 LFSR 的初始狀態設為機密。現在上面解釋的最後一段應該是：
LFSR 的回饋多項式和時鐘頻率是公共參數，數字也是 $ b $ 和 $ t $ . LFSR 的初始狀態是秘密的，攻擊者不知道。
這是一種攻擊，我認為以極好的機率可以確定勾結玩家的票證上的價值；因此，在猜測這些勾結玩家的門票時有優勢，而在猜測誠實玩家的門票時有（通常較小的）優勢。我假設：
- 對手知道每張票的價值（由評論確認），在票的方向上沒有歧義。
- 不知道 LFSR 的初始狀態（如現在明確的那樣）。
- 所有玩家都隨意按下他們的按鈕，當確切的時刻未知時，這會部分地重新播種 LFSR。
- 對手知道確切的時間 $ m $ 連續玩家按下按鈕（因為這些 $ m $ 玩家與對手勾結），因此在這些壓力機之間究竟有多少 LFSR 步驟；這允許攻擊者將 LFSR 在共謀玩家按鍵時的狀態表達為第一個共謀玩家按下按鈕時（假設未知）狀態的線性函式。
- $ n $ 足夠低以至於對手可以對每個（最多）執行一些處理 $ n!/(n-m)! $ 共謀玩家的不同價值順序（ $ n=15 $ , $ m=10 $ 意味著關於 $ 11\cdot10^9 $ 訂單將被考慮，並且非常可行）。
- $ t $ 足夠大，很可能這些訂單中只有一個與線性函式匹配；有 $ b $ 未知位， $ (n-1)\cdot t $ 已知位，因此通過熵參數（基於模糊且未經證實的假設，即玩家的隨意行為使線性方程組不起眼），通常應該有一個可能的值順序 $$ m\cdot t\gg b+\log_2(n!/(n-m)!) $$
然後很容易檢查候選訂單，並推斷出 $ b $ 位的初始狀態。只需插入 $ m={2\over3}n $ 為了 $ 2\over3 $ 的玩家勾結。
此外，如果誠實玩家何時按下的不確定性（假設在與 $ u $ 步驟，每個頻率的時間乘積）是這樣的 $ u\ll2^t/(n-m) $ ，我們經常可以在開票前後立即猜出其他玩家的票的（價值） $ m $ 勾結玩家；甚至他們所有人，如果 $ u\ll2^t/(n-m)! $ 或者那個曲子上的東西。
進一步（正如 NSA 所說的那樣，並通過此答案的第 5 版的顯著改進來說明）：攻擊只會變得更好；他們永遠不會變得更糟。特別是，我沒有充分利用可以從誠實玩家門票的已知價值中獲得的資訊，如果 $ u\ll2^t $ ; 或許多參數可能會加速以顯著減少 $ n!/(n-m)! $ 探索；或者當勾結玩家在選定的時刻而不是在隨機但已知的時刻按下時可以實現哪些改進。
上述內容並未給出保證對手無法成功的條件。以下是對此的一些想法。我會認為 LFSR 是最大長度（有句點 $ 2^b-1 $ , 或等效地使用原始多項式並且永遠不會全為零）；並且當 LFSR 為一體時發生的按鍵會列印一張一體的票，但會使 LFSR 就像沒有發生按鍵一樣。
假設玩家完全停留 $ u=2^b-1 $ 房間裡的時鐘週期，並考慮 4 個變數
- LFSR 狀態 $ I $ 在入口處
- LFSR 狀態 $ P $ 通過按鍵採樣（其中 $ t $ 在……之外 $ b $ 位被列印）
- LFSR 狀態 $ O $ 退出時
- 時鐘週期數 $ w $ 在入口和按鍵之間，與 $ 0\le w<2^w $
它認為 $ P=M^w\cdot I $ 和 $ \hat P=M^w\cdot O $ ， 在哪裡 $ \hat P $ 是按位補碼 $ \bar P $ 的 $ P $ 除了全1不變；和 $ M $ 是個 $ b\times b $ 稀疏矩陣對應於將 LFSR 推進一步。當任何一個 $ I $ $ P $ $ O $ $ w $ 是固定的，這些關係定義了從其他三個變數中的任何一個到最後兩個變數中的任何一個的一對一映射。注意：當 $ w $ 是未知的，找到它（或 $ P $ 如果也是未知的）似乎是一個離散對數問題；我認為對手能夠解決這個問題。
因此，當一個誠實的玩家在房間裡停留的時間比 $ 2^b-1 $ 時鐘週期，攻擊者只知道進入或退出時的 LFSR 狀態之一，
- 這些狀態中的其他狀態與均勻隨機的非零變數無法區分，
- 票上列印的值與隨機抽樣具有相同的分佈（全零，賠率 $ 2^{b-t}-1\over2^b-1 $ , 任何其他 $ 2^t-1 $ 賠率更高的值 $ 2^{b-t}\over2^b-1 $ ).
然而，上述兩個未知數密切相關。
如果我們將 LFSR 視為一個熵池，
- 一個誠實的球員在房間裡待的時間比 $ 2^b-1 $ 時鐘週期將熵池重新填充到其全部容量 $ c=\log_2(2^b-1) $ 少量
- 然而，對一張票的價值的了解最多只能顯示 $ r=\log_2(2^b-1)-\log_2(2^{b-t}-1) $ 一點資訊什麼時候 $ t<b $ （當列印的值全為零時會發生這種情況），或 $ r=\log_2(2^b-1) $ 有點什麼時候 $ t=b $ （列印的值不能全為零）。
據此**，我初步推測，除了非常小的 $ b $ , 對手的優勢可以忽略不計，如果至少 $ h $ 誠實的球員，他們每個人在房間里呆的時間都比 $ 2^b-1 $ 期間，站在與對手勾結的任何兩名玩家之間，並且**
$$ h\cdot c\ge (h+1)\cdot r \text{ , that is } t<b \text{ and } (h+1)\cdot\log_2(2^{b-t}-1)\ge\log_2(2^b-1) $$ 條件構造為：在一系列 $ h+1 $ 玩家，至少注入的熵與揭示所有門票價值消耗的一樣多。我的直覺是，這種情況足以讓對手在玩家按下一個鍵時無法了解更多關於 LFSR 狀態的資訊，而不是相應票值的知識所揭示的資訊，並且/因此無法判斷一個假設是否票屬於誰或多或少的可能性。
如果我知道第一個玩家按下按鈕的初始狀態和時間視窗，我可以執行 LFSR 直到並通過那個時間視窗。第一個玩家的令牌將匹配其中一個狀態，這意味著您知道玩家 1 離開後的 LFSR 狀態。您可以重複此操作以找到玩家 2 的標記，因為應用反轉會為您提供輪到玩家 2 之前的初始狀態。您還知道玩家 1 按下按鈕的確切時間。
狀態反轉將 LFSR 從其循環中的一個位置“跳轉”到另一個位置，因此甕可能有兩個標記對應於玩家時間視窗內發生的 LFSR 狀態。如果玩家數量少而狀態大，這是不太可能的。如果確實發生了，我們可以通過玩家的整個時間視窗對 LFSR 進行計時來檢測它，然後我們必須遵循兩種可能的初始狀態來找到下一個玩家的令牌。
這些分析都沒有使用系統使用 LFSR 的事實。如果我們知道它的所有初始狀態，任何確定性 PRNG 都會有這個問題。
如果我們不知道初始狀態，那麼隨時重建狀態會有點困難。但是您可以將 LFSR 狀態設置為令牌的狀態並向前和向後執行它。它的狀態最終將匹配另一個令牌，此時您反轉並繼續前進。這樣，您可以將令牌按順序連結在一起，並將它們與玩家匹配。
請注意，這僅適用於令牌代表整個 LFSR 狀態。如果令牌是狀態的加密版本，這是不可能的，如果它只是狀態的一部分，那就更困難了。