??? 摘? 要：一種基于FPGA的數據加密標準算法的實現。就資源優先和性能優先分別使用循環法和流水線法對DES加密算法進行了設計，并對其進行了比較。通過采用子密鑰簡單產生和ROM優化S盒的方法，對流水線法進行改進，達到了資源占用率低、加密速度快的效果。?

??? 關鍵詞： DES； 流水線； 循環法； FPGA； 密碼學

?

??? 付費節目是數字電視的重要新業務之一，建立付費頻道，其中關鍵性的技術就是加密技術，數字電視條件接收系統CAS（Conditional Access System）是數字電視加密控制的核心技術的保證。典型的CAS由前端子系統、終端接收子系統等組成，前端子系統邏輯結構如圖1所示。圖1中加密器B采用數據加密標準DES（Data Encryption Standard）加密算法進行硬件實現，以達到對控制字CW進行快速加密。盡管目前DES算法已經出現很多變形的算法，但基礎仍然是DES算法，可見，對DES算法的研究具有很大現實意義。?

?

?

??? 通過軟件實現的安全系統從本質上來說很難做到真正的保密，而通過硬件來實現加密模塊的內部運作，可實現硬件的自鎖、自毀功能，能夠實現真正意義上的保密。現場可編程門陣列FPGA在實現算法方面具有靈活性、物理安全性和比軟件高的速度性能，已成為硬件實現DES算法最好的選擇。本文就資源優先和性能優先上對DES算法進行了設計和比較，這兩種設計方法和針對流水線改進后的方法都在Altera CycloneⅡ芯片上得到了實現。?

1 DES加密算法原理?

??? 本文采用電碼本模式ECB(Electric Code Book)的DES加密算法，通過直接使用分組密碼算法來進行消息加密。這一工作模式的優點就是分組密碼的優點，其缺點是相同的密文對應相同的明文。DES是迭代型分組密碼，明文分組長度為64bit，密鑰的長度也為64bit，但實際上只有56bit有效，密鑰中第8、16、24、…、64位被舍去，因為它們通常是奇偶校驗位。DES加密算法從數據流的角度來看，可以分為兩部分：明文的變換和密鑰的變換。變換中引入了輪的概念，每一輪的算法都是重復的，一般要進行16輪。?

??? 在每輪密鑰變換過程中，密鑰擴展算法還需要用到循環左移變換。密鑰變換的原則是：在第1、2、9、16輪變換時，密鑰循環左移1位；當第3～8輪或者10～15輪變換時，密鑰循環左移2位。每個循環左移變換的輸入和輸出都是28bit串。將移位所得的56bit密鑰通過壓縮變換變成48bit密鑰，此密鑰即為這輪變換所得的子密鑰^[1]。?

??? 在一輪明文變換時，輸入數據被分為左右對稱的兩部分。通過一個擴展置換將數據的右半部分擴展成48bit，將其與此輪生成的子密鑰進行模二加運算，經過S盒代換將模二加生成的48bit密鑰替代成32bit密鑰，最后將其進行P盒置換。以上四個運算過程構成函數F。通過另一個模二加運算，函數F的輸出與輸入數據左半邊模二加構成新的右半部分，原來的右半部分變成新的左半部分。以上過程即完成了DES算法的完整的一輪運算。DES加密算法一輪運算和總運算流程如圖2所示。?

?

?

2 DES加密算法的FPGA實現?

2.1 資源優先設計方案?

??? 資源優先方案就是通過硬件設計出一個密鑰變換輪函數和一個明文變換輪函數，通過16輪反復調用這一個硬件系統實現一次DES加密運算。由于16輪運算都只占用一輪運算所需的硬件資源，使硬件的開銷大大減少。但是，一個時鐘周期只能進行一輪加密運算，要完成整個加密過程要花費16個時鐘周期，從而在速度性能上大打折扣。而采用循環法實現DES加密算法能達到減少資源占用的目的，具體實現方法如圖3所示。?

?

?

2.2 性能優先設計方案?

??? 性能優先設計方案剛好與資源優先設計方案相反。傳統方案是將循環全部打開配合流水線結構進行設計,即將16輪函數進行硬件級聯構成一個16級的流水線結構，提前生成16個子密鑰，隨著流水線的進程發送給相對應的流水級，從而達到16個數據塊同時加密的目的^[3-4]。這樣，從第一個數據塊開始加密起，每一個時鐘周期延時都會有一個數據塊進行加密，經16個時鐘周期延時后，得到最終的密文。流水線結構設計通過一個時鐘周期即可進行一個數據塊的加密，通過占用資源換取速度性能的提高。

??? 本文通過子密鑰的簡化和S盒的優化來改進傳統的流水線結構，實現一個占用資源少、加密速度快的加密系統。具體的設計框圖如圖4所示。?

?

?

