Efficient Large Numbers Karatsuba-Ofman Multiplier Designs for Embedded Systems
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.
[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.
[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.
@article{"International Journal of Electrical, Electronic and Communication Sciences:57460", author = "M.Machhout and M.Zeghid and W.El hadj youssef and B.Bouallegue and A.Baganne and R.Tourki", title = "Efficient Large Numbers Karatsuba-Ofman Multiplier Designs for Embedded Systems", 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.", volume = "3", number = "4", pages = "786-10", }
