基于改进型Montgomery模块的RSA算法及其Verilog模型的实现

曾小波　易志中　丁士憬

摘 要： 详细分析了RSA加密算法的原理及优化方法，提出一种高效可行改进型硬件模块的实现方案，并给出了效率分析以及在硬件平台上的仿真结果分析；通过仿真分析发现，相比以往的算法模型，该方案在时序以及面积上均做到了相当程度的优化，硬件的占用面积大幅度减少，具体的性能及功耗、稳定性有较大提高，为工程应用提供了良好的借鉴。

关键词： RSA； 不对称加密； 硬件实现成本； Montgomery算法

中图分类号： TN918.4?34 文献标识码： A 文章编号： 1004?373X（2014）17?0082?04

Abstract： The principles and optimization method of RSA encryption algorithm are analyzed in detail in this paper. A feasible and efficient implementation scheme of modified hardware modules is proposed. The analyses of efficiency and simulation results on the hardware platform are conducted. The simulation results show that， compared with the previous algorithm models， the scheme has already been optimized to a certain extent in both the time sequence and the volume， reduced the area that the hardwares used to occupy significantly， improved performance， power consumption， stability greatly and provided a good reference for engineering applications.

Keywords： RSA； asymmetric encryption； hardware implementation cost； Montgomery algorithm

0 引 言

作为首个较为完善的公开密钥算法，RSA密钥体系自1977年发布至今[1]，仍然有能力为多个领域的数据传输提供良好的保密功能。但是受其自身密钥体系的不对称性，以及破解的手段日益成熟等多方面因素的制约，现已证实当前只有长度大于1 024位的RSA密钥才有足够能力提供相对可以接收的密保性[2]。相应地，大密钥势必要求较长的运算时间，同时增加其硬件实现的成本（速度，面积等）。本文旨在提出一种高效可行的由硬件实现RSA加密算法的方案，并给出其相应Verilog模型的仿真结果。

4 结 语

本文细致分析了RSA加密算法的原理及简化过程，提出一种改进型硬件模块的实现方案，并给出了效率分析以及在硬件平台上的验证结果。相较于以往的算法模型，该方案在时序以及面积上均做到了相当程度的优化，在仅仅占用了一个CSA的Montgomery模型可减少50%左右在组合逻辑电阻中的传输延迟；该方法仅用一个类似于查找表的方案（4个预置寄存器，1个数选）替代了重组过程中的另一个CSA与大数乘法器，故硬件的占用面积亦可大幅度减少。

参考文献

[1] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and publick?key cryptosystems [J]. Communications of the ACM， 1978， 21（2）： 120?126.

[2] KOC C K. RSA hardware implementation [R]. Redwood City： RSA Laboratories， 1995.

[3] RSA Laboratories. The publick?key cryptography standards （PKCS） [R]. [S.l.]： RSA Data Security， Inc.， 1993.

[4] VANDERSYPEN L M K. NMR quantum computing： Realizing Shor′s algorithm [J]. Nature， 2001， 414： 883?887.

[5] TENCA A F， KOC C K. A scalable architecture for modular multipli?cation based on montgomery′s algorithm [J]. Lecture Notes in Computer Science， 1999， 1717： 94?108.

[6] COOK D L， IOANNIDIS J， KEROMYTIS A D， et al. Cryptographics： Secret key cryptography using graphics cards [C]// Proceedings of RSA Conference. New York： Springer， 2005： 540?574.

[7] CASTELLUCCIA C，MYKLETUN E， TSUDIK G. Improving secure server performance by Rebalancing SSL/TLS handshakes [EB/OL]. [2012?01?01]. http：// www.citeseerx.ist.psu.edu.

[8] CHE Shuai， BOYER M， MENG Jia?yuan， et al. A performance study ofgeneral?purpose applications on graphics processors using CUDA [J]. Journal of Parallel and Distributed Computing， 2008， 68（10）： 1370?1380.

[9] WALTER C D. Precise bounds for montgomery modular multiplication and some potentially insecure RSA Moduli [M]. San Jose： CT?RSA， 2002.

[10] SHAND M， VUILLEMIN J. Fast implementation of RSA cryptography [C]// Proceedings of 11th IEEE Synposium on Computer Arithmetic. [S.l.]： IEEE， 1993： 252?259.

[11] LU Chenghuai， ANDRE L M. Implementation of fast RSA key generation on smart cards [C]// Proceedings of the 2002 ACM Symposium on Applied Computing. USA： ACS Press， 2002： 214?220.

[12] BUNIMOV V， SCHIMMLER M， TOLG B. A complexity?effective version of Montgomery′s algorithm [C]// proceedings of Workshop on Complexity Effective Designs. Germany： Technical University of Braunschweig， 2002： 3?5.

