本文介紹的一些設計原理與技巧可嘗試在采用賽靈思FPGA 實現當前及未來A5/x 算法時進行運用。

        作者：ManSoor Naseer，巴基斯坦伊斯蘭堡 E-8 區巴利亞大學(Bahria University) 助理教授

電子郵件：Manssor.naseer@gmail.com

    移動電話、互聯網與流媒體應用不僅使人們能夠進行遠程交流，而且還可以在線查找信息、開展娛樂活動。但是，隨著移動通信使用量的激增，以無線傳輸海量信息極易遭受安全風險。為安全起見，工程師紛紛采用加密技術來保護數據。在全球移動通信系統(GSM) 標準中，選用的算法為 A5/1。使用 A5/1 的情況下，加密與解密都可通過網絡同時在手持終端和基站進行。

     本文以實現不同分組密碼時所用的代碼片段(code snippet) 為側重點，將向您介紹如何實現 A5/1 流密碼。外，為提高安全性，我們還將探討幾個原始 A5/1 算法的新的不同變體。具體來說，我將改變反饋功能的作用方式、重新設計合成器的輸出。為此，我需要采用賽靈思 Virtex®-4 LX 系列 FPGA 進行硬件實現，采用賽靈思 ISE® 進行綜合，以及 Mentor Graphics 的ModelSim 6.0 進行仿真。

      在具體的實現工作開始之前，讓我們首先簡要了解一下A5/1 算法。

A5/1 算法的輸入與輸出

      在GSM 標準中，信息以幀序列的形式通過電波進行傳輸。幀序列包含數字化的用戶語音數據以及用于移動互聯網瀏覽的音/視頻數據流。該系統按順序傳輸每一個幀，時間間隔為4.6 毫秒。每幀由228 位構成，前114 位稱為“上行鏈路數據”，后114 位稱為“下行鏈路數據”。

     我們采用64 位密鑰和22 位寬的已知幀編號來初始化A5/1。下一步是將幀的輸入位和密鑰提供給三個線性反饋移位寄存器(LFSR)，大小分別為19位、22位和23 位。在對選定抽頭進行異或(XOR) 運算后，即可提供反饋，這有助于提高最終輸出的隨機性。我將三個LFSR 分別命名為R0、R1 和R2，每個LFSR 跟隨一個原函數。R0、R1 和R2 分別使用X¹⁹+X⁵+X²+X+1、X²²+X+1 和X²³+X¹⁵+X²+X+1 作為各自的原函數。

     LFSR 的時鐘序列需要采用一種特定的機制，否則會很容易破解LFSR 的輸出。因此，時鐘采用多數裁定規則(majority rule)，使用從R0、R1 和R2 中分別抽取的一個值，然后判定主要的抽頭是0 還是1。也就是說，當兩個或兩個以上的抽頭為0 時，則多數情況值為0；反之，則為1。一旦多數情況判定成立，若LFSR 的輸入位與多數情況位相匹配，則為LFSR 提供時鐘。若輸入位與多數情況值不匹配，則不在LFSR 中插入任何輸入位，因此也就不會有移位。此外，我們還可通過在原始A5/1 中對R0、R1 和R2 的每個輸出位進行異或運算來得到結果。在本例中，我采用一種我們稱為“合成器”的更高級的輸出生成函數來替代標準異或函數。

A5/1 算法的主要設置例程如下：

1. 將R0、R1 和R2 初始化為0；
2. 按先后次序在LFSR 中加載會話密鑰KC 的值和幀Fn。會話密鑰KC 在加載中占用64 個周期，而Fn 則占用另外22 個周期。在每個周期中，輸入位都與選擇抽頭產生的線性反饋值進行異或運算；
3. 隨后，讓LFSR 運行100 個時鐘周期，該過程稱為混合。此時線性反饋處于工作狀態，芯片也被啟用，從而使移位/非移位也處于工作狀態；
4. 混合步驟完成后，接下來的228 個周期用于生成最終的輸出密鑰流。上行鏈路流與下行鏈路流（各包含114 位）用于加密和解密運算。與上文所述的傳統A5/1 算法相比，本步驟采用非線性反饋以及改進的合成器。
5. 對每一個新的幀Fn，可以重復上述步驟。幀號會不斷更新，但會話密鑰保持不變，直至認證協議將其激活。

硬件實現

       我在賽靈思Virtex-4 系列FPGA 上完成了所提出的算法的硬件實現。由于我們設計實現為了邏輯更緊湊，所以我選擇了Virtex-4 系列中最小型的器件，即XC4VLX15。圖1 顯示了該頂層模塊的總體架構情況。

