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

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

電子郵件：[email protected]

    移動電話、互聯(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 上,。