高速數據壓縮及加密硬件加速電路研究*

王 飛 李 釗 尹曉華 雷振江 曹 智 范賽龍

（1.國網遼寧省電力有限公司信息通信分公司 沈陽 110006）（2.國網遼寧省電力有限公司科技信通部 沈陽 110006）（3.南京航空航天大學電子信息工程學院 南京 211106）

1 引言

隨著云計算和物聯網技術的飛速發展，數據爆炸式增長，數據壓縮技術變得越來越重要，已經成為網絡數據傳輸的關鍵技術。根據數據解壓的結果，數據壓縮可分為兩大類，有損壓縮和無損壓縮。無損壓縮的結果，其數據可以完全恢復，而有損壓縮后的結果，數據不能完全恢復，但是它的壓縮比通常高于無損壓縮［1］。本文研究的LZ4數據壓縮算法屬于無損壓縮，是一種最新的無損數據壓縮算法，可對文本、音頻等文件進行壓縮，其數據可被完全恢復。

目前，信息安全威脅日益嚴峻，大量關鍵數據在網絡上存儲和傳輸，僅僅進行數據壓縮，壓縮后的數據將面臨竊聽和泄漏等信息安全風險。在許多關鍵領域，如智能電網和工業控制網絡等，如果只壓縮不加密，那么用戶發送的信息就有可能存在被泄漏和篡改的可能，這樣可能會對企業和用戶造成嚴重的損失。

因此，對關鍵和重要數據進行數據壓縮和數據加密就變成一個十分迫切的技術需求。但是，目前的壓縮和加密算法通常都是在CPU上由軟件來實現的，這樣將會受限于CPU的處理速度，同時還會極大地消耗CPU的資源。當處理非常龐大的數據時，CPU將會一直滿負荷運行，無法繼續再處理其它事情。本文研究了在FPGA上同時實現LZ4數據壓縮模塊和AES數據加密模塊的硬件加速，極大地提高了系統性能。在實現LZ4壓縮時，本研究修改了部分數據格式以滿足硬件數據連續輸出的需求，在AES加密時，以面積換取速度，乒乓操作優化實現了數據連續的輸入和處理。

2 LZ4算法分析和改進

無損數據壓縮起源于霍夫曼編碼［2］。其基于概率上的編碼，需要先遍歷全文，數據量較大時不易完成，后來Jacob Ziv和Abraham Lempel兩位學者提出了LZ77和LZ78算法［3～4］，奠定了詞典編碼的基礎，后來人們又根據這兩個算法創新，衍生出了一系列變體，被稱為LZ77算法家族和LZ78算法家族。LZ4算法就是由LZ77算法衍生而來。

Yann Collet于2012年提出了LZ4算法［5］，LZ4算法主要追求壓縮和解壓的速度，通常能夠達到極高的單核壓縮速度，并且支持多核系統。由于無損壓縮算法的特點，其解壓速度比壓縮速度更快。

2.1 LZ4序列塊

每個LZ4塊都由序列組成，每個序列都以token開頭，token用來預測不可匹配字符長度和匹配字符長度，token是一個字節，分成兩個4位字段，每個字段范圍是0到15；token高4位是不可匹配字符長度（literal length），它指出接下來復制的字符多少，如果字段為0，則接下來沒有不可匹配字符，如果字段是15，則需要另一個字節來表示全長，每個附加字節表示0到255的值，當字節又達到255，則需要另加一個字節。例如：長度48表示為15+33，長度280表示為15+255+10，注意長度15表示為15+0，其中0不可缺少。token低4位是匹配長度（match length），指出最大匹配字符的長度減去4，超過15需要在塊最后額外添加字節，采取的具體措施和literal length一樣。token后接額外的不可匹配字符長度（可能沒有），然后是不可匹配字符，再接著是偏移位置offset，由兩個字節組成，最大值是65535，表示匹配字符間的長度，最后面是額外的匹配長度。具體如表1所示。其中，最小匹配是4個字符，小于4個字符則不認為是匹配，當不小于4個字符則判斷為匹配，然后進行后向查找，找到最長的匹配，但是match length是減去4個字符的結果，例如match length=2，意味著匹配字符長度為6。

表1 LZ4序列數據格式

2.2 LZ4算法流程

LZ4算法過程主要分為5個過程，其中包括散列（hash）計算、匹配、后向查找、參數計算和數據輸出，具體流程圖見圖1。

圖1 LZ4算法流程圖

原始的LZ4算法主要是針對于通用處理器設計的，沒有考慮硬件電路進行優化，直接將其應用到硬件電路實現時會出現以下問題：

