線性反饋移位寄存器

移位寄存器是產生信號和序列的常用設備，它分為線性和非線性兩大類，著名的一序列和序列就是分別由線性和非線性反饋移位寄存器所生成的。線性反饋移位寄存器（Linear feedback shift register，LFSR）是

通常由動態或靜態主從型觸發器構成。反饋迴路由異或門構成。其特性通常由一個特徵多項式表徵。使用二輸入異或門計算反饋函數的最大長度或近最大長度不糾立寄存器的特徵多項式。這種電路的特點是結構簡單，它的上限移位速度取決於移位單元的延遲時間和二輸入異或門的延遲時間，因此，能獲得較高的速度 ^[1]  。線性反饋移位寄存器中的移位單元是由主一從型邊沿觸發器構成的。在這種結構的移位單元中，主從兩極鎖存器在兩相不交疊時鐘的控制下，使數據在時鐘上升沿被採樣，並一直保持到下一個時鐘上升沿。電路中四個移位單元都是由動態主從邊沿型觸發器構成的，每次移位的操作都需要數據串行依次經過兩級鎖存器。

賦給寄存器的初始值叫做“種子”，因為線性反饋移位寄存器的運算是確定性的，所以，由寄存器所生成的數據流完全決定於寄存器當時或者之前的狀態。而且，由於寄存器的狀態是有限的，它最終肯定會是一個重複的循環。然而，通過本原多項式，線性反饋移位寄存器可以生成看起來是隨機的且循環週期非常長的序列。移位寄存器結構簡單，運行速度快，實用的密鑰流產生器大多基於移位寄存器，移位寄存器理論也成了現代流密碼體制的基礎。

線性反饋移位寄存器的應用包括生成偽隨機數，偽隨機噪聲序列，快速數字計數器，還有擾頻器。線性反饋移位寄存器在硬件和軟件方面的應用都非常得普遍。循環冗餘校驗中用於快速校驗傳輸錯誤的數學原理，就與線性反饋移位寄存器密切相關。

影響下一個狀態的比特位叫做抽頭。圖1中，抽頭序列為[16,14,13,11]。LFSR最右端的比特為輸出比特。抽頭依次與輸出比特進行異或運算，然後反饋回最左端的位。最右端位置所生成的序列被稱為輸出流。

作為基於異或運算的LFSR的替換，LFSR也可以給予同或運算。與使用異或門的LFSR全零狀態下為無效狀態相應的，使用同或門的LFSR在全“1”狀態下也是無效的。有LFSR或者基於同或門的LFSR生成的序列可以被認為是同格雷碼或者自然二進制碼同樣有效的二進制序列。

在LFSR中，抽頭的設定可以用有限域算數中模2的多項式來表示。這就意味着，多項式中的所有係數必須是“1”或者“0”。這個多項式被稱作回授多項式或特徵多項式。例如圖1中的抽頭為在第16，14，13，11個比特，則相應的特徵多項式為：

多項式中常數“1”並不代表某一個抽頭，它所指的是一個比特位的輸入（例如

等效為 1 ）。多項式中的指數代表從左至右的抽頭位。第一個和最後一個比特一般相應的是輸入和輸出位。當且僅當相應的回授多項式是本原多項式時，LFSR才能達到最大長度。這表示以下條件是必須的：

生成最長LFSRs的本原多項式表可通過下部的鏈接找到。 這類型LFSR也被成為標準，多對一或外部異或門的LFSR。

在不同的分支數學，本原多項式有不同的含義：

域論中，一個本原多項式是有限域GF(pm)有限擴張的本原元的最小多項式（域論）。

在代數（特別是環理論），如果一個整係數多項式的所有係數是互素的,則稱它是一個本原多項式，本原多項式對判定不可約多項式有很大幫助，高次多項式的不可約多項式判定一直是個未完全解決的難題。

有限域的不可約多項式都是本原多項式，這點對通訊編碼和密碼學有重要作用。每個有理係數多項式都能寫成一個有理數與一個本原多項式的乘積。高斯引理（環的）兩個本原多項式的乘積仍是本原多項式。

流密碼是私鑰密碼體制的一類流密碼與分組密碼用固定變換處理明文序列的一組數據不同，其加密過程是先把報文、語音、圖象等原始明文轉換成數據，然後將它同密鑰序列逐位加密生成密文序列發送給接收者，接收者用相同的密鑰序列對密文進行逐位解密來恢復明文。現代數字電子技術的發展已使密鑰序列可以方便地利用以移位寄存器為基礎的電路來產生，加上有效的數學工具，使得流密碼迅速發展並走向較成熟階段同時，由於流密碼不存在數據擴展和錯誤傳播，其硬件加、解密速度快，且實現容易，因此流密碼在實際中得到廣泛的應用。密鑰流序列必須滿足的一些性質對作為密鑰流生成器重要部件的反饋移位寄存器進行分析，包括線性反饋移位寄存器序列的特性和衡量流密碼系統強度的重要指標等。在流密碼中，由於明文序列與密鑰序列逐位加密，密鑰序列一定要具有與明文序列相當的長度但這樣的密鑰序列難於分配和管理，實際上密鑰序列都是由密鑰空間中較短的密鑰經過某些算法生成的 ^[2]  。