Paralelização Eficiente para o Algoritmo Binário de Exponenciação Modular

• Pedro Carlos da Silva Lara LNCC
• Fábio Borges de Oliveira LNCC
• Renato Portugal LNCC

DOI: https://doi.org/10.5753/sbseg.2009.20620

Resumo

Algoritmos de exponenciação modular têm um papel importante na criptografia assimétrica. O desempenho do RSA, por exemplo, depende de um algoritmo de exponenciação modular. Esta operação é a mais custosa em muitos métodos de criptografia, por exemplo, no protocolo Diffie-Hellman. Uma implementação eficiente da exponenciação modular tem forte impacto sobre estes métodos.Neste trabalho, é proposta uma modificação do algoritmo binário de exponenciação modular, que explora um método de paralelização e reduz a complexidade do algoritmo por um fator quadrático no número de multiplicações.

Referências

Bosselaers, A., Govaerts, R., and Vandewalle, J. (1994). Comparison of three modular reduction functions. In In Advances in Cryptology-CRYPTO’93, LNCS 773, pages 175–186. Springer-Verlag.

Brickell, E. F. (1990). A survey of hardware implementation of RSA. In CRYPTO ’89: Proceedings of the 9th Annual International Cryptology Conference on Advances in Cryptology, pages 368–370, London, UK. Springer-Verlag.

Brickell, E. F., Gordon, D. M., Mccurley, K. S., and Wilson, D. B. (1992). Fast exponentiation with precomputation. In Advances in Cryptology – Proceedings of CRYPTO’92, volume 658, pages 200–207. Springer-Verlag.

Brickell, E. F., Gordon, D. M., Mccurley, K. S., and Wilson, D. B. (1995). Fast exponentiation with precomputation: Algorithms and lower bounds. Preprint http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.606.

Diffie, W. and Hellman, M. E. (1976). New directions in cryptography. IEEE Trans. Information Theory, IT-22(6):644–654.

Eigenmann, R. and Ayguade, E. (2009). Special Issue: OpenMP Introduction. International Journal of Parallel Programming, 37(3):247–249.

Granlund, T. (2002). GNU multiple precision arithmetic library 4.1.2. http://swox.com/gmp/.

Knuth, D. E. (1997). Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd Edition). Addison-Wesley Professional.

Koç, C. K. (1994). High-speed RSA implementation. Technical Report, RSA Laboratories.

Lim, C. H. and Lee, P. J. (1994). More flexible exponentiation with precomputation. In Advances in Cryptology – CRYPTO’94, pages 95–107.

Menezes, A. J., Oorschot, P. C. V., Vanstone, S. A., and Rivest, R. L. (1997). Handbook of applied cryptography.

Nedjah, N. and Mourelle, L. M. (2002). Efficient parallel modular exponentiation algorithm. In ADVIS ’02: Proceedings of the Second International Conference on Advances in Information Systems, pages 405–414, London, UK. Springer-Verlag.

Nedjah, N. and Mourelle, L. M. (2007). Parallel computation of modular exponentiation for fast cryptography. International Journal of High Performance Systems Architecture, 1(1):44–49.

Rivest, R. L., Shamir, A., and Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120–126.

RSA Labs (2000). PKCS1 v2.0 Amendment 1: Multi-Prime RSA.