Compact SD: a new encoding algorithm and its application in multiplication

References

• A. Aris, B. Ors, and G. Saldamli, Architectures for Fast Modular Multiplication, Proceedings of the 14th IEEE Euromicro. Conf. Digit. Syst. Design, Oulu, 2011, pp. 434–437.
   Google Scholar
• T. Blum and C. Paar, High-radix Montgomery modular exponentiation on reconfigurable hardware, IEEE Trans. Comput. 50 (2001), pp. 759–764. doi: 10.1109/12.936241
   Web of Science ®Google Scholar
• B. Bollig, On the OBDD complexity of the most significant bit of integer multiplication, Theor. Comput. Sci. 412 (2011), pp. 1686–1695. doi: 10.1016/j.tcs.2010.12.043
   Web of Science ®Google Scholar
• A. Booth, A signed binary multiplication technique, J. Mech. Appl. Math. 4 (1951), pp. 236–240. doi: 10.1093/qjmam/4.2.236
   Web of Science ®Google Scholar
• Y. Fan, T. Ikenaga, and S. Goto, A high-speed design of Montgomery multiplier, IEICE Trans. Fundam. E91-A (2008), pp. 971–977. doi: 10.1093/ietfec/e91-a.4.971
   Web of Science ®Google Scholar
• A.P. Fournaries, Fault and Simple Power Attack Resistant RSA Using Montgomery Modular Multiplication, Proceedings of the IEEE Int. Symp. Circuits Syst., Paris, 2010, pp. 1875–1878.
   Google Scholar
• A.P. Fournaris and O. Koufopavlou, A New RSA Encryption Architecture and Hardware Implementation Based on Optimized Montgomery Multiplication, Proceedings of the IEEE ISCAS, Kobe, 2005, pp. 4645–4648.
   Google Scholar
• D. Harris, R. Krishnamurthy, M. Andersm, S. Mathew, and S. Hsu, An Improved Unified Scalable Radix-2 Montgomery Multiplier, Proceedings of the IEEE ARITH-17, Cape Cod, MA, 2005, pp. 172–178.
   Google Scholar
• J.H. Hong and C.W. Wu, Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified booth's algorithm, IEEE Trans. Very Large Scale Integr. Syst. 11 (2003), pp. 474–484. doi: 10.1109/TVLSI.2003.812308
   Web of Science ®Google Scholar
• A. Ibrahim, H. Elsimary, and F. Gebali, Low-power, high-speed unified and scalable word-based radix-8 architecture for Montgomery modular multiplication, Arab J. Sci. Eng. 39 (2014), pp. 7847–7863. doi: 10.1007/s13369-014-1363-5
   Web of Science ®Google Scholar
• A. Ibrahim, F. Gebali, H. Elsimary, and A. Nassar, Processor array architectures for scalable radix 4 Montgomery modular multiplication algorithm, IEEE Trans. Parallel Distrib. Syst. 22 (2011), pp. 1142–1149. doi: 10.1109/TPDS.2010.196
   Web of Science ®Google Scholar
• K. Javeed and X. Wang, Radix-4 and Radix-8 Booth Encoded Interleaved Modular Multipliers Over General Fp, Proceedings of the IEEE 24th Int. Conf. Field Prog. Logic Appl. (FPL), Munich, 2014, pp. 1–6.
   Google Scholar
• N. Jiang and D. Harris, Parallelized Radix-2 Scalable Montgomery Multiplier, Proceedings of the IFIP Int. Conf. Very Large Scale Integr., Atlanta, 2007, pp. 146–150.
   Google Scholar
• K. Kelley and D. Harris, Very High-radix Scalable Montgomery Multiplier, Proceedings of the 5th Int. Workshop System-on-chip Real-time Appl., Banff, 2005, pp. 400–404.
   Google Scholar
• P. Keshavarzi, VLSI implementation of public key cryptography algorithms, Ph.D. diss., Manchester University, 1999.
   Google Scholar
• C.K. Koc and C.Y. Hung, Adaptive m-ary segmentation and canonical recoding algorithms for multiplication of large binary numbers, Comput. Math. Appl. 24 (1992), pp. 3–12. doi: 10.1016/0898-1221(92)90209-Z
   Web of Science ®Google Scholar