1）僅僅針對不匹配數據計算hash值，hash計算也不用于后向匹配，這樣部分匹配數據的hash值將不會計算。

2）當新數據和hash表中存在的數據不一致時，就發生了沖突，這將需要重新計算hash值，會花費較多的時鐘。

3）輸入數據受限于hash表地址位寬，hash表中內存地址的最大值就是輸入數據的最大長度，這樣不能連續不斷地壓縮數據。

4）輸出延遲不能確定，在原始格式中，在查找完成一次全部匹配之前不會輸出任何數據，如果匹配長度很大，也需要在查找完成后才能輸出，這樣會使得數據在硬件中來不及輸出。

為了改善硬件壓縮速度，將LZ4數據格式更改如表2所示。其中token和offset的數據格式沒有變，僅改變了literal和literal length，在token之后立即接上最大15個字節的literal，如果更長需要先加上一個字節的literal length，然后后面接上最大128個字節的literal，如果更大后面重復以上。LZ4塊序列最后面是match length，匹配長度小于15+4時沒有后面的match length字節，如果超過的話就額外添加兩個字節表示，總的匹配長度是上面三者的總和。

表2 修改后LZ4數據格式

針對上面4個LZ4算法出現的問題的具體改善措施如下：

1）由于FPGA具有并行性，所以可以利用它在后向匹配時仍然計算hash值，這樣可以改善壓縮比。

2）為了減少hash沖突浪費的時間，改善壓縮速度，增加一個與hash表對應的word表，不同的是hash表中存地址，而word表中存的是hash值對應的數據，這樣在查找匹配時，可以在讀hash表中地址時也能讀取數據，然后進行匹配。

3）為了在硬件上連續的進行壓縮，在hash表中增加一個有效位，數據有效置位，無效清零。定期清理hash表，當數據無效時就清零有效位，這樣就不會出現地址存滿導致無法匹配。

4）為減小輸出延遲，將官方的數據格式修改為表2所示，當不可匹配字符超過300個字節，匹配長度設為4個字節，例如不可匹配字符長度是40k，那么對于新的格式在literal length到達300字節就可以輸出了，這樣大大的減少了等待匹配的時間。

綜上所述，修改后的LZ4算法流程圖如圖2所示。

3 AES算法分析

為改善傳統DES算法短密鑰的缺點，美國國家標準局NIST于2001年公布高級加密標準算法（AES）［6］，AES算法規定分組長度為128位，密鑰長度可為128位、192位和256位。相應的迭代輪數分別為10、12和14輪。本文實現為128位密鑰，工作模式為CBC密文塊鏈接模式。

圖2 修改后LZ4算法流程圖

AES算法是在一個4×4的字節矩陣上進行運算，這個矩陣稱為狀態矩陣（state）。以本文研究的128位密鑰來討論，共進行10輪迭代，每輪迭代（除最后一輪）主要包括四個步驟［7］：字節代替、行移位、列混合、輪密鑰加。

1）字節代替（SubByte）：首先在伽羅華域GF（28）上計算乘法逆，然后再進行仿射變換。由于輸入的字節只有256種可能，而且這種變換只是將源字節和另一字節一一映射，因此可以使用查找表來存儲所有的可能情況，稱為替換盒（S-box），里面的值就是字節代替變換后的值，繼續參與其后運算。

2）行移位（ShiftRow）：將矩陣中的每個橫列進行循環移位。狀態矩陣第一行循環左移0字節，第二行循環左移1字節，第三行循環左移2字節，第四行循環左移3字節［8］。

3）列混合（MixColumn）：利用線性轉換來混合矩陣中每行的4個字節。列混合可看做狀態矩陣與一個常數矩陣相乘，打亂行線性變化。

4）輪密鑰加（AddRoundKey）：矩陣中的每個字節都與該次循環的輪密鑰做異或運算，每個輪密鑰的生成來自于密鑰擴展。

5）密鑰擴展算法：輸入原始的128位密鑰，產生10輪子密鑰，通過循環字移位和字代替來實現。

6）CBC密文塊鏈接模式：在CBC模式中，第一個明文分組與初始矢量IV相異或，然后再進行分組加密，后面的明文也要和前一密文相異或，然后進行分組加密，形成一條加密鏈，這樣明文和密文之間的順序不再有固定的關系［9］。

綜上所述，AES加密算法流程圖如圖3所示。

圖3 AES算法加密流程圖

4 FPGA實現

