LFSR 跳轉算法

已在此處提出並回答了一個相關問題。我的問題特別是關於為非常大的 J 找出 C。我在網上搜尋過很多關於“向前跳躍”以及如何有效地做到這一點的學術文章，但我正在尋找一種更“外行”的算法。

這是背景資訊。我正在努力了解在密碼學中使用 LFSR 的薄弱環節。為了證明這個概念，我有一個使用 N 位 LFSR 的流密碼的加密消息。純文字是 ASCII，所以我知道純文字位以特定間隔 (8) 重複出現，稱之為 m。由此，我得到一組不連續的密鑰位。我在 m 的索引倍數的前 128 個這樣的位上使用了 Berlekamp-Massey，然後使用結果係數和傳遞給 BM 的前 64 位來初始化 LFSR。我已經瀏覽了消息的其餘部分，向自己證明了多個 m 處的位都是可預測的。

現在我想向自己證明剩下的部分，即取回消息的 LFSR 係數，只有關鍵位的子集和這些位的關聯 LFSR。在我提到的問題中，我一直試圖弄清楚b一世=C(一世米−1反對p) $ b_i=c_{(i,m^{-1}\bmod p)} $ . 換句話說，C(一世米−1反對p) $ c_{(i,m^{-1}\bmod p)} $ 與 LFSR 一起向前跳躍是一個巨大的跳躍，太大了，無法在狀態下步到那個點。正如我所說，我發現有文章討論了 LFSR “跳躍式前進”，但我認為我需要更明確的方法來說明這一點。

例如，一種簡單的方法（而且速度很慢）是預先計算矩陣冪一個:=FĴ $ A := F^J $ （多項式空間中線性遞歸的快速跳轉算法）。但我沒有找到有關如何創建矩陣的資訊一個 $ A $ 從係數。為了證明這個概念，我不需要一個快速的算法，只需要我可以應用來關閉循環。

算法（Python、C、Java 等）或實現將是最有幫助的。但即使是一篇提供有關該方法的更完整細節的文章也可以達到目的。你能推荐一些東西嗎？

下面是一個使用斐波那契模式建立約定的具體範例：

Coeffients: 1111100000010100101010001111110101111100110010110011101111001001
State:      0000111101011011011000011101100111001010000011001001100100011110
Output:     000011110101101101100001110110011100101000001100100110010001111010110011001100101111011110110001010001001110010011101010110101001001110000000101111110001001110001000010100111110111001001100001111001010011110110110010010110010001101000100001111101110011101100011001110100010111101111010101101001001000011100011001010110100010001111011110000110010100000000011100011111011110011111100110010110001100011101001111010101101101100010100110110110100000100011111001011111001111000010011011101000111110111101001111001101011101101001111110001111011111100100101010011000101011001010111001001001..

縮短；見這裡的起源。

伽羅瓦 LFSR

在具有多項式的伽羅瓦 LFSR 中磷 $ P $ 學位n $ n $ ，狀態是一個向量n $ n $ 與度項的二進制係數同化的位n−1 $ n-1 $ 至0 $ 0 $ 多項式的；我們注意到狀態和它的多項式小號j $ S_j $ 當在步驟j≥0 $ j\ge0 $ .

下一個狀態計算為小號j+1=小號jX反對磷 $ S_{j+1}=S_j,x\bmod P $ . 等效地，狀態向高階係數移動，從狀態中輸出並丟棄；引入a 0 作為低階係數；然後如果輸出為 1，則索引處的狀態位對應於非零項磷 $ P $ （忽略高階項Xn $ x^n $ ) 得到補充。

因此，在伽羅瓦 LFSR 中， 小號j=小號0Xj反對磷$$ S_j=S_0,x^j\bmod P $$ 這允許有效的直接訪問。多項式模冪可以使用與整數一相同的方法，除了使用無進位算法，簡單的算法有成本○(日誌(j)n2) $ O(\log(j),n^2) $ .

此外，伽羅瓦 LFSR 的輸出j $ j $ 步驟是商的係數問 $ Q $ 的多項式除法小號0Xj $ S_0,x^j $ 經過磷 $ P $ ，從度係數開始j−1 $ j-1 $ 對於第一個輸出位，下降到零jth $ j^\text{th} $ ; 它擁有磷問+小號j=小號0Xj $ P,Q+S_j=S_0,x^j $ .

---

斐波那契 LFSR

該問題使用斐波那契 LFSR，從輸出開頭的狀態可以明顯看出。之後，下一個輸出位是位與的奇偶校驗n $ n $ 先前的位和定義多項式的係數。我將使用先前生成的位與度數係數進行與運算的約定n−1 $ n-1 $ 的多項式。使用該約定，多項式的低階（常數）係數是問題 的最左邊位Coeffients，並且多項式磷 $ P $ 是1+X+X2+X3+X4+X11+X13+X16+⋯+X55+X56+X57+X60+X63+X64 $ 1+x+x^2+x^3+x^4+x^{11}+x^{13}+x^{16}+\dots+x^{55}+x^{56}+x^{57}+x^{60}+x^{63}+x^{64} $

