基于改進(jìn)型Montgomery模塊的RSA算法及其Verilog模型的實(shí)現(xiàn)

曾小波　易志中　丁士憬

摘 要： 詳細(xì)分析了RSA加密算法的原理及優(yōu)化方法，提出一種高效可行改進(jìn)型硬件模塊的實(shí)現(xiàn)方案，并給出了效率分析以及在硬件平臺(tái)上的仿真結(jié)果分析；通過(guò)仿真分析發(fā)現(xiàn)，相比以往的算法模型，該方案在時(shí)序以及面積上均做到了相當(dāng)程度的優(yōu)化，硬件的占用面積大幅度減少，具體的性能及功耗、穩(wěn)定性有較大提高，為工程應(yīng)用提供了良好的借鑒。

關(guān)鍵詞： RSA； 不對(duì)稱加密； 硬件實(shí)現(xiàn)成本； Montgomery算法

中圖分類號(hào)： TN918.4?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

作為首個(gè)較為完善的公開(kāi)密鑰算法，RSA密鑰體系自1977年發(fā)布至今[1]，仍然有能力為多個(gè)領(lǐng)域的數(shù)據(jù)傳輸提供良好的保密功能。但是受其自身密鑰體系的不對(duì)稱性，以及破解的手段日益成熟等多方面因素的制約，現(xiàn)已證實(shí)當(dāng)前只有長(zhǎng)度大于1 024位的RSA密鑰才有足夠能力提供相對(duì)可以接收的密保性[2]。相應(yīng)地，大密鑰勢(shì)必要求較長(zhǎng)的運(yùn)算時(shí)間，同時(shí)增加其硬件實(shí)現(xiàn)的成本（速度，面積等）。本文旨在提出一種高效可行的由硬件實(shí)現(xiàn)RSA加密算法的方案，并給出其相應(yīng)Verilog模型的仿真結(jié)果。

4 結(jié) 語(yǔ)

本文細(xì)致分析了RSA加密算法的原理及簡(jiǎn)化過(guò)程，提出一種改進(jìn)型硬件模塊的實(shí)現(xiàn)方案，并給出了效率分析以及在硬件平臺(tái)上的驗(yàn)證結(jié)果。相較于以往的算法模型，該方案在時(shí)序以及面積上均做到了相當(dāng)程度的優(yōu)化，在僅僅占用了一個(gè)CSA的Montgomery模型可減少50%左右在組合邏輯電阻中的傳輸延遲；該方法僅用一個(gè)類似于查找表的方案（4個(gè)預(yù)置寄存器，1個(gè)數(shù)選）替代了重組過(guò)程中的另一個(gè)CSA與大數(shù)乘法器，故硬件的占用面積亦可大幅度減少。

參考文獻(xiàn)

