簡易檢索 / 詳目顯示

回結果列表
研究生： 呂俊瑋
Lyu, Jyun-Wei
論文名稱： 基於AES的合成對偶密碼器之設計與實現
Design and Implementation of Composite-Dual Cipher Based on AES
指導教授： 賴溪松
Laih, Chi-Sung
學位類別： 碩士
Master
系所名稱： 電機資訊學院 - 電腦與通信工程研究所
Institute of Computer & Communication Engineering
論文出版年： 2006
畢業學年度： 94
語文別： 英文
論文頁數： 116
中文關鍵詞： 進階加密標準 、次級場 、合成場 、對偶密碼器 、區塊密碼器 、合成對偶進階加密標準 、合成對偶密碼器
外文關鍵詞： Output Feedback (OFB), AES, Dual Cipher, Counter (CTR), Electronic Codebook (ECB), Composite Fields, Cipher Feedback (CFB), Cipher Block Chaining (CBC), Galois Field
相關次數： 點閱：75  下載：1 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 美國國家標準與技術局在西元2001年時選定Rijndael演算法，並且發表了進階加密標準(AES)。雖然AES可以被使用在許多不同的應用層面，在過去的五年間，特定硬體實現的研究已經成為了一個熱門的主題。Rijndael演算法的作者Rijmen就曾建議在計算256個元素的反元素這條重要路徑上使用次級場的算術運算。尤其當場元素被映射到一個同型的(isomorphic)合成場，某些Galois場運算的計算成本是比較少的，這是眾所皆知。另一方面，Barkan與Biham在西元2002年曾提出對偶密碼器的概念。對偶密碼器的出現已將進階加密標準的討論帶往了更廣泛的領域。儘管在加密或解密過程中，對偶密碼器的中間值與進階加密標準的中間值不一致，對偶密碼器與進階加密標準在各個方面都是等價的。在本論文中，我們先將進階加密標準的場元素映射到對偶進階加密標準的場元素，再將對偶進階加密標準的場元素映射到合成場的表示法—合成對偶進階加密標準。接下來，合成對偶進階加密標準可以被參數化後形成一個可調整的進階加密標準—合成對偶密碼器。這個提出的合成對偶密碼器可以提供超過2的21次方個不同的進階加密標準區塊密碼器組合。資料不僅可以用私密金鑰與初始值加密，而且可以用不同的區塊密碼器加密。

    Advanced Encryption Standard (AES) was published in 2001 with Rijndael algorithm. Although AES is used in many different applications, the study of dedicated hardware implementation has become a hot topic in the past five years. Rijmen, one of the designer of Rijndael algorithm, had suggested the usage of subfield arithmetic in the critical path of computing an inverse of 256 elements. In particular, it is well-known that the computational cost of certain Galois Field operations is lower when field elements are mapped to an isomorphic composite field. On the other side, Barkan and Biham proposed the concept of dual ciphers in 2002. The emersion of dual ciphers has brought the discussion of AES to a wide region. Although the intermediate values of dual cipher during encryption or decryption are different from those of AES, the dual ciphers are equivalent to AES in all aspects. In this thesis, we map the field elements of AES to those of Dual AES first, and then translate the field elements of Dual AES to a composite field representation—Composite-Dual AES. Next, the Composite-Dual AES can be parameterized to become a configurable AES—Composite-Dual Cipher. The proposed Composite-Dual Cipher can provide more than 2^21 different AES block cipher schemes. Data can be encrypted not only with secret keys and initial vectors, but also by different block ciphers.

    Chinese Abstract　-iii- English Abstract　-iv- Acknowledgments　-v- Contents　-vii- List of Tables　-xi- List of Figures　-xiii- Acronyms and Trademarks　-xv- 1　Introduction　-1- 　1.1　General Background　-1- 　1.2　Research Motives　-2- 　1.3　Contributions　-3- 　　1.3.1　Improve Paar's Algorithm to Suit General Case　-3- 　　1.3.2　Improve Wu and Lu's Algorithm　-3- 　　1.3.3　Find All the Implementations of Dual AES　-3- 　　1.3.4　Find All the Matrices for Mapping from GF(2^8) to GF((2^4)^2)　-4- 　　1.3.5　Propose the Composite-Dual Cipher　-4- 　1.4　Overview　-4- 2　Composite Fields　-6- 　2.1　Galois Fields　-6- 　　2.1.1　Essential Background　-6- 　　2.1.2　Polynomials and Extension Fields　-9- 　　2.1.3　Bases of Finite Fields　-11- 　2.2　Mapping from Binary to Composite Field Representations　-11- 　　2.2.1　Mapping with Primitive Polynomial　-12- 　　2.2.2　Extension from Primitive to Irreducible　-15- 　2.3　Multiplicative Inverse over Composite Fields　-17- 　　2.3.1　Inverse over GF((2^4)^2)　-17- 　　2.3.2　Inverse over GF(((2^2)^2)^2)　-18- 　2.4　Extensive Discussion of Composite Fields　-20- 　　2.4.1　Expressions in GF((2^4)^2)　-20- 　　2.4.2　Expressions in GF(((2^2)^2)^2)　-21- 3　The Design of Dual AES　-22- 　3.1　An Overview of AES　-22- 　　3.1.1　AES History　-22- 　　3.1.2　Operation in Byte Array　-22- 　　3.1.3　State, Secret Key, and the Number of Rounds　-23- 　　3.1.4　Cipher　-24- 　　3.1.5　Key Expansion　-28- 　　3.1.6　Inverse Cipher　-30- 　3.2　Discussion of Dual AES　-31- 　　3.2.1　Generalized Representation of Dual AES　-31- 　　3.2.2　Development of Dual AES　-32- 　　3.2.3　Mapping from AES into Dual AES　-35- 　3.3　A Comprehensive Dissection of Dual AES　-39- 　　3.3.1　Another Aspect of Generalized Dual AES　-40- 　　3.3.2　Varied Implementaion of Dual AES　-41- 4　Composite-Dual Cipher　-42- 　4.1　Derivation　-42- 　4.2　AES in a Composite Field—Composite AES　-43- 　4.3　Composite-Dual AES　-45- 　4.4　A Configurable AES—Composite-Dual Cipher　-46- 5　Hardware Architecture in AES　-49- 　5.1　State of the Art in High Speed　-49- 　　5.1.1　Design Issues　-49- 　　5.1.2　Optimization Criteria　-51- 　　5.1.3　Related Work　-52- 　5.2　State of the Art in Low Cost　-54- 　　5.2.1　Low Die Size Design　-54- 　　5.2.2　Low Power Consumption Design　-54- 　　5.2.3　Related Work　-55- 6　Implementation Details　-56- 　6.1　SubBytes Unit　-56- 　6.2　MixColumns Unit　-57- 　6.3　Key Schedule Unit　-59- 　6.4　Matrix Generation Unit　-60- 　6.5　Multiplication in Galois Field GF(2^8)　-61- 　6.6　Arithmetic in Composite Field GF((2^4)^2)　-62- 　　6.6.1　Multiplication　-62- 　　6.6.2　Inversion　-63- 　6.7　Arithmetic in Galois Field GF(2^4)　-64- 　　6.7.1　Multiplication　-64- 　　6.7.2　Inversion　-65- 　6.8　Encryption　-66- 　　6.8.1　128-bit Key Length　-67- 　　6.8.2　192-bit Key Length　-67- 　　6.8.3　256-bit Key Length　-68- 　6.9　Decryption　-68- 　　6.9.1　128-bit Key Length　-69- 　　6.9.2　192-bit Key Length　-69- 　　6.9.3　256-bit Key Length　-70- 　6.10　Throughput　-71- 7　Conclusions and Future Work　-72- 　7.1　Conclusions　-72- 　7.2　Future Work　-73- Bibliography　-74- Appendix　-80- A　Modes of Operation　-80- 　A.1　Electronic Codebook Mode　-80- 　A.2　Cipher Block Chaining Mode　-80- 　A.3　Cipher Feedback Mode　-81- 　A.4　Output Feedback Mode　-82- 　A.5　Counter Mode　-83- B　Direct Inversion over GF(2^4)　-85- C　Generators for Mapping Matrix M　-88- D　Sets of Primitive Elements　-90- E　The Transformation Matrix T　-107- F　The Reduction Matrix Q for Different R(x)　-112- Vita　-116-

    [1]　"Data Encryption Standard (DES)," National Institute of Standards and Technology, Federal Information Processing Standards Publications 46-3, Oct. 1999.

    [2]　"Advanced Encryption Standard (AES)," National Institute of Standards and Technology, Federal Information Processing Standards Publications 197, Nov. 2001.

    [3]　"Recommendation for block cipher modes of operation - methods and techniques,"National Institute of Standards and Technology, Special Publication 800-38A, Dec. 2001, http://csrc.nist.gov/publications/nistpubs/800-38a/sp800-38a.pdf.

    [4]　R. Anderson, E. Biham, and L. Knudsen, "The Serpent algorithm," [Online]. Available: http://www.cl.cam.ac.uk/ftp/users/rja14/serpent.tar.gz, Aug. 1998.

    [5]　E. Barkan and E. Biham, "In how many ways can you write Rijndael?" in Proc. ASIACRYPT 2002, ser. Lecture Notes in Computer Science, Y. Zheng, Ed., vol. 2501. Berlin, Germany: Springer-Verlag, Dec. 2002, pp. 160-175.

    [6]　C. Burwick, D. Coppersmith, E. D'Avignon, R. Gennaro, S. Halevi, C. Jutla, S. M. M. Jr., L. O’Connor, M. Peyravian, D. Safford, and N. Zunic, "The MARS algorithm," [Online]. Available: http://www.research.ibm.com/security/mars.pdf, Aug. 1998.

    [7]　D. Canright, "A very compact S-Box for AES," in Proc. CHES 2005, ser. Lecture Notes in Computer Science, J. R. Rao and B. Sunar, Eds., vol. 3659. Berlin, Germany: Springer-Verlag, Aug. 2005, pp. 441-455.

    [8]　P. Chodowiec and K. Gaj, "Very compact FPGA implementation of the AES algorithm," in Proc. CHES 2003, ser. Lecture Notes in Computer Science, C. D. Walter, C. K. Koc, and C. Paar, Eds., vol. 2779. Berlin, Germany: Springer-Verlag, Sept. 2003, pp. 319-333.

    [9]　P. Chodowiec, K. Gaj, P. Bellows, and B. Schott, "Experimental testing of the gigabit IPSec-compliant implementations of Rijndael and triple DES using SLAAC-1V FPGA accelerator board," in Proc. ISC 2001, ser. Lecture Notes in Computer Science, G. I. Davida and Y. Frankel, Eds., vol. 2200. Berlin, Germany: Springer-Verlag, Oct. 2001, pp. 220-234.

    [10]　P. Chodowiec, P. Khuon, and K. Gaj, "Fast implementations of secret-key block ciphers using mixed inner- and outer-round pipelining," in Proc. ACM/SIGDA International Symposium on Field programmable gate arrays, M. Schlag and R. Tessier, Eds. New York, USA: ACM Press, Feb. 2001, pp. 94-102.

    [11]　J. Daemen and V. RijmenTwofish, "The Rijndael algorithm," [Online]. Available: http://csrc.nist.gov/CryptoToolkit/aes/rijndael/Rijndael-ammended.pdf, Aug. 1998.

    [12]　A. Dandalis, V. K. Prasanna, and J. D. Rolim, "A comparative study of performance of AES final candidates using FPGAs," in Proc. CHES 2000, ser. Lecture Notes in Computer Science, C. K. Koc and C. Paar, Eds., vol. 1965. Berlin, Germany: Springer-Verlag, Aug. 2000, pp. 125-140.

    [13]　A. J. Elbirt, W. Yip, B. Chetwynd, and C. Paar, "An FPGA-based performance evaluation of the AES block cipher candidate algorithm finalists," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 9, no. 4, pp. 545-557, Aug. 2001.

    [14]　M. Feldhofer, J. Wolkerstorfer, and V. Rijmen, "AES implementation on a grain of sand," IEE Proceedings Information Security, vol. 152, no. 1, pp. 13-20, Oct. 2005.

    [15]　V. Fischer and M. Drutarovsky, "Two methods of Rijndael implementation in reconfigurable hardware," in Proc. CHES 2001, ser. Lecture Notes in Computer Science, C. K. Koc, D. Naccache, and C. Paar, Eds., vol. 2162. Berlin, Germany: Springer-Verlag, May 2001, pp. 77-92.

    [16]　F. K. Gurkaynak, A. Burg, N. Felber, W. Fichtner, D. Gasser, F. Hug, and H. Kaeslin, "A 2 Gb/s balanced AES crypto-chip implementation," in Proc. ACM Great Lakes Symposium on VLSI 2004, J. Lach, G. Qu, and Y. I. Ismail, Eds. New York, USA: ACM Press, Apr. 2004, pp. 60-63.

    [17]　D. W. Hardy and C. L. Walker, Applied Algebra: Codes, Ciphers, and Discrete Algorithms. Prentice Hall, 2003.

    [18]　A. Hodjat, D. D. Hwang, B. Lai, K. Tiri, and I. Verbauwhede, "A 3.84 Gbits/s AES crypto coprocessor with modes of operation in a 0.18-um CMOS technology," in Proc. ACM Great Lakes Symposium on VLSI 2005, J. Lach, G. Qu, and Y. I. Ismail, Eds. New York, USA: ACM Press, Apr. 2005, pp. 60-63.

    [19]　A. Hodjat and I. Verbauwhede, "A 21.54 Gbits/s fully pipelined AES processor on FPGA," in Proc. IEEE Symposium on Field-Programmable Custom Computing Machines, J. Arnold and K. L. Pocek, Eds., Apr. 2004, pp. 308-309.

    [20]　A. Hodjat and I. Verbauwhede, "Minimum area cost for a 30 to 70 Gbits/s AES processor," in Proc. IEEE Computer society Annual Symposium on VLSI, A. Smailagic and M. Bayoumi, Eds., Feb. 2004, pp. 83-88.

    [21]　A. Hodjat and I. Verbauwhede, "Area-throughput trade-offs for fully pipelined 30 to 70 Gbits/s AES processors," IEEE Transactions on Computers, vol. 55, no. 4, pp. 366-372, Apr. 2006.

    [22]　N. S. Kim, T.Mudge, and R. Brown, "A 2.3Gb/s fully integrated and synthesizable AES Rijndael core," in Proc. IEEE 2003 Custom Integrated Circuits Conference, Sept. 2003, pp. 193-196.

    [23]　A. Labbe and A. Perez, "AES implementation on FPGA: Time - flexibility tradeoff," in Proc. FPL 2002, ser. Lecture Notes in Computer Science, M. Glesner, P. Zipf, and M. Renovell, Eds., vol. 2438. Berlin, Germany: Springer-Verlag, Sept. 2002, pp. 836-844.

    [24]　H. Li and Z. Friggstad, "An efficient architecture for the AES mix columns operation," in Proc. IEEE International Symposium on Circuits and Systems, vol. 5, May 2005, pp. 4637-4640.

    [25]　R. Lidl and H. Niederreiter, Introduction to Finite Fields and their Applications, 2nd ed. Cambridge University Press, July 1994.

    [26]　S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Prentice Hall, 2004, ch. 2, pp. 25-65.

    [27]　C.-C. Lu and S.-Y. Tseng, "Integrated design of AES (Advanced Encryption Standard) encrypter and decrypter," in Proc. IEEE International Conference on Application-Specific Systems, Architectures and Processors, July 2002, pp. 277-285.

    [28]　S.-C. Lu, "On the design of AES based on dual cipher and composite field," Master’s thesis, Department of Electrical Engineering, National Cheng Kung University, Tainan, Taiwan, R.O.C., June 2003.

    [29]　S. Mangard, M. Aigner, and S. Dominikus, "A highly regular and scalable AES hardware architecture," IEEE Transactions on Computers, vol. 52, no. 4, pp. 483-491, Apr. 2003.

    [30]　E. D. Mastrovito, "VLSI designs for multiplication over finite fields GF(2m)," in Proc. AAECC-6, ser. Lecture Notes in Computer Science, J. R. Rao and B. Sunar, Eds., vol. 357. Berlin, Germany: Springer-Verlag, July 1988, pp. 297-309.

    [31]　M. McLoone and J. McCanny, "High performance single-chip FPGA Rijndael algorithm implementations," in Proc. CHES 2001, ser. Lecture Notes in Computer Science, C. K. Koc, D. Naccache, and C. Paar, Eds., vol. 2162. Berlin, Germany: Springer-Verlag, May 2001, pp. 65-76.

    [32]　S. McMillan and C. Patterson, "JBitstm implementations of the Advanced Encryption Standard (Rijndael)," in Proc. FPL 2001, ser. Lecture Notes in Computer Science, G. Brebner and R. Woods, Eds., vol. 2147. Berlin, Germany: Springer-Verlag, Aug. 2001, pp. 162-171.

    [33]　N. Mentens, L. Batina, B. Preneel, and I. Verbauwhede, "A systematic evaluation of compact hardware implementations for the Rijndael S-Box," in Proc. CT-RSA 2005, ser. Lecture Notes in Computer Science, A. Menezes, Ed., vol. 3376. Berlin, Germany: Springer-Verlag, Feb.14-18, 2005, pp. 323-333.

    [34]　S. Morioka and A. Satoh, "An optimized S-Box circuit architecture for low power AES design," in Proc. CHES 2002, ser. Lecture Notes in Computer Science, B. S. K. Jr., C. K. Koc, and C. Paar, Eds., vol. 2523. Berlin, Germany: Springer-Verlag, Aug. 2002, pp. 172-186.

    [35]　C. Paar, "Efficient VLSI architectures for bit parallel computation in Galois fields," Ph.D. dissertation, Institute for Experimental Mathematics, University of Essen, Germany, 1994.

    [36]　E. Painkras, "Efficient modeling and implementation of advanced encryption standard using systemc," in Proc. IEEE International Symposium on Signal Processing and Information Technology, Dec. 2004, pp. 85-89.

    [37]　N. Pramstaller and J. Wolkerstorfer, "A universal and efficient AES co-processor for field programmable logic arrays," in Proc. FPL 2004, ser. Lecture Notes in Computer Science, J. Becker, M. Platzner, and S. Vernalde, Eds., vol. 3203. Berlin, Germany: Springer-Verlag, Dec. 2004, pp. 565-574.

    [38]　A. Reyhani-Masoleh and M. A. Hasan, "On low complexity bit parallel polynomial basis multipliers," in Proc. CHES 2003, ser. Lecture Notes in Computer Science, C. D.Walter, C. K. Koc, and C. Paar, Eds., vol. 2779. Berlin, Germany: Springer-Verlag, Sept. 2003, pp. 189-202.

    [39]　A. Reyhani-Masoleh and M. A. Hasan, "Low complexity bit parallel architectures for polynomial basis multiplication over GF(2m)," IEEE Transactions on Computers, vol. 53, no. 8, pp. 945-959, Aug. 2004.

    [40]　V. Rijmen, Efficient Implementation of the Rijndael S-box, Department of Electrical Engineering, Katholieke Universiteit Leuven, Belgium, 2000.

    [41]　R. Rivest, "The RC6 algorithm," [Online]. Available: ftp://ftp.rsasecurity.com/pub/rsalabs/rc6/rc6v11.pdf, Aug. 1998.

    [42]　G. Rouvroy, F.-X. Standaert, J.-J. Quisquater, and J.-D. Legat, "Compact and efficient encryption/decryption module for FPGA implementation of the AES Rijndael very well suited for small embedded applications," in Proc. International Conference on Information Technology: Coding and Computing, vol. 2. IEEE Computer Society, Apr. 2004, pp. 583-587.

    [43]　A. Rudra, P. K. Dubey, C. S. Jutla, V. Kumar, J. R. Rao, and P. Rohatgi, "Efficient Rijndael encryption implementation with composite field arithmetic," in Proc. CHES 2001, ser. Lecture Notes in Computer Science, C. K. Koc, D. Naccache, and C. Paar, Eds., vol. 2162. Berlin, Germany: Springer-Verlag, May 2001, pp. 171-184.

    [44]　G. Saggese, A. Mazzeo, N. Mazzocca, and A. Strollo, "An FPGA-based performance analysis of the unrolling, tiling, and pipelining of the AES algorithm," in Proc. FPL 2003, ser. Lecture Notes in Computer Science, P. K. Cheung, G. A. Constantinides, and J. T. de Sousa, Eds., vol. 2778. Berlin, Germany: Springer-Verlag, Sept. 2003, pp. 292-302.

    [45]　A. Satoh, S. Morioka, K. Takano, and S. Munetoh, "A compact Rijndael hardware architecture with S-Box optimization," in Proc. ASIACRYPT 2001, ser. Lecture Notes in Computer Science, C. Boyd, Ed., vol. 2248. Berlin, Germany: Springer-Verlag, Dec. 2001, pp. 239-254.

    [46]　B. Schneier, J. Kelsey, D. Whiting, D. Wagner, C. Hall, and N. Ferguson, "The Twofish algorithm," [Online]. Available: http://www.schneier.com/paper-twofish-paper.pdf, Aug. 1998.

    [47]　W. Stallings, Cryptography and Network Security: Principles and Practices, 4th ed. Prentice Hall, 2006.

    [48]　F.-X. Standaert, G. Rouvroy, J.-J. Quisquater, and J.-D. Legat, "Efficient implementation of Rijndael encryption in reconfigurable hardware: Improvements and design tradeoffs," in Proc. CHES 2003, ser. Lecture Notes in Computer Science, C. D.Walter, C. K. Koc, and C. Paar, Eds., vol. 2779. Berlin, Germany: Springer-Verlag, Sept. 2003, pp. 334-350.

    [49]　C.-P. Su, C.-T. H. Tsung-Fu Lin, and C.-W. Wu, "A high-throughput low-cost AES processor," IEEE Communications Magazine, vol. 41, no. 12, pp. 86-91, 2003.

    [50]　I. Verbauwhede, P. Schaumont, and H. Kuo, "Design and performance testing of a 2.29-GB/s Rijndael processor," IEEE Journal of Solid-State Circuits, vol. 38, no. 3, pp. 569-572, 2003.

    [51]　S.-S. Wang and W.-S. Ni, "An efficient FPGA implementation of advanced encryption standard algorithm," in Proc. IEEE International Symposium on Circuits and Systems, vol. 2, May 2004, pp. 597-600.

    [52]　J. Wolkerstorfer, E. Oswald, and M. Lamberger, "An ASIC implementation of the AES SBoxes," in Proc. CT-RSA 2002, ser. Lecture Notes in Computer Science, B. Preneel, Ed., vol. 2272. Berlin, Germany: Springer-Verlag, Feb. 2002, pp. 67-78.

    [53]　S.-Y. Wu, S.-C. Lu, and C.-S. Laih, "Design of AES based on Dual Cipher and composite field," in Proc. CT-RSA 2004, ser. Lecture Notes in Computer Science, T. Okamoto, Ed., vol. 2964. Berlin, Germany: Springer-Verlag, Feb. 23-27, 2004, pp. 25-38.

    [54]　J. Zambreno, D. Nguyen, and A. Choudhary, "Exploring area/delay tradeoffs in an AES FPGA implementation," in Proc. FPL 2004, ser. Lecture Notes in Computer Science, J. Becker, M. Platzner, and S. Vernalde, Eds., vol. 3203. Berlin, Germany: Springer-Verlag, Dec. 2004, pp. 575-585.

    [55]　X. Zhang and K. K. Parhi, "Implementation approaches for the advanced encryption standard algorithm," IEEE Circuits and Systems Magazine, vol. 2, no. 4, pp. 22-46, Apr. 2002.

    [56]　X. Zhang and K. K. Parhi, "High-speed VLSI architectures for the AES algorithm," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 12, no. 9, pp. 957-967, Sept. 2004.

    下載圖示 校內：2007-07-11公開
    校外：2008-07-11公開
    QR CODE