• P. Kornerup, High-radix Modular Multiplication for Cryptosystems, Proceedings of the IEEE Int. Symp. Comput. Arith., Windsor, OT, 1993, pp. 277–283.
   Google Scholar
• S.R. Kuang, J.P. Wang, K.C. Chang, and H.W. Hsu, Energy-efficient high-throughput Montgomery modular multiplier for RSA cryptography, IEEE Trans. Very Large Scale Integr. Syst. 21 (2013), pp. 1999–2009. doi: 10.1109/TVLSI.2012.2227846
   Web of Science ®Google Scholar
• C. McIvor, M. McLoone, and J.V. McCanny, Modified Montgomery modular multiplication and RSA exponentiation techniques, IEEE Proc. Comput. Digit. Technol. 151 (2004), pp. 402–408. doi: 10.1049/ip-cdt:20040791
   Web of Science ®Google Scholar
• P.L. Montgomery, Modular multiplication without trial division, Math. Comput. 44 (1985), pp. 519–521. doi: 10.1090/S0025-5718-1985-0777282-X
   Web of Science ®Google Scholar
• N. Nedjah, L.M. Mourelle, M. Santana, and S. Raposo, Massively parallel modular exponentiation method and its implementation in software and hardware for high-performance cryptographic systems, IET Comput. Digit. Technol. 6 (2012), pp. 290–301. doi: 10.1049/iet-cdt.2011.0074
   Web of Science ®Google Scholar
• J.C. Neto, A.F. Tenca, and W.V. Ruggiero, Toward an Efficient Implementation of Sequential Montgomery Multiplication, Proceedings of the Asilomar Conf. Signals, Syst. Comput., Pacific Grove, CA, 2010, pp. 1680–1684.
   Google Scholar
• J.C. Neto, A.F. Tenca, and W.V. Ruggiero, A parallel and uniformly k-partition method for Montgomery multiplication, IEEE Trans. Comput. 63 (2014), pp. 2122–2133. doi: 10.1109/TC.2013.89
   Web of Science ®Google Scholar
• S.B. Ors, L. Batina, B. Preneel, and J. Vandewalle, Hardware Implementation of a Montgomery Modular Multiplier in a Systolic Array, Proceedings of the IEEE. Int. Parallel Distrib. Process. Symp., Nice, 2003.
   Google Scholar
• H. Orup, Simplifying Quotient Determination in High-radix Modular Multiplication, Proceedings of the IEEE Int. Symp. Comput. Arith., Bath, 1995, pp. 193–199.
   Google Scholar
• N. Pinckney and D. Harris, Parallelized Radix-4 Scalable Montgomery Multiplier, Proceedings of the 20th Ann. Conf. Integr. Circuit. Syst. Design, Rio de Janeiro, 2007, pp. 306–331, 2007.
   Google Scholar
• G. Reitwiesner, Binary arithmetic, Adv. Comput. 1 (1960), pp. 231–308. doi: 10.1016/S0065-2458(08)60610-5
   Google Scholar
• A. Rezai and P. Keshavarzi, High-performance Implementation Approach of Elliptic Curve Cryptosystem for Wireless Network Applications, Proceedings of the IEEE. Int. Conf. Consum. Electron. Commun. Netw., XianNing, 2011, pp. 1323–1327.
   Google Scholar
• A. Rezai and P. Keshavarzi, A new CMM-NAF modular exponentiation algorithm by using a new modular multiplication algorithm, Trends Appl. Sci. Res. 7 (2012), pp. 240–247. doi: 10.3923/tasr.2012.240.247
   Google Scholar
• A. Rezai and P. Keshavarzi, CCS Representation: A new non-adjacent form and its application in ECC, J. Basic Appl. Sci. Res. 2 (2012), pp. 4577–4586.
   Google Scholar
• A. Rezai and P. Keshavarzi, High-throughput modular multiplication and exponentiation algorithms using multibit-scan-multibit-shift technique, IEEE Trans. Very Large Scale Integr. Syst., in press. doi:10.1109/TVLSI.2014.2355854
   Web of Science ®Google Scholar
• G.A. Ruiz and M. Granda, Efficient canonic signed digit recoding, Microelectron J. 42 (2011), pp. 1090–1097. doi: 10.1016/j.mejo.2011.06.006
   Web of Science ®Google Scholar
