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

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

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

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

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

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

A5/1 算法的輸入與輸出

      在GSM 標(biāo)準(zhǔn)中，信息以幀序列的形式通過電波進行傳輸。幀序列包含數(shù)字化的用戶語音數(shù)據(jù)以及用于移動互聯(lián)網(wǎng)瀏覽的音/視頻數(shù)據(jù)流。該系統(tǒng)按順序傳輸每一個幀，時間間隔為4.6 毫秒。每幀由228 位構(gòu)成，前114 位稱為“上行鏈路數(shù)據(jù)”，后114 位稱為“下行鏈路數(shù)據(jù)”。

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

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

A5/1 算法的主要設(shè)置例程如下：

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

硬件實現(xiàn)

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

圖1 －頂層模塊架構(gòu)圖

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

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

      同樣，我們發(fā)現(xiàn)maj2 的值建立在抽頭編號7、5、8 的基礎(chǔ)之上。根據(jù)這些多數(shù)函數(shù)，我們定義R0 的芯片使能端為：

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

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

LFSR 組

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

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

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

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

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

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

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

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

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

流中斷器的偽代碼：

4. 匯總lfsr 19、22、23 的內(nèi)容

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

6. 則將1 傳輸至LFSR

7. 否則

8. 將0 傳輸至LFSR

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

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

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

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

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