SpringerLink
Log in

Residue Number Systems in Cryptography: Design, Challenges, Robustness

  • Chapter
Secure System Design and Trustable Computing

Abstract

As conventional arithmetic solutions have improved at a fine-grain level, researchers have turned their attention to alternative number system representations in an effort to further boost up cryptosystem performance. The ancient Residue Number System (RNS) has emerged as a key-player in this endeavor. This chapter attempts to highlight important concepts of residue arithmetic and new RNS applications in modern cryptography are presented in a systematic and holistic manner. Progressing from algorithm and complexity analysis to state-of-the-art hardware implementations and useful cryptanalytic properties, the prospective reader is acquainted with most of the implications and challenges of this emerging field, while open research points are also highlighted.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Aumüller, C., Bier, P., Fischer, W., Hofreiter, P., Seifert, J.P.: Fault attacks on RSA with CRT: concrete results and practical counter-measures. In: Proceedings of International Workshop Cryptographic Hardware and Embedded Systems (CHES ’02), pp. 260–275, 2002

    Google Scholar 

  2. Bajard, J., Eynard, J., Gandino, F.: Fault detection in rns montgomery modular multiplication. In: 21st IEEE Symposium on Computer Arithmetic, ARITH, pp. 119–126, 2013

    Google Scholar 

  3. Bajard, J., Kaihara, M., Plantard, T.: Selected RNS Bases for Modular Multiplication. In: 19th IEEE International Symposium on Computer Arithmetic, pp. 25–32, 2009

    Google Scholar 

  4. Bajard, J.C., Didier, L.S., Kornerup, P.: Modular multiplication and base extensions in residue number systems. In: Proceedings of the 15th Symposium on Computer Arithmetic, ARITH ’01, pp. 59–65, 2001

    Google Scholar 

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

    Article  Google Scholar 

  6. Bajard, J.C., Imbert, L., Jullien, G.A.: Parallel Montgomery multiplication in GF(2k) using trinomial residue arithmetic. IEEE Symp. Comput. Arith. 0, 164–171 (2005). doi:10.1109/ARITH.2005.34

    Google Scholar 

  7. Blake, I., Seroussi, G., Smart, N.: Elliptic Curves in Cryptography. Cambridge University Press, Cambridge (2002)

    Google Scholar 

  8. Blömer, J., Otto, M., Seifert, J.P.: A new CRT-RSA algorithm secure against bellcore attacks. In: Proceedings of the 10th ACM Conference on Computer and Communications Security, CCS ’03, pp. 311–320, 2003

    Google Scholar 

  9. Boneh, D., DeMillo, R., Lipton, R.: On the importance of eliminating errors in cryptographic computations. J. Cryptol. 14, 101–119 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  10. Deschamps, J.P., Bioul, G.J.A., Sutter, G.D.: Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems. Wiley, Hoboken, New Jersey (2006)

    Google Scholar 

  11. Di Claudio, E.D., Piazza, F., Orlandi, G.: Fast combinatorial rns processors for dsp applications. IEEE Trans. Comput. 44(5), 624–633 (1995)

    Google Scholar 

  12. Ercegovac, M., Lang, T.: Digital Arithmetic. Morgan Kaufmann, San Francisco (2004)

    Google Scholar 

  13. 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. VLSI Syst. 8(21), 1545–1549 (2013)

    Article  Google Scholar 

  14. Gandino, F., Lamberti, F., Montuschi, P., Bajard, J.: A General Approach for Improving RNS Montgomery Exponentiation Using Pre-processing. In: 20th IEEE Symposium on Computer Arithmetic, ARITH, pp. 195–204, 2011

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  16. Giraud, C.: An RSA implementation resistant to fault attacks and to simple power analysis. IEEE Trans. Comput. 55(9), 1116–1120 (2006)

    Article  Google Scholar 

  17. Goldreich, O., Goldwasser, S., Halevi, S.: Public-key cryptosystems from lattice reduction problems. In: Kaliski, B.J. (ed.) Advances in Cryptology CRYPTO ’97. Lecture Notes in Computer Science, vol. 1294, pp. 112–131. Springer Berlin/Heidelberg (1997). doi:10.1007/BFb0052231. http://dx.doi.org/10.1007/BFb0052231

    Google Scholar 

  18. Hankerson, D., Menezes, A., Vanstone, S.: Guide to Elliptic Curves Cryptography. Springer and Hall/CRC, New York (2004)

    Google Scholar 

  19. Hiasat, A., Abdel-Aty-Zohdy, H.: A high-speed division algorithm for residue number system. In: IEEE International Symposium on Circuits and Systems, 1995. ISCAS ’95, vol. 3, pp. 1996–1999, 1995

    Google Scholar 

  20. Huang, C.H., Taylor, F.J.: A memory compression scheme for modular arithmetic. IEEE Trans. Acoust. Speech Signal Process. ASSP-27, 608–611 (1979)

    Article  MathSciNet  Google Scholar 

  21. Joye, M., Yen, S.M.: The Montgomery powering ladder. In: Proceedings of Workshop on Cryptographic Hardware and Embedded Systems (CHES’02) LNCS, pp. 291–302, 2002

    Google Scholar 

  22. Jullien, G.A.: Residue number scaling and other operations using rom arrays. IEEE Trans. Comput. C-27(4), 325–336 (1978)

    Article  MathSciNet  Google Scholar 

  23. Kaliski, B.: TWIRL and RSA key size. http://www.rsasecurity.com/rsalabs/node.asp?id=2004

  24. Kawamura, S., Koike, M., Sano, F., Shimbo, A.: Cox-Rower architecture for fast parallel Montgomery multiplication. In: EUROCRYPT’00: Proceedings of the 19th international conference on Theory and application of cryptographic techniques, pp. 523–538. Springer, Berlin/Heidelberg (2000)

    Google Scholar 

  25. Knuth, D.E.: The Art of Computer Programming: Seminumerical Algorithms, 3rd edn. vol. 2. Addison-Wesley Longman Publishing, Boston, MA (1997)

    Google Scholar 

  26. Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  27. Koren, I.: Computer Arithmetic Algorithms. A K Peters, Natick, Massachusetts (2002)

    MATH  Google Scholar 

  28. Lab, R.: High-speed RSA implementation (2011). ftp://ftp.rsasecurity.com/pub/pdfs/tr201.pdf

  29. Lab, R.: RSA hardware implementation (2011). ftp://ftp.rsasecurity.com/pub/pdfs/tr801.pdf

  30. Lidl, R., Niederreiter, H.: Introduction to Finite Fields and their Applications. Cambridge University Press, New York (1986)

    MATH  Google Scholar 

  31. Ma, K., Liang, H., Wu, K.: Homomorphic property-based concurrent error detection of RSA: a countermeasure to fault attack. IEEE Trans. Comput. 61(7), 1040–1049 (2012)

    Article  MathSciNet  Google Scholar 

  32. McEliece, R.J.: Finite Field for Scientists and Engineers. Kluwer Academic, Norwell (1987)

    Book  Google Scholar 

  33. Miller, V.: Use of elliptic curves in cryptography. In: Advances in Cryptology (CRYPTO’85) LNCS, vol. 218, pp. 47–426, 1986

    Google Scholar 

  34. Mohan, P.: RNS-to-binary converter for a new three-moduli Set \(\{2^{n+1} - 1,2^{n},2^{n} - 1\}\). IEEE Trans. Circuits Syst. Express Briefs 54(9), 775–779 (2007)

    Article  Google Scholar 

  35. Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 16, 519–521 (1985)

    Article  Google Scholar 

  36. Navi, K., Molahosseini, A., Esmaeildoust, M.: How to teach residue number system to computer scientists and engineers. IEEE Trans. Educ. 54(1), 156–163 (2011)

    Article  Google Scholar 

  37. Nozaki, H., Motoyama, M., Shimbo, A., Kawamura, S.: Implementation of RSA algorithm Based on RNS Montgomery multiplication. In: Proceedings of Workshop on Cryptographic Hardware and Embedded Systems (CHES’01) LNCS, vol. 2162, pp. 364–376, 2001

    Google Scholar 

  38. Posch, K., Posch, R.: Base extension using a convolution sum in residue number systems. Computing 50(2), 93–104 (1993)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  40. Ramirez, J., Fernandez, P., Meyer-Base, U., Taylor, F., Garcia, A., Lloris, A.: Index-based rns dwt architectures for custom ic designs. In: IEEE Workshop on Signal Processing Systems, pp. 70–79, 2001

    Google Scholar 

  41. Regev, O.: Lattice-based cryptography. In: Advances in Cryptology CRYPTO ’06. Lecture Notes in Computer Science, pp. 131–141. Springer, Berlin/Heidelberg (2006)

    Google Scholar 

  42. Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commum. ACM 21, 120–126 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  43. Savaş, E., Tenca, A., Koç, Çetin.: A scalable and unified multiplier architecture for finite fields GF(p) and GF(2m). In: Cryptographic Hardware and Embedded Systems (CHES 2000). Lecture Notes in Computer Science, vol. 1965, pp. 277–292. Springer, Berlin (2000)

    Google Scholar 

  44. Schinianakis, D.: Versatile architectures for cryptographic systems, Ph.D. dissertation. University of Patras, Patras, Greece, 2013

    Book  Google Scholar 

  45. Schinianakis, D., Fournaris, A., Michail, H., Kakarountas, A., Stouraitis, T.: An RNS implementation of an F p elliptic curve point multiplier. IEEE Trans. Circuits Syst. I 56(6), 1202–1213 (2009)

    Article  MathSciNet  Google Scholar 

  46. Schinianakis, D., Stouraitis, T.: A RNS Montgomery multiplication architecture. In: IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1167–1170, 2011

    Google Scholar 

  47. Schinianakis, D., Stouraitis, T.: Hardware-fault attack handling in RNS-based Montgomery multipliers. In: IEEE International Symposium on Circuits and Systems (ISCAS), pp. 3042–3045, 2013

    Google Scholar 

  48. Schinianakis, D., Stouraitis, T.: Multifunction residue architectures for cryptography. IEEE Trans. Circuits Syst. I: Reg. pap. 61(4), 1156–1169 (2014)

    Article  Google Scholar 

  49. Shamir, A.: Improved method and apparatus for protecting public key schemes from timing and fault attacks. U.S Patent, 1999

    Google Scholar 

  50. Shenoy, M., Kumaresan, R.: 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 

  51. Skavantzos, A., Wang, Y.: New efficient rns-to-weighted decoders for conjugate-pair-moduli residue number systems. In: Conference Record of the Thirty-Third Asilomar Conference on Signals, Systems, and Computers, vol. 2, pp. 1345–1350, 1999

    Google Scholar 

  52. Smith, W.: Swift. In: Symposium on Very High Speed Computing Technology (held with IEEE ICASSD Conference) 1980

    Google Scholar 

  53. Sousa, L.: Efficient method for magnitude comparison in RNS based on two pairs of conjugate moduli. In: 18th IEEE Symposium on Computer Arithmetic, 2007. ARITH ’07, pp. 240–250, 2007

    Google Scholar 

  54. Szabo, N., Tanaka, R.: Residue Arithmetic and its Applications to Computer Technology. McGraw-Hill, New York (1967)

    MATH  Google Scholar 

  55. Taylor, F., Zelniker, G., Smith, J., Mellott, J.: The gauss machine-a dsp processor with a high rns content. In: International Conference on Acoustics, Speech, and Signal Processing, 1991. ICASSP-91, vol. 2, pp. 1081–1084, 1991

    Google Scholar 

  56. Taylor, F.J.: A vlsi residue arithmetic multiplier. IEEE Trans. Comput. C-31(6), 540–546 (1982)

    Article  Google Scholar 

  57. Taylor, F.J.: Residue arithmetic: a tutorial with examples. IEEE Comput. 17, 50–62 (1988)

    Article  Google Scholar 

  58. Tomczak, T.: Fast sign detection for RNS \((2^{n} - 1,2^{n},2^{n} + 1)\). IEEE Trans. Circuits Syst. Regul. Pap. 55(6), 1502–1511 (2008)

    Article  MathSciNet  Google Scholar 

  59. Vigilant, D.: RSA with CRT: a new cost-effective solution to Thwart fault attacks. In: Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems (CHES 08), pp. 130–145, 2008

    Google Scholar 

  60. Wang, W., Swamy, M., Ahmad, O., Wang, Y.: New Chinese Remainder Theorems applications to special moduli sets. In: CCECE99, vol. 2, pp. 1345–1350, 1999

    Google Scholar 

  61. Wang, Y.: Residue-to-binary converters based on new chinese remainder theorems. IEEE Trans. Circuits Syst. II: Analog Digit. Signal Process. 47(3), 197–205 (2000)

    Article  MATH  Google Scholar 

  62. Yang, J.H., Chang, C.C., Chen, C.Y.: A high-speed division algorithm in residue number system using parity-checking technique. Int. J. Comput. Math. 81(6), 775–780 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  63. Yassine, H.M., Moore, W.: Improved mixed-radix conversion for residue number system architectures. IEE Proc. G Circuits Devices Syst. 138(1), 120–124 (1991)

    Article  Google Scholar 

  64. Yen, S., Joye, M.: Checking before output may not be enough against fault-based cryptanalysis. IEEE Trans. Comput. 49(9), 967–970 (2000)

    Article  MATH  Google Scholar 

  65. Yen, S., Kim, S., Lim, S., Moon, S.: RSA speedup with Chinese remainder theorem immune against hardware fault cryptanalysis. IEEE Trans. Comput. 52(4), 461–472 (2003)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical and Computer Engineering, University of Patras, Patras, Greece

    Dimitris Schinianakis

  2. Department of Electrical and Computer Engineering, University of Patras, Rio, 26110, Greece

    Thanos Stouraitis

Authors
  1. Dimitris Schinianakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thanos Stouraitis
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thanos Stouraitis .

Editor information

Editors and Affiliations

  1. School of EEE, Nanyang Technological University, Singapore, Singapore

    Chip-Hong Chang

  2. University of California Los Angeles, Los Angeles, California, USA

    Miodrag Potkonjak

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer International Publishing Switzerland

About this chapter

Cite this chapter

Schinianakis, D., Stouraitis, T. (2016). Residue Number Systems in Cryptography: Design, Challenges, Robustness. In: Chang, CH., Potkonjak, M. (eds) Secure System Design and Trustable Computing. Springer, Cham. https://doi.org/10.1007/978-3-319-14971-4_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-14971-4_4

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-14970-7

  • Online ISBN: 978-3-319-14971-4

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics

Search

Navigation