證明交替步進生成器和修改後的 ASG’ 具有同等安全性？

交替步進生成器(ASG) 是一個結合了 3 個 LFSR的PRNG。ASG 的輸出是兩個時鐘門控 LFSR 輸出的 XOR。在每一步，根據控制 LFSR 的輸出，對這些 LFSR 中的一個進行計時。

對 ASG 的最佳（AFAIK）聲稱攻擊是對 ASG 的降低複雜性攻擊 （幻燈片）。然而，它攻擊變體 ASG’，其輸出是時鐘門控 LFSR 的輸出。

*該論文中給出的理由是：眾所周知 [ 13、8、12 []](ftp://ftp.hacktic.nl/pub/mirrors/Advances%20in%20Cryptology/HTML/PDF/C97/499.PDF)，我們可以考慮稍微不同的描述 (..)，而不是使用 ASG 的原始定義。[ 13 ] only states不難證明 ASG 和 ASG’ 是等價的 (..)*沒有參數。[我在 8 ]中找不到關於 ASG’ 的討論。[ 12 ] 有一個建設性的證明，但我沒有得到它（除非我假設一個 LFSR 是已知的/列舉的）。

關於對 ASG 的攻擊重建 LFSR 的初始狀態的證明/草圖/論點的任何線索可以變成對 ASG 的同樣有效的攻擊？

好的，我查看了您的來源 [ 12 ]，例如ON EDIT DISTANCE ATTACK TO ALTERNATING STEP GENERATOR。

原始 ASG 通過以下步驟從三個移位寄存器 X = {x_i}、Y = {y_i} 和 C = {c_i} 定義密鑰流 Z = {z_i}：

1. 最初，l = 0，t = 1。
2. 如果 ct = 1，則 l = l + 1；
3. 輸出 z_t = x_l ⊕ y_(t−l) ，其中 ⊕ 是 XOR 運算符；
4. t = t + 1 並轉到步驟 2。

例如，我們根據 c_t 對它們進行第一步處理，並使用兩者的最新輸出。

---

對於變體，我們定義 w_i = z_i ⊕ z_(i-1), u_i = x_i ⊕ x_(i-1), v_i = y_i ⊕ y_(i-1)，例如簡單的原始序列的“差異序列” .

U = {u_i} 和 V = {v_i} 可以通過與 X 和 Y 相同長度的 LFSR 輕鬆創建，只需添加或刪除一個回饋連結。（如果我們有 U 和 V 的寄存器，我們可以取回 X 和 Y 的寄存器。）

它現在表明，我們不僅可以直接從 Z 導出 W = {w_i}，還可以使用修改後的構造從 U、V 和 C 導出 W = {w_i}：

1. 最初 l = 0，t = 1；
2. 如果 c_t = 1，則 l = l + 1 並輸出 w_t = u_l ；
3. 如果 c_t = 0，則輸出 w_t = v_(t−l)。
4. t = t + 1，轉到步驟 2。

為什麼？簡單地說一下公式：

如果 c_t = 1，那麼

w_t =      z_t        ⊕        z_(t-1)
   = (x_l ⊕ y_(t−l)) ⊕ (x_(l-1) ⊕ y_((t-1)−(l-1)))
   = (x_l ⊕ x_(l-1)) ⊕ (y_((t-1)−(l-1)) ⊕ y_(t−l))
   =      u_l        ⊕ (y_(t−l) ⊕ y_(t−l))
   =      u_l        ⊕         0
   =      u_l.

如果 c_t = 0，那麼

w_t =     z_t         ⊕     z_(t-1)
   = (x_l ⊕ y_(t−l)) ⊕ (x_l ⊕ y_((t-1)−l))
   = (x_l ⊕ x_l) ⊕ (y_(t−l) ⊕ y_((t-1)−l)
   =       0     ⊕ (y_(t−l) ⊕ y_((t-l)−1)
   =       0     ⊕      v_(t-l)
   =                    v_(t-l).

這有點令人困惑，因為1這裡l看起來非常相似。

那麼，給定對 W 的攻擊，我們將如何對 Z 進行攻擊呢？

1. 通過計算連續元素的差異，將觀察到的 Z 序列轉換為 W 序列。
2. 打破 W，得到 C、U 和 V 的公式。
3. 通過添加/刪除一個回饋連結，將 U 和 V 的公式轉換回 X 和 Y 的公式。

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