Efficient Big Integer Multiplication in Cryptography

Year 2017, Volume: 6 Issue: 4, 70 - 78, 01.12.2017

Murat Burhan İlter Murat Cenk

Abstract

Most of the public key cryptography algorithms require efficient big integer multiplications. In this paper, we show how to develop efficient integer multiplication algorithms for cryptographic applications by combining different methods. We determine the complexities by taking into account the cost of single word multiplication, single word addition and double word addition on different platforms. This paper is an extended version of [11]. We add the complexity of the last term method that is used for computing complexity of multiplication of degree n - 1 polynomials from the product of degree n - 2 polynomials. The unbalanced refined Karatsuba 2-way multiplication algorithm is also included. These new contributions improved the complexity results introduced in [11]. Moreover, we present the best multiplication algorithm complexities for NIST primes on different implementation platforms.

Keywords

—Integer multiplication, Karatsuba algorithm, Karatsuba-like algorithms, Public Key Cryptography

References

• Cenk, M., & Hasan, M. A. (2015). Some new results on binary polynomial multiplication. Journal of Cryptographic Engineering, 5(4), 289-303. 1345-1361.
• Karatsuba, A. (1963). Multiplication of multidigit numbers on automata. In Sov. Phys. Dokl. (Vol. 7, No. 7, pp. 595-596).
• Bernstein, D. (2009). Batch binary Edwards. In: Advances in Cryptology CRYPTO 2009, LNCS, (vol. 5677, pp. 317336 ).
• Zhou, G., & Michalik, H. (2010). Comments on” A New Archi- tecture for a Parallel Finite Field Multiplier with Low Complexity Based on Composite Field”. IEEE Transactions on Computers, 59(7), 1007-1008.
• Toom, A. L. (1963). The complexity of a scheme of functional elements realizing the multiplication of integers. In Soviet Math- ematics Doklady (Vol. 3, No. 4, pp. 714-716).
• Cook, S. A., & Aanderaa, S. O. (1969). On the minimum computation time of functions. Transactions of the American Mathematical Society, 142, 291-314.
• Harvey, D., Van Der Hoeven, J., & Lecerf, G. (2016). Even faster integer multiplication. Journal of Complexity, 36, 1-30.
• Weimerskirch, A., & Paar, C. (2006). Generalizations of the Karatsuba Algorithm for Efficient Implementations. IACR Cryp- tology ePrint Archive, 2006, 224.
• Cenk, M., Hasan, M. A., & Negre, C. (2014). Efficient sub- quadratic space complexity binary polynomial multipliers based on block recombination. IEEE Transactions on Computers, 63(9), 2273-2287.
• Fips, P. U. B. (2000). 186-2. digital signature standard (dss). National Institute of Standards and Technology (NIST), 20, 13.
• ˙Ilter, M. B., & Cenk, M. (2017). Efficient big integer multiplica- tion in cryptography. ISCTurkey 2017 Conference Proceedings, 8-13.