使用 LFSR 和 Berlekamp-Massey 使用部分密鑰片段解密密文

編輯

狀態寄存器（LFSR）是否總是必須保持 16 位（我假設是）。

如果是這樣，我們是否將寄存器右移一位（lfsr>>1）並將輸出位插入到最左邊的位（lfsr>>1 | bit<<15），這允許我們在相同的 16 位地址空間內迴繞。

因此，考慮到這一點，如何生成給定的連續密鑰流：

種子：1100101001110101

水龍頭：3, 12, 14, 15

---

假設您獲得以下資訊：

種子：1100101001110101

關鍵片段：000100011110101100001101101111101

以及以下密文/加密流：10101011000000010010110011001100101000010101010101010111101111110111010000010011

我似乎無法將整個文本解密為一些 ASCII 值（UTF-8 解碼）。我最初編寫了一個 Berlekamp-Massey 實現和一個線上計算器來獲取上述關鍵片段的點擊位置，它返回以下多項式：

$$ x^{15} + x^{14}+x^{12}+x^{3}+1 $$

在 Rust 中實現的斐波那契 LFSR：

fn next(&mut self) -> Option<(u16, u16)> {
   self.bit = ((self.lfsr >> self.taps[0]) ^ (self.lfsr >> self.taps[1]) ^
               (self.lfsr >> self.taps[2]) ^ (self.lfsr >> self.taps[3])) & 1;

   self.lfsr = (self.lfsr >> 1) | (self.bit << 15);

   if self.lfsr != self.seed {
       Some((self.bit, self.lfsr))
   } else {
       None
   }
}

• 密鑰片段從未出現在生成的密鑰流中，這表明可能出現了問題。
• 解密的密碼不映射到 ASCII 值，只是神秘的 UTF-8 符號。

Berlekamp-Massey 實施基於以下白皮書 - https://www.osti.gov/servlets/purl/12658

完整的程式碼可以在這裡找到 - https://gist.github.com/JuxhinDB/ef8dac92b5af5de2e365d326b8dbc410

TL;博士：

如果您有類似的問題，則使用線上 Berlakamp-Massey算法通過提供給定的密鑰流來獲得最小多項式，然後從github獲取 C++ 程式碼，然後替換您的點擊位置、種子和密文，然後編譯並執行。

---

答案是attraction

如何得到它

**給出的內容：**我們提供了以下資訊；

• 關鍵片段
• 種子
• 密文

**攻擊構想：**給出密鑰片段，計算輸出給定密鑰片段的最短LFSR。一旦你得到水龍頭，用種子初始化 LFSR，然後解密密文流。

詳細步驟；

1. 使用Berlakamp-Massay算法找到最短的 LFSR（不需要唯一）。使用線上版本。
2. 輸出為 $ x^{16} + x^{12} + x^3 + x^1 + 1 $
3. 如線上站點上所述，LFSR 的大小為 16，分接頭位置為

0,1,3,12

 xxxxxxxxxxxxxxxx <-|
 || |       |       |
 ++-+-------+-------|  
 01 3       12

4. 用種子和這個抽頭位置初始化大小為 16 的 LSFR。執行 LFSR 並獲取密鑰流； 11001010011101010101100010111110110000000011011000100011110101100001101101111101
5. X-或帶有密文的密鑰流
6. 將明文轉換為ASCII得到

attraction

---

**注意 1：**如果您使用 x 或 16 位種子與密文，您將獲得at. 這包含來自英文字母表的兩個字母的機率非常低。如果我們假設只使用小英文字母，那麼機率是 $ 26^2/256^2 \approx 1.031% $ . 這是問題的實際線索。而且，通常情況下，真正的流密碼不會從初始化後立即開始。他們從一開始就踩了一定的步數。

**注 2：**可以在github中找到範例 C++ 程式碼。

引用自：https://crypto.stackexchange.com/questions/66102