用這個詞X64 $ x^{64} $ 未在問題中顯示（並且在步進 LFSR 時從未通過按位與任何內容組合）。

注意：關於 Fibonacci LFSR 和 Berlekamp-Massey 的標准文獻經常使用所謂的反射或倒數多項式，其中階係數一世 $ i $ 和n−一世 $ n-i $ 被交換（這可能會改變多項式的順序）。目前的答案不使用這種形式的多項式。

沒有證明：按照我們的約定，當多項式的低階係數為1 $ 1 $ （按照 Berlekamp-Massey 的慣例），使用相同多項式的 Galois 和 Fibonacci LFSR 產生相同的輸出序列，只是從不同的起點和不同的狀態（當多項式的最低階非零係數具有階l>0 $ l>0 $ , 斐波那契 LFSR 在之後達到與伽羅瓦 LFSR 相同的周期序列l $ l $ 最多步，當伽羅瓦 LFSR 總是從一開始就進入那個週期序列時；我們可以選擇刪除第一個l $ l $ 位並將多項式的次數減少到n−l $ n-l $ , 使得多項式的低階係數變為 1$)。

我們總是可以通過步進 Galois LFSR 將 Galois 狀態轉換為 Finnonacci 狀態，從而產生相同的輸出n $ n $ 次；它的輸出（按時間順序）是所需的斐波那契狀態（由多項式中相應位的遞增順序產生，與問 $ Q $ 通過多項式除法獲得小號0Xn $ S_0,x^n $ 經過磷 $ P $ , 通過交換階係數一世 $ i $ 和n−1−一世 $ n-1-i $ ); 這是因為斐波那契 LFSR 首先輸出它的狀態（在我們的約定中，從低階開始）。

同理，當多項式的低階係數為1 $ 1 $ , 伽羅瓦狀態小號0 $ S_0 $ 對應於某個斐波那契狀態必須使得對應的輸出問0 $ Q_0 $ 下一個伽羅瓦 LFSRn $ n $ bits 是斐波那契狀態（由多項式中相應位的遞增順序產生）。因此認為磷問0+小號n=小號0Xn $ P,Q_0+S_n=S_0,x^n $ . 由此可見，伽羅瓦狀態的係數小號0 $ S_0 $ 從n−1 $ n-1 $ 至0 $ 0 $ 是的係數磷問0 $ P,Q_0 $ 從2n−1 $ 2n-1 $ 至n $ n $ ， 在哪裡問0 $ Q_0 $ 是通過交換順序係數反映的斐波那契狀態一世 $ i $ 和n−1−一世 $ n-1-i $ .

當多項式的低階係數為1 $ 1 $ , 計算斐波那契 LFSR 之後的狀態j $ j $ 步驟，因此我們可以將其狀態轉換為伽羅瓦形式，快進，然後再轉換回來。

和~Fj $ \widetilde{F_j} $ 步的斐波那契狀態j $ j $ 通過交換術語進行反思一世 $ i $ 和n−1−一世 $ n-1-i $ ， 和⌊在/在⌋ $ \lfloor U/V\rfloor $ 多項式除法的商在 $ U $ 經過在 $ V $ ~Fj=⌊(⌊~F0磷/Xn⌋Xj反對磷)Xn/磷⌋$$ \widetilde{F_j}=\left\lfloor{\left(\left\lfloor{\widetilde{F_0};P}/{x^n}\right\rfloor,x^j\bmod P\right)x^n}/P\right\rfloor $$

詳細資訊：

1. 反映斐波那契初始狀態，產生問0=~F0 $ Q_0=\widetilde{F_0} $ （其中第一個輸出0 $ 0 $ 至n−1 $ n-1 $ 是訂單條款n−1 $ n-1 $ 至0 $ 0 $ );
2. 計算磷問0 $ P,Q_0 $ 並保持秩序2n−1 $ 2n-1 $ 至n $ n $ , 產生小號0 $ S_0 $ 從訂單n−1 $ n-1 $ 至0 $ 0 $ ;
3. 計算小號j=小號0Xj反對磷 $ S_j=S_0,x^j\bmod P $ ;
4. 計算商問j $ Q_j $ 的多項式除法小號jXn $ S_j,x^n $ 經過磷 $ P $ ;
5. 反映問j $ Q_j $ 計算斐波那契狀態Fj $ F_j $ 後j $ j $ 步驟（從訂單0 $ 0 $ 至n−1 $ n-1 $ 也是輸出j $ j $ 至j+n−1 $ j+n-1 $ ).

注意：步驟 4. 和 5. 等效於步進 Galois LFSRn $ n $ 時間從小號j $ S_j $ ，從訂單形成斐波那契狀態0 $ 0 $ 至n−1 $ n-1 $ （問題中從左到右）。

---

另一種矩陣方法將步進 LFSR（Fibonacci 或 Galois）所產生的變換視為（稀疏）矩陣的乘法。該矩陣可以提升到jth $ j^\text{th} $ 得到步進對應的矩陣j $ j $ 次，但矩陣不再稀疏，並且（使用教科書矩陣乘法算法）時間增長○(日誌(j)n3) $ O(\log(j),n^3) $ 而不是○(日誌(j)n2) $ O(\log(j),n^2) $ , 有空格○(n2) $ O(n^2) $ 而不是○(n) $ O(n) $ .

