{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T23:33:36Z","timestamp":1776209616930,"version":"3.50.1"},"reference-count":14,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2018,9,13]],"date-time":"2018-09-13T00:00:00Z","timestamp":1536796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Cryptography"],"abstract":"<jats:p>Modular inversions are widely employed in public key crypto-systems, and it is known that they imply a bottleneck due to the expensive computation. Recently, a new algorithm for inversions modulo     p k     was proposed, which may speed up the calculation of a modulus dependent quantity used in the Montgomery multiplication. The original algorithm lacks security countermeasures; thus, a straightforward implementation may expose the input. This is an issue if that input is a secret. In the RSA-CRT signature using Montgomery multiplication, the moduli are secrets (primes p and q). Therefore, the moduli dependent quantities related to p and q must be securely computed. This paper presents a security analysis of the novel method considering that it might be used to compute secrets. We demonstrate that a Side Channel Analysis leads to disclose the data being manipulated. In consequence, a secure variant for inversions modulo     2 k     is proposed, through the application of two known countermeasures. In terms of performance, the secure variant is still comparable with the original one.<\/jats:p>","DOI":"10.3390\/cryptography2030023","type":"journal-article","created":{"date-parts":[[2018,9,13]],"date-time":"2018-09-13T11:46:04Z","timestamp":1536839164000},"page":"23","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A Secure Algorithm for Inversion Modulo 2k"],"prefix":"10.3390","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2346-2163","authenticated-orcid":false,"given":"Sadiel","family":"De la Fe","sequence":"first","affiliation":[{"name":"Department of Microelectronics and Electronic Systems, Universitat Aut\u00f2noma de Barcelona, 08193 Barcelona, Spain"},{"name":"Applus Laboratories, Bellaterra, 08193 Barcelona, Spain"}]},{"given":"Carles","family":"Ferrer","sequence":"additional","affiliation":[{"name":"Department of Microelectronics and Electronic Systems, Universitat Aut\u00f2noma de Barcelona, 08193 Barcelona, Spain"}]}],"member":"1968","published-online":{"date-parts":[[2018,9,13]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/0021-9991(67)90047-2","article-title":"Computational problems associated with Racah algebra","volume":"1","author":"Stein","year":"1967","journal-title":"J. Comput. Phys."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Ac\u0131i\u00e7mez, O., Ko\u00e7, \u00c7.K., and Seifert, J.-P. (2007, January 22\u201327). On the power of simple branch prediction analysis. Proceedings of the 2nd ACM Symposium on Information, Computer and Communications Security, ASIACCS\u201907, Singapore.","DOI":"10.1145\/1229285.1266999"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/s13389-016-0135-4","article-title":"SPA vulnerabilities of the binary extended Euclidean algorithm","volume":"7","year":"2017","journal-title":"J. Cryptogr. Eng."},{"key":"ref_4","unstructured":"Ko\u00e7, \u00c7.K. (2018, September 12). A New Algorithm for Inversion Mod pk. Available online: https:\/\/eprint.iacr.org\/2017\/411.pdf."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1090\/S0025-5718-1985-0777282-X","article-title":"Modular multiplication without trial division","volume":"44","author":"Montgomery","year":"1985","journal-title":"Math. Comput."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd, I.B. (1990). A cryptographic library for the Motorola DSP56000. Advances in Cryptology\u2014EUROCRYPT 90, Springer.","DOI":"10.1007\/3-540-46877-3"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1435","DOI":"10.1109\/TC.2008.54","article-title":"On calculating multiplicative inverses modulo 2m","volume":"57","author":"Arazi","year":"2008","journal-title":"IEEE Trans. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_9","unstructured":"EMVCO (2018, September 12). Integrated Circuit Card Specifications for Payment Systems (Book 2\u2014Security and Key Management). Available online: https:\/\/www.emvco.com."},{"key":"ref_10","unstructured":"Witteman, M. (2018, September 12). A DPA Attack on RSA in CRT Mode. Available online: http:\/\/www.riscure.com."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/s13389-013-0050-x","article-title":"Attacking RSA-CRT signatures with faults on Montgomery multiplication","volume":"3","author":"Fouque","year":"2013","journal-title":"J. Cryptogr. Eng."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Kiss, A., Kramer, J., Rauzy, P., and Seifert, J.P. (2016, January 14\u201315). Algorithmic countermeasures against fault attacks and power analysis for RSA-CRT. Proceedings of the International Workshop on Constructive Side-Channel Analysis and Secure Design, Graz, Austria.","DOI":"10.1007\/978-3-319-43283-0_7"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1007\/3-540-48405-1_25","article-title":"Differential power analysis","volume":"Volume 1666","author":"Kocher","year":"1999","journal-title":"Advances in Cryptology (CRYPTO\u201999)"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1090\/S0025-5718-1987-0866113-7","article-title":"Speeding the Pollard and elliptic curve methods of factorization","volume":"48","author":"Montgomery","year":"1987","journal-title":"Math. Comput."}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/2\/3\/23\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T15:20:20Z","timestamp":1760196020000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/2\/3\/23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,13]]},"references-count":14,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2018,9]]}},"alternative-id":["cryptography2030023"],"URL":"https:\/\/doi.org\/10.3390\/cryptography2030023","relation":{},"ISSN":["2410-387X"],"issn-type":[{"value":"2410-387X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,13]]}}}