[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.

摘 要： 詳細(xì)分析了RSA加密算法的原理及優(yōu)化方法，提出一種高效可行改進(jìn)型硬件模塊的實(shí)現(xiàn)方案，并給出了效率分析以及在硬件平臺(tái)上的仿真結(jié)果分析；通過(guò)仿真分析發(fā)現(xiàn)，相比以往的算法模型，該方案在時(shí)序以及面積上均做到了相當(dāng)程度的優(yōu)化，硬件的占用面積大幅度減少，具體的性能及功耗、穩(wěn)定性有較大提高，為工程應(yīng)用提供了良好的借鑒。

關(guān)鍵詞： RSA； 不對(duì)稱加密； 硬件實(shí)現(xiàn)成本； Montgomery算法

中圖分類號(hào)： TN918.4?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

作為首個(gè)較為完善的公開(kāi)密鑰算法，RSA密鑰體系自1977年發(fā)布至今[1]，仍然有能力為多個(gè)領(lǐng)域的數(shù)據(jù)傳輸提供良好的保密功能。但是受其自身密鑰體系的不對(duì)稱性，以及破解的手段日益成熟等多方面因素的制約，現(xiàn)已證實(shí)當(dāng)前只有長(zhǎng)度大于1 024位的RSA密鑰才有足夠能力提供相對(duì)可以接收的密保性[2]。相應(yīng)地，大密鑰勢(shì)必要求較長(zhǎng)的運(yùn)算時(shí)間，同時(shí)增加其硬件實(shí)現(xiàn)的成本（速度，面積等）。本文旨在提出一種高效可行的由硬件實(shí)現(xiàn)RSA加密算法的方案，并給出其相應(yīng)Verilog模型的仿真結(jié)果。

4 結(jié) 語(yǔ)

本文細(xì)致分析了RSA加密算法的原理及簡(jiǎn)化過(guò)程，提出一種改進(jìn)型硬件模塊的實(shí)現(xiàn)方案，并給出了效率分析以及在硬件平臺(tái)上的驗(yàn)證結(jié)果。相較于以往的算法模型，該方案在時(shí)序以及面積上均做到了相當(dāng)程度的優(yōu)化，在僅僅占用了一個(gè)CSA的Montgomery模型可減少50%左右在組合邏輯電阻中的傳輸延遲；該方法僅用一個(gè)類似于查找表的方案（4個(gè)預(yù)置寄存器，1個(gè)數(shù)選）替代了重組過(guò)程中的另一個(gè)CSA與大數(shù)乘法器，故硬件的占用面積亦可大幅度減少。

參考文獻(xiàn)

[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.

摘 要： 詳細(xì)分析了RSA加密算法的原理及優(yōu)化方法，提出一種高效可行改進(jìn)型硬件模塊的實(shí)現(xiàn)方案，并給出了效率分析以及在硬件平臺(tái)上的仿真結(jié)果分析；通過(guò)仿真分析發(fā)現(xiàn)，相比以往的算法模型，該方案在時(shí)序以及面積上均做到了相當(dāng)程度的優(yōu)化，硬件的占用面積大幅度減少，具體的性能及功耗、穩(wěn)定性有較大提高，為工程應(yīng)用提供了良好的借鑒。

關(guān)鍵詞： RSA； 不對(duì)稱加密； 硬件實(shí)現(xiàn)成本； Montgomery算法

中圖分類號(hào)： TN918.4?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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 引 言

作為首個(gè)較為完善的公開(kāi)密鑰算法，RSA密鑰體系自1977年發(fā)布至今[1]，仍然有能力為多個(gè)領(lǐng)域的數(shù)據(jù)傳輸提供良好的保密功能。但是受其自身密鑰體系的不對(duì)稱性，以及破解的手段日益成熟等多方面因素的制約，現(xiàn)已證實(shí)當(dāng)前只有長(zhǎng)度大于1 024位的RSA密鑰才有足夠能力提供相對(duì)可以接收的密保性[2]。相應(yīng)地，大密鑰勢(shì)必要求較長(zhǎng)的運(yùn)算時(shí)間，同時(shí)增加其硬件實(shí)現(xiàn)的成本（速度，面積等）。本文旨在提出一種高效可行的由硬件實(shí)現(xiàn)RSA加密算法的方案，并給出其相應(yīng)Verilog模型的仿真結(jié)果。

4 結(jié) 語(yǔ)

本文細(xì)致分析了RSA加密算法的原理及簡(jiǎn)化過(guò)程，提出一種改進(jìn)型硬件模塊的實(shí)現(xiàn)方案，并給出了效率分析以及在硬件平臺(tái)上的驗(yàn)證結(jié)果。相較于以往的算法模型，該方案在時(shí)序以及面積上均做到了相當(dāng)程度的優(yōu)化，在僅僅占用了一個(gè)CSA的Montgomery模型可減少50%左右在組合邏輯電阻中的傳輸延遲；該方法僅用一個(gè)類似于查找表的方案（4個(gè)預(yù)置寄存器，1個(gè)數(shù)選）替代了重組過(guò)程中的另一個(gè)CSA與大數(shù)乘法器，故硬件的占用面積亦可大幅度減少。

參考文獻(xiàn)

[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.