Low latency Montgomery multiplier for cryptographic applications
DOI:
https://doi.org/10.33317/ssurj.213Abstract
In this modern era, data protection is very important. To achieve this, the data must be secured using either public-key or private-key cryptography (PKC). PKC eliminates the need of sharing key at the beginning of communication. PKC systems such as ECC and RSA is implemented for different security services such as key exchange between sender, receiver and key distribution between different network nodes and authentication protocols. PKC is based on computationally intensive finite field arithmetic operations. In the PKC schemes, modular multiplication (MM) is the most critical operation. Usually, this operation is performed by integer multiplication (IM) followed by a reduction modulo M. However, the reduction step involves a long division operation that is expensive in terms of area, time and resources. Montgomery multiplication algorithm facilitates faster MM operation without the division operation. In this paper, low latency hardware implementation of the Montgomery multiplier is proposed. Many interesting and novel optimization strategies are adopted in the proposed design. The proposed Montgomery multiplier is based on school-book multiplier, Karatsuba-Ofman algorithm and fast adders techniques. The Karatsuba-Ofman algorithm and school-book multiplier recommends cutting down the operands into smaller chunks while adders facilitate fast addition for large size operands. The proposed design is simulated, synthesized and implemented using Xilinx ISE Design Suite by targeting different Xilinx FPGA devices for different bit sizes (64-1024). The proposed design is evaluated on the basis of computational time, area consumption, and throughput. The implementation results show that the proposed design can easily outperform the state of the art
References
Diffie, W., & Hellman, M. (1976). New directions in cryptography. IEEE transactions on Information Theory, 22(6), 644-654.
Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(177), 203-209.
Khan, S., Javeed, K., & Shah, Y. A. (2018). High-speed FPGA implementation of full-word Montgomery multiplier for ECC applications. Microprocessors and Microsystems, 62, 91-101.
San, I., & At, N. (2014). Improving the computational efficiency of modular operations for embedded systems. Journal of Systems Architecture, 60(5), 440-451.
Mondal, A., Ghosh, S., Das, A., & Chowdhury, D. R. (2012). Efficient FPGA implementation of Montgomery multiplier using DSP blocks. In Progress in VLSI Design and Test (pp. 370-372). Springer, Berlin, Heidelberg.
Brinci, R., Khmiri, W., Mbarek, M., Rabaâ, A. B., Bouallegue, A., & Chekir, F. (2013). Efficient Multiplier for pairings over Barreto-Naehrig Curves on Virtex-6 FPGA. IACR Cryptol. ePrint Arch., 2013, 5.
Kuang, S. R., Wu, K. Y., & Lu, R. Y. (2015). Low-cost high-performance VLSI architecture for Montgomery modular multiplication. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 24(2), 434-443.
Rezai, A., & Keshavarzi, P. (2014). High-throughput modular multiplication and exponentiation algorithms using multibit-scan–multibit-shift technique. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 23(9), 1710-1719.
Javeed, K., & Wang, X. (2014, July). Efficient Montgomery multiplier for pairing and elliptic curve-based cryptography. In 2014 9th International Symposium on Communication Systems, Networks & Digital Sign (CSNDSP) (pp. 255-260). IEEE.
Yang, Y., Wu, C., Li, Z., & Yang, J. (2016). Efficient FPGA implementation of modular multiplication based on the Montgomery algorithm. Microprocessors and Microsystems, 47, 209-215.
McIvor, C. J., McLoone, M., & McCanny, J. V. (2006). Hardware Elliptic Curve Cryptographic Processor Over rm GF (p). IEEE Transactions on Circuits and Systems I: Regular Papers, 53(9), 1946-1957.
Morales-Sandoval, M., & Diaz-Perez, A. (2016). Scalable GF (p) Montgomery multiplier based on a digit–digit computation approach. IET Computers & Digital Techniques, 10(3), 102-109.
Gong, Y., & Li, S. (2010, March). High-throughput FPGA implementation of 256-bit Montgomery modular multiplier. In 2010 Second International Workshop on Education Technology and Computer Science (Vol. 3, pp. 173-176). IEEE.
Ghosh, S., Verbauwhede, I., & Roychowdhury, D. (2012, May). Core-based architecture to speed up optimal ate pairing on the FPGA platform. In International Conference on Pairing-Based Cryptography (pp. 141-159). Springer, Berlin, Heidelberg.
Chow, G. C., Eguro, K., Luk, W., & Leong, P. (2010, August). A Karatsuba-based Montgomery multiplier. In 2010 International Conference on Field Programmable Logic and Applications (pp. 434-437). IEEE.
San, I., & At, N. (2014). Improving the computational efficiency of modular operations for embedded systems. Journal of Systems Architecture, 60(5), 440-451.
Yan, X., Wu, G., Wu, D., Zheng, F., & Xie, X. (2013, December). An implementation of Montgomery modular multiplication on FPGAs. In 2013 International Conference on Information Science and Cloud Computing (pp. 32-38). IEEE.
Javeed, K., Wang, X., & Scott, M. (2017). High-performance hardware support for elliptic curve cryptography over a general prime field. Microprocessors and Microsystems, 51, 331-342.
Javeed, K., & Wang, X. (2017). Low latency flexible FPGA implementation of point multiplication on elliptic curves over GF (p). International Journal of Circuit Theory and Applications, 45(2), 214-228.
Ors, S. B., Batina, L., Preneel, B., & Vandewalle, J. (2003, June). Hardware implementation of an elliptic curve processor over GF (p). In Proceedings IEEE International Conference on Application-Specific Systems, Architectures, and Processors. ASAP 2003 (pp. 433-443). IEEE.
Javeed, K., Wang, X., & Scott, M. (2015, September). Serial and parallel interleaved modular multipliers on the FPGA platform. In 2015 25th International Conference on Field Programmable Logic and Applications (FPL) (pp. 1-4). IEEE.
Karatsuba, A. A., & Ofman, Y. P. (1962). Multiplication of many digital numbers by automatic computers. In Doklady Akademii
Nauk (Vol. 145, No. 2, pp. 293-294). Russian Academy of Sciences.
Montgomery, P. L. (1985). Modular multiplication without trial division. Mathematics of computation, 44(170), 519-521.
Mondal, A., Ghosh, S., Das, A., & Chowdhury, D. R. (2012). Efficient FPGA implementation of Montgomery multiplier using DSP blocks. In Progress in VLSI Design and Test (pp. 370-372). Springer, Berlin, Heidelberg.
Brinci, R., Khmiri, W., Mbarek, M., Rabaâ, A. B., Bouallegue, A., & Chekir, F. (2013). Efficient Multiplier for pairings over Barreto-Naehrig Curves on Virtex-6 FPGA. IACR Cryptol. ePrint Arch., 2013, 5.
Javeed, K., & Wang, X. (2014, July). Efficient Montgomery multiplier for pairing and elliptic curve-based cryptography. In 2014 9th International Symposium on Communication Systems, Networks & Digital Sign (CSNDSP) (pp. 255-260). IEEE.
Yang, Y., Wu, C., Li, Z., & Yang, J. (2016). Efficient FPGA implementation of modular multiplication based on the Montgomery algorithm. Microprocessors and Microsystems, 47, 209-215.
McIvor, C. J., McLoone, M., & McCanny, J. V. (2006). Hardware Elliptic Curve Cryptographic Processor Over rm GF (p). IEEE Transactions on Circuits and Systems I: Regular Papers, 53(9), 1946-1957.
Chow, G. C., Eguro, K., Luk, W., & Leong, P. (2010, August). A Karatsuba-based Montgomery multiplier. In 2010 International Conference on Field Programmable Logic and Applications (pp. 434-437). IEEE.
San, I., & At, N. (2014). Improving the computational efficiency of modular operations for embedded systems. Journal of Systems Architecture, 60(5), 440-451.
Yan, X., Wu, G., Wu, D., Zheng, F., & Xie, X. (2013, December). An implementation of Montgomery modular multiplication on FPGAs. In 2013 International Conference on Information Science and Cloud Computing (pp. 32-38). IEEE.
Javeed, K., Wang, X., & Scott, M. (2015, September). Serial and parallel interleaved modular multipliers on the FPGA platform. In 2015 25th International Conference on Field Programmable Logic and Applications (FPL) (pp. 1-4). IEEE.
Javeed, K., Wang, X., & Scott, M. (2017). High-performance hardware support for elliptic curve cryptography over a general prime field. Microprocessors and Microsystems, 51, 331-342.
Javeed, K., & Wang, X. (2017). Low latency flexible FPGA implementation of point multiplication on elliptic curves over GF (p). International Journal of Circuit Theory and Applications, 45(2), 214-228.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 khalid javeed, Muhammad Huzaifa, Safiullah Khan, Atif Raza Jafri (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
