RSA加密算法及其IC设计方法研究
|
摘要
在当今的信息时代,信息是社会发展需要的战略资源。国际上围绕信息的获取、使用和控制的竞争愈演愈烈,信息安全成为维护国家安全和社会稳定的一个焦点,因此其成为信息领域的研究课题。作为信息安全的核心和基石,密码算法一直是国内外研究和讨论的热点问题。
RSA密码体制是目前比较成熟的公钥密码体制,可以用于数据加解密、数字签名、身份认证等。RSA算法的核心运算是大整数模幂运算,而模幂运算是由一系列的模乘运算构成。模幂、模乘运算是RSA算法运算速度的瓶颈,它们的运算速度决定了RSA密码算法运算的效率。对RSA加密芯片优化主要有两方面:一是提高速度;二是减小面积。本文工作主要是对RSA加密算法进行研究并在优化面积的基础上进行IC设计。
为了很好的解决RSA密码芯片的优化问题,本文深入研究了RSA密码算法,采用了从左到右的密钥扫描方式与Montgomery算法相结合的优化算法,提高了RSA算法的运算效率,特别是减少了资源占用,缩小了规模。在此基础上,设计了RSA密码芯片的总体方案和系统结构;阐述了RSA加密模块的详细设计方法并进行了仿真测试;仿真测试结果证明了本文所设计的RSA加密模块能够正确的实现RSA加/解密功能。
本文设计的模块主要是减小规模,缩小面积,适用于便携式、移动式的加密设备,例如:移动式电脑加密机。创新之处:在优化加密算法基础上提出了一种低规模的RSA加密模块的体系结构设计方案;提出详细的电路设计方法。最终实现了1024位的RSA密码算法,并通过了软件的仿真与测试。
In the period of information, the information becomes one of the strategic resources which the society develops needs. The international competition about the acquistion, use and control of the information is upgrading. As the information security has become a focus of safeguarding national security and social stability, so the ways to make the information safe are the important issues in the information field. As the core and the foundation of information security,the cryptography is the focus of correlated researches and discussions in the world.
RSA is mature public-key cryptography at present,it can encrypt,use a scratch of digital and validate degee.RSA is applied in many secure system.The large numer exponentiation algorithms is the key of RSA cryptography system,which is performed by a series of modular multiplication.Exponentiation algorithms and modular multiplication are bottlenecks of efficiency.Their efficiency decides the efficiency of RSA. Optimization of the RSA encryption chips has two aspects :One, improving the speed;The other,reducing the area.My thesis is that researching RSA arithmetic and IC designing based on optimization in the area.
In order to optimize encryption chip of RSA, this paper research RSA cryptogram arithmetic in depth, bring forward a parallel arithmetic, which combined secret key from left to right scan mode and Montgomery algorithm, which shift the operation efficiency of RSA arithmetic, In particular it reducts resources occupation, reduces the Scale.And, gives the total design scheme and system structure of RSA cryptogram chip, expounds the design of RSA encryption module in detail and simulation test; simulation test proves that the design of this RSA encryption module can realize RSA encryption /RSA decryption.
In this paper, the encryption module is that reducing the scale and narrowing area, applying to portable encryption equipment, such as: mobile computer encryption machine. Innovation: Proposes a design of a low scale RSA encryption module and architecture based on optimization of encryption algorithm.The module realizes the 1024-bit RSA cipher algorithm and passes the simulation tests.
RSA密码体制是目前比较成熟的公钥密码体制,可以用于数据加解密、数字签名、身份认证等。RSA算法的核心运算是大整数模幂运算,而模幂运算是由一系列的模乘运算构成。模幂、模乘运算是RSA算法运算速度的瓶颈,它们的运算速度决定了RSA密码算法运算的效率。对RSA加密芯片优化主要有两方面:一是提高速度;二是减小面积。本文工作主要是对RSA加密算法进行研究并在优化面积的基础上进行IC设计。
为了很好的解决RSA密码芯片的优化问题,本文深入研究了RSA密码算法,采用了从左到右的密钥扫描方式与Montgomery算法相结合的优化算法,提高了RSA算法的运算效率,特别是减少了资源占用,缩小了规模。在此基础上,设计了RSA密码芯片的总体方案和系统结构;阐述了RSA加密模块的详细设计方法并进行了仿真测试;仿真测试结果证明了本文所设计的RSA加密模块能够正确的实现RSA加/解密功能。
本文设计的模块主要是减小规模,缩小面积,适用于便携式、移动式的加密设备,例如:移动式电脑加密机。创新之处:在优化加密算法基础上提出了一种低规模的RSA加密模块的体系结构设计方案;提出详细的电路设计方法。最终实现了1024位的RSA密码算法,并通过了软件的仿真与测试。
In the period of information, the information becomes one of the strategic resources which the society develops needs. The international competition about the acquistion, use and control of the information is upgrading. As the information security has become a focus of safeguarding national security and social stability, so the ways to make the information safe are the important issues in the information field. As the core and the foundation of information security,the cryptography is the focus of correlated researches and discussions in the world.
RSA is mature public-key cryptography at present,it can encrypt,use a scratch of digital and validate degee.RSA is applied in many secure system.The large numer exponentiation algorithms is the key of RSA cryptography system,which is performed by a series of modular multiplication.Exponentiation algorithms and modular multiplication are bottlenecks of efficiency.Their efficiency decides the efficiency of RSA. Optimization of the RSA encryption chips has two aspects :One, improving the speed;The other,reducing the area.My thesis is that researching RSA arithmetic and IC designing based on optimization in the area.
In order to optimize encryption chip of RSA, this paper research RSA cryptogram arithmetic in depth, bring forward a parallel arithmetic, which combined secret key from left to right scan mode and Montgomery algorithm, which shift the operation efficiency of RSA arithmetic, In particular it reducts resources occupation, reduces the Scale.And, gives the total design scheme and system structure of RSA cryptogram chip, expounds the design of RSA encryption module in detail and simulation test; simulation test proves that the design of this RSA encryption module can realize RSA encryption /RSA decryption.
In this paper, the encryption module is that reducing the scale and narrowing area, applying to portable encryption equipment, such as: mobile computer encryption machine. Innovation: Proposes a design of a low scale RSA encryption module and architecture based on optimization of encryption algorithm.The module realizes the 1024-bit RSA cipher algorithm and passes the simulation tests.
引文
[1]涂序彦,柔性智能计算机的发展前景,计算机世界.1999.4.19
[2]刘大力,MISC体系结构计算机的理论与方法,The 9th International Conference on Advabced Science and Technology.1993.3.PP16~26.
[3]冯登国.网络安全与技术[M].北京:科学出版社,2003.
[4]William Stallingx Cryptography and Network Security : Prindplesand PracticSecond Edition[M].北京:清华大学出版社,2002.
[5] Ann L Chervenak,Vivekanand Vellanki,Zachary Kurmas.Protecting File Systems: A Survey of Backup Techn iques[A].Proc 0{Joint NASA and IEEE Mass Storage ConeC].1998.
[6]张振祥,“一个53位数的分解”,计算机研究与发展.V.32,N6.1995.6PP1~4.
[7]周同衡,“单RSA位的密码安全性及注记”,计算机研究与发展,V.24,N.5,1987.5
[8]R.Fischlin and C.P.Schnorr,Stronger security proofs for RASA and Rabin bits,proceedings of CRYPTO97LNCS1233,1997,springer-verlag,pp267~297.
[9]D.Coppersmith.M.Franklin,J.Patarin and M.reiter,Low-exponent RASA with related messages,proceedings of CRYPTO96LNCS1070,1996,springer-verlag,pp1~9.
[10]M.Bellare and P.Rogaway,The exact security of digital signatures-how to sign with RSA and Rabin,proceedings of CRYPTO96LNCS1070,1996, springer-verlag, pp399~416.
[11]P.Emerson,prime number generation and primality,testing,www.middleburg.edu, Dcc,1997.
[12]Y.Saouter,A new method for the generation of strong prime numbers.citeseer.nj. Nec.com/cachepage/3815,jun.1995.
[13]Bruce Schneier著,“应用密码学”,机械工业出版社,2000年1月。
[14]T.ELGamal,A public key cryptosystem and a signature scheme base on discrete Logarithms,IEEE traction on information theory,V.31,N.4,July1985.pp469~472.
[15]Colin D.Walter,”Exponentiation using division chains”,IEEE trasactions on computers,V.47,N.7,July1998,pp757~765.
[16]D.E.Knuth,the art of computer programming:seminumerical algorithms,V2. Reading,MA Addison-Wesley,Second edition,1981.
[17]Daniel M.Gordon,”A survey of fast exponentiation methods”,http://citeseer.nj. nec.com,December 30,1997.
[18]Cetin Kaya Koc,RSA hardware implementation,Koc@ece.orst.edu,August1995.
[19]G.R.Blakley,A computer algorithm for the product AB modulo M,IEEE Transact- ions on computers,V.32,N.5,1983.5,pp497~500.
[20]Antoon Bosselaers,Rene Govaerts and Joos Vandewalle,Comparison of three mo- dular reduction functions,www:esat.luleuven.ac.be,October 1993.
[21]IN.Chen and R.Willoner.”An O(n) parallel multiplier with bit-sequential input”IEEE TRASACTJONS ON COMPUTERS,V.C-28,N.8,OCTOBER 1979,pp721~727.
[22]M.T.Santoro and M.A.Horoeitz.”SPIM:A pipelined 64×64 bit iterative multiplier”IEEE J.Solid state Circuits,V.24,N.2,APRIL 1989,pp487~494.
[23]L.Dadda,”Some schemes for parallel multipliers”Alta Frequenza,V.34,N.5,1965, pp349~356.
[24]李占才,高速RSA密码算法硬件实现研究,北京科技大学,2001.10
[25]麻永新、曾晓洋,基于Barrett模乘算法的RASA密码协处理器设计,系统工程与电子技术,Vol28,No.6,2006.6
[26]陈幕羿、胡海军,脉动阵列变换的搜索策略及自动化算法,计算机应用研究,2007.4.
[27]焉永明、曾云,FPGA器件结构及系统集成研究,吉首大学学报,2006年02期。
[28]王冕、周玉洁,分割式Montgomery模乘运算的线性高基心动阵列新结构,计算机科学,2006年01期。
[29]陈智萍,应用LPM简化CPLD器件开发的探讨,现代电子技术,2006年16期。
[30]王英,RASA算法中大素数的快速生成方式,湖南科技学院学报,2005,26(5):14-16
[31]B.Scheier著,应用密码学-协议、算法和C源程序。机械工业出版社,2001.
[32]李树国、周润德,RSA密码协处理器的实现,电子学报,2001,29(11):1441-1444.
[33]黄秀荪、仇玉林,LFU算法的ASIC实现,电子器件,2007年01期。
[34]钟文明、刘新宁,基于Cyclone系列FPGA的1024点FFT算法的实现,电子工程师,2007年02期。
[35]H.Orup.A100Kbits/s single chip modular exponentition processor.Hot chips VI, Symposium record,1994:53-59.
[36]Po-Song Chen,Hwang Shih-Arm,Wu Cheng-Wen.Systolic RSA public key cry- ptosystem.IEEE,1996,4:408-411.
[37]Ching-Chao Yang,A new RSA public key cryptosystem hardware design based On Montgomery’s algorithm.IEEE,1998,45(7):908-913.
[38]Jyh-Huei Guo,Design and implementation of an RASA public-key cryptosystem. IEEE,1999:504-507.
[39]Teak-Won Kwon,Chang-Seok You,Two implementation methods of a 1024-bitRSA Cryptoprocessor based on modified Montgomery Algorithm,0-7803-6685-9/01 2001 IEEE.
[40]Altera corporation.Altera Digital Library,2002.
[2]刘大力,MISC体系结构计算机的理论与方法,The 9th International Conference on Advabced Science and Technology.1993.3.PP16~26.
[3]冯登国.网络安全与技术[M].北京:科学出版社,2003.
[4]William Stallingx Cryptography and Network Security : Prindplesand PracticSecond Edition[M].北京:清华大学出版社,2002.
[5] Ann L Chervenak,Vivekanand Vellanki,Zachary Kurmas.Protecting File Systems: A Survey of Backup Techn iques[A].Proc 0{Joint NASA and IEEE Mass Storage ConeC].1998.
[6]张振祥,“一个53位数的分解”,计算机研究与发展.V.32,N6.1995.6PP1~4.
[7]周同衡,“单RSA位的密码安全性及注记”,计算机研究与发展,V.24,N.5,1987.5
[8]R.Fischlin and C.P.Schnorr,Stronger security proofs for RASA and Rabin bits,proceedings of CRYPTO97LNCS1233,1997,springer-verlag,pp267~297.
[9]D.Coppersmith.M.Franklin,J.Patarin and M.reiter,Low-exponent RASA with related messages,proceedings of CRYPTO96LNCS1070,1996,springer-verlag,pp1~9.
[10]M.Bellare and P.Rogaway,The exact security of digital signatures-how to sign with RSA and Rabin,proceedings of CRYPTO96LNCS1070,1996, springer-verlag, pp399~416.
[11]P.Emerson,prime number generation and primality,testing,www.middleburg.edu, Dcc,1997.
[12]Y.Saouter,A new method for the generation of strong prime numbers.citeseer.nj. Nec.com/cachepage/3815,jun.1995.
[13]Bruce Schneier著,“应用密码学”,机械工业出版社,2000年1月。
[14]T.ELGamal,A public key cryptosystem and a signature scheme base on discrete Logarithms,IEEE traction on information theory,V.31,N.4,July1985.pp469~472.
[15]Colin D.Walter,”Exponentiation using division chains”,IEEE trasactions on computers,V.47,N.7,July1998,pp757~765.
[16]D.E.Knuth,the art of computer programming:seminumerical algorithms,V2. Reading,MA Addison-Wesley,Second edition,1981.
[17]Daniel M.Gordon,”A survey of fast exponentiation methods”,http://citeseer.nj. nec.com,December 30,1997.
[18]Cetin Kaya Koc,RSA hardware implementation,Koc@ece.orst.edu,August1995.
[19]G.R.Blakley,A computer algorithm for the product AB modulo M,IEEE Transact- ions on computers,V.32,N.5,1983.5,pp497~500.
[20]Antoon Bosselaers,Rene Govaerts and Joos Vandewalle,Comparison of three mo- dular reduction functions,www:esat.luleuven.ac.be,October 1993.
[21]IN.Chen and R.Willoner.”An O(n) parallel multiplier with bit-sequential input”IEEE TRASACTJONS ON COMPUTERS,V.C-28,N.8,OCTOBER 1979,pp721~727.
[22]M.T.Santoro and M.A.Horoeitz.”SPIM:A pipelined 64×64 bit iterative multiplier”IEEE J.Solid state Circuits,V.24,N.2,APRIL 1989,pp487~494.
[23]L.Dadda,”Some schemes for parallel multipliers”Alta Frequenza,V.34,N.5,1965, pp349~356.
[24]李占才,高速RSA密码算法硬件实现研究,北京科技大学,2001.10
[25]麻永新、曾晓洋,基于Barrett模乘算法的RASA密码协处理器设计,系统工程与电子技术,Vol28,No.6,2006.6
[26]陈幕羿、胡海军,脉动阵列变换的搜索策略及自动化算法,计算机应用研究,2007.4.
[27]焉永明、曾云,FPGA器件结构及系统集成研究,吉首大学学报,2006年02期。
[28]王冕、周玉洁,分割式Montgomery模乘运算的线性高基心动阵列新结构,计算机科学,2006年01期。
[29]陈智萍,应用LPM简化CPLD器件开发的探讨,现代电子技术,2006年16期。
[30]王英,RASA算法中大素数的快速生成方式,湖南科技学院学报,2005,26(5):14-16
[31]B.Scheier著,应用密码学-协议、算法和C源程序。机械工业出版社,2001.
[32]李树国、周润德,RSA密码协处理器的实现,电子学报,2001,29(11):1441-1444.
[33]黄秀荪、仇玉林,LFU算法的ASIC实现,电子器件,2007年01期。
[34]钟文明、刘新宁,基于Cyclone系列FPGA的1024点FFT算法的实现,电子工程师,2007年02期。
[35]H.Orup.A100Kbits/s single chip modular exponentition processor.Hot chips VI, Symposium record,1994:53-59.
[36]Po-Song Chen,Hwang Shih-Arm,Wu Cheng-Wen.Systolic RSA public key cry- ptosystem.IEEE,1996,4:408-411.
[37]Ching-Chao Yang,A new RSA public key cryptosystem hardware design based On Montgomery’s algorithm.IEEE,1998,45(7):908-913.
[38]Jyh-Huei Guo,Design and implementation of an RASA public-key cryptosystem. IEEE,1999:504-507.
[39]Teak-Won Kwon,Chang-Seok You,Two implementation methods of a 1024-bitRSA Cryptoprocessor based on modified Montgomery Algorithm,0-7803-6685-9/01 2001 IEEE.
[40]Altera corporation.Altera Digital Library,2002.