{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T23:55:16Z","timestamp":1781913316507,"version":"3.54.5"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T00:00:00Z","timestamp":1603756800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T00:00:00Z","timestamp":1603756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Institute for Information & communications Technology Planning & Evaluation","award":["2019-0-00033"],"award-info":[{"award-number":["2019-0-00033"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Modular multiplication is one of the most time-consuming operations that account for almost 80% of computational overhead in a scalar multiplication in elliptic curve cryptography. In this paper, we present a new speed record for modular multiplication over 192-bit NIST prime P-192 on 8-bit AVR ATmega microcontrollers.\n We propose a new integer representation named Range Shifted Representation (RSR) which enables an efficient merging of the reduction operation into the subtractive Karatsuba multiplication. This merging results in a dramatic optimization in the intermediate accumulation of modular multiplication by reducing a significant amount of unnecessary memory access as well as the number of addition operations. Our merged modular multiplication on RSR is designed to have two duplicated groups of 96-bit intermediate values during accumulation. Hence, only one accumulation of the group is required and the result can be used twice.\n Consequently, we significantly reduce the number of load\/store instructions which are known to be one of the most time-consuming operations for modular multiplication on constrained devices. Our implementation requires only 2888 cycles for the modular multiplication of 192-bit integers and outperforms the previous best result for modular multiplication over P-192 by a factor of 17%. In addition, our modular multiplication is even faster than the Karatsuba multiplication (without reduction) which achieved a speed record for multiplication on AVR processor.<\/jats:p>","DOI":"10.1007\/s11227-020-03441-5","type":"journal-article","created":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T21:11:38Z","timestamp":1603833098000},"page":"4852-4870","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient implementation of modular multiplication over 192-bit NIST prime for 8-bit AVR-based sensor node"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3588-2985","authenticated-orcid":false,"given":"Dong-won","family":"Park","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7506-4023","authenticated-orcid":false,"given":"Seokhie","family":"Hong","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nam Su","family":"Chang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sung Min","family":"Cho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,10,27]]},"reference":[{"key":"3441_CR1","first-page":"119","volume-title":"Cryptographic hardware and embedded systems (lecture notes in computer science)","author":"N Gura","year":"2004","unstructured":"Gura N, Patel A, Wander A, Eberle H, Shantz SC (2004) Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye M, Quisquater JJ (eds) Cryptographic hardware and embedded systems (lecture notes in computer science), vol 3156. Springer, Berlin, pp 119\u2013132"},{"key":"3441_CR2","doi-asserted-by":"crossref","unstructured":"Liu A, Ning P (2008) TinyECC: a configurable library for elliptic curve cryptography in wireless sensor networks. In: Proceedings of the 7th International Conference on Information Processing in Sensor Networks (IPSN), pp 245\u2013256","DOI":"10.1109\/IPSN.2008.47"},{"issue":"7","key":"3441_CR3","doi-asserted-by":"publisher","first-page":"1385","DOI":"10.1109\/TIFS.2015.2491261","volume":"11","author":"Z Liu","year":"2016","unstructured":"Liu Z, Seo H, Gro\u00dfsch\u00e4dl J, Kim H (2016) Efficient implementation of NIST-compliant elliptic curve cryptography for 8-bit AVR-based sensor nodes. IEEE Trans Inf Forensics Secur 11(7):1385\u20131397","journal-title":"IEEE Trans Inf Forensics Secur"},{"key":"3441_CR4","doi-asserted-by":"publisher","first-page":"67637","DOI":"10.1109\/ACCESS.2018.2878777","volume":"6","author":"SC Seo","year":"2018","unstructured":"Seo SC, Seo H (2018) Highly efficient implementation of NIST-compliant Koblitz curve for 8-bit AVR-based sensor nodes. IEEE Access 6:67637\u201367652","journal-title":"IEEE Access"},{"issue":"4","key":"3441_CR5","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1147\/sj.294.0526","volume":"29","author":"PG Comba","year":"1990","unstructured":"Comba PG (1990) Exponentiation cryptosystems on the IBM PC. IBM Syst J 29(4):526\u2013538","journal-title":"IBM Syst J"},{"key":"3441_CR6","unstructured":"Scott M, Szczechowiak P (2007) Optimizing multiprecision multiplication for public key cryptography. Cryptology ePrint archive, report 2007\/299"},{"key":"3441_CR7","doi-asserted-by":"crossref","unstructured":"Szczechowiak P, Oliveira LB, Scott M, Collier M, Dahab R (2008) NanoECC: testing the limits of elliptic curve cryptography in sensor networks. In: Proceedings of the International Conference on Wireless Sensor Networks\u201908). Springer, Berlin, pp 305\u2013320","DOI":"10.1007\/978-3-540-77690-1_19"},{"key":"3441_CR8","doi-asserted-by":"crossref","unstructured":"Uhsadel L, Poschmann A, Paar C (2007) Enabling full-size public-key algorithms on 8-bit sensor nodes. In: Proceedings of the International Conference on Security and Privacy in Ad-Hoc and Sensor Networks (ESAS\u201907). Springer, Berlin, pp 73\u201386","DOI":"10.1007\/978-3-540-73275-4_6"},{"key":"3441_CR9","doi-asserted-by":"crossref","unstructured":"Yang Z, Johann G (2011) Efficient prime-field arithmetic for elliptic curve cryptography on wireless sensor nodes. In: Proceedings of the International Conference on Computer Science and Network Technology, pp 459\u2013466","DOI":"10.1109\/ICCSNT.2011.6181997"},{"key":"3441_CR10","first-page":"459","volume-title":"Cryptographic hardware and embedded systems (lecture notes in computer science)","author":"M Hutter","year":"2011","unstructured":"Hutter M, Wenger E (2011) Fast multi-precision multiplication for publickey cryptography on embedded microprocessors. In: Preneel B, Takagi T (eds) Cryptographic hardware and embedded systems (lecture notes in computer science), vol 6917. Springer, Berlin, pp 459\u2013474"},{"key":"3441_CR11","series-title":"Lecture notes in computer science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-35416-8_5","volume-title":"Information security applications","author":"H Seo","year":"2012","unstructured":"Seo H, Kim H (2012) Multi-precision multiplication for public-key cryptography on embedded microprocessors. In: MotiYung DHL (ed) Information security applications, vol 7690. Lecture notes in computer science. Springer, Berlin, pp 55\u201367"},{"issue":"3","key":"3441_CR12","doi-asserted-by":"publisher","first-page":"255","DOI":"10.7763\/IJCCE.2013.V2.183","volume":"2","author":"H Seo","year":"2013","unstructured":"Seo H, Kim H (2013) Optimized multi-precision multiplication for public-key cryptography on embedded microprocessors. Int J Comput Commun Eng 2(3):255","journal-title":"Int J Comput Commun Eng"},{"issue":"3","key":"3441_CR13","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s13389-015-0093-2","volume":"5","author":"M Hutter","year":"2015","unstructured":"Hutter M, Schwabe P (2015) Multiprecision multiplication on AVR revisited. J Cryptogr Eng 5(3):201\u2013214","journal-title":"J Cryptogr Eng"},{"key":"3441_CR14","doi-asserted-by":"crossref","unstructured":"Miller VS (1985) Use of elliptic curves in cryptography. In: Proceedings of the Conference on the Theory and Application of Cryptographic Techniques, Santa Barbara, CA, USA. Springer, Berlin, pp 417\u2013426 (1985)","DOI":"10.1007\/3-540-39799-X_31"},{"issue":"177","key":"3441_CR15","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","volume":"48","author":"N Koblitz","year":"1987","unstructured":"Koblitz N (1987) Elliptic curve cryptosystems. Math Comput 48(177):203\u2013209","journal-title":"Math Comput"},{"key":"3441_CR16","unstructured":"National Institute of Standards and Technology (1999) Recommended elliptic curves for federal government use. http:\/\/csrc.nist.gov\/encryption\/dss\/ecdsa\/NISTReCur.pdf"},{"issue":"7","key":"3441_CR17","first-page":"595","volume":"7","author":"AA Karatsuba","year":"1963","unstructured":"Karatsuba AA, Ofman YP (1963) Multiplication of multidigit numbers on automata. Sov Phys Dokl 7(7):595\u2013596","journal-title":"Sov Phys Dokl"},{"issue":"2","key":"3441_CR18","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/s11390-016-1627-5","volume":"31","author":"Z Liu","year":"2016","unstructured":"Liu Z, Seo H, Kim H (2016) A synthesis of multi-precision multiplication and squaring techniques for 8-bit sensor nodes: state of-the-art research and future challenges. J Comput Sci Technol 31(2):284\u2013299","journal-title":"J Comput Sci Technol"},{"issue":"170","key":"3441_CR19","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1090\/S0025-5718-1985-0777282-X","volume":"44","author":"PL Montgomery","year":"1985","unstructured":"Montgomery PL (1985) Modular multiplication without trial division. Math Comput 44(170):519\u2013521","journal-title":"Math Comput"},{"key":"3441_CR20","doi-asserted-by":"crossref","unstructured":"Liu Z, Gro\u00dfsch\u00e4dl J, Wong DS (2014) Low-weight primes for lightweight elliptic curve cryptography on 8-bit AVR processors. In: Information Security and Cryptology\u2014INSCRYPT 2013. LNCS (2014)","DOI":"10.1007\/978-3-319-12087-4_14"},{"key":"3441_CR21","unstructured":"Liu Z, Gro\u00dfsch\u00e4dl J, Kizhvatov I (2010) Efficient and Side-Channel Resistant RSA Implementation for 8-bit AVR Microcontrollers. In: Workshop on the Security of the Internet of Things\u2014SOCIOT 2010, 1st International Workshop, Tokyo, Japan, November 29. IEEE Computer Society, Los Alamitos"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03441-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-020-03441-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03441-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,26]],"date-time":"2021-10-26T23:29:02Z","timestamp":1635290942000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-020-03441-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,27]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["3441"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03441-5","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,27]]},"assertion":[{"value":"25 September 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}