可調式密碼處理器設計與支援平台

Design of a Scalable Cryptographic Processor and Supporting Platforms

王振興(Chen-Hsing Wang)

指導教授 ： 吳誠文

國立清華大學/電機資訊學院/電機工程學系/博士(2009年)

https://doi.org/10.6843/NTHU.2009.00710

摘要

隨著有線和無線通訊應用的快速發展，資訊安全已經變的越來越重要，因為這些通訊應用經常帶來致命的威脅。為了有效保護在公開
網路上流通的隱密資料，密碼學是目前最安全同時也是最可靠的方
法，然而實做這些可靠的密碼演算法通常耗費非常高的硬體或軟體
複雜度，因此好的硬體或軟體設計方法是非常重要的。

在這篇論文中，基於一個非對稱性字元基礎的蒙哥馬利乘法演算法
，我們提出一個高效能多模乘法器，此乘法器支援一般整數乘法、
多項式乘法與矩陣向量乘法。由於大部分的非對稱性密碼演算法是
由模數指數、模數反元素與模數乘法運算所構成，而蒙哥馬利演算
法可有效加速這些模數運算，因此我們所提出的多模乘法器，可以
加速大部分的非對稱性密碼演算法。另外，此字元基礎乘法器支援
可變長度的金鑰，在電路實做時，此架構在效能與硬體成本上亦提
供高彈性的選擇。我們更進一步擴展這個多模乘法器來支援完整的
AES演算法。我們利用組合場數學來化簡AES演算法中最複雜的運算
，接著我們重新排列化簡過後的AES運算順序，最後我們合併可以
化簡的矩陣向量乘法。經由化簡後，AES 演算法可拆解成矩陣向量
乘法與非矩陣向量乘法，其中非矩陣向量乘法約佔AES 所有面積的
11%，而矩陣向量乘法部分和輸、輸出緩衝器約佔總面積的87%。我
們選擇128 x 32 bits 大小的規格來實做多模乘法器電路，因為這
個乘法器的大小同時對AES和非對稱性密碼演算法可以得到最大的
效益。我們所提出的128 x 32 bits 多模乘法器對256-bit 的一般
乘法可以提供441Mbps 效能，對256-bit 的多項式乘法可以提供
511Mbps 效能。搭配另外的21.93K 等效邏輯匣(實做非矩陣向量乘
法部分)，在AES 演算法方面，此多模乘法器分別對128-bit、192-
bit、256-bit 的金鑰可以提供1.28Gbps、1.06Gbps、0.91Gbps 效能。

遵循平台式的設計方法，我們亦提出一個通用的單晶片密碼系統，
此密碼系統可應付現有之有線、無線通訊應用所需的密碼處理效能
。針對此單晶片密碼系統，我們開發了四個輔助設計平台：架構平
台、自動化設計軟體平台、設計輔助測試平台、雛型驗證平台。架
構平台利用AMBA 匯流排系統，整合實驗室自行開發的密碼處理器
與一個商用的一般處理器，此密碼處理器提供四類的密碼功能：
AES、RSA、HMAC-SHA1/HMAC-MD5、亂數產生器。自動化設計軟體平
台提供一個完整的軟體環境，此平台整合了晶片設計所用到的軟體
，包含由清大電機系、資工系所開發的軟體與商用的軟體。設計輔
助測試平台利用實驗室所開發的兩套軟體(STEAC、BRAINS)，提供
此密碼單晶片系統一個完整的測試架構。雛型驗證平台加速此單晶
片系統開發與驗證的時間。利用所開發的四個平台，我們已陸續設
計並製造了幾個晶片，這證明了我們所開發之平台的實用性。

關鍵字

密碼處理器 ； 純量乘法 ； 多項式乘法 ； 矩陣向量乘法 ； 平台式設計 ； 單晶片系統

並列摘要

With the dramatic growth of wired and wireless communication applications, information security becomes more and more important as these applications usually bring more security threats. To secure personal/private information on the public and unprotected network, cryptography is one of the safest and most reliable method based on its robust mathematical foundation. However, the robust mathematic computation usually results in high hardware or time complexity when the cryptographic algorithms are implemented by hard-wired logic
or software program, respectively. A good methodology in
hardware or software implementation thus is highly desirable.

