Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Scalable GF(p) Montgomery multiplier based on a digit–digit computation approach

© The Institution of Engineering and Technology
Received 10/04/2015, Accepted 08/07/2015, Revised 24/06/2015, Published 01/05/2016

This study presents a scalable hardware architecture for modular multiplication in prime fields GF(p). A novel iterative digit–digit Montgomery multiplication (IDDMM) algorithm is proposed and two hardware architectures that compute that algorithm are described. The input operands (multiplicand, multiplier and modulus) are represented using as radix β = 2 k . Multiplication over GF(p) is possible using almost the same hardware since the complexity of multiplier's kernel module depends mainly on k and not on p. The novel hardware architectures of GF(p) multipliers were evaluated on three Xilinx FPGA families. Design trade-offs were analysed considering different operand sizes commonly used in cryptography and different digits sizes. The proposed designs for IDDMM are well suited to be implemented in modern FPGAs, making use of available dedicated multipliers and memory blocks reducing drastically the FPGA's standard logic while keeping an acceptable performance compared with other implementation approaches. From the Virtex5 implementation, the proposed MM multiplier reaches a throughput of 242 Mbps using only 219 FPGA slices and achieving a 1024-bit modular multiplication in 4.21μs. This is 26 times less area resources than similar related works in the literature with an improved efficiency of 7x.

Inspec keywords: multiplying circuits; field programmable gate arrays; cryptography; Galois fields

Other keywords: memory blocks; cryptography; digit-digit computation approach; multiplier kernel module complexity; Xilinx FPGA families; scalable hardware architecture; scalable GF(p) Montgomery multiplier; digit sizes; IDDMM algorithm; iterative digit–digit Montgomery multiplication algorithm; word length 1024 bit; bit rate 242 Mbit/s; time 4.21 mus; design trade-off analysis; Virtex5

Subjects: Logic and switching circuits; Logic circuits; Cryptography; Security aspects of hardware; Codes

References

    1. 1)
      • 20. Suzuki, D.: ‘How to maximize the potential of FPGA resources for modular exponentiation’. Proc. of Cryptographic Hardware and Embedded Systems 2007, Vienna, Austria, September 2007, pp. 272–288.
    2. 2)
      • 19. Mentens, N., Sakiyama, K., Preneel, B., et al: ‘Efficient pipelining for modular multiplication architectures in prime fields’. Proc. 17th ACM Great Lakes Symp. on VLSI, Stresa-Lago Maggiore, Italy, March 2007, pp. 534–539.
    3. 3)
    4. 4)
      • 21. Oksuzoglu, E., Savas, E.: ‘Parametric, secure and compact implementation of RSA on FPGA’. Proc. of Int. Conf. on Reconfigurable Computing and FPGAs, Cancun, Mexico, December 2008, pp. 391–396.
    5. 5)
    6. 6)
      • 17. Morales-Sandoval, M., Diaz-Perez, A.: ‘A compact FPGA-based Montgomery multiplier over prime fields’. Proc. 23rd ACM Int. Conf. on Great Lakes Symp. on VLSI, Paris, France, May 2013, pp. 245–250.
    7. 7)
    8. 8)
      • 3. Miller, V.: ‘Use of elliptic curves in cryptography’. Proc. of Advances in Cryptology, CRYPTO'85, Santa Barbara, CA, August 1985, pp. 417–426.
    9. 9)
      • 26. Fan, J., Sakiyama, K., Verbauwhede, I.: ‘Montgomery modular multiplication algorithm on multi-core systems’. Proc. of 2007 IEEE Workshop on Signal Processing Systems, Shanghai, China, October 2007, pp. 261–266.
    10. 10)
      • 27. Gong, Y., Li, S.: ‘High-throughput FPGA implementation of 256-bit Montgomery modular multiplier’. Proc. of IEEE Second Int. Workshop on Education Technology and Computer Science, Wuhan, China, March 2010, pp. 173–177.
    11. 11)
    12. 12)
      • 15. Kelley, K., Harris, D.: ‘Parallelized very high radix scalable Montgomery multipliers’. Proc. of IEEE 39th Asilomar Conf. on Signals, Systems, and Computers, Pacific Grove, CA, USA, October 2005, pp. 1196–1200.
    13. 13)
    14. 14)
      • 24. Itoh, K., Takenaka, M., Torii, N., et al: ‘Fast implementation of public-key cryptography on a DSP TMS320C6201’. Proc. First Int. Workshop on Cryptographic Hardware and Embedded Systems, Worcester, Massachusetts, USA, August 1999, pp. 61–72.
    15. 15)
    16. 16)
      • 23. Brown, M., Hankerson, D., López, J., et al: ‘Software implementation of the NIST elliptic curves over prime fields’. Proc. 2001 Conf. on Topics in Cryptology: The Cryptographer's Track at RSA, San Francisco, CA, USA, April 2001, pp. 250–265.
    17. 17)
      • 16. Walter, C.D.: ‘Montgomery's multiplication technique: How to make it smaller and faster’. Proc. of Workshop on Cryptographic Hardware and Embedded Systems, Worcester, Massachusetts, USA, August 1999, pp. 80–93.
    18. 18)
    19. 19)
    20. 20)
      • 10. Huang, M., Gaj, K., Kwon, S., et al: ‘An optimized hardware architecture for the Montgomery multiplication algorithm’. Proc. of the Practice and Theory in Public Key Cryptography, 11th Int. Conf. on Public Key Cryptography, Barcelona, Spain, March 2008, pp. 214–228.
    21. 21)
      • 11. Kong, Y.: ‘High radix Montgomery multipliers for residue arithmetic channels on FPGAs’. Proc. of 2010 First Int. Conf. on Electrical and Electronics Engineering, Wuhan, China, December 2010, pp. 23–30.
    22. 22)
      • 14. Jiang, N., Harris, D.: ‘Quotient pipelined very high radix scalable Montgomery multipliers’. Proc. of IEEE 40th Asilomar Conf. on Signals, Systems and Computers, Pacific Grove, CA, USA, November 2006, pp. 1673–1677.
    23. 23)
      • 6. Tenca, A.F., Koç, C.K.: ‘A scalable architecture for Montgomery multiplication’. Workshop on Cryptographic Hardware and Embedded Systems, Worcester, Massachusetts, USA, August 1999, pp. 94–108.
    24. 24)
      • 13. Tenca, A.F., Todorov, G., Koç, C.K.: ‘High-radix design of a scalable modular multiplier’. Proc. of Workshop on Cryptographic Hardware and Embedded Systems, Paris, France, May 2001, pp. 185–201.
    25. 25)
      • 7. Hamilton, M., Marnane, W., Tisserand, A.: ‘A comparison on FPGA of modular multipliers suitable for elliptic curve cryptography over GF(pat) for specific p values’. Int. Conf. on Field Programmable Logic and Applications, Chania, Crete, Greece, September 2011, pp. 273–276.
    26. 26)
    27. 27)
      • 5. Mondal, A., Ghosh, S., Das, A., et al: ‘Efficient FPGA implementation of Montgomery multiplier using DSP blocks’. Proc. 16th Int. Conf. on Progress in VLSI Design and Test, Shipur, India, July 2012, pp. 370–372.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2015.0055
Loading

Related content

content/journals/10.1049/iet-cdt.2015.0055
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address