Algoritmos de Multiplicação de Montgomery em Hardware e Impacto no Algoritmo RSA
Resumo
Neste artigo descreve-se o método de Montgomery para multiplicação modular, bem como são examinados dois dos seus algoritmos, a saber: O Algoritmo Rápido de Montgomery (Fast Montgomery Algorithm) e o Algoritmo Mais Rápido de Montgomery (Faster Montgomery algorithm). São ainda apresentadas dois diagramas de máquinas de Estados correspondentes à descrição em VHDL desses algoritmos e a respectiva implementação em FPGAs. No final são apresentadas comparações entre os desempenhos dos algoritmos Rápido e Mais Rápido de Montgomery, focando seu impacto no algoritmo RSA para diferentes tamanhos de chaves.Referências
Amanon, D.N., Dissertação de Mestrado, The University of Applied Sciences Offenburg, Germany, Supervisores Prof. Dr. Angelika Erhardt e Prof. Dr. Christof Paar.
Bailey DV, Cammack W, Guajardo J, Paar C; Cryptography in Modern Communication Systems; Texas Instruments DSPS FEST, Houston, TX, Agosto, 1999.
BISSOLI, MARÇAL LUIZ. Impacto da Multiplicação e Exponenciação Modular em Hardware no Algoritmo RSA. Dissertação de Mestrado, Ciência da Computação, UNIVEM, Marilia, S.P., Brasil, 2007.
Blum T., Paar C" Modular Exponentiation on Reconfigurable Hardware (1999), A Master Thesis, The Worcester Polythechnic Institute.
Chiaramonte R. B.; SICO: Um Sistema de Comunicação de Dados com Suporte Dinâmico à Segurança; Dissertação de Mestrado, UNIVEM, Marília, 2006.
Dally Alan, Marname L., Popovici E., Fast Modular Inversion in The Montgomery Domain on Reconfigurable Logic - ISSC, julho de 2003.
Dally A.; Marname W; Efficient Architectures for implementing Montgomery Modular mulltiplication and RSA Modular Exponentiation on Reconfigurable Logic; ACM, 2002.
Data, S.A.V.A.; Rattlesnake, J.H.A.; RSA Encryption Algorithm in a Nutshell; Neworder Bol St, 2002.
Diffie, W and M.E. Hellman, Exhaustive cryptanalysis of the NBS Data Encryption Standard; Computer 10, 1977.
Dormale, G.M., Bulens, P., Quisquater, J-J., An Improved Montgomery Modular Inversion Targeted for Efficient Implementation on FPGA; International Conference on Field- Programmable Technology, 2004.
Eberle, H., Gura N., Shantz S.C, Gupta V., Rarick L, Sundaran S, A Public-Key Cryptographic Process for RSA and ECC, 15º Conferencia Internacional IEEE para Sistemas de Aplicações Específicas, Arquiteturas e Processadores, 2004.
Gaubatz, Gunnar A. MSc Thesis Submitted to the Faculty of the Worcester Polytechnic Institute, orientadores: Dr. Berk Sunar e Dr. Fred J. Looft, abril de 2002.
Gutub, A.. Modulo Multiplication Hardware Design; Oregon State University, EGE 575, 2000.
Khaldoon M., Prototyping Of Scalable Montgomery Multiplier Using Field Programmable Gate Arrays (FPGAs); M.S. Thesis, Department of Electrical & Computer Engineering, Oregon State University, July 23, 2002.
Kalisy Jr, B.S., The Montgomery Inverse and its Applications; IEEE, 44(8), pg.1064-1065, Agosto de 1995.
Knuth, E. The Art of Computer Programming - Seminumerical Algorithms; Addison-Wesley, 1997.
Koç Ç. K.; Acar T; Kalisky Jr, B.S.. - Analyzing and Comparing Montgomery Multiplication Algorithms; IEEE Micro, v.16 n.3, p.26-33, June 1996.
Koç, Ç, K.; Montgomery Reduction With Even Modulus; IEEE Proceedings: Computers and Digital Techniques - Setembro de 1994.
Muzzi, F. A. G., O Padrão de Segurança PKCS#11 em FPGA's - RSA um Estudo de Caso; Dissertação de Mestrado, UNIVEM, Marília, 2006.
Mctaggart M., Introduction to cryptography, Part 3: Asymmetric cryptography, 01.03.2001, p. da IBM, Internet, abril de 2006.
Moreno E.D. et Al. Criptografia em Software e hardware; Livro pela Editora Novatec, pg. 288 - 2005.
Prince, B.J., Scalable Montgomery Multiplication Algorithm; Oregon State University, Department of Electrical & Computer Engineering, 2002.
Rivest, R.; Shamir, A.; Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems; Communications of ACM, 1978.
Savas E,; Koç, Ç.K. The Montgomery Modular Inverse - Revisited; IEEE, Special issue on computer arithmetic, Vol.49, nº 7, julho de 2000, pg 763-766.
S. C. Shantz S. C. Shantz, "From Euclid's GCD to Montgomery multiplication to the great divide" Tech. Rep. TR-2001-95, Sun Microsystems Laboratories, Santa Clara, Calif, USA, June 2001.
Todorov G.; Tenca A.F.; ASIC Design, Implementations and Analysis of a Scalable High-Radix Montgomery Multiplier - M.S.Thesis - Dezembro - 2000.
Bailey DV, Cammack W, Guajardo J, Paar C; Cryptography in Modern Communication Systems; Texas Instruments DSPS FEST, Houston, TX, Agosto, 1999.
BISSOLI, MARÇAL LUIZ. Impacto da Multiplicação e Exponenciação Modular em Hardware no Algoritmo RSA. Dissertação de Mestrado, Ciência da Computação, UNIVEM, Marilia, S.P., Brasil, 2007.
Blum T., Paar C" Modular Exponentiation on Reconfigurable Hardware (1999), A Master Thesis, The Worcester Polythechnic Institute.
Chiaramonte R. B.; SICO: Um Sistema de Comunicação de Dados com Suporte Dinâmico à Segurança; Dissertação de Mestrado, UNIVEM, Marília, 2006.
Dally Alan, Marname L., Popovici E., Fast Modular Inversion in The Montgomery Domain on Reconfigurable Logic - ISSC, julho de 2003.
Dally A.; Marname W; Efficient Architectures for implementing Montgomery Modular mulltiplication and RSA Modular Exponentiation on Reconfigurable Logic; ACM, 2002.
Data, S.A.V.A.; Rattlesnake, J.H.A.; RSA Encryption Algorithm in a Nutshell; Neworder Bol St, 2002.
Diffie, W and M.E. Hellman, Exhaustive cryptanalysis of the NBS Data Encryption Standard; Computer 10, 1977.
Dormale, G.M., Bulens, P., Quisquater, J-J., An Improved Montgomery Modular Inversion Targeted for Efficient Implementation on FPGA; International Conference on Field- Programmable Technology, 2004.
Eberle, H., Gura N., Shantz S.C, Gupta V., Rarick L, Sundaran S, A Public-Key Cryptographic Process for RSA and ECC, 15º Conferencia Internacional IEEE para Sistemas de Aplicações Específicas, Arquiteturas e Processadores, 2004.
Gaubatz, Gunnar A. MSc Thesis Submitted to the Faculty of the Worcester Polytechnic Institute, orientadores: Dr. Berk Sunar e Dr. Fred J. Looft, abril de 2002.
Gutub, A.. Modulo Multiplication Hardware Design; Oregon State University, EGE 575, 2000.
Khaldoon M., Prototyping Of Scalable Montgomery Multiplier Using Field Programmable Gate Arrays (FPGAs); M.S. Thesis, Department of Electrical & Computer Engineering, Oregon State University, July 23, 2002.
Kalisy Jr, B.S., The Montgomery Inverse and its Applications; IEEE, 44(8), pg.1064-1065, Agosto de 1995.
Knuth, E. The Art of Computer Programming - Seminumerical Algorithms; Addison-Wesley, 1997.
Koç Ç. K.; Acar T; Kalisky Jr, B.S.. - Analyzing and Comparing Montgomery Multiplication Algorithms; IEEE Micro, v.16 n.3, p.26-33, June 1996.
Koç, Ç, K.; Montgomery Reduction With Even Modulus; IEEE Proceedings: Computers and Digital Techniques - Setembro de 1994.
Muzzi, F. A. G., O Padrão de Segurança PKCS#11 em FPGA's - RSA um Estudo de Caso; Dissertação de Mestrado, UNIVEM, Marília, 2006.
Mctaggart M., Introduction to cryptography, Part 3: Asymmetric cryptography, 01.03.2001, p. da IBM, Internet, abril de 2006.
Moreno E.D. et Al. Criptografia em Software e hardware; Livro pela Editora Novatec, pg. 288 - 2005.
Prince, B.J., Scalable Montgomery Multiplication Algorithm; Oregon State University, Department of Electrical & Computer Engineering, 2002.
Rivest, R.; Shamir, A.; Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems; Communications of ACM, 1978.
Savas E,; Koç, Ç.K. The Montgomery Modular Inverse - Revisited; IEEE, Special issue on computer arithmetic, Vol.49, nº 7, julho de 2000, pg 763-766.
S. C. Shantz S. C. Shantz, "From Euclid's GCD to Montgomery multiplication to the great divide" Tech. Rep. TR-2001-95, Sun Microsystems Laboratories, Santa Clara, Calif, USA, June 2001.
Todorov G.; Tenca A.F.; ASIC Design, Implementations and Analysis of a Scalable High-Radix Montgomery Multiplier - M.S.Thesis - Dezembro - 2000.
Publicado
24/10/2007
Como Citar
BISSOLI, Marçal Luiz; BRANCO, Kalinka R. L. J. Castelo; MORENO, Edward David.
Algoritmos de Multiplicação de Montgomery em Hardware e Impacto no Algoritmo RSA . In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 8. , 2007, Gramado.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2007
.
p. 113-120.
DOI: https://doi.org/10.5753/wscad.2007.18760.