圖1 －頂層模塊架構圖

     頂層包含兩個構建模塊與膠合邏輯。我設計膠合邏輯是為了實現芯片連接、啟動邏輯以及數據加載等功能。還有另外兩個構建模塊，多數/抽頭規則與LFSR 組，每個都有其自身獨特的功能。

     多數/抽頭規則模塊可從LFSR 組接收選擇的抽頭位置，并獨立執行兩項單獨的功能。由于多數或抽頭規則的選擇標準依據的是R0、R1 和R2 的最后一個抽頭，因而多數規則和抽頭規則的邏輯是并行實現的。此外，在實現多數規則方面，我還進行了另一項優化。選擇多數情況的偽算法具體如下：

      同樣，我們發現maj2 的值建立在抽頭編號7、5、8 的基礎之上。根據這些多數函數，我們定義R0 的芯片使能端為：

     我以簡單的與/或門形式為來實現用于選擇maj1 和maj2 的偽代碼。同樣，將芯片使能端的偽代碼映射到簡單的XNOR 函數上，從而既可合并所有邏輯，也能縮小面積。

     該方法使用選擇語句(case statement) 實現抽頭規則算法。原始的A5/1 算法僅依據多數規則來決定LFSR 的移位運算或芯片使能端。由于我引入了改進的多數規則和額外的抽頭規則來進行LFSR 移位，因而還需要另一種機制。因此，我依據PoliSel 信號來進行R0、R1 和R2 芯片使能端的最終選擇，讓PoliSel 信號來決定是否輸出由多數規則或抽頭規則建立的芯片使能端信號。PoliSel 信號符合該等式：PoliSel = R0[18] XOR R1[21] XOR R2[22]。

LFSR 組

      LFSR 組模塊集成了多種函數與實現方法。該模塊可利用可變參數例化核心LFSR，以建立R0、R1 和R2 LFSR。這些LFSR 的寬度分別為19、22 和23。該模塊還可例化在A5/1 基礎上改進的線性反饋函數。此外，該LFSR 組還能夠實現我們新開發的非線性反饋邏輯，而且我還在該模塊中實現了用于產生最終輸出的合成器。圖2 顯示了LFSR 組的結構圖。在此，LFSR 是串行輸入、并行輸出的移位寄存器。賽靈思Virtex-4 器件可方便地將此類移位寄存器映射到硬件上。使用如下所示的LFSR 標準模板，我們還能推導出一般性的串行寄存器。

      通過使用參數，可在更高的層面上輕松例化LFSR。使用Verilog 的“defparam”特性可進行參數的傳輸，從而在頂層推導出所需的19 位、22 位和23 位寬的LFSR。采用下列代碼行即可便捷完成推導工作：

圖2 －LFSR 組模塊中R0、R1 和R2 輸入與輸出的邏輯塊

圖3 －非線性反饋控制器與輸入選擇值

（后者控制著實例lsr. 中的參數寬度）

從以下代碼段可以看出，LFSR 的輸入加載路徑可用簡單的異或運算來準確定義。

      異步門的存在增加了關鍵路徑的長度。但是，這里還是沒有超出容限范圍，因為本例中的關鍵路徑僅由三個異或門與一個多路復用器構成。

     加載完畢之后，反饋路徑可在線性或非線性反饋之間進行選擇，具體的選擇取決于非線性反饋控制器。選擇非線性反饋會立即更改設計規范和參數。例如，非線性反饋函數每11 個時鐘周期激活一次，并在10 個時鐘周期內保持激活狀態。為了縮小實現面積，我們采用了計數器而非加法器來強制執行非線性反饋函數的周期性行為。實現時需要為R0、R1 和R2 分別配備計數器，以便計算抽頭為1 的次數。本實現的偽算法如下：

1. 探測ldlfsr 信號的下降沿；
2. 計數100 個周期；
3. 100 個周期后，每10 個周期激活一次流中斷器(stream breaker)，然后休眠10 個周期，依此類推直至114 個時鐘周期結束。

流中斷器的偽代碼：

4. 匯總lfsr 19、22、23 的內容

5. 若count19 > 10、count22 > 11 或count23 > 11

6. 則將1 傳輸至LFSR

7. 否則

8. 將0 傳輸至LFSR

     由于需要在每個時鐘周期中決定是否在R0、R1 和R2 的輸入中插入1 或0，因而一旦激活非線性反饋，計數器與加法器的數量就會顯著增加占用面積與關鍵路徑長度。

     將芯片使能端與輸入相結合，可使非線性反饋路徑根據流中斷器的算法來呈現為1 或0。圖3 是實現該方案的硬件構建模塊。

     使用帶設定閾值的加法器可協助非線性反饋控制器的實現。注意，切勿使加法器在降至0 以后繼續減少，或在R0、R1 和R2 達到相應最大值（即19、22 和23）后繼續增加。下列代碼段為實現該計數器提供了一個范例：

     此外，該代碼還說明，增加和減少不僅取決于芯片使能端信號，而且還取決于時鐘的每個上升沿在LFSR 輸入側的值。

     對于未來的移動通信標準而言，實現緊密而安全的加密算法至關重要。隨著帶寬需求的快速演進發展、流媒體數據量呈指數級增長，實現各種高速并行密碼來確保數據安全勢在必行。對于此類應用所需的并行性、高速度以及高帶寬，賽靈思Virtex-4 器件可謂理想的解決方案。該平臺具備工作電壓低、功耗超低等特性，能夠輕松適應新興的安全移動應用。采用本文所述的小竅門與代碼段，您可輕而易舉地將A5/1 及其將來的變體映射到賽靈思FPGA 上。