本文實現了LZ4數據壓縮［10］和AES數據加密模塊［11］的流水線設計，整體實現了實時處理，每個時鐘都可以輸入數據，不浪費一個時鐘。

4.1 硬件設計框架

本文的FPGA設計在Xilinx公司的Kintex-7 KC705評估板上實現，軟件開發環境為Vivado 2016.4版本。在開發軟件中設計了Verilog代碼，然后仿真測試、觀察波形，最后在評估板上進行了實現和測試［12］。

LZ4和AES模塊的硬件結構框架分別如圖4和圖5所示，中間使用一塊FIFO來連接兩個模塊。LZ4提出者沒有考慮硬件的實現，所以算法改動較大，但是AES算法在設計時就考慮了硬件的實現，因此其結構適合硬件實現不需要進行格式改動。

輸入數據使用ROM每個時鐘產生8位數據，然后移位產生32位數據，計算hash值，寫hash表和word表，匹配比較，然后如果匹配就后向查找，并計算literal length和match length，最后整理格式輸出16位的壓縮數據，然后進入連接模塊，將數據存入FIFO內，輸出128位待加密數據，送入加密模塊，然后經過10輪變換輸出密文數據［13］。

圖4 LZ4算法的硬件結構框架

圖5 AES算法的硬件結構框架

4.2 乒乓優化策略

乒乓優化以面積換取速度，將輸入的數據按時鐘分成兩塊，分別送入兩個緩存/處理核內，然后分別進行處理，輸出的數據再經過合并處理模塊來將數據按時鐘進行合并，這樣就可以連續地輸出數據，這樣的優化策略一般可以將速度提高1倍。

本研究在LZ4數據輸出的時候，為提高數據的輸出速度，并且為了不妨礙數據的緩存，使用了乒乓優化，開辟兩塊RAM供存入數據，將輸入的8位數據變成輸出16位的數據，這樣也為后面AES算法要輸入的128位數據節省了讀入時間。由于LZ4算法輸出的壓縮數據是16位，讀取128位待加密明文數據需要8個時鐘，但是AES加密有10輪變換，共需要11個時鐘，這樣數據將不能及時處理，無法做到實時系統，因此，使用乒乓優化策略來加速處理，每8個時鐘來回切換AES加密核，處理之后合并數據，這樣就能連續加密計算，提高了速度，做到了實時處理。AES乒乓優化策略如圖6所示。

5 實驗結果分析

實驗平臺為Kintex-7 KC705評估板，芯片為XC7K325T-2FFG900C，系統時鐘頻率為200MHz差分LVDS時鐘，然后經過時鐘生成IP核輸出220MHz時鐘信號供本實驗模塊使用。

圖6 AES乒乓優化策略

仿真測試數據來自于ROM中產生的數據，每個時鐘產生8位數據，然后經過壓縮加密輸出128位數據。

LZ4壓縮和AES加密模塊資源總消耗如表3所示，資源消耗包括了數據生成的ROM模塊。

表3 資源消耗表

LZ4算法的FPGA實現與同類FPGA壓縮比較如表4所示。與同類壓縮核LZRW［14］、LZW［15］、LZMA［16］的FPGA設計相比，本設計的各項指標都大大優于同類。

表4 無損數據壓縮算法性能比較

對于AES算法，大多都是邏輯運算，只有輪變換需要消耗時鐘，因此本實驗設計的瓶頸不在AES算法，只是AES在乒乓優化時消耗了雙倍的資源換取速度，以滿足實時處理的需求。

本文設計整體上實現了流水線的處理，能在每個時鐘都接收處理數據，并且實時輸出。經過板級測試，設計最高可運行在220MHz的系統時鐘，每個時鐘輸入處理8位，即吞吐率為1760Mbps。如表4所示，本文所設計的LZ4硬件加速器比之前最好的設計提高了1.5倍，為目前已知的性能最高的數據壓縮加速電路。

由于FPGA的并行性，可以通過實現多個壓縮核并行進一步提高壓縮吞吐率。同時加上并行的加密模塊，可以實現高速實時的數據壓縮加密加速器。

6 結語

本文實現了LZ4壓縮和AES加密算法的FPGA加速電路，通過修改LZ4的數據格式將其更適于硬件計算，并且通過乒乓優化將AES數據處理速度翻倍，以適應實時處理數據的需求。與現有設計對比，本文的設計的數據壓縮加速器吞吐率比同類電路有著顯著提升，硬件資源消耗也較小。未來的工作將重點設計多個壓縮和加密模塊并行的高速實時電路，進一步提升性能。