Bit-serial and digit-serial GF(2m) Montgomery multipliers using linear feedback shift registers

M. Morales-Sandoval; C. Feregrino-Uribe; P. Kitsos

Bit-serial and digit-serial GF(2^m) Montgomery multipliers using linear feedback shift registers

Access Full Text

Bit-serial and digit-serial GF(2^m) Montgomery multipliers using linear feedback shift registers

Author(s): M. Morales-Sandoval ; C. Feregrino-Uribe ; P. Kitsos
DOI: 10.1049/iet-cdt.2010.0021

For access to this article, please select a purchase option:

Buy article PDF

Buy Knowledge Pack

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership

Recommend Title Publication to library

IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Author(s): M. Morales-Sandoval ¹ ; C. Feregrino-Uribe ² ; P. Kitsos ³
- Affiliations: 1: Embedded and Distributed Systems Group, Polytechnic University of Victoria, Tamaulipas, Mexico
  2: FPGAs Laboratory, Computer Science Department, National Institute for Astrophysics, Optics and Electronics (INAOE), Puebla, Mexico
  3: Digital Systems and Media Computing Laboratory, School of Science and Technology, Hellenic Open University, Patras, Greece
Source: Volume 5, Issue 2, March 2011, p. 86 – 94
DOI: 10.1049/iet-cdt.2010.0021 , Print ISSN 1751-8601, Online ISSN 1751-861X

Published

This work presents novel multipliers for Montgomery multiplication defined on binary fields GF(2^m). Different to state of the art Montgomery multipliers, this work uses a linear feedback shift register (LFSR) as the main building block. The authors studied different architectures for bit-serial and digit-serial Montgomery multipliers using the LFSR and the Montgomery factors x^m and x^m−1. The proposed multipliers are for different classes of irreducible polynomials: general, all one polynomials, pentanomials and trinomials. The results show that the use of LFSRs simplifies the design of the multipliers architecture reducing area resources and retaining high performance compared to related works.

References

1. 1)
  - A.J. Menezes , P.C. Van Oorschot , S.A. Vanstone . (1997) Handbook of applied cryptography.
2. 2)
  - de Dormale, G., Quisquater, J.: `Iterative modular division over GF(2', Proc. Int. Workshop on Applied Reconfigurable Computing (ARC2006), 2006, p. 370–382.
3. 3)
  - C. Lee , J. Horng , I. Jou , E. Lu . Low-complexity bit parallel systolic Montgomery multipliers for special classes of GF(2m). Trans. Comput. , 9 , 1061 - 1070
4. 4)
  - P.A. Scott , L.E. Travares , L.E. Peppard . A fast VLSI multiplier for GF(2m). IEEE J. Sel. Areas Commun. , 62 - 65
5. 5)
  - T. Itoh , S. Tsujii . Structure of parallel multipliers for a class of fields GF(2m). Inf. Comput. , 21 - 40
6. 6)
  - C.-Y. Lee . Low-Complexity parallel systolic Montgomery multipliers over GF(2m): using toeplitz matrix-vector representation. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. , 6 , 1470 - 1477
7. 7)
  - C. Chiou , C. Lee , J. Lin . Finite field polynomial multiplier with linear feedback shift register. J. Sci. Eng. , 3 , 253 - 264
8. 8)
  - H. Kim , S. Lee . LFSR multipliers over GF(2m) defined by all-one polynomial. Integr. VLSI J. , 40 , 473 - 478
9. 9)
  - J.-C. Jeon , K.-Y. Yoo . Programmable cellular automata based Montgomery hardware architecture. Appl. Math. Comput. , 186 , 915 - 922
10. 10)
  - P. Kitsos , G. Theodoridis , O. Koufopavlou . An efficient reconfigurable multiplier architecture for Galois field GF(2m). Microelectron. J. , 10 , 975 - 980
11. 11)
  - Sudhakar, M., Srinivas, M.B.: `A unified and reconfigurable Montgomery multiplier architecture without four-to-two CSA', Proc. 20th Annual Conf. on Integrated Circuits and Systems Design, 2007, New York, NY, p. 147–152.
12. 12)
  - C.-Y. Lee , C.-W. Chiou , J.-M. Lin , C.-C. Chang . Scalable and systolic Montgomery multiplier over GF(2m) generated by trinomials. IET Circuits Devices Syst. , 6 , 477 - 484
13. 13)
  - Ç.K. Koç , B. Sunar . Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields. IEEE Trans. Comput. , 3 , 353 - 356
14. 14)
  - S. Kumar , T. Wollinger , C. Paar . Optimum digit-serial GF(2m) multipliers for curve-based cryptography. IEEE Trans. Comput. , 10 , 1306 - 1311
15. 15)
  - P.L. Montgomery . Modular multiplication without trial division. Math. Comput. , 170 , 519 - 521
16. 16)
  - R. Katti , X. Ruan , H. Khattri . Multiple-output low-power linear feedback shift register design. IEEE Trans. Circuits Sys. I , 7 , 1487 - 1495
17. 17)
  - M. Sudhakar , R.V. Kamala , M.B. Srinivas . New and improved architectures for Montgomery modular multiplication. Mob. Netw. Appl. , 4 , 281 - 291
18. 18)
  - Ç.K. Koç , T. Acar . Montgomery multiplication in GF(2k). Des. Codes Cryptogr. , 1 , 57 - 69
19. 19)
  - Ku, K.M., Ha, K.J., Yoo, W.H., Yoo, K.Y.: `Parallel montgomery multiplication and squaring over GF(2', Proc. ICCSA 2004, (LNCS, 3046), 2004, p. 196–205.
20. 20)
  - C.W. Chiou , C.Y. Lee , A.W. Deng , J.M. Lin . Structure of parallel multipliers for a class of finite fields GF(2m). Tamkang J. Sci. Eng. , 4 , 65 - 372
21. 21)
  - H. Wu . Montgomery multiplier and squarer for a class of finite fields. IEEE Trans. Comput. , 5 , 521 - 529
22. 22)
  - A. Hariri , A. Reyhani-Masoleh . Bit-serial and bit-parallel Montgomery multiplication and squaring over GF(2m). IEEE Trans. Comput. , 10 , 1332 - 1345
23. 23)
  - M. Abramovici , M. Breuer , A. Friedman . (1990) Digital system testing and testable design.
24. 24)
  - M.A. Hasan , M. Wang , V.K. Bhargava . Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m). IEEE Trans. Comput. , 8 , 962 - 971

Login

Not registered yet?

Share

Tools

Login to add to favourites

Key

Bit-serial and digit-serial GF(2^m) Montgomery multipliers using linear feedback shift registers

Bit-serial and digit-serial GF(2^m) Montgomery multipliers using linear feedback shift registers

Buy article PDF

Buy Knowledge Pack

Thank you

References

Related content