有限域乘法器的设计实现与优化
|
摘要
本论文研究的主要内容是有限域算术、椭圆曲线加密算法和有限域乘法器。椭圆曲线加密算法是目前提供了最短的密钥长度和最优的每比特加密强度的公钥加密算法。而椭圆曲线加密算法的性能取决于有限域运算的速度,有限域乘法运算又是有限域运算中其他运算的基础。这使得有限域内的快速运算尤其是二元括域上的乘法运算成为了近期的研究热点。
本文的重点在于有限域乘法及有限域乘法器的算法设计,尤其是由三项式及五项式生成的二元域。考虑到目前信息安全系统的有效性,本文所提出的有限域乘法器结构均为位并行乘法器。
本文基于移位多项式基底(SPB)及其弱共轭基底(WDB)的有限域乘法器结构对有限域乘法器的设计实现进行了研究。在由不可约三项式和不可约五项式构建的有限域中,本文提出的架构在相同的空间复杂度下有着目前最小的时间复杂度。而且,本文提出的乘法器结构具有很高的规则性,大大降低了硬件电路设计者对数学知识的要求,为乘法器的快速设计实现提供了极为有利的条件。
进一步的,通过verilog硬件描述语言对三项式乘法器设计进行了实现,通过EDA软件Design Compiler,Power Compiler对设计进行了综合及优化、功耗分析及优化。研究得到结论,该乘法器架构在相同的空间复杂度的前提下实现了最低的时间复杂度(最短的关键路径)。不仅如此,该乘法器架构还以其规范性易于通过硬件描述语言实现。
The finite field arithmetic, elliptic curve cryptography (ECC) and the finite field multiplier are investigated in this thesis. ECC is the one of the known public crypto arithmetic which provides the smallest key size and the best strength-per-bit The calculation speed over finite field greatly affects the performance of ECC implementation. This fact has inspired many researchers to find ways on performing fast computations over finite fields, especially over large finite fields of characteristic two.
The central theme of the thesis is an investigation of finite field computations and their architectures, particularly the irreducible trinomials and pentanomials. All the multiplier architectures proposed in this thesis are bit-parallel finite field multipliers which canimprove the efficiency of cryptosystems significantly.
New structures of bit-parallel multiplier based on SPB and its weakly dual basis (WDB) over finite field are presented. To the fields generated by trinomials and pentanomials, the proposed structures have the shortest critical path up to date with nearly the same space complexity. Furthermore, it is easy for a designer to implement the proposed multipliers into hardware for their regular structures.
Furthermore, by implemented the proposal of new structure of finite field multiplier using verilog HDL, and analyzing in detail the performance of algorithms in finite field and the performance of the proposal using EDA soft Design Compiler, Power Compiler, we have drawn a conclusion that this proposal structures have the shortest critical path up to date with nearly the same space complexity. Furthermore, it is easy for a designer to implement the proposed multipliers into hardware for their regular structures. We also optimize the power consumption of the proposal structure.
本文的重点在于有限域乘法及有限域乘法器的算法设计,尤其是由三项式及五项式生成的二元域。考虑到目前信息安全系统的有效性,本文所提出的有限域乘法器结构均为位并行乘法器。
本文基于移位多项式基底(SPB)及其弱共轭基底(WDB)的有限域乘法器结构对有限域乘法器的设计实现进行了研究。在由不可约三项式和不可约五项式构建的有限域中,本文提出的架构在相同的空间复杂度下有着目前最小的时间复杂度。而且,本文提出的乘法器结构具有很高的规则性,大大降低了硬件电路设计者对数学知识的要求,为乘法器的快速设计实现提供了极为有利的条件。
进一步的,通过verilog硬件描述语言对三项式乘法器设计进行了实现,通过EDA软件Design Compiler,Power Compiler对设计进行了综合及优化、功耗分析及优化。研究得到结论,该乘法器架构在相同的空间复杂度的前提下实现了最低的时间复杂度(最短的关键路径)。不仅如此,该乘法器架构还以其规范性易于通过硬件描述语言实现。
The finite field arithmetic, elliptic curve cryptography (ECC) and the finite field multiplier are investigated in this thesis. ECC is the one of the known public crypto arithmetic which provides the smallest key size and the best strength-per-bit The calculation speed over finite field greatly affects the performance of ECC implementation. This fact has inspired many researchers to find ways on performing fast computations over finite fields, especially over large finite fields of characteristic two.
The central theme of the thesis is an investigation of finite field computations and their architectures, particularly the irreducible trinomials and pentanomials. All the multiplier architectures proposed in this thesis are bit-parallel finite field multipliers which canimprove the efficiency of cryptosystems significantly.
New structures of bit-parallel multiplier based on SPB and its weakly dual basis (WDB) over finite field are presented. To the fields generated by trinomials and pentanomials, the proposed structures have the shortest critical path up to date with nearly the same space complexity. Furthermore, it is easy for a designer to implement the proposed multipliers into hardware for their regular structures.
Furthermore, by implemented the proposal of new structure of finite field multiplier using verilog HDL, and analyzing in detail the performance of algorithms in finite field and the performance of the proposal using EDA soft Design Compiler, Power Compiler, we have drawn a conclusion that this proposal structures have the shortest critical path up to date with nearly the same space complexity. Furthermore, it is easy for a designer to implement the proposed multipliers into hardware for their regular structures. We also optimize the power consumption of the proposal structure.
引文
[1]N.Koblitz,"Elliptic Curve Cryptosystems," Mathematics of Computation,48,pp.203-209,1987.
[2]V.Miller,"Uses of Elliptic Curves in Cryptography," Advances in Cryptology,CRYPTO' 85,LNCS,vol.218,pp.417-426,1986.
[3]P.L.Montgomery,"Modular Multiplication without Trial Division," Mathematics of Computation,vol.44,no.170,pp.519-521,1985.
[4]C.K.Koc,and T.Acar,"Montgomery Multiplication in GF(2~k)," Design,Codes and Cryptography,vol.14,no.1,pp.57-69,1998.
[5]E.Savas,A.F.Tenca,and C.K.Koc,"A Scalable and Unified Multiplier Architecture for Finite Fields GF(p)and GF(2~m)," Cryptographic Hardware and Embedded Systems(CHES2000),pp.277-292,2000.
[6]E.D.Mastrovito,"VLSI Architectures for Multiplication over Finite Field GF(2~m)," Applied Algebra,Algebraic Algorithms and Error-Correcting Codes,T.Moraed,pp.297-309,Berlin:Springer-Verlag,1988.
[7]B.Sunar,and C.K.Roc,"Mastrovito Multiplier for All Wrinomials," IEEE Trans.Computers,vol.48,no.5,pp.522-527,2002.
[8]A.Halbutogullari,and C.K.Koc,"Mastrovito Multiplier for General Irreducible Polynomials," IEEE Trans.Computers,vol.49,no.5,pp.503-518,2000.
[9]T.Zhang,and K.K.Parhi,"Systematic Design of Original and Modified Mastrovito Multipliers for General Irreducible Polynomials," IEEE Trans Computers,vol.50,no.7,pp.734-749,2001.
[10]F.R-Henriquez,and C.K.Koc,"Parallel Multipliers Based on Special Irreducible Pentanomials," IEEE Trans Computers,vol.52,no.12,pp.1535-1542,2004.
[11]方冰,樊海宁,戴一奇GF(2~m)域上的一种Ⅱ型优化正规基乘法器及其FPGA实现[J].电子学报,2002,30(12A):2045-2048
[12]IEEE Std 1363-2000.IEEE Standard specifications for public-key cryptography.January 2000
[13]A.R.Masoleh and M.A.Hasan.Efficient digit-serial normal basis multipliers over GF(2~m).ACM Trans.Embedded Computing Systems(TECS),special issue on embedded systems and security,2004,3(3):575-592
[14]D.Hankerson,A.Menezes,and S.Vanstone,Guide to Elliptic Curve Cryptography,Springer-Verlag,2004.
[15]R.Schroeppel,H.Orman,S.O' Malley,and O.Spatscheck,"Fast Key Exchange with Elliptic Curve Systems," Advances in Cryptology-CRYPTO' 95,pp.43-56,1995.
[16]A.Satoh,and K.Takano," A Scalable Dual-Field Elliptic Curve Cryptographic Processor," IEEE Trans.Computers,vol.52,no.4,pp.449-460,2003.
[17]Darrel Hankerson,Alfred Menezes,Scott Vanstone,Guide to Elliptic Curve Cryptography[M]Springer-Verlag,2004.
[18]王庆先.有限域运算和椭圆曲线数乘运算研究:[学位论文].成都:电子科技大学,2005
[19]I.S.Hsu,T.K.Truong,L.J.Deutsch,and I.S.Reed,"A Comparison of VLSI Architecture of Finite Field Multipliers Using Dual,Normal,or Standard Bases,"IEEE Trans.Computers,vol.37,no.6,pp.735-739,1988.
[20]王毅.有限域GF(2~n)上椭圆胁线密码算法研究:[学位论文].重庆:西南交通大学,2006
[21]陈文宇.基于椭圆曲线加密系统的FPGA实现:[学位论文].上海:中国科学院研究生院
[22]龚书,刘文江,戎蒙恬 一种椭圆曲线加密算法及其实现[J].高技术通讯,2004,(3):25-28
[23]Paar C.Efficient VLSI architectures for bit-parallel computation in Galois fields[D].German:Univ of Essen,1994
[24]胡进.有限域GF(2~n)上椭圆曲线密码系统的硬件实现:[学位论文].武汉:武汉大学,2005
[25]张文龙 有限域上的通用乘法器设计[J].上海师范大学学报(自然科学版),2002,31(3):26-30
[26]H.Fan,and Y.Dai,"Fast Bit-Parallel GF(2~n)Multiplier for All Trinomials," IEEE Trans.Computers,vol.54,no.4,pp.485-490,2005.
[27]H.Wu,M.A.Hasan,and I.F.Blake,"New Low-Complexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases" IEEE Trans.Computers,vol.47,no.11,pp.1223-1234,2002.
[28]S.T.J.Fenn,M.Benaissa,and O.Taylor,"GF(2~n)Multiplication and Division Over the Dual Basis" IEEE Trans.Computers,vol.45,no.3,pp.319-327,1996.
[29]song L,Parhi K K.Efficient finite fields serial/parallel multiplication[A].Proc Int Conf Aplication Specific System Architectures and Processors[C].Chicago,IL.1996.72-82
[30]谭丽娟,陈运 适合资源受限环境的GF(2~m)域上乘法器结构[J].计算机工程与应用,2005,(12):80-81
[31]金意儿.高性能有限域乘法器的研究与实现:[学位论文].杭州:浙江大学,2007
[32]Mastrovito E.VLSI architectures for computation in Galois Fields[D].Linkoping Univ,Sweden.1991
[33]H.Wu.Bit-parallel finite field multiplier and squarer using polynomial basis[J].IEEE Trans Computers,2002,51(7):750-758
[34]A.R-Masoleh,and M.A.Hasan,"Low Complexity bit parallel Architectures for Polynomial Basis Multiplication over GF(2~m)," IEEE Trans.Computers,vol.53,no.8,pp.945-958,2004.
[35]F.R-Henriquez,and C.K.Koc,"Parallel Multipliers Based on Special Irreducible Pentanomials," IEEE Trans.Computers,vol.52,no.12,pp.1535-1542,2004.
[36]R.Lidl,and H.Niederreiter,Finite Fields,Reading,Mass.Addison-Wesley,1983.
[37]袁丹寿,戎蒙恬 一种可重构的快速有限域乘法器结构[J].电子与信息学报,2006,28(4):717-720
[38]卫学陶,戴紫彬,陈韬GF(2~m)域上通用可配置乘法器的设计与实现[J].计算机工程与应用,2007,43(12):91-93
[39]周浩华,沈泊,章倩苓.一种GF(2~k)域的高效乘法器及其VLSI实现[J].半导体学报.2001,22(8).
[40]Kitsos P,Theodoridis G,Koufopavlou O.An efficient reconfigurable multiplier architecture for GF(2~m)[J].Microelectronic Journal,2003,34(10):975-980
[41]唐薛峰,沈海斌,严晓浪GF(2~m)上椭圆曲线密码体制的硬件实现[J].计算机工程与应用,2004,(11):96-98
[42]Halbutogullari A,Koc,C K.Mastrovito multiplier for general irreducible polynomials[J].IEEE Transactions on Computers,2000,49(5):503-518
[43]袁丹寿,戎蒙恬,陈波 一种并行的有限域乘法器结构[J].上海交通大学学报,2005,39(4):636-639,644
[44]顾震宇,曾晓洋,陈超等 一种高效的可伸缩分组并行有限域乘法器及VLSI实现[J].微 电子学与计算机,2003,(4):50-56
[45]袁丹寿,戎蒙恬,陈波 一种快速有限域乘法器结构及其VLSI实现[J].微电子学,2005,35(3):314-317
[46]Moon S,Park J,Lee Y,A fast finite field multiplier architecture for high-security cryptographic application[J].IEEE Trans Consumer Electronics,2001,47(3):700-708
[47]H Wu,M A Hasan,Low complexity Bit-parallel Multipliers for a Class of Finite Fields.IEEE Trans Computers,Aug.1998,47(8)
[48]SMIC 0.35 micron,3.3 volt Optimum Silicon SC Library,Synopsys Corp.2003.
[49]SMIC 0.18μm Logic18 Process 1.8-Volt SAGE-X~(TM)Standard Cell Library Databook,Artisan Components,2003.
[50]A P Chandrakasan,R Brodesen.Low Power Digital CMOS Design.Kluwer,1995
[2]V.Miller,"Uses of Elliptic Curves in Cryptography," Advances in Cryptology,CRYPTO' 85,LNCS,vol.218,pp.417-426,1986.
[3]P.L.Montgomery,"Modular Multiplication without Trial Division," Mathematics of Computation,vol.44,no.170,pp.519-521,1985.
[4]C.K.Koc,and T.Acar,"Montgomery Multiplication in GF(2~k)," Design,Codes and Cryptography,vol.14,no.1,pp.57-69,1998.
[5]E.Savas,A.F.Tenca,and C.K.Koc,"A Scalable and Unified Multiplier Architecture for Finite Fields GF(p)and GF(2~m)," Cryptographic Hardware and Embedded Systems(CHES2000),pp.277-292,2000.
[6]E.D.Mastrovito,"VLSI Architectures for Multiplication over Finite Field GF(2~m)," Applied Algebra,Algebraic Algorithms and Error-Correcting Codes,T.Moraed,pp.297-309,Berlin:Springer-Verlag,1988.
[7]B.Sunar,and C.K.Roc,"Mastrovito Multiplier for All Wrinomials," IEEE Trans.Computers,vol.48,no.5,pp.522-527,2002.
[8]A.Halbutogullari,and C.K.Koc,"Mastrovito Multiplier for General Irreducible Polynomials," IEEE Trans.Computers,vol.49,no.5,pp.503-518,2000.
[9]T.Zhang,and K.K.Parhi,"Systematic Design of Original and Modified Mastrovito Multipliers for General Irreducible Polynomials," IEEE Trans Computers,vol.50,no.7,pp.734-749,2001.
[10]F.R-Henriquez,and C.K.Koc,"Parallel Multipliers Based on Special Irreducible Pentanomials," IEEE Trans Computers,vol.52,no.12,pp.1535-1542,2004.
[11]方冰,樊海宁,戴一奇GF(2~m)域上的一种Ⅱ型优化正规基乘法器及其FPGA实现[J].电子学报,2002,30(12A):2045-2048
[12]IEEE Std 1363-2000.IEEE Standard specifications for public-key cryptography.January 2000
[13]A.R.Masoleh and M.A.Hasan.Efficient digit-serial normal basis multipliers over GF(2~m).ACM Trans.Embedded Computing Systems(TECS),special issue on embedded systems and security,2004,3(3):575-592
[14]D.Hankerson,A.Menezes,and S.Vanstone,Guide to Elliptic Curve Cryptography,Springer-Verlag,2004.
[15]R.Schroeppel,H.Orman,S.O' Malley,and O.Spatscheck,"Fast Key Exchange with Elliptic Curve Systems," Advances in Cryptology-CRYPTO' 95,pp.43-56,1995.
[16]A.Satoh,and K.Takano," A Scalable Dual-Field Elliptic Curve Cryptographic Processor," IEEE Trans.Computers,vol.52,no.4,pp.449-460,2003.
[17]Darrel Hankerson,Alfred Menezes,Scott Vanstone,Guide to Elliptic Curve Cryptography[M]Springer-Verlag,2004.
[18]王庆先.有限域运算和椭圆曲线数乘运算研究:[学位论文].成都:电子科技大学,2005
[19]I.S.Hsu,T.K.Truong,L.J.Deutsch,and I.S.Reed,"A Comparison of VLSI Architecture of Finite Field Multipliers Using Dual,Normal,or Standard Bases,"IEEE Trans.Computers,vol.37,no.6,pp.735-739,1988.
[20]王毅.有限域GF(2~n)上椭圆胁线密码算法研究:[学位论文].重庆:西南交通大学,2006
[21]陈文宇.基于椭圆曲线加密系统的FPGA实现:[学位论文].上海:中国科学院研究生院
[22]龚书,刘文江,戎蒙恬 一种椭圆曲线加密算法及其实现[J].高技术通讯,2004,(3):25-28
[23]Paar C.Efficient VLSI architectures for bit-parallel computation in Galois fields[D].German:Univ of Essen,1994
[24]胡进.有限域GF(2~n)上椭圆曲线密码系统的硬件实现:[学位论文].武汉:武汉大学,2005
[25]张文龙 有限域上的通用乘法器设计[J].上海师范大学学报(自然科学版),2002,31(3):26-30
[26]H.Fan,and Y.Dai,"Fast Bit-Parallel GF(2~n)Multiplier for All Trinomials," IEEE Trans.Computers,vol.54,no.4,pp.485-490,2005.
[27]H.Wu,M.A.Hasan,and I.F.Blake,"New Low-Complexity Bit-Parallel Finite Field Multipliers Using Weakly Dual Bases" IEEE Trans.Computers,vol.47,no.11,pp.1223-1234,2002.
[28]S.T.J.Fenn,M.Benaissa,and O.Taylor,"GF(2~n)Multiplication and Division Over the Dual Basis" IEEE Trans.Computers,vol.45,no.3,pp.319-327,1996.
[29]song L,Parhi K K.Efficient finite fields serial/parallel multiplication[A].Proc Int Conf Aplication Specific System Architectures and Processors[C].Chicago,IL.1996.72-82
[30]谭丽娟,陈运 适合资源受限环境的GF(2~m)域上乘法器结构[J].计算机工程与应用,2005,(12):80-81
[31]金意儿.高性能有限域乘法器的研究与实现:[学位论文].杭州:浙江大学,2007
[32]Mastrovito E.VLSI architectures for computation in Galois Fields[D].Linkoping Univ,Sweden.1991
[33]H.Wu.Bit-parallel finite field multiplier and squarer using polynomial basis[J].IEEE Trans Computers,2002,51(7):750-758
[34]A.R-Masoleh,and M.A.Hasan,"Low Complexity bit parallel Architectures for Polynomial Basis Multiplication over GF(2~m)," IEEE Trans.Computers,vol.53,no.8,pp.945-958,2004.
[35]F.R-Henriquez,and C.K.Koc,"Parallel Multipliers Based on Special Irreducible Pentanomials," IEEE Trans.Computers,vol.52,no.12,pp.1535-1542,2004.
[36]R.Lidl,and H.Niederreiter,Finite Fields,Reading,Mass.Addison-Wesley,1983.
[37]袁丹寿,戎蒙恬 一种可重构的快速有限域乘法器结构[J].电子与信息学报,2006,28(4):717-720
[38]卫学陶,戴紫彬,陈韬GF(2~m)域上通用可配置乘法器的设计与实现[J].计算机工程与应用,2007,43(12):91-93
[39]周浩华,沈泊,章倩苓.一种GF(2~k)域的高效乘法器及其VLSI实现[J].半导体学报.2001,22(8).
[40]Kitsos P,Theodoridis G,Koufopavlou O.An efficient reconfigurable multiplier architecture for GF(2~m)[J].Microelectronic Journal,2003,34(10):975-980
[41]唐薛峰,沈海斌,严晓浪GF(2~m)上椭圆曲线密码体制的硬件实现[J].计算机工程与应用,2004,(11):96-98
[42]Halbutogullari A,Koc,C K.Mastrovito multiplier for general irreducible polynomials[J].IEEE Transactions on Computers,2000,49(5):503-518
[43]袁丹寿,戎蒙恬,陈波 一种并行的有限域乘法器结构[J].上海交通大学学报,2005,39(4):636-639,644
[44]顾震宇,曾晓洋,陈超等 一种高效的可伸缩分组并行有限域乘法器及VLSI实现[J].微 电子学与计算机,2003,(4):50-56
[45]袁丹寿,戎蒙恬,陈波 一种快速有限域乘法器结构及其VLSI实现[J].微电子学,2005,35(3):314-317
[46]Moon S,Park J,Lee Y,A fast finite field multiplier architecture for high-security cryptographic application[J].IEEE Trans Consumer Electronics,2001,47(3):700-708
[47]H Wu,M A Hasan,Low complexity Bit-parallel Multipliers for a Class of Finite Fields.IEEE Trans Computers,Aug.1998,47(8)
[48]SMIC 0.35 micron,3.3 volt Optimum Silicon SC Library,Synopsys Corp.2003.
[49]SMIC 0.18μm Logic18 Process 1.8-Volt SAGE-X~(TM)Standard Cell Library Databook,Artisan Components,2003.
[50]A P Chandrakasan,R Brodesen.Low Power Digital CMOS Design.Kluwer,1995