http://iet.metastore.ingenta.com
1887

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

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

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

Buy article PDF
$19.95
(plus tax if applicable)
Buy Knowledge Pack
10 articles for $120.00
(plus taxes if applicable)

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.

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.

References

    1. 1)
    2. 2)
    3. 3)
      • 3. Miller, V.: ‘Use of elliptic curves in cryptography’. Proc. of Advances in Cryptology, CRYPTO'85, Santa Barbara, CA, August 1985, pp. 417426.
    4. 4)
    5. 5)
      • 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. 370372.
    6. 6)
      • 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. 94108.
    7. 7)
      • 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. 273276.
    8. 8)
    9. 9)
    10. 10)
      • 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. 214228.
    11. 11)
      • 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. 2330.
    12. 12)
    13. 13)
      • 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. 185201.
    14. 14)
      • 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. 16731677.
    15. 15)
      • 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. 11961200.
    16. 16)
      • 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. 8093.
    17. 17)
      • 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. 245250.
    18. 18)
    19. 19)
      • 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. 534539.
    20. 20)
      • 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. 272288.
    21. 21)
      • 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. 391396.
    22. 22)
    23. 23)
      • 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. 250265.
    24. 24)
      • 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. 6172.
    25. 25)
    26. 26)
      • 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. 261266.
    27. 27)
      • 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. 173177.
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
This is a required field
Please enter a valid email address