Efficient Large Numbers Karatsuba-Ofman Multiplier Designs for Embedded Systems

Authors: M.Machhout, M.Zeghid, W.El hadj youssef, B.Bouallegue, A.Baganne, R.Tourki

Abstract:

Long number multiplications (n ≥ 128-bit) are a primitive in most cryptosystems. They can be performed better by using Karatsuba-Ofman technique. This algorithm is easy to parallelize on workstation network and on distributed memory, and it-s known as the practical method of choice. Multiplying long numbers using Karatsuba-Ofman algorithm is fast but is highly recursive. In this paper, we propose different designs of implementing Karatsuba-Ofman multiplier. A mixture of sequential and combinational system design techniques involving pipelining is applied to our proposed designs. Multiplying large numbers can be adapted flexibly to time, area and power criteria. Computationally and occupation constrained in embedded systems such as: smart cards, mobile phones..., multiplication of finite field elements can be achieved more efficiently. The proposed designs are compared to other existing techniques. Mathematical models (Area (n), Delay (n)) of our proposed designs are also elaborated and evaluated on different FPGAs devices.

Keywords: finite field, Karatsuba-Ofman, long numbers, multiplication, mathematical model, recursivity.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1070785

References:

[1] D.V.Bailey, C.Paar, "Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography," Journal of Cryptology, vol. 14, 2001, pp.153-176.
[2] N.S.Chang, C.H.Kim, Y.H .Park, J.Lim,"A non-redundant and efficient design for Karatsuba-Ofman algorithm," In ISC, Springer-Verlag Berlin Heidelberg, 2005,pp. 288-299.
[3] L.S.Cheng, A.Miri, T.H.Yeap, "Improved FPGA implementations of parallel Karatsuba multiplication over GF (2n)," In Proc. 23rd Biennial Symposium on Communications conf, 2006.
[4] L.Dong-Ho, and O.Jong-Soo, "Multi-Segment GF (2m) Multiplication and its Application to Elliptic Curve Cryptography)," in Proc.GLSVLSI-07 conf. Stresa-Lago Maggiore, Italy, pp. 546-551.
[5] Z.Dyka, P. Langendoerfer,, "Area efficient hardware implementation of elliptic curve cryptography by iteratively applying karatsuba-s method," in Proc. of the Design, Automation and Test in Europe conf, pp.70-75.
[6] W.El hadj youssef, M.Zghid, M.Machhout, B.Bouallegue, R.Tourki, "Design and Performance testing of Arithmetic Operators Library for Cryptographic Applications," International Journal of Computer Sciences and Engineering Systems (IJCSES), Vol.1, No.3, 2008,pp. 201- 212.
[7] M.Ernst, M.Jung, F.Madlener, S. Huss, R.Blumel, "A Reconfigurable System on Chip Implementation for Elliptic Curve Cryptography over GF(2n) ,"In CHES, LNCS 2523, 2002, pp. 381-399.
[8] F. U.S. Department of Commerce (2000) ÔÇÿDigital Signature Standard (DSS)-, NIST /FIPS PUB 186-2, January.
[9] F.Rodriguez-Henriquez, N.A.Saqib, A.Diaz-Pérez, "A fast parallel implementation of elliptic curve point multiplication over GF (2m)", Microprocessors and Microsystems, Vol.28, pp.329-339.
[10] Z.Guitouni, W.El hadj youssef, M.Machhout, R.Tourki, "Implementation of Elliptic Curve Point Multiplication in Projective Systems over GF(2m)", In Proc.Fourth International Multi-Conference on Systems, Signals & Devices (SSD-07), March.
[11] J.Großschadl, R.M.Avanzi, E.Sava, S. Tillich,"Energy-Efficient Software Implementation of Long Integer Modular Arithmetic," In CHES 2005, LNCS 3659, pp. 75-90.
[12] P.Kocher, L.Ruby, G.McGraw, A.Raghunathan, R.Srivaths, "Security as a New Dimension in Embedded System Design," In Proc. DAC 2004, June, San Diego, California, USA.
[13] L. A. B.Kowada, R.Portugal, C.M.H.Figueiredo,"Reversible Karatsuba-s Algorithm," Journal of Universal Computer Science, Vol. 12, no. 5, pp.499-511.
[14] N.Nedjah, L.M.Mourelle, "Fast Less Recursive Hardware for Large Number Multiplication Using Karatsuba-Ofman-s Algorithm," In Proc. ISCIS 2003, LNCS 2869, pp. 43-50.
[15] N.Nedjah, L.M.Mourelle,"A Review of Modular Multiplication Methods and Respective Hardware Implementations," Informatica, Vol. 30, pp.111-129.
[16] P.L.Montgomery, "Five, Six, and seven-Term Karatsuba-Like Formulae," IEEE Transactions on Computers, Vol. 54, No. 3, pp. 362- 69.
[17] W.Qingxian, "The application of elliptic curves cryptography in embedded systems," In Proc. Second International Embedded Software and Systems Conf., pp.16-18.
[18] S.Peter, P.Langendorferv, "An Efficient Polynomial Multiplier in GF (2m) and its Application to ECC Designs," In Proc. DATE0 Conf EDAA.
[19] J.Von zur Gathen, J.Shokrollahi, "Efficient FPGA-based Karatsuba multipliers for polynomials over F2," In Proc.SAC 2005 conf, LNCS 3897, pp. 359-369.
[20] J.Von zur Gathen, J.Shokrollahi, "Fast arithmetic for polynomials over F2 in hardware," In Proc. IEEE Information Theory Workshop, Punta del Este, Uruguay.
[21] LC.Washington.,"Elliptic Curves: Number Theory and Cryptography,"In Chapman & Hall New York CRC Press.
[22] Weimerskirch, A. and Paar, C. (2003) ÔÇÿGeneralizations of the Karatsuba Algorithm for Efficient Implementations-, Ruhr-Universitat-Bochum, Germany, Tech. Rep.
[23] T.Wollinger, G.Guajardo, C.Paar ,"Cryptography in Embedded Systems: An Overview," In Proc. of the Embedded World 2003 Exhibition and Conference, Design & Elektronik, Nuernberg, Germany, February, pp. 735-744.