{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:46:50Z","timestamp":1760233610625,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"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 arithmetic over integers is required for many cryptography systems. Montgomery reduction is an efficient algorithm for the modulo reduction after a multiplication. Typically, Montgomery reduction is used for rings of ordinary integers. In contrast, we investigate the modular reduction over rings of Gaussian integers. Gaussian integers are complex numbers where the real and imaginary parts are integers. Rings over Gaussian integers are isomorphic to ordinary integer rings. In this work, we show that Montgomery reduction can be applied to Gaussian integer rings. Two algorithms for the precision reduction are presented. We demonstrate that the proposed Montgomery reduction enables an efficient Gaussian integer arithmetic that is suitable for elliptic curve cryptography. In particular, we consider the elliptic curve point multiplication according to the randomized initial point method which is protected against side-channel attacks. The implementation of this protected point multiplication is significantly faster than comparable algorithms over ordinary prime fields.<\/jats:p>","DOI":"10.3390\/cryptography5010006","type":"journal-article","created":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T11:40:48Z","timestamp":1612179648000},"page":"6","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Montgomery Reduction for Gaussian Integers"],"prefix":"10.3390","volume":"5","author":[{"given":"Malek","family":"Safieh","sequence":"first","affiliation":[{"name":"Institute for System Dynamics (ISD), HTWG Konstanz, University of Applied Sciences, 78462 Konstanz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5913-4981","authenticated-orcid":false,"given":"J\u00fcrgen","family":"Freudenberger","sequence":"additional","affiliation":[{"name":"Institute for System Dynamics (ISD), HTWG Konstanz, University of Applied Sciences, 78462 Konstanz, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,1]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","unstructured":"Mahapatra, P.P., and Agrawal, S. (2017, January 14\u201316). RSA Cryptosystem with Modified Montgomery Modular Multiplier. Proceedings of the IEEE International Conference on Computational Intelligence and Computing Research (ICCIC), Coimbatore, India.","DOI":"10.1109\/ICCIC.2017.8524218"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1049\/iet-ifs.2018.5191","article-title":"Fast Montgomery modular multiplier for Rivest-Shamir-Adleman cryptosystem","volume":"13","author":"Parihar","year":"2019","journal-title":"IET Inf. Secur."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1090\/S0025-5718-1987-0866109-5","article-title":"Elliptic Curve Cryptosystems","volume":"48","author":"Koblitz","year":"1987","journal-title":"Math. Comput."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"2753","DOI":"10.1109\/TVLSI.2014.2375640","article-title":"Scalable Elliptic Curve Cryptosystem FPGA Processor for NIST Prime Curves","volume":"23","author":"Loi","year":"2015","journal-title":"IEEE Trans. Very Large Scale Integr. (VLSI) Syst."},{"key":"ref_6","first-page":"1078","article-title":"Throughput\/Area-efficient ECC Processor Using Montgomery Point Multiplication on FPGA","volume":"62","author":"Khan","year":"2015","journal-title":"IEEE Trans. Circuits Syst. II Express Briefs"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Hossain, M.S., Saeedi, E., and Kong, Y. (2015, January 11\u201313). High-Speed, Area-Efficient, FPGA-Based Elliptic Curve Cryptographic Processor over NIST Binary Fields. Proceedings of the IEEE International Conference on Data Science and Data Intensive Systems, Sydney, NSW, Australia.","DOI":"10.1109\/DSDIS.2015.44"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Bosmans, J., Roy, S.S., Jarvinen, K., and Verbauwhede, I. (2016, January 4\u20138). A Tiny Coprocessor for Elliptic Curve Cryptography over the 256-bit NIST Prime Field. Proceedings of the 29th International Conference on VLSI Design (VLSID), Kolkata, India.","DOI":"10.1109\/VLSID.2016.82"},{"key":"ref_9","unstructured":"Lam, K.Y., Chi, C.H., and Qing, S. (2016). Low-Cost Hardware Implementation of Elliptic Curve Cryptography for General Prime Fields. Information and Communications Security, Springer International Publishing. Lecture Notes in Computer Science."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Mozhi, S.A., and Ramya, P. (2016, January 3\u20135). Efficient bit-parallel systolic multiplier over GF(2m). Proceedings of the International Conference on Electrical, Electronics, and Optimization Techniques (ICEEOT), Chennai, India.","DOI":"10.1109\/ICEEOT.2016.7755632"},{"key":"ref_11","unstructured":"Amiet, D., Curiger, A., and Zbinden, P. (September, January 31). Flexible FPGA-Based Architectures for Curve Point Multiplication over GF(p). Proceedings of the Euromicro Conference on Digital System Design (DSD), Limassol, Cyprus."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1109\/TVLSI.2016.2574620","article-title":"High-Speed and Low-Latency ECC Processor Implementation Over GF(2m) on FPGA","volume":"25","author":"Khan","year":"2017","journal-title":"IEEE Trans. Very Large Scale Integr. (VLSI) Syst."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Safieh, M., Thiers, J.P., and Freudenberger, J. (2019, January 11\u201314). Area Efficient Coprocessor for the Elliptic Curve Point Multiplication. Proceedings of the 12th International ITG Conference on Systems, Communications and Coding (SCC), Rostock, Germany.","DOI":"10.3390\/electronics9122050"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1587","DOI":"10.1109\/TVLSI.2019.2905899","article-title":"High-Speed Implementation of ECC Scalar Multiplication in GF(p) for Generic Montgomery Curves","volume":"27","author":"Roy","year":"2019","journal-title":"IEEE Trans. Very Large Scale Integr. (VLSI) Syst."},{"key":"ref_15","unstructured":"Elkamchouchi, H., Elshenawy, K., and Shaban, H. (2002, January 28). Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers. Proceedings of the 8th International Conference on Communication Systems (ICCS), Singapore."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Koval, A., and Verkhovsky, B.S. (2008, January 7\u20139). Analysis of RSA over Gaussian Integers Algorithm. Proceedings of the Fifth International Conference on Information Technology: New Generations (ITNG), Las Vegas, NV, USA.","DOI":"10.1109\/ITNG.2008.44"},{"key":"ref_17","unstructured":"Koval, A. (2011). Security Systems Based on Gaussian Integers: Analysis of Basic Operations and Time Complexity of Secret Transformations, New Jersey Institute of Technology."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Koval, A. (2016). Algorithm for Gaussian Integer Exponentiation. Information Technology: New Generations, Springer International Publishing.","DOI":"10.1007\/978-3-319-32467-8_93"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Bhargava, K., and Soni, V. (2017, January 1\u20132). A novice cryptosystem based on nth root of Gaussian integers. Proceedings of the 2017 International Conference on Computer, Communications and Electronics (Comptelix), Jaipur, India.","DOI":"10.1109\/COMPTELIX.2017.8003977"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Awad, Y., El-Kassar, A.N., and Kadri, T. (2018, January 25\u201326). Rabin Public-Key Cryptosystem in the Domain of Gaussian Integers. Proceedings of the International Conference on Computer and Applications (ICCA), Beirut, Lebanon.","DOI":"10.1109\/COMAPP.2018.8460338"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Safieh, M., Thiers, J., and Freudenberger, J. (2020, January 26\u201327). Side Channel Attack Resistance of the Elliptic Curve Point Multiplication using Gaussian Integers. Proceedings of the Zooming Innovation in Consumer Technologies Conference (ZINC), Novi Sad, Serbia.","DOI":"10.1109\/ZINC50678.2020.9161769"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Safieh, M., Thiers, J., and Freudenberger, J. (2020). A Compact Coprocessor for the Elliptic Curve Point Multiplication over Gaussian Integers. Electronics, 9.","DOI":"10.3390\/electronics9122050"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1109\/18.272484","article-title":"Codes over Gaussian integers","volume":"40","author":"Huber","year":"1994","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"3042","DOI":"10.1109\/TIT.2007.903126","article-title":"Perfect Codes for Metrics Induced by Circulant Graphs","volume":"53","author":"Martinez","year":"2007","journal-title":"IEEE Trans. Inf. Theory"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Quilles, C., and Palazzo, R. (2010, January 13\u201318). Quasi-Perfect Geometrically Uniform Codes Derived from Graphs over Gaussian Integer Rings. Proceedings of the IEEE International Symposium on Information Theory (ISIT), Austin, TX, USA.","DOI":"10.1109\/ISIT.2010.5513673"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"3114","DOI":"10.1109\/TCOMM.2013.061913.120742","article-title":"New Coding Techniques for Codes over Gaussian Integers","volume":"61","author":"Freudenberger","year":"2013","journal-title":"IEEE Trans. Commun."},{"key":"ref_27","unstructured":"Freudenberger, J., Ghaboussi, F., and Shavgulidze, S. (2013, January 21\u201324). Set Partitioning and Multilevel Coding for Codes Over Gaussian Integer Rings. Proceedings of the 9th International ITG Conference on Systems, Communications and Coding (SCC), Munich, Germany."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Rohweder, D., Freudenberger, J., and Shavgulidze, S. (2018, January 17\u201322). Low-Density Parity-Check Codes over Finite Gaussian Integer Fields. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT), Vail, CO, USA.","DOI":"10.1109\/ISIT.2018.8437456"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Safieh, M., and Freudenberger, J. (2020, January 18\u201322). Montgomery Modular Arithmetic over Gaussian Integers. Proceedings of the 24th International Information Technology Conference (IT), Zabljak, Montenegro.","DOI":"10.1109\/IT48810.2020.9070297"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Kocher, P. (1996, January 18\u201322). Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/3-540-68697-5_9"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Kocher, P., Jaffe, J., and Jun, B. (1999, January 15\u201319). Differential Power Analysis. Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/3-540-48405-1_25"},{"key":"ref_32","unstructured":"Hankerson, D., Menezes, A.J., and Vanstone, S. (2003). Guide to Elliptic Curve Cryptography, Springer."},{"key":"ref_33","doi-asserted-by":"crossref","unstructured":"Desmedt, Y.G. (2002). A Refined Power-Analysis Attack on Elliptic Curve Cryptosystems. Public Key Cryptography\u2014PKC 2003, Springer.","DOI":"10.1007\/3-540-36288-6"},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Boyd, C., and Mao, W. (2003). Zero-Value Point Attacks on Elliptic Curve Cryptosystem. Information Security, Springer.","DOI":"10.1007\/b13828"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1016\/j.compeleceng.2007.05.009","article-title":"Differential power and electromagnetic attacks on a FPGA implementation of elliptic curve cryptosystems","volume":"33","author":"Mulder","year":"2007","journal-title":"Comput. Electr. Eng."},{"key":"ref_36","unstructured":"Lerman, L., Bontempi, G., and Markowitch, O. (2011, January 14). Side channel attack: An approach based on machine learning. Proceedings of the Proc. 2nd International Workshop on Constructive Side-Channel Analysis and Secure Design, Darmstadt, Germany."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Maghrebi, H., Portigliatti, T., and Prouff, E. (2016, January 14\u201318). Breaking cryptographic implementations using deep learning techniques. Proceedings of the International Conference on Security, Privacy, and Applied Cryptography Engineering, Hyderabad, India.","DOI":"10.1007\/978-3-319-49445-6_1"},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Deng, R.H., Bao, F., Pang, H., and Zhou, J. (2005). Countermeasures for Preventing Comb Method Against SCA Attacks. Information Security Practice and Experience, Springer.","DOI":"10.1007\/b107167"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Salman, A., Ferozpuri, A., Homsirikamol, E., Yalla, P., Kaps, J., and Gaj, K. (2017, January 4\u20136). A scalable ECC processor implementation for high-speed and lightweight with side-channel countermeasures. Proceedings of the International Conference on ReConFigurable Computing and FPGAs (ReConFig), Cancun, Mexico.","DOI":"10.1109\/RECONFIG.2017.8279769"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Matutino, P.M., Ara\u00fajo, J., Sousa, L., and Chaves, R. (2017, January 17\u201320). Pipelined FPGA coprocessor for elliptic curve cryptography based on residue number system. Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS), Pythagorion, Greece.","DOI":"10.1109\/SAMOS.2017.8344638"},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Diekert, V., Kufleitner, M., Rosenberger, G., and Hertrampf, U. (2016). Discrete Algebraic Methods: Arithmetic, Cryptography, Automata and Groups, De Gruyter.","DOI":"10.1515\/9783110413335"},{"key":"ref_42","unstructured":"Krisell, M. (2012). Elliptic Curve Digital Signatures in RSA Hardware, Scholar\u2019s Press."},{"key":"ref_43","unstructured":"Jarvinen, K., Tommiska, M., and Skytta, J. (2004, January 6\u20138). A scalable architecture for elliptic curve point multiplication. Proceedings of the IEEE International Conference on Field\u2014Programmable Technology, Brisbane, NSW, Australia."},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Boyd, C., and Gonza\u2019lez Nieto, J.M. (2005). Efficient Representations on Koblitz Curves with Resistance to Side Channel Attacks. Information Security and Privacy, Springer.","DOI":"10.1007\/b137750"},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Preneel, B., and Tavares, S. (2006). SPA Resistant Left-to-Right Integer Recodings. Selected Areas in Cryptography, Springer.","DOI":"10.1007\/11693383"},{"key":"ref_46","first-page":"660","article-title":"Secure and efficient elliptic curve cryptography resists side-channel attacks","volume":"20","author":"Tao","year":"2009","journal-title":"J. Syst. Eng. Electron."},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Liu, S., Yao, H., and Wang, X.A. (2015, January 4\u20136). SPA Resistant Scalar Multiplication Based on Addition and Tripling Indistinguishable on Elliptic Curve Cryptosystem. Proceedings of the 10th International Conference on P2P, Parallel, Grid, Cloud and Internet Computing (3PGCIC), Krakow, Poland.","DOI":"10.1109\/3PGCIC.2015.20"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Gallant, R., Lambert, R., and Vanstone, S. (2001). Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms. Advances in Cryptology\u2014CRYPTO 2001, Springer.","DOI":"10.1007\/3-540-44647-8_11"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Thiers, J.P., Safieh, M., and Freudenberger, J. (2020, January 9\u201313). Side Channel Attack Resistance of the Elliptic Curve Point Multiplication using Eisenstein Integers. Proceedings of the IEEE 10th International Conference on Consumer Electronics (ICCE), Berlin, Germany.","DOI":"10.1109\/ICCE-Berlin50680.2020.9352202"}],"container-title":["Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2410-387X\/5\/1\/6\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:18:22Z","timestamp":1760159902000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2410-387X\/5\/1\/6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,1]]},"references-count":49,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2021,3]]}},"alternative-id":["cryptography5010006"],"URL":"https:\/\/doi.org\/10.3390\/cryptography5010006","relation":{},"ISSN":["2410-387X"],"issn-type":[{"type":"electronic","value":"2410-387X"}],"subject":[],"published":{"date-parts":[[2021,2,1]]}}}