Hardware Implementation of Residue Multipliers based Signed RNS Processor for Cryptosystems

Elango S, Sampath P

Abstract


The Residue Number System (RNS) characterize large integer numbers into smaller residues using moduli sets to enhance the performance of digital cryptosystems. A parallel Signed Residue Multiplication (SRM) algorithm, VLSI hierarchical array architecture for balanced (2n-1, 2n, 2n+1) and unbalanced (2k-1, 2k, 2k+1) word-length moduli are proposed which is capable of handling signed input numbers. Balanced 2n-1 SRM is used as a reference to design an unbalanced 2k-1 and 2k+1. The synthesized results show that the proposed 2n-1 SRM architecture achieves 17% of the area, 26% of speed and 24% of Power Delay Product (PDP) improvement compared to the Modified Booth Encoded (MBE) architectures discussed in the literature. The proposed 2n+1 SRM architecture achieves 23% of the area, 20% of speed and 22% of PDP improvement compared to recent counterparts. There is a significant improvement in the results due to the fully parallel hierarchical approach adopted for the design which is hardly attempted for signed numbers using array architectures. Finally, the proposed SRM modules are used to design {2n-1, 2n, 2n+1} special moduli set based RNS processor and the real-time verification is performed on Zynq (XC7Z020CLG484-1) Field Programmable Gate Array (FPGA).


Keywords


signed modulo multiplication; Very Large Scale Integration (VLSI); Field Programmable Gate Array (FPGA); computer arithmetic; Residue Number System (RNS)

Full Text:

PDF

References


Sousa, L., Antao, S., Martins, P., “ Combining Residue Arithmetic to Design Efficient Cryptographic Circuits and Systems,” IEEE Circuits Syst. Mag., vol.16, no.4, pp.6-32, 2016. doi:10.1109/MCAS.2016.2614714

Celesti, A., Fazio, M., Villari, M., Puliafito, A.,“Adding long-term availability, obfuscation, and encryption to multi-cloud storage systems,” J. Netw. Comput. Appl., vol.59, pp. 208–218, 2016. doi:10.1016/j.jnca.2014.09.021

Chang, C.H., Molahosseini, A.S., Zarandi, A.A.E., Tay, T.F., “Residue number systems: A new paradigm to datapath optimization for low-power and high-performance digital signal processing applications,” IEEE Circuits Syst. Mag., vol.15, no.5,pp.26–44,2015. doi:10.1109/MCAS.2015.2484118

Molahosseini, A.S., Zarandi, A.A.E., Martins, P., Sousa, L., “A multifunctional unit for designing efficient RNS-based datapaths,” IEEE Access, vol.5, pp. 25972–25986,2017. doi:10.1109/ACCESS.2017.2766841

Patronik, P., Piestrak, S.J., “Hardware/Software Approach to Designing Low-Power RNS-Enhanced Arithmetic Units,” IEEE Trans. Circuits Syst. I Regul. Pap., vol.64, no.5 , pp.1031–1039 , 2017. doi:10.1109/TCSI.2017.2669108

He, D., Chen, Y. & Chen, J., “An Id-Based Three-Party Authenticated Key Exchange Protocol Using Elliptic Curve Cryptography for Mobile-Commerce Environments,” Arabian Journal for Science and Engineering (2013) 38: 2055. https://doi.org/10.1007/s13369-013-0575-4

Esmaeildoust, M., Schinianakis, D., Javashi, H., Stouraitis, T., Navi, K., “Efficient RNS implementation of elliptic curve point multiplication over GF(p),” IEEE Trans. Very Large Scale Integr. Syst. vol.21, no.8, pp.1545–1549, 2013. doi:10.1109/TVLSI.2012.2210916

Ding, J., Li, S., “A Modular Multiplier Implemented with Truncated Multiplication,” IEEE Trans. Circuits Syst. II Express Briefs. vol.65, no.11, pp.1713–1717,2018. doi:10.1109/TCSII.2017.2771239

Antao, S., Sousa, L., “The CRNS framework and its application to programmable and reconfigurable cryptography,” ACM Trans. Archit. Code Optim. , vol.9,no.4,pp.1–25,2013. doi:10.1145/2400682.2400692

Sung-Ming Y., Kim S., Lim S., Moon S., “RSA Speedup with Residue Number System Immune against Hardware Fault Cryptanalysis,” In: Kim K. Information Security and Cryptology — ICISC 2001 Lecture Notes in Computer Science, vol 2288. Springer, Berlin, Heidelberg, 2002.

Fathy, K.A., Bahig, H.M. & Ragab A.A., “A Fast Parallel Modular Exponentiation Algorithm,” Arabian Journal for Science and Engineering vol. 43, 903, 2018. https://doi.org/10.1007/s13369-017- 2797-3

Wei Wang, Swamy, M.N.S., Ahmad, M.O., “Moduli selection in RNS for efficient VLSI implementation,” In: Proceedings of the 2003 International Symposium on Circuits and Systems, 2003. ISCAS ’03. pp. 512-515, IEEE 2003.

Omondi, A., Premkumar, B., Residue number systems, Published by Imperial College Press and Distributed By World Scientific Publishing Co. , 2014.

Muralidharan, R., Chang, C.H., “Radix-8 booth encoded modulo 2n -1 multipliers with adaptive delay for high dynamic range residue number system,” IEEE Trans. Circuits Syst. I Regul. Pap. vol.58,no.5,pp.982–993,2011. doi:10.1109/TCSI.2010.2092133

Vergos, H.T., Efstathiou, C., “Design of efficient modulo 2n+1 multipliers,” IET Comput. Digit. Tech. vol.1,pp.49-57,2007. doi:10.1049/iet-cdt:20060026

Chen, J.W., Yao, R.H. “Efficient modulo 2n+1 multipliers for diminished-1 representation,” IET Circuits, Devices Syst., vol.4, pp.291-300,2010. doi:10.1049/iet-cds.2009.0284

Chen, J.W., Yao, R.H., Wu, W.J., “Efficient modulo 2n+1 multipliers,” IEEE Trans. Very Large Scale Integr. Syst., vol.19,no.12, pp.2149–2157, 2011. doi:10.1109/TVLSI.2010.2080330

Muralidharan, R., Chang, C.H., “Area-power efficient modulo 2n-1 and Modulo 2n+1 Multipliers for {2n-1, 2n, 2n+1} Based RNS,” IEEE Trans. Circuits Syst. I Regul. Pap., vol.59, no.10,pp.2263–2274 , 2012. doi:10.1109/TCSI.2012.2185334

Efstathiou, C., Moshopoulos, N., Axelos, N., Pekmestzi, K., “Efficient modulo 2n+1 multiply and multiply-add units based on modified Booth encoding,” Integr. VLSI J., vol.47, pp.140–147 ,2014. doi:10.1016/j.vlsi.2013.04.001

Mirhosseini, S.M., Molahosseini, A.S., Hosseinzadeh, M., Sousa, L., Martins, P., “A Reduced-Bias Approach with a Lightweight Hard-Multiple Generator to Design a Radix-8 Modulo 2n + 1 Multiplier,” IEEE Trans. Circuits Syst. II Express Briefs, vol.64, no.7, pp.817–821, 2017. doi:10.1109/TCSII.2016.2601285

Efstathiou, C., Vergos, H.T., Dimitrakopoulos, G., Nikolos, D., “Efficient diminished-1 modulo 2n+1 multipliers,” IEEE Trans. Comput., vol.54, pp.491–496,2005. doi:10.1109/TC.2005.63

Efstathiou, C., Vergos, H.T., Nikolos, D., “Modified booth modulo 2n - 1 multipliers,” IEEE Trans. Comput., vol.53, 370–374,2004. doi:10.1109/TC.2004.1261842

Li, L., Hu, J., Chen, Y., “Modified booth encoding modulo (2n-1) multipliers,” IEICE Electron. Express, vol.9, no.5, pp.352–358, 2012. doi:10.1587/elex.9.352

Alaie, M.A., Timarchi, S., “Efficient modulo 2n+1 multiplier,” Int. J. Comput. Aided Eng. Technol. , vol.8, no.3, pp. 260-276, 2016. doi:10.1504/ijcaet.2016.077604

M. Shoba, R. Nakkeeran, “Energy and area efficient hierarchy multiplier architecture based on Vedic mathematics and GDI logic,” Eng. Sci. Technol. an Int. J., vol.20, pp.321–331,2017. doi:10.1016/j.jestch.2016.06.007.

Gupta, T., Sharma, J.B., “Han–Carlson adder based high-speed Vedic multiplier for complex multiplication,” Microsyst. Technol., vol.24, pp. 3901–3906, 2018. doi:10.1007/s00542-018-3872-8

Ananda Mohan, P. V., Residue number systems: Theory and applications, Springer International Publishing, Cham, 2016.

Noorimehr, M.R., Hosseinzadeh, M. & Farshidi, R. ‘High Speed Residue to Binary Converter for the New Four-Moduli Set {22n , 2n +1, 2n/2 + 1, 2n/2−1} Arabian Journal for Science and Engineering, vol.39, 2887,2014. https://doi.org/10.1007/s13369-014-0963-4

Sousa, L., Antão, S.: MRC-based RNS reverse converters for the four-moduli sets {2n-1,2n, 2n+1, 22n+1-1},”IEEE Trans. Circuits Syst. II Express Briefs,vol.59,no.4,pp.244–248,2012. doi:10.1109/TCSII.2012.2188456

Sedjelmaci, S.M., “A parallel extended GCD algorithm,” J. Discret. Algorithms, vol.6, pp.526 – 538,2008. doi:10.1016/j.jda.2006.12.009




DOI: https://doi.org/10.33180/InfMIDEM2020.201

Refbacks

  • There are currently no refbacks.


Copyright (c) 2020 Elango S, Sampath P

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.