除了 BMA 之外，還有哪些工具可以對 LFSR 進行逆向工程？
我有一個我似乎無法弄清楚的時間碼。我們使用 Berlekamp-Massey 算法成功解碼了其他用於相同目的的程式碼，但該程式碼似乎具有 110 的線性複雜度，這在任何方面都不實用。它也不能用 BMA 找到的 110 位不可約多項式來重構。只是前幾位是預期的，然後這些位似乎翻轉，即它們是預期位的倒數。
我是密碼學的初學者，目前不知道如何進行。是否有其他算法可以分析 LFSR（或類似的偽隨機序列）？或者有沒有人知道 BMA 在什麼條件下檢測到如此長的多項式？
目前尚不清楚“特定時間碼”究竟是什麼，但我將其理解為有限長度序列 $ s_0, s_1, \ldots, s_{N-1} $ 的 $ N $ 位。序列本身可能是由 LFSR 生成的，也可能不是——我們不知道——但我們希望找到一個（斐波那契）LFSR 來生成序列。
讓我們稍微設置一下舞台。長度的斐波那契 LFSR $ n $ 是一個數組 $ n $ 具有初始值的位 $$ (s_0, \quad s_1,\quad \ldots, \quad s_{n-2}, \quad s_{n-1}) $$和連續值 $$ (s_0, \quad s_1, \quad \ldots, \quad s_{n-2}, \quad s_{n-1})\ \downarrow\ (s_1, \quad s_2, \quad \ldots, \quad s_{n-1}, \quad s_n)\ \downarrow\ (s_2, \quad s_3, \quad \ldots, \quad s_n, \quad \quad s_{n+1})\ \downarrow\ \cdots \quad \cdots $$ 其中數組內容在每個步驟（時鐘週期）向左移動，以便從左端（LFSR輸出）掉下來的位是給定的序列，而顯示為在右側進入 LFSR的位 被計算為線性組合上一步中**某些LFSR 內容的（又名異或和） 。特別是，對於 $ i \geq 0 $ ，狀態轉移可以表示為 $$ \biggr(s_i, \quad s_{i+1}, \ldots, \quad s_{i+n-2}, \quad s_{i+n-1}\biggr)\ \downarrow\ \biggr(s_{i+1}, \quad s_{i+2}, \ldots, \quad s_{i+n-1}, \quad {\Large{\oplus}}{j=0}^{n-1}c{n-j} s_{i+j}\biggr), $$ 在哪裡 $ c_i $ 有值 $ 0 $ 或者 $ 1 $ , 使得線性組合 $ c_ns_i\oplus c_{n-1}s_{i+1} \oplus \cdots \oplus c_1s_{i+n-1} $ 之前的 LFSR 內容被回饋到 LFSR 的右端，如 $ s_{n+i} $ 實際上是先前內容的選定幾個位的異或和（對應的那些 $ c_i $ 有價值 $ 1 $ ）。因此命名為線性回饋移位寄存器，它被初始化為 LFSR。
考慮到上述描述，LFSR 問題的一個答案在某種意義上是微不足道的： $ N $ 具有回饋係數的階段 LFSR $ (c_N,c_{N-1}, \cdots, c_1) = (1,0,0,\cdots, 0) $ 和初始載入 $ \big(s_0, s_1, \ldots, s_{N-1}\big) $ 會產生無休止的重複 $$ s_0, s_1, \ldots, s_{N-1},s_0, s_1, \ldots, s_{N-1}, s_0, s_1, \ldots, s_{N-1}, \cdots $$ 給定時間碼的 $ s_0, s_1, \ldots, s_{N-1} $ 永遠。或者，任何其他選擇 $ (c_N,c_{N-1}, \cdots, c_1) $ 將用其他東西填充移位寄存器，但第一個 $ N $ 位仍然會 $ s_0, s_1, \ldots, s_{N-1} $ 之後的情況將有所不同。這顯然不是我們想要的，因此我們尋求一個更好的標準：找到將生成的最短LFSR（及其初始載入） $ s_0, s_1, \ldots, s_{N-1} $ ，這正是 Berlekamp-Massey 算法發現的。
Berlekamp-Massey 算法是一個迭代過程，包括找到生成第一個 $ t $ 位 $ s_0, s_1, \ldots s_{t-1} $ 並檢查 LFSR 是否找到 $ s_t $ 正確。如果是這樣， $ s_{t+1} $ 被檢查，如果沒有，則 $ c_i $ 的被更新，以便修改後的 LFSR 生成 $ s_t $ . 通常，但不總是，LFSR 的長度會增加。迭代過程一直持續到最後一個可用位 $ s_{N-1} $ 已被處理，因此當 Berlekamp-Massey 算法終止時，合成的 LFSR 產生整個序列 $ s_0, s_1, \ldots, s_{N-1} $ 在其輸出。如果合成的 LFSR 有 $ n\leq N $ 階段，那麼它的初始載入是 $ \big(s_0, s_1, \ldots, s_{n-1}\big) $ （這是第一個 $ n $ 輸出位）和LFSR正確計算 $ s_n, s_{n+1}, \cdots, s_{N-1} $ （即給定序列的其餘部分）。Berlekamp-Massey 算法合成的 LFSR 的長度保證是最小的： 沒有生成的 LFSR $ s_0, s_1, \ldots, s_{N-1} $ 可以有更短的長度。**但是，**沒有人聲稱 $ n $ 保證小於 $ N $ ; 很可能上面描述的微不足道的解決方案是最小的解決方案。事實上，我認為這確實是大多數序列的情況。LFSR 的長度 $ N $ . *Kolmogorov 複雜性理論*說，列印出大多數長度字元串的最短程序 $ N $ 有長度 $ N+c $ ，或者通俗地說，對於大多數字元串，除了儲存字元串並將其列印出來之外，沒有什麼比這更好的了；這 ” $ c $ " 只是“列印以下字元串”命令的長度。在移位寄存器的上下文中，對於大多數長度序列 $ N $ ，其輸出為給定長度序列的最短移位寄存器 $ N $ 只是長度的移位寄存器 $ N $ 初始化為給定的序列。回饋是什麼（如果有任何回饋的話）是無關緊要的。
- 如果序列確實是由 $ n $ 如上所述的階段 LFSR，其中 $ n \leq \frac N2 $ ,然後 Berlekamp-Massey 算法找到所有 $ n $ 係數 $ c_i $ 檢查後 $ s_0, s_1, \ldots, s_{2n-1} $ . 合成 LFSR 的初始載入當然只是 $ \big(s_0, s_1, \ldots, s_{n-1}\big) $ . 從此時開始，Berlekamp-Massey 算法可以繼續檢查序列的其餘部分（如果需要），但不需要更新 $ c_i $ 是因為對下一個符號的每次檢查都只是簡單地報告一切正常；目前的 LFSR 也生成下一位。 然而，一般來說，密碼分析者根本不知道時間碼是否是由 LFSR 生成的。它只是一個序列 $ N $ 來歷不明的位，因此對於密碼分析員的目的，所有 $ N $ 必須檢查位以找到可以生成的最短 LFSR $ s_0, s_1, \ldots, s_{N-1} $ . 如果附加位 $ s_N, s_{N+1}, \ldots $ 可用，則不能保證檢查後找到的 LFSR $ N $ 位也會產生這些額外的位。事實上，Berlekamp-Massey 算法背後的整個想法是，如果測試“目前 LFSR 是否也生成 $ s_n $ ?" 失敗，算法從目前 LFSR 中合成一個修改後的 LFSR，以便修改後的 LFSR 生成 $ s_0, s_1, \ldots, s_{n-1},s_n $ . 在這個過程中，LFSR 的長度可能（也可能不會）增加。
- *如果序列確實是由 $ n $ 如上所述的階段 LFSR，其中 $ \frac N2 < n \leq N $ ，*然後 Berlekamp-Massey 算法找到生成的最短 LFSR $ s_0, s_1, \ldots, s_{N-1} $ . 它可能會或可能不會生成相同的值 $ s_N, s_{N+1}, \cdots, s_{2n-1} $ 就像實際的 LFSR 一樣。
考慮到上述冗長的謾罵，讓我們解決 OP 的問題。在標題中，OP問
除了 BMA 之外，還有哪些工具可用於對 LFSR 進行逆向工程？
嗯，多項式最大公約數的*擴展歐幾里得算法可以用，但是在某種意義上，它等價於Berlekamp-Massey算法；*可以看成是逆序處理序列 $ s_{N-1}, s_{N-2}, \cdots, s_1, s_0 $ 與訂單相比 $ s_0, s_1, \cdots, s_{N-2}, s_{N-1} $ 由 Berlekamp-Massey 算法使用。
在問題的正文中，OP抱怨
這段程式碼似乎有 110 的線性複雜度，這在任何方面都不實用。它也不能用 BMA 找到的 110 位不可約多項式來重構。只有前幾位符合預期，然後位似乎翻轉。
這個問題很可能是 BMA 實施中的錯誤問題。“以任何方式都不實用”表明分配的記憶體可能不足以儲存 BMA 內部使用的各種多項式，或者緩衝區溢出等。正如@kodlu 指出的那樣，如果時間碼的長度 $ 220 $ 位，然後檢查所有 $ 220 $ 位可能導致長度為 LFSR $ 110 $ . 否則，如上所述，如果時間碼有長度 $ 110 $ 或更多（也許 $ 128 $ 位 $ = 16 $ 字節？），BMA 很可能會合成一個長度為 LFSR $ 110 $ . 最後，對於 OP 的觀察，除了程序員錯誤之外，我沒有其他解釋，即在合成的 LFSR 輸出中，“前幾位”是正確的，但其餘的都被翻轉了。
有沒有人知道 BMA 在什麼條件下檢測到如此長的多項式？
請參閱此答案中虛線上方的材料。