LFSR 是否足以對有偏差的 TRNG 進行後處理？
我正在基於環形振盪器的 FPGA 上建構 TRNG。我發現線性回饋移位寄存器 (LFSR) 通常用於 TRNG 的後處理。這是我最初的設計：
假設 TRNG 核心模組產生了一個有偏差的輸出（例如，1 多於 0，或者值更可能在樣本之間轉換）。LFSR 是否足以消除輸入的偏差？使案例如馮諾依曼提取器使輸入無偏是否有益？
一個相關的問題是——由於有偏差的輸入具有較少的熵——LSFR 是否能夠通過執行更多的移位來提取隨時間推移的隨機性？如果是，我們如何估計必須從弱隨機熵源饋送到 LFSR 以獲得強輸出的比特數量？
編輯： Clk是一個較慢的時鐘，與環形振盪器的振盪速度無關。
我假設問題圖中正確的 16 是告訴 LFSR 一次解除安裝 16 位；除非另有說明，否則我將假設 LFSR 每 16 個時鐘週期完成一次。
LFSR 是否足以消除輸入的偏差？
大多數情況下是的，但這在加密貨幣中還不夠。對於知道系統設計（這裡，有一個 16 位 LFSR，甚至是哪個）的對手，希望使輸出與隨機（不僅僅是無偏）無法區分。這是根據Kerckhoffs 的（第二個）原則。
LFSR 是否足以對有偏差的 TRNG 進行後處理？
肯定 no，在未指定的加密上下文中，並假設充分使用輸出（見第一段）。
問題是從 LFSR 的輸出，它的設計（主要是回饋多項式），也許它是初始狀態（見下文），返回 LFSR 的確切輸入是微不足道的，並從中利用偏差為區分者。如果 LFSR 輸出用於關鍵的事情（例如生成 One Time Pad），那可能是一場災難。
如果 LFSR 處於“加擾器”配置，攻擊者可以將 LFSR 的輸出饋送到相應的“解擾器”中，這將輸出加擾器的輸入。如果解擾器與擾頻器同步開始，或者在前 16 位之後（否則為和 $ n $ -bit LFSR 自同步後 $ n $ 位）。換句話說，對手可以應用的解擾器技巧會撤銷問題生成器中的 LFSR 所做的，因此 LFSR 是不夠的。
如下圖所示。圖片頂部是問題的 LFSR，簡化（串列輸出加擾， $ n=4 $ 階段）。底部是解擾器，由攻擊者添加/模擬。應該很明顯，之後 $ n=4 $ 時鐘，底部電路與頂部電路同步，解擾的是輸入，具有任何可檢測的偏差。
如果 LFSR 處於其他配置（解擾器或“加擾器”），如果在上下文中不知道（例如復位時為零），攻擊者需要猜測 LFSR 的初始狀態。即使沒有線索，攻擊仍然很容易：只有 $ 2^{16} $ 可能的初始狀態，我們可以選擇任何一個為重構輸入提供最明顯的偏差，再次使 LFSR 不夠。
對於有效但仍然只使用相對較小的 LFSR 的東西，我們希望在加擾器配置中對 LFSR 的輸出進行嚴重欠採樣（“抽取”）；例如，在 64 位中保留一個輸出位（幾乎等效地，每 1024 個時鐘而不是 16 個時鐘解除安裝 LFSR 的 16 位）。總體構想是在輸出之間的 LFSR 中收集/混合熵。輸出質量和輸出速率之間存在權衡，由欠採樣/抽取率控制。
關於抽取多少太少有一個簡單的理論：如果有 $ h<1 $ 採樣器中每比特的熵，然後小於 $ 1/h $ 進入 LFSR 階段的每個位輸出的位太少。因此，如果在實驗中我們擷取採樣器的輸出並將其提供給像 bzip2 這樣的無損壓縮器，它的壓縮係數為 $ c $ （例如 $ c=4 $ 對於 100MiB 壓縮到 25MiB），然後任何抽取小於 $ c=4 $ LFSR 階段的一位採樣位太少。此外，如果在採樣器的輸出我們有平均位 $ a\ne1/2 $ , 任何小於 $ c=-1/(a\log_2(a)+(1-a)\log_2(1-a)) $ 太少了（注意這個公式沒有考慮位之間的相關性，因此除了極有偏差的輸入之外幾乎沒有用）。
不幸的是，對於抽取多少就足夠了，或者 LFSR 大小有多重要，我沒有簡單的理論！如果 LFSR 是調節採樣器輸出的唯一方法，或者（更好）保守並使用 LFSR 播種加密安全偽隨機數生成器，則標準建議是非常保守的，最終使用該輸出。另請參閱關於需要檢測現場故障的最後一段。
我希望我確切地知道加擾器模式下 LFSR 上的什麼條件（如果有）是必要的，以確保輸出中沒有長期偏差（假設從輸出到輸入沒有回饋，並且輸入中的獨立位
$$ or even much weaker and plausible assumptions $$）。但即使是擾頻器配置中的 1 級 LFSR（回饋多項式 $ x+1 $ ，單 D 門，2 輸入 XOR，包括輸入）做到了。隨後進行大量抽取，這是最簡單的正確 RNG 後處理之一。
使案例如馮諾依曼提取器使輸入無偏是否有益？
很可能這將是有益的。如果採樣器輸出的位是獨立的，它甚至可以完美地工作。但
- 如果沒有這種保險，可能仍然存在可檢測的偏差。
- 輸出速率變得不規則，沒有最小值，這可能是一個嚴重的問題¹。
第一個問題可以通過級聯幾個馮諾依曼提取器來解決，但每個狀態都會將平均通過輸出減半，並使第二個問題惡化。加擾器配置中的 LFSR 隨後進行大量欠採樣更加穩健，並且至少吞吐量是可預測的。
請注意，設計加密安全真隨機數發生器最困難的部分不是讓它在工作時變得安全²，而是檢測它何時不能按預期工作（比如因為攻擊者倒了液氮，或者只是墨菲定律的一些平凡推論） ，從而使整體 Gizmo 保持安全。
¹ 我曾經參與找出為什麼某些智能卡接受設備有時會在現場被某種類型的卡阻塞，從而導致代價高昂的後果。在超時之後，接收設備最終對 ISO/IEC 7816-3 協議中的故障反應過度：卡有時太慢而無法響應。根據智能卡製造商的說法，這是由於馮諾依曼提取器引起的隨機操作延遲（我懷疑這是卡不當行為的全部故事，但相信它涉及不規則的 RNG 吞吐量）。
² 還是很難！許多潛在問題包括從條件輸出到源/採樣器的不需要的回饋迴路。