??? (1) 子密鑰的簡單生成?

??? 由DES加密算法原理可知，一個64bit的初始密鑰輸入后通過一次壓縮變換、移位變換、二次壓縮變換后得到第一輪子密鑰，其密鑰為48bit。第一輪子密鑰變換結果如圖5所示。由圖5可知，第一輪子密鑰的第1、2、3、…、46、47、48位分別為初始密鑰的第10、51、34、…、62、55、31位。每一輪子密鑰產生的方法是一樣的，如果采用硬件描述語言按照其子密鑰產生的原理一步步地推導出16次DES迭代的密鑰，不僅語言表述繁瑣，而且占用很多的硬件資源。同時，由于每一輪子密鑰產生的時間并不相同，會給DES密碼的迭代運算帶來很多不必要的麻煩。?

?

?

??? 對密鑰變換原理進行分析可以發現，每一輪子密鑰的產生只是將初始密鑰經過置換和不同次數的循環移位。每一輪循環移位的次數對原始密鑰是固定的，其每一位相對于初始密鑰的每一位存在著固定的關系，由此可以列出每一輪子密鑰與初始密鑰之間的關系表，通過關系表采用硬件描述語言可同時產生16輪子密鑰。采用此方法大大簡化了程序語言、節約了硬件的資源開銷。?

??? (2) S盒的優化?

??? S盒的設計是DES算法的關鍵部分, S盒設計的優劣將影響整個算法的性能。S盒是DES加密算法中唯一的非線性函數，S盒的非線性變換使算法達到很好的“混亂”效果,從而具有較強的安全性。?

??? S盒的原理是輸入6bit的數據，其中第1位和第6 位確定行，中間4bit確定列，通過行、列查表確定對應的4 bit的輸出。根據S盒的工作原理，可直接使用輸入為6變量、輸出為4變量的case語句進行描述，構成一個4bit 64個存儲空間的表。然而這樣的語句雖然可讀性很強,但綜合的效率往往不高，占用資源過多，速度也比較低，使S盒成為系統速度的瓶頸。?

??? 本文采用8個ROM來實現S盒。把輸入的6bit作為地址，對應的地址空間里存放的就是待輸出的4bit，這樣可提高運算時間，解決S盒變換的時間瓶頸;利用FPGA內部自帶的ROM，大大減少邏輯資源的占用。以第一個S盒設計為例，其設計實現電路如圖6所示。輸入為IN[6:1],經地址變換電路將輸入的初始值轉換為相應的查表地址{IN[6]、IN[1]、IN[5:2]}，即ADR[6:1],以此對64×4 ROM進行查表,ROM值按照S盒查找表進行初始化,由ADR[6:1]讀取ROM中相對應的數據從而得到OUT[3:0]^[2，5]。采用同樣的辦法，通過ROM實現其他7個S盒，以達到優化的目的。?

?

?

3 綜合仿真結果對比?

??? 利用ModelSim對三種不同方法實現的DES加密算法程序進行了仿真，得到的仿真波形初步驗證了DES加密功能的正確性。選用Altera公司的QuartusⅡ6.0環境下成功編譯、綜合、適配、仿真，并下載到CycloneⅡ系列的FPGA中進行了驗證，通過分析得到循環法、傳統流水線法、改進流水線法在速度性能和資源占用上的差異如表1所示。?

?

?

??? 從表1可以看出，三種不同的方法，各自占用硬件資源、可以達到的最大時鐘頻率、加密速率上都存在各自的特點。循環法占用資源少、時鐘頻率低、加密速度相對較慢。傳統流水線法通過改進后，大大減少了邏輯資源的占用量，同時在時鐘頻率和加密速率上都得到很大的提升。?

??? 本文按照資源優先和性能優先兩種不同的設計方案，分別采取循環法和流水線法予以實現。同時，對性能優先方案提出了改進方法即：子密鑰簡單生成和S盒的優化。通過對這三種方法進行綜合仿真驗證，證實了改進流水線法的正確可行性。這兩種方案可以用于不同要求的應用領域，具有較大的靈活性。?

參考文獻?

[1] 胡予濮，張玉清，肖國鎮.對稱密碼學[M].北京：機械工業出版社，2002：143-162.?

[2] HASKINS G M. Securing asynchronous transfer mode?networks[D].Worcester Polytechnic Institute,Worcester,Massachusetts,USA,1997. ?

[3] MCLOONE M, MCCANNY J V. High-performance FPGA?implementation of DES using a novel method for implementing the key schedule[J]. Circuits, Devices and?Systems, IEE Proceedings,2003,150(5):373-378.?

[4] LUBBE V D. Basic methods of cryptography[J].IEE?Review, 1999,45(2):77-77.?

[5] 艾顯峰,葉宇煌.高速通用DES加解密芯片設計與實現.寧德師專學報，2004，16（3）.