---

這是有希望的符合 C99 的程式碼，專門用於n=64 $ n=64 $ 和斐波那契形式，針對速度進行了高度優化。值得注意的是，程式碼：

• 在 64 位上並行處理並且不使用表，我猜與 64 位 CPU 上的逐位相比，這可以節省 100 倍的速度，而且成本會隨著j $ j $ 作為○(日誌(j)) $ O(\log(j)) $ .
• 分支預測器是否友好（內部循環中唯一的測試是它們的結束條件）；-(uint64_t)1這是通過屏蔽而不是測試獲得的，通常使用 negation: is 0xFFFFFFFFFFFFFFFFwhile -(uint64_t)0is將低位擴展到 64 位0x0000000000000000，這是符合標準的。

題外話：如果你是某大公司的編譯器作者，請不要使用變通方法；不，我不會屈服於a\&(0-b)何時a\&-b更容易辨識。

• 儲存多項式的低階係數磷 $ P $ 在變數的高位p $ p $ ：這是伽羅瓦 LFSR 的一種常見實現技術，並且可以簡化從問題順序中的位到整數的轉換。

程式碼首先執行計算Xj $ x^j $ 在步驟3中，通過二進制取冪掃描j $ j $ 從右到左（低 6 位被優化掉，因為Xj $ x^j $ 需要一個班次j<26 $ j<2^6 $ ); 然後步驟 1 和 2（初始反射減少到掃描位s $ s $ 以適當的順序）；然後剩下的3個；然後通過步進 Galois LFSR 處理步驟 4 和 5（最終反射減少為以適當的順序累積結果）。

我想適應函式的程式碼，包括 ≈2 5行中的註釋，不需要滾動，所以我（ab）使用了 C 語法，比如在同一行上使用多個運算符,和分隔符。;

// fffibo64:  Fast-Forward a 64-bit Fibonacci LFSR
//  Inputs:
//   p  The polynomial, of degree 64; high-order bit of p is the poly's
//      constant term, and must be 1; coefficient x^^64 is implicit
//   s  Initial Fibonacci state (that is outputs 0 to 63 starting at high-order)
//   j  Number of steps
// Output: Fibonacci state after j steps (that is outputs j to j+63 starting high-order)
#include <stdint.h>
#ifdef _MSC_VER                     // this vendor has its own views on C, workaround that
#pragma warning (push)
#pragma warning (disable : 4146)    // avoids "unary minus operator applied to unsigned type"
#endif
uint64_t fffibo64(uint64_t p, uint64_t s, uint64_t j) {
   uint64_t u,v,w,x;               // workhorse temporaries
   // compute x^^j mod p into x, with optimization for low-order 6 bits
   x=((uint64_t)1<<63)>>(j&63);    // takes care of the low-order 6 bits of j
   if((j>>=6)!=0)
       for(v=p;;) {                // for remaining bits of j, if any
           if ((j&1)!=0)           // perform x = x*v mod p
               for(u=x, x&=-((w=v)>>63); w+=w; x^=(u=(p&-(u&1))^(u>>1))&-(w>>63));
           if ((j>>=1)==0) break;  // we have handled all bits of j
           // perform v = v*v mod p
           for(v&=-((u=w=v)>>63); w+=w; v^=(u=(p&-(u&1))^(u>>1))&-(w>>63));
           }
   // perform p*reflected(s) and keep coefficients 127 to 64 of that into v
   for(w=(p+p)|1, v=0; v^=w&-(s>>63), w+=w; s+=s);
   // perform u = v*x  mod p
   for(u=v&-(x>>63); x+=x; u^=(v=(p&-(v&1))^(v>>1))&-(x>>63));
   // here u is the Galois state after j steps; step it into x, reflecting
   for(w=64, x=0; x+=x+(v=u&1), u=(p&-v)^(u>>1), --w;);
   return x;
   }
#ifdef _MSC_VER
#pragma warning (pop)
#endif

// demo of the above, producing the output stream bit by bit both sequentialy, and with
// direct access, with (hopefully) identical result.
#include <stdio.h>
int main(void) {
   uint64_t j,
       p=0xf814a8fd7ccb3bc9,   // 1111100000010100101010001111110101111100110010110011101111001001
       s=0x0f5b61d9ca0c991e,   // 0000111101011011011000011101100111001010000011001001100100011110
       t=s,x;
   for(j=0; j<800; ++j) {
       printf("%d", (int)(t>>63));
       // evolve the state t step by step
       x=p&t; x^=x>>32; x^=x>>16; x^=x>>8; x^=x>>4; x^=x>>2; x^=x>>1; t=(t+t)|(x&1);
   }
   printf("\n");
   // same sequence with direct access
   for(j=0; j<800; ++j) printf("%d", (int)(fffibo64(p,s,j)>>63));
   printf("\n");
   return 0;
}

線上嘗試！

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