• I. San and N. At, Improving the computational efficiency of modular operations for embedded systems, J. Syst. Architect. 60 (2014), pp. 440–451. doi: 10.1016/j.sysarc.2013.10.013
   Web of Science ®Google Scholar
• G. Sassaw, C.J. Jimenez, and M. Valencia, High Radix Implementation of Montgomery Multipliers with CSA, Proceedings of the Int. Conf. Microelectron, Cairo, 2010, pp. 315–318.
   Google Scholar
• M.D. Shieh, J.H. Chen, W.C. Lin, and H.H. Wu, A new algorithm for high-speed modular multiplication design, IEEE Trans. Circuits Syst. I, Reg. Pap. 56 (2009), pp. 2009–2019. doi: 10.1109/TCSI.2008.2011585
   Web of Science ®Google Scholar
• M.D. Shieh, J.H. Chen, H.H. Wu, and W.C. Lin, A new modular exponentiation architecture for efficient design of RSA cryptosystem, IEEE Trans. Very Large Scale Integr. Syst. 16 (2008), pp. 1151–1161. doi: 10.1109/TVLSI.2008.2000524
   Web of Science ®Google Scholar
• M. Shieh and W. Lin, Word-based Montgomery modular multiplication algorithm for low-latency scalable architectures, IEEE Trans. Comput. 59 (2010), pp. 1145–1151. doi: 10.1109/TC.2010.72
   Web of Science ®Google Scholar
• G.D. Sutter, J.P. Deschamps, and J.L. Imana, Modular multiplication and exponentiation architecture for fast RSA cryptosystem based on digit serial computation, IEEE Trans. Ind. Electron. 58 (2011), pp. 3101–3109. doi: 10.1109/TIE.2010.2080653
   Web of Science ®Google Scholar
• L.A. Tawalbeh, A.F. Tenca, and C.K. Koc, A radix-4 scalable design, IEEE Potentials, 24 (2005), pp. 16–18. doi: 10.1109/MP.2005.1462460
   Google Scholar
• A.F. Tenca and C.K. Koc, A scalable architecture for modular multiplication based on Montgomery's algorithm, IEEE Trans. Comput. 52 (2003), pp. 1215–1221. doi: 10.1109/TC.2003.1228516
   Web of Science ®Google Scholar
• A.F. Tenca, G. Todorov, and C.K. Koc, High-radix Design of a Scalable Modular Multiplication, Proceedings of the CHES, pp. 189–205, 2001.
   Google Scholar
• J. Xie, J.J. He, and P.K. Meher, Low latency systolic Montgomery multiplier for finite field GF(2 m) based on pentanomials, IEEE Trans. Very Large Scale Integr. Syst. 21 (2013), pp. 385–389. doi: 10.1109/TVLSI.2012.2185257
   Web of Science ®Google Scholar
• C.D. Walter, Systolic modular multiplication, IEEE Trans. Comput. 42 (1993), pp. 376–378. doi: 10.1109/12.210181
   Web of Science ®Google Scholar
• C.L. Wu, Fast exponentiation based on common-multiplicand-multiplication and minimal-signed-digit techniques, Int. J. Comput. Math. 84 (2007), pp. 1405–1415. doi: 10.1080/00207160701303136
   Web of Science ®Google Scholar
• T. Wu, S. Li, and L. Liu, Fast, compact and symmetric modular exponentiation architecture by common-multiplicand Montgomery modular multiplication, Integr. VLSI, J. 36 (2013), pp. 323–332. doi: 10.1016/j.vlsi.2012.09.002
   Web of Science ®Google Scholar
• C.L. Wu, D.C. Lou, and T.J. Chang, Fast modular multiplication based on complement representation and canonical recoding, Int. J. Comput. Math. 87 (2010), pp. 2871–2879. doi: 10.1080/00207160903033630
   Web of Science ®Google Scholar
• Y. Zhang, Z. Li, L. Yang, and S. Zhang, An efficient CSA architecture for Montgomery modular multiplication, Microprocess. Microsyst. J. 31 (2007), pp. 456–459. doi: 10.1016/j.micpro.2006.12.003
   Web of Science ®Google Scholar