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

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

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

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

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

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

A5/1 算法的輸入與輸出

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

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

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

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

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

硬件實(shí)現(xiàn)

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

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

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

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

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

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

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

LFSR 組

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

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

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

圖3 －非線(xiàn)性反饋控制器與輸入選擇值

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

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

      異步門(mén)的存在增加了關(guān)鍵路徑的長(zhǎng)度。但是，這里還是沒(méi)有超出容限范圍，因?yàn)楸纠械年P(guān)鍵路徑僅由三個(gè)異或門(mén)與一個(gè)多路復(fù)用器構(gòu)成。

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

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

流中斷器的偽代碼：

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

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

6. 則將1 傳輸至LFSR

7. 否則

8. 將0 傳輸至LFSR

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

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

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

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

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