High speed hardware architecture to compute galois fields GF(p) montgomery inversion with scalability features

Access Full Text

High speed hardware architecture to compute galois fields GF(p) montgomery inversion with scalability features

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

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

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

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

Modular inversion is a fundamental process in several cryptographic systems. It can be computed in software or hardware, but hardware computation has been proven to be faster and more secure. This research focused on improving an old scalable inversion hardware architecture proposed in 2004 for finite field GF(p). The architecture comprises two parts, a computing unit and a memory unit. The memory unit holds all the data bits of computation whereas the computing unit performs all the arithmetic operations in word (digit) by word bases such that the design is scalable. The main objective of this paper is to show the cost and benefit of modifying the memory unit to include shifting, which was previously one of the tasks of the scalable computing unit. The study included remodeling the entire hardware architecture removing the shifter from the scalable computing part and embedding it in the non-scalable memory unit instead. This modification resulted in a speedup to the complete inversion process with an area increase due to the new memory shifting unit. Several design schemes have been compared giving the user the complete picture to choose from depending on the application need.

Inspec keywords: cryptography; Galois fields; computer architecture

Other keywords: memory unit; galois fields montgomery inversion; nonscalable memory unit; computing unit; cryptographic systems; memory shifting unit; modular inversion; high speed hardware architecture

Subjects: Algebra; Computer architecture; Data security; Algebra

References

    1. 1)
      • Feldhofer, M., Trathnigg, T., Schnitzer, B.: `A self-timed arithmetic unit for elliptic curve cryptography', Proc. Euromicro Symp. on Digital System Design (DSD), 2002.
    2. 2)
      • I. Blake , G. Seroussi , N. Smart . Elliptic curves in cryptography.
    3. 3)
      • N. Takagi . Modular inversion hardware with a redundant binary representation. IEICE Trans. Inform. Syst. , 8 , 863 - 869
    4. 4)
      • S. Fenn , M. Benaissa , D. Taylor . GF(2m) multiplication and division over the dual basis. IEEE Trans. Computers , 3 , 319 - 327
    5. 5)
      • M. Ercegovac , T. Lang , J. Moreno . (1999) Introduction to Digital System.
    6. 6)
      • P. Montgomery . Modular multiplication without trail division. Mathematics Computation , 170 , 519 - 521
    7. 7)
      • Zhou, T., Wu, X., Bai, G., Chen, H.: `New algorithm and fast VLSI implementation for modular inversion in galois field GF(p)', IEEE Int. Conf. on Communications, Circuits and Systems, 2002, 2, p. 1491–1495.
    8. 8)
      • N. Takagi . A VLSI algorithm for modular division based on the binary GCD algorithm. IEICE Trans. Fundamentals of Electron., Commun. Computer Sciences , 5 , 724 - 728
    9. 9)
      • C. McIvor , M. McLoone , J. McCanny . Improved montgomery modular inverse algorithm. Electron. Lett. , 18 , 1110 - 1111
    10. 10)
      • G. Feng . A VLSI architecture for fast inversion in GF(2m). IEEE Trans. Computers , 10 , 1383 - 1386
    11. 11)
      • E. Savas , C. Koc . The montgomery modular inverse–revisited. IEEE Trans. Computers , 7 , 763 - 766
    12. 12)
      • T. Kobayashi , H. Morita . Fast modular inversion algorithm to match any operation unit. IEICE Trans. Fundamentals , 5 , 733 - 740
    13. 13)
      • M. Kovac , N. Ranganathan , M. Varanasi . SIGMA: A VLSI systolic array implementation of galois field GF(2m) based multiplication and division algorithm. IEEE Trans. VLSI , 1 , 22 - 30
    14. 14)
      • Hasan, M.A.: `Efficient computation of multiplicative inverse for cryptographic applications', Proc. 15th IEEE Symp. on Computer Arithmetic, 2001.
    15. 15)
      • http://www.mentor.com/partners/hep/AsicDesignKit/dsheet/ami05databook.html, Mentor Graphics Co., ASIC Design Kit., accessed January 2006.
    16. 16)
      • Dormale, G., Bulens, P., Quisquater, J.: `An improved montgomery modular inversion targeted for efficient implementation on FPGA', Int. Conf. on Field-Programmable Technology (FPT), 2004, p. 441–444.
    17. 17)
      • D. Hankerson , J. Menezes , J. Hernandez . (2000) Software implementation of elliptic curve cryptography over binary fields.
    18. 18)
      • Fiaz, F., Masud, S.: `Design and implementation of a hardware divider in finite field', National Conf. on Emerging Technologies, 2004.
    19. 19)
      • Daly, A., Marnane, W., Popovici, E.: `Fast modular inversion in the montgomery domain on reconfigurable logic', Irish Signals and Systems Conf. (ISSC), 2003, p. 362–367.
    20. 20)
      • Tawalbeh, L., Tenca, A., Park, S., Koc, C.: `A dual-field modular division algorithm and architecture for application specific hardware', Thirty-Eighth Asilomar Conf. on Signals, Systems and Computers, 2004, 1, p. 483–487.
    21. 21)
      • Gutub, A., Tenca, A., Koc, C.: `Scalable VLSI architecture for GF(p) montgomery modular inverse computation', IEEE Computer Society Annual Symp. on VLSI (ISVLSI), 2002, Pittsburgh, Pennsylvania.
    22. 22)
      • Gutub, A., Tenca, A.: `Efficient scalable hardware architecture for montgomery inverse computation in GF(P)', IEEE Workshop on Signal Processing Systems (SIPS), 2003, p. 93–98.
    23. 23)
      • C. Wang , T. Truong , H. Shao , L. Deutsch , J. Omura , I. Reed . VLSI architectures for computing multiplications and inverses in GF(2m). IEEE Trans. Computers , 8 , 709 - 717
    24. 24)
      • T. Zhou , X. Wu , G. Bai , H. Chen . Fast GF(p) modular inversion algorithm suitable for VLSI implementation. Electron. Lett. , 14 , 706 - 707
    25. 25)
      • J. Guo , C. Wang . Systolic array implementation of Euclid's algorithm for inversion and division in GF(2m). IEEE Trans. Computers , 10 , 1161 - 1167
    26. 26)
      • A. Gutub , A. Tenca . Efficient scalable VLSI architecture for montgomery inversion in GF(p). Integration, The VLSI J. , 2 , 103 - 120
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt_20060183
Loading

Related content

content/journals/10.1049/iet-cdt_20060183
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading