Fast Reverse converter Design for three moduli set {2^n,2^n-1,2^(n-1)-1} Using CRTF

Document Type : Original Research Article


1 Faculty of Marine Engineering, Khorramshahr University of Marine Science and Technology, Khorramshahr, Iran

2 Department of Basic Sciences, Abadan Faculty of Petroleum Engineering, Petroleum University of Technology, Abadan, Iran


Security is necessary for marine communication systems such as marine wireless sensor networks and automatic identification system which is the emerging system for automatic traffic control and collision avoidance services in the maritime transportation sector. Public key cryptography algorithms have an important role in these systems to realize secure communication systems. Public key cryptography algorithms such as RSA and Elliptic curve cryptography (ECC) have high computation costs and many works are done by researcher in order to speed up the operation. Residue number system which is a carry free system is widely used to speed up the operation in public key cryptography algorithm. In this paper, an improved RNS reverse converter for three-module set {2^n,2^n-1,2^(n-1)-1} using chinese reminder theorem with fractional is presented. Unit gate delay and area comparison of the proposed reverse converter with literature have confirmed that the proposed reverse conversion takes fewer hardware costs and higher speed.


[1]  Y. J. Kim and K. Kyung. “Secured radio communication based on fusion of cryptography algorithms.” in 2015 IEEE International Conference on Consumer Electronics (ICCE). 2015. pp. 388–389. doi: 10.1109/ICCE.2015.7066457.
[2]  A. Goudossis and S. K. Katsikas. “Towards a secure automatic identification system (AIS).” J. Mar. Sci. Technol.. vol. 24. no. 2. pp. 410–423. 2019. doi: 10.1007/s00773-018-0561-3.
[3]  L. Wei. L. Zhang. D. Huang. and K. Zhang. “Efficient and provably secure identity-based multi-signature schemes for data aggregation in marine wireless sensor networks.” in 2017 IEEE 14th International Conference on Networking. Sensing and Control (ICNSC). 2017. pp. 593–598. doi: 10.1109/ICNSC.2017.8000158.
[4]  R. L. Rivest. A. Shamir. and L. M. Adleman. “A method for obtaining digital signatures and public key cryptosystems.” Secur. Commun. Asymmetric Cryptosystems. vol. 21. no. 2. pp. 217–239. 2019.
[5]  B. N. Koblitz. “Elliptic Curve Cryptosystems.” vol. 4. no. 177. pp. 203–209. 1987.
[6]  V. S. Miller. “Use of Elliptic Curves in Cryptography.” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics). vol. 218 LNCS. pp. 417–426. 1986. doi: 10.1007/3-540-39799-X_31.
[7]  S. Goldwasser. S. Micali. and R. L. Rivest. “Digital signature scheme secure against adaptive chosen-message attacks.” S[1] S. Goldwasser. S. Micali. R. L. Rivest. “Digital Signat. scheme Secur. against Adapt. chosen-message attacks.” SIAM J. Comput. vol. 17. no. 2. pp. 281–308. 1988. doi 10.1137/0217017.IAM J. Comput.. vol. 17. no. 2. pp. 281–308. 1988. doi: 10.1137/0217017.
[8]  M. Esmaeildoust. D. Schinianakis. H. Javashi. T. Stouraitis. and K. Navi. “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.
[9]  D. M. Schinianakis. A. P. Fournaris. H. E. Michail. A. P. Kakarountas. and T. Stouraitis. “An RNS implementation of an Fp elliptic curve point multiplier.” IEEE Trans. Circuits Syst. I Regul. Pap.. vol. 56. no. 6. pp. 1202–1213. 2009. doi: 10.1109/TCSI.2008.2008507.
[10] L. Imbert. J. Bajard. L. Imbert. J. B. A. Full. and R. N. S. Implementation. “A Full RNS Implementation of RSA To cite this version : HAL Id : lirmm-00090366 A Full RNS Implementation of RSA.” 2006.
[11] K. Navi. A. S. Molahosseini. and M. Esmaeildoust. “How to teach residue number system to computer scientists and engineers.” IEEE Trans. Educ.. vol. 54. no. 1. pp. 156–163. 2011. doi: 10.1109/TE.2010.2048329.
[12] S. Asif. M. S. Hossain. Y. Kong. and W. Abdul. “A Fully RNS based ECC Processor.” Integration. vol. 61. pp. 138–149. 2018. doi:
[13] S. Asif and Y. Kong. “Highly Parallel Modular Multiplier for Elliptic Curve Cryptography in Residue Number System.” Circuits. Syst. Signal Process.. vol. 36. no. 3. pp. 1027–1051. 2017. doi: 10.1007/s00034-016-0336-1.
[14] W. Wang. M. N. S. Swamy. and M. O. Ahmad. “Moduli selection in RNS for efficient VLSI implementation.” in Proceedings of the 2003 International Symposium on Circuits and Systems. 2003. ISCAS ’03.. 2003. vol. 4. pp. IV–IV. doi: 10.1109/ISCAS.2003.1205945.
[15] Y. Wang. X. Song. M. Aboulhamid. and H. Shen. “Adder based residue to binary number converters for (2/sup n/-1. 2/sup n/. 2/sup n/+1).” IEEE Trans. Signal Process.. vol. 50. no. 7. pp. 1772–1779. 2002. doi: 10.1109/TSP.2002.1011216.
[16] A. Hiasat. “An Efficient Reverse Converter for the Three-Moduli Set ($2^{n+ 1}-1. 2^{n}. 2^{n}-1$).” IEEE Trans. Circuits Syst. II Express Briefs. vol. 64. no. 8. pp. 962–966. 2016.
[17] A. Hiasat and L. Sousa. “On the Design of RNS Inter-Modulo Processing Units for the Arithmetic-Friendly Moduli Sets {2 n+ k. 2 n− 1. 2 n+ 1− 1}.” Comput. J.. vol. 62. no. 2. pp. 292–300. 2019.
[18] P. Lyakhov. M. Bergerman. N. Semyonova. D. Kaplun. and A. Voznesensky. “Design Reverse Converter for Balanced RNS with Three Low-cost Modules.” no. 3. pp. 1–7. 2021. doi: 10.1109/meco52532.2021.9460200.
[19] P. M. Kogge and H. S. Stone. “A parallel algorithm for the efficient solution of a general class of recurrence equations.” IEEE Trans. Comput.. vol. 100. no. 8. pp. 786–793. 1973.
[20] A. Omondi and B. Premkumar. Residue Number Residue Number. 1951.
[21] C. Y. Hung and B. Parhami. “An approximate sign detection method for residue numbers and its application to RNS division.” Comput. Math. with Appl.. vol. 27. no. 4. pp. 23–35. 1994. doi: 10.1016/0898-1221(94)90052-3.
[22] N. I. Chervyakov. A. S. Molahosseini. P. A. Lyakhov. M. G. Babenko. and M. A. Deryabin. “Residue-to-binary conversion for general moduli sets based on approximate Chinese remainder theorem.” Int. J. Comput. Math.. vol. 94. no. 9. pp. 1833–1849. 2017. doi: 10.1080/00207160.2016.1247439.
[23] H. Nakahara and T. Sasao. “A High-speed Low-power Deep Neural Network on an FPGA based on the Nested RNS: Applied to an Object Detector.” in 2018 IEEE International Symposium on Circuits and Systems (ISCAS). 2018. pp. 1–5.
[24] S. G. R and R. Kalaimathi. “Design and Analysis of Kogge-Stone and Han-Carlson Adders in 130nm CMOS Technology.” no. March 2018. 2020.
[25] M. Obeidi Daghlavi. M. R. Noorimehr. and M. Esmaeildoust. “Efficient two-level reverse converters for the four-moduli set {2n−1. 2n–1. 2n−1–1. 2n+1–1}.” Analog Integr. Circuits Signal Process.. vol. 0123456789. 2020. doi: 10.1007/s10470-020-01749-z.