摘 要： 详细分析了RSA加密算法的原理及优化方法，提出一种高效可行改进型硬件模块的实现方案，并给出了效率分析以及在硬件平台上的仿真结果分析；通过仿真分析发现，相比以往的算法模型，该方案在时序以及面积上均做到了相当程度的优化，硬件的占用面积大幅度减少，具体的性能及功耗、稳定性有较大提高，为工程应用提供了良好的借鉴。

关键词： RSA； 不对称加密； 硬件实现成本； Montgomery算法

中图分类号： TN918.4?34 文献标识码： A 文章编号： 1004?373X（2014）17?0082?04

Abstract： The principles and optimization method of RSA encryption algorithm are analyzed in detail in this paper. A feasible and efficient implementation scheme of modified hardware modules is proposed. The analyses of efficiency and simulation results on the hardware platform are conducted. The simulation results show that， compared with the previous algorithm models， the scheme has already been optimized to a certain extent in both the time sequence and the volume， reduced the area that the hardwares used to occupy significantly， improved performance， power consumption， stability greatly and provided a good reference for engineering applications.

Keywords： RSA； asymmetric encryption； hardware implementation cost； Montgomery algorithm

0 引 言

作为首个较为完善的公开密钥算法，RSA密钥体系自1977年发布至今[1]，仍然有能力为多个领域的数据传输提供良好的保密功能。但是受其自身密钥体系的不对称性，以及破解的手段日益成熟等多方面因素的制约，现已证实当前只有长度大于1 024位的RSA密钥才有足够能力提供相对可以接收的密保性[2]。相应地，大密钥势必要求较长的运算时间，同时增加其硬件实现的成本（速度，面积等）。本文旨在提出一种高效可行的由硬件实现RSA加密算法的方案，并给出其相应Verilog模型的仿真结果。

4 结 语

本文细致分析了RSA加密算法的原理及简化过程，提出一种改进型硬件模块的实现方案，并给出了效率分析以及在硬件平台上的验证结果。相较于以往的算法模型，该方案在时序以及面积上均做到了相当程度的优化，在仅仅占用了一个CSA的Montgomery模型可减少50%左右在组合逻辑电阻中的传输延迟；该方法仅用一个类似于查找表的方案（4个预置寄存器，1个数选）替代了重组过程中的另一个CSA与大数乘法器，故硬件的占用面积亦可大幅度减少。

参考文献

[1] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and publick?key cryptosystems [J]. Communications of the ACM， 1978， 21（2）： 120?126.

[2] KOC C K. RSA hardware implementation [R]. Redwood City： RSA Laboratories， 1995.

[3] RSA Laboratories. The publick?key cryptography standards （PKCS） [R]. [S.l.]： RSA Data Security， Inc.， 1993.

[4] VANDERSYPEN L M K. NMR quantum computing： Realizing Shor′s algorithm [J]. Nature， 2001， 414： 883?887.

[5] TENCA A F， KOC C K. A scalable architecture for modular multipli?cation based on montgomery′s algorithm [J]. Lecture Notes in Computer Science， 1999， 1717： 94?108.

[6] COOK D L， IOANNIDIS J， KEROMYTIS A D， et al. Cryptographics： Secret key cryptography using graphics cards [C]// Proceedings of RSA Conference. New York： Springer， 2005： 540?574.

[7] CASTELLUCCIA C，MYKLETUN E， TSUDIK G. Improving secure server performance by Rebalancing SSL/TLS handshakes [EB/OL]. [2012?01?01]. http：// www.citeseerx.ist.psu.edu.

[8] CHE Shuai， BOYER M， MENG Jia?yuan， et al. A performance study ofgeneral?purpose applications on graphics processors using CUDA [J]. Journal of Parallel and Distributed Computing， 2008， 68（10）： 1370?1380.

[9] WALTER C D. Precise bounds for montgomery modular multiplication and some potentially insecure RSA Moduli [M]. San Jose： CT?RSA， 2002.

[10] SHAND M， VUILLEMIN J. Fast implementation of RSA cryptography [C]// Proceedings of 11th IEEE Synposium on Computer Arithmetic. [S.l.]： IEEE， 1993： 252?259.

[11] LU Chenghuai， ANDRE L M. Implementation of fast RSA key generation on smart cards [C]// Proceedings of the 2002 ACM Symposium on Applied Computing. USA： ACS Press， 2002： 214?220.

[12] BUNIMOV V， SCHIMMLER M， TOLG B. A complexity?effective version of Montgomery′s algorithm [C]// proceedings of Workshop on Complexity Effective Designs. Germany： Technical University of Braunschweig， 2002： 3?5.