In this thesis, we propose a highly efficient multi-mode
multiplier supporting prime field, polynomial field, and
matrix-vector multiplications based on an asymmetric word-based Montgomery multiplication algorithm. Since many asymmetric-key cryptographic algorithms are composed of modular exponentiation, modular inversion, or modular multiplication, they can be well addressed by the proposed multi-mode multiplier. In addtion, as the design of the multi-mode multiplier is based on a word-based architecture, it supports a scalable key if the
data storage size is large enough; and it provides a flexible trade-off between performance and area cost in multiplier circuit design. We further extend the multi-mode multiplier to deal with the major operation of AES (Advanced Encryption Standard), i.e.,
matrix-vector multiplication. We apply the composite field
arithmetic on the AES round function to reduce its most
area-consuming step, i.e., SubBytes. By the composite field
arithmetic, the SubBytes step is partitioned into multiplicative inversion over GF((2^4)^2) and some matrix-vector multiplications. The order of four AES steps is rearranged such that the matrices for different steps can be merged into a single matrix. Finally, the AES round is unrolled and recombined; then more matrices can be merged. After the decomposition and regrouping, the original AES round is clearly divided into two parts:
matrix-vector multiplications and non-matrix-vector
multiplications, where the non-matrix-vector multiplication part only stands for 11% of the total gates in the preliminary analysis. We choose the size, 128 x 32 bits, to implement the multi-mode multiplier circuit, as it can get the maximum benefits for both AES and asymmetric-key cryptographic algorithms. The proposed multi-mode 128 x 32 bits multiplier provides a throughput of 441Mbps and 511Mbps for 256-bit operands over GF(p) and GF(2n) at a clock rate of 100MHz, respectively. With 21.93K additional gates for AES (to implement the nonmatrix- vector multiplication part), it can provide 1.28Gbps, 1.06Gbps, and 0.91Gbps throughput rate for 128-, 192-, and
256-bit keys, respectively.

Following the platform-based design methodology, we also propose a generic crypto-SOC and four supporting platforms, where the crypto-SOC is suitable for a wide range of security related protocols in wired and wireless network applications. The four specific platforms, i.e., architecture platform, EDA platform, DFT platform, and prototyping platform, can assist users to develop SOC products more systematically and efficiently.
The architecture platform integrates a general-purpose processor and an in-house crypto-processor by a commercial bus system, i.e.,AMBA (Advanced Micro-controller Bus Architecture). The in-house crypto-processor integrates four crypto-engines (AES, RSA, HMAC-MD5/SHA-1, and Random Number Generator (RNG)) and an intelligent crypto-DMA controller by an AHB (Advanced High-performance Bus). Here, the AES, HMAC-MD5/SHA-1, and RNG are contributed by our group members. The crypto-DMA not only manages
the bulk data movement between internal crypto-engines and
external RAMs, but also manipulates sophisticated flow controls of crypto-engines. The EDA platform provides a complete CAD tool environment which integrates in-house tools and commercial EDA tools to a core-based design flow. The DFT platform provides an SOC test integration methodology, mainly based on two of our in-house tools: STEAC (SOC TEst Aid Console) and BRAINS (BIST for RAM in Seconds). The prototyping platform accelerates function verification of the proposed crypto-SOC when new
crypto-engines or components are integrated. Based on the
proposed crypto-SOC and four assisting platforms, several
prototype chips, for different applications, have been designed and fabricated by different CMOS processes, demonstrating the feasibility and effectiveness of the proposed platforms.

並列關鍵字

crypto-processor ； normal integer multiplication ； polynomial multiplication ； matrix-vector multiplication ； platform-based design ； SOC

參考文獻

[2] S. Kent and R. Atkinson, Security Architecture for the Internet Protocol. IETF Network Working Group, 1998. RFC 2401.

[6] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communications of the ACM, vol. 21, no. 2, pp. 120–126, Feb. 1978.

[9] NIST, Advanced Encryption Standard (AES). Springfield, VA 22161: National Technical Information Service, Nov. 2001.

[12] L. Wu, C. Weaver, and T. Austin, “CryptoManiac: A fast flexible architecture for secure communication,” in Proc. 28th Ann. Int’l Symp. on Computer Architecture, pp. 110–119, 2001.

[13] I. Corporation, “Intel IXP2800 network processor product brief.” http://www.intel.com/, 2002.