Highly Parallel Modular Multiplier for Elliptic Curve Cryptography in Residue Number System | Circuits, Systems, and Signal Processing Skip to main content
Springer Nature Link
Log in

Highly Parallel Modular Multiplier for Elliptic Curve Cryptography in Residue Number System

  • Published:
Circuits, Systems, and Signal Processing Aims and scope Submit manuscript

Abstract

This article proposes a novel architecture to perform modular multiplication in the Residue Number System (RNS) by using sum of residues. The highly parallel architecture is implemented using VHDL and verified by extensive simulations in ModelSim SE. The pipelined and non-pipelined versions of the design are implemented on ASIC and FPGA platforms to allow a broad comparison. The proposed architecture requires only one iteration to complete modular multiplication and achieves 12–90 % less delay as compared to the existing RNS and binary modular multipliers. The complexity of the proposed design is also less than the existing state-of-the-art RNS-based modular multipliers. The high scalability and flexibility of the proposed architecture allows it to be used for a wide range of high-speed applications.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. O. Aichholzer, H. Hassler, A fast method for modulus reduction in residue number system. In: Proceedings Economical Parallel Processing, pp. 41–54. Vienna, Austria (1993)

  2. H. Alrimeih, D. Rakhmatov, Pipelined modular multiplier supporting multiple standard prime fields. In: Application-specific Systems, Architectures and Processors (ASAP), 2014 IEEE 25th International Conference on, pp. 48–56 (2014). doi:10.1109/ASAP.2014.6868630

  3. S. Antão, L. Sousa, A flexible architecture for modular arithmetic hardware accelerators based on RNS. J. Signal Process. Syst. 76(3), 249–259 (2014). doi:10.1007/s11265-014-0879-y

    Article  Google Scholar 

  4. S. Asif, Y. Kong, Design of an algorithmic Wallace multiplier using high speed counters. In: Computer Engineering Systems (ICCES), 2015 10th International Conference on, pp. 133–138 (2015). doi:10.1109/ICCES.2015.7393033

  5. J.C. Bajard, L.S. Didier, P. Kornerup, Modular multiplication and base extensions in residue number systems. In: Proceedings 15th IEEE Symposium on Computer Arithmetic, vol. 2 pp. 59–65 (2001)

  6. J.C., Bajard, L. Imbert, A full RNS implementation of RSA. IEEE Trans. Comput. 53(6), 769–774 (2004)

  7. P. Barrett, Communications authentication and security using public key encryption—a design for implementation. Master’s thesis, Oxford University (1984)

  8. P. Barrett, Implementing the Rivest, Shamir and Adleman public-key encryption algorithm on a standard digital signal processor, Advances in Cryptology - Crypto 86, vol. 263, Lecture Notes in Computer Science (Springer, Berlin/Heidelberg, 1987), pp. 311–323

  9. F. Barsi, M.C. Pinotti, Fast base extension and precise scaling in RNS for look-up table implementations. IEEE Trans. Signal Process. 43(10), 2427–2430 (1995)

    Article  Google Scholar 

  10. B. Cao, C.H. Chang, T. Srikanthan, A residue-to-binary converter for a new five-moduli set. IEEE Trans. Circuits Syst. I Regul. Pap. 54(5), 1041–1049 (2007)

    Article  MathSciNet  Google Scholar 

  11. R.C.C. Cheung, S. Duquesne, J. Fan, N. Guillermin, I. Verbauwhede, G.X. Yao, FPGA implementation of pairings using residue number system and lazy reduction, Proceedings of the 13th International Conference on Cryptographic Hardware and Embedded Systems, CHES’11 (Springer-Verlag, Berlin, Heidelberg, 2011), pp. 421–441

  12. R. Crandall, C. Pomerance, Prime Numbers, A Computational Perspective (Springer, Berlin, 2001)

    Book  MATH  Google Scholar 

  13. J.F. Dhem, Modified version of the Barrett modular multiplication algorithm. Tech. rep, UCL Crypto Group, Louvain-la-Neuve (1994)

  14. J.F. Dhem, Design of an efficient public-key cryptographic library for RISC based smart cards. Ph.D. thesis, Université Catholique de Louvain (1998)

  15. C. Doche, L. Imbert, Extended double-base number system with applications to elliptic curve cryptography. In: Progress in Cryptology - INDOCRYPT 2006, vol. 4329. Springer (2006)

  16. P.A. Findlay, B.A. Johnson, Modular exponentiation using recursive sums of residues, Advances in Cryptology—Crypto 89, vol. 435, Lecture Notes in Computer Science. (Springer, Berlin/Heidelberg, 1990), pp. 371–386

  17. W.L. Freking, K.K. Parhi, Modular multiplication in the residue number system with application to massively-parallel public-key cryptography systems. In: Proc. 34th Asilomar Conference on Signals, Systems and Computers, vol. 2, pp. 1339–1343 (2000)

  18. F. Gandino, F. Lamberti, G. Paravati, J. Bajard, P. Montuschi, An algorithmic and architectural study on Montgomery exponentiation in RNS. IEEE Trans. Comput. 61(8), 1071–1083 (2012). doi:10.1109/TC.2012.84

    Article  MathSciNet  Google Scholar 

  19. A. Garcia, A. Lloris, A look-up scheme for scaling in the RNS. IEEE Trans. Comput. 48(7), 748–751 (1999)

    Article  Google Scholar 

  20. N. Guillermin, A high speed coprocessor for elliptic curve scalar multiplications over F\(_p\), Proceedings of the 12th International Conference on Cryptographic Hardware and Embedded Systems, CHES’10 (Springer-Verlag, Berlin, Heidelberg, 2010), pp. 48–64

  21. K. Javeed, X. Wang, Radix-4 and radix-8 Booth encoded interleaved modular multipliers over general Fp. In: Field Programmable Logic and Applications (FPL), 2014 24th International Conference on, pp. 1–6 (2014). doi:10.1109/FPL.2014.6927452

  22. Javeed, K., Wang, X., Scott, M.: Serial and parallel interleaved modular multipliers on FPGA platform. In: Field Programmable Logic and Applications (FPL), 2015 25th International Conference on, pp. 1–4 (2015). doi:10.1109/FPL.2015.7293986

  23. G.A. Jullien, Residue number scaling and other operations using ROM arrays. IEEE Trans. Comput. 27(4), 325–336 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  24. S. Kawamura, M. Koike, F. Sano, A. Shimbo, Cox-Rower architecture for fast parallel Montgomery multiplication. In: Advances in Cryptology—Eurocrypt 2000, Lecture Notes in Computer Science, vol. 1807, pp. 523–538. Springer (2000)

  25. S.I. Kawamura, K. Hirano, A fast modular arithmetic algorithm using a residue table, Advances in Cryptology - Eurocrypt 88, vol. 330, Lecture Notes in Computer Science. (Springer, Berlin/Heidelberg, 1988), pp. 245–250

  26. N. Koblitz, A Course in Number Theory and Cryptography. Graduate Texts in Mathematics 114. Springer-Verlag (1987)

  27. Y. Kong, S. Asif, M. Khan, Modular multiplication using the core function in the residue number system. Appl. Algebra Eng. Commun. Comput. 27(1), 1–16 (2016). doi:10.1007/s00200-015-0268-1

    Article  MathSciNet  MATH  Google Scholar 

  28. Y., Kong, B. Phillips, Residue number system scaling schemes. In: S.F. Al-Sarawi (ed.) Proc. SPIE, Smart Structures, Devices, and Systems II, vol. 5649, pp. 525–536 (2005)

  29. S.R. Kuang, J.P. Wang, K.C. Chang, H.W. Hsu, Energy-efficient high-throughput montgomery modular multipliers for RSA cryptosystems. IEEE Trans. VLSI Syst. 21(11), 1999–2009 (2013). doi:10.1109/TVLSI.2012.2227846

    Article  Google Scholar 

  30. H. Marzouqi, M. Al-Qutayri, K. Salah, D. Schinianakis, T. Stouraitis, A high-speed FPGA implementation of an RSD-based ECC processor. IEEE Trans. VLSI Syst. 24(1), 151–164 (2016). doi:10.1109/TVLSI.2015.2391274

    Article  Google Scholar 

  31. P.L. Montgomery, Modular multiplication without trial division. Math. Comput. 44(170), 519–521 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  32. R. Muralidharan, C.H. Chang, Radix-8 Booth encoded modulo \(2 ^{n} -1\) multipliers with adaptive delay for high dynamic range residue number system. IEEE Trans. Circuits Syst. I Regul. Pap. 58(5), 982–993 (2011)

    Article  MathSciNet  Google Scholar 

  33. J. Neto, A. Ferreira Tenca, W. Ruggiero, A parallel and uniform k -partition method for Montgomery multiplication. IEEE Trans. Comput. 63(9), 2122–2133 (2014). doi:10.1109/TC.2013.89

    Article  MathSciNet  Google Scholar 

  34. K.C. Posch, R. Posch, Modulo reduction in residue number systems. IEEE Trans. Parallel Distrib. Syst. 6(5), 449–454 (1995)

    Article  MATH  Google Scholar 

  35. L. Rahimzadeh, M. Eshghi, S. Timarchi, Radix-4 implementation of redundant interleaved modular multiplication on FPGA. In: Electrical Engineering (ICEE), 2014 22nd Iranian Conference on, pp. 523–526 (2014). doi:10.1109/IranianCEE.2014.6999599

  36. R.L. Rivest, A. Shamir, L.M. Adleman, A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)

    Article  MathSciNet  MATH  Google Scholar 

  37. D. Schinianakis, T. Stouraitis, Multifunction residue architectures for cryptography. IEEE Trans. Circuits Syst. I Regul. Pap. 61(4), 1156–1169 (2014). doi:10.1109/TCSI.2013.2283674

    Article  Google Scholar 

  38. D. Schinianakis, T. Stouraitis, An RNS Barrett modular multiplication architecture. In: Circuits and Systems (ISCAS), 2014 IEEE International Symposium on, pp. 2229–2232 (2014). doi:10.1109/ISCAS.2014.6865613

  39. A. Shenoy, R. Kumaseran, A fast and accurate RNS scaling technique for high speed signal processing. IEEE Trans. Acoust. Speech Signal Process. 37(6), 929–937 (1989)

    Article  Google Scholar 

  40. A. Shenoy, R. Kumaseran, Fast base extension using a redundant modulus in RNS. IEEE Trans. Comput. 38(2), 292–297 (1989)

    Article  MATH  Google Scholar 

  41. M.A. Soderstrand, W. Jenkins, G. Jullien, Residue number system arithmetic: Modern applications. Digital Signal Processing (1986)

  42. N.S. Szabo, R.H. Tanaka, Residue Arithmetic and its Applications to Computer Technology (McGraw Hill, New York, 1967)

    MATH  Google Scholar 

  43. F.J. Taylor, C.H. Huang, An autoscale residue multiplier. IEEE Trans. Comput. 31(4), 321–325 (1982)

    Article  Google Scholar 

  44. A. Tomlinson, Bit-serial modular multiplier. Electron. Lett. 25(24), 1664 (1989)

    Article  Google Scholar 

  45. Y. Tong-jie, D. Zi-bin, Y. Xiao-Hui, Z. Qian-jin, An improved RNS Montgomery modular multiplier. In: Computer Application and System Modeling (ICCASM), 2010 International Conference on, vol. 10, pp. V10 144–V10 147 (2010). doi:10.1109/ICCASM.2010.5622857

  46. Z.D. Ulman, M. Czyzak, Highly parallel, fast scaling of numbers in nonredundant residue arithmetic. IEEE Trans. Signal Process. 46, 487–496 (1998)

    Article  MathSciNet  Google Scholar 

  47. G. Yao, J. Fan, R. Cheung, I. Verbauwhede, Novel RNS parameter selection for fast modular multiplication. IEEE Trans. Comput. 63(8), 2099–2105 (2014). doi:10.1109/TC.2013.92

    Article  MathSciNet  Google Scholar 

  48. G. Zervakis, N. Eftaxiopoulos, K. Tsoumanis, N. Axelos, K. Pekmestzi, A high radix Montgomery multiplier with concurrent error detection. In: Design Test Symposium (IDT), 2014 9th International, pp. 199–204 (2014). doi:10.1109/IDT.2014.7038613

Download references

Author information

Authors and Affiliations

  1. Department of Engineering, Macquarie University, Sydney, NSW, 2109, Australia

    Shahzad Asif & Yinan Kong

Authors
  1. Shahzad Asif
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yinan Kong
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shahzad Asif.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Asif, S., Kong, Y. Highly Parallel Modular Multiplier for Elliptic Curve Cryptography in Residue Number System. Circuits Syst Signal Process 36, 1027–1051 (2017). https://doi.org/10.1007/s00034-016-0336-1

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00034-016-0336-1

Keywords

Search

Navigation