摘 要： 详细分析了RSA加密算法的原理及优化方法，提出一种高效可行改进型硬件模块的实现方案，并给出了效率分析以及在硬件平台上的仿真结果分析；通过仿真分析发现，相比以往的算法模型，该方案在时序以及面积上均做到了相当程度的优化，硬件的占用面积大幅度减少，具体的性能及功耗、稳定性有较大提高，为工程应用提供了良好的借鉴。

关键词： RSA； 不对称加密； 硬件实现成本； Montgomery算法

中图分类号： TN918.4?34 文献标识码： A 文章编号： 1004?373X（2014）17?0082?04

Abstract： The principles and optimization method of RSA encryption algorithm are analyzed in detail in this paper. A feasible and efficient implementation scheme of modified hardware modules is proposed. The analyses of efficiency and simulation results on the hardware platform are conducted. The simulation results show that， compared with the previous algorithm models， the scheme has already been optimized to a certain extent in both the time sequence and the volume， reduced the area that the hardwares used to occupy significantly， improved performance， power consumption， stability greatly and provided a good reference for engineering applications.

Keywords： RSA； asymmetric encryption； hardware implementation cost； Montgomery algorithm

0 引 言

作为首个较为完善的公开密钥算法，RSA密钥体系自1977年发布至今[1]，仍然有能力为多个领域的数据传输提供良好的保密功能。但是受其自身密钥体系的不对称性，以及破解的手段日益成熟等多方面因素的制约，现已证实当前只有长度大于1 024位的RSA密钥才有足够能力提供相对可以接收的密保性[2]。相应地，大密钥势必要求较长的运算时间，同时增加其硬件实现的成本（速度，面积等）。本文旨在提出一种高效可行的由硬件实现RSA加密算法的方案，并给出其相应Verilog模型的仿真结果。

4 结 语

本文细致分析了RSA加密算法的原理及简化过程，提出一种改进型硬件模块的实现方案，并给出了效率分析以及在硬件平台上的验证结果。相较于以往的算法模型，该方案在时序以及面积上均做到了相当程度的优化，在仅仅占用了一个CSA的Montgomery模型可减少50%左右在组合逻辑电阻中的传输延迟；该方法仅用一个类似于查找表的方案（4个预置寄存器，1个数选）替代了重组过程中的另一个CSA与大数乘法器，故硬件的占用面积亦可大幅度减少。

参考文献

[1] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and publick?key cryptosystems [J]. Communications of the ACM， 1978， 21（2）： 120?126.

[2] KOC C K. RSA hardware implementation [R]. Redwood City： RSA Laboratories， 1995.

[3] RSA Laboratories. The publick?key cryptography standards （PKCS） [R]. [S.l.]： RSA Data Security， Inc.， 1993.

[4] VANDERSYPEN L M K. NMR quantum computing： Realizing Shor′s algorithm [J]. Nature， 2001， 414： 883?887.

[5] TENCA A F， KOC C K. A scalable architecture for modular multipli?cation based on montgomery′s algorithm [J]. Lecture Notes in Computer Science， 1999， 1717： 94?108.

[6] COOK D L， IOANNIDIS J， KEROMYTIS A D， et al. Cryptographics： Secret key cryptography using graphics cards [C]// Proceedings of RSA Conference. New York： Springer， 2005： 540?574.

[7] CASTELLUCCIA C，MYKLETUN E， TSUDIK G. Improving secure server performance by Rebalancing SSL/TLS handshakes [EB/OL]. [2012?01?01]. http：// www.citeseerx.ist.psu.edu.

[8] CHE Shuai， BOYER M， MENG Jia?yuan， et al. A performance study ofgeneral?purpose applications on graphics processors using CUDA [J]. Journal of Parallel and Distributed Computing， 2008， 68（10）： 1370?1380.

[9] WALTER C D. Precise bounds for montgomery modular multiplication and some potentially insecure RSA Moduli [M]. San Jose： CT?RSA， 2002.

[10] SHAND M， VUILLEMIN J. Fast implementation of RSA cryptography [C]// Proceedings of 11th IEEE Synposium on Computer Arithmetic. [S.l.]： IEEE， 1993： 252?259.

[11] LU Chenghuai， ANDRE L M. Implementation of fast RSA key generation on smart cards [C]// Proceedings of the 2002 ACM Symposium on Applied Computing. USA： ACS Press， 2002： 214?220.

[12] BUNIMOV V， SCHIMMLER M， TOLG B. A complexity?effective version of Montgomery′s algorithm [C]// proceedings of Workshop on Complexity Effective Designs. Germany： Technical University of Braunschweig， 2002： 3?5.