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

Abstract

Algorithms for modular exponentiation play an important role in asymmetric cryptography. The efficiency of RSA, for instance, depends on algorithms for modular exponentiation. This operation is the most expensive part in many methods of cryptography, for instance, in the Diffie-Hellman protocol. An efficient implementation of modular exponentiation has a strong impact on the performance of those methods. In this paper, a modification of the algorithm for binary modular exponentiation is proposed, which exploits a method of parallelization and reduces the computational complexity of the algorithm by a quadratic factor in the number of multiplications.

References

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.