AN APPLICATION OF RESIDUE NUMBER SYSTEM ARITHMETICS TO SECURE HASH FUNCTIONS DESIGN

Milija Pavlović; Stefan Panić; Boris Damjanović; Negovan Stamenković

doi:10.5937/bnsr15-58114

Milija Pavlović Faculty of Sciences and Mathematics, University of Priština in Kosovska Mitrovica, Kosovska Mitrovica, Serbia https://orcid.org/0009-0007-3519-2689
Stefan Panić Faculty of Sciences and Mathematics, University of Priština in Kosovska Mitrovica, Kosovska Mitrovica, Serbia https://orcid.org/0000-0002-5868-1764
Boris Damjanović Faculty of Information Technologies and Engineering, Union- Nikola Tesla University, Belgrade, Serbia https://orcid.org/0000-0003-4774-5774
Negovan Stamenković Faculty of Sciences and Mathematics, University of Priština in Kosovska Mitrovica, Kosovska Mitrovica, Serbia https://orcid.org/0000-0003-4025-5342

DOI: https://doi.org/10.5937/bnsr15-58114

Keywords: Cryptographic hash function, Residue number system, Avalanche effect, Diffusion, Entropy, Parallelism, Modular arithmetic

Abstract

This paper presents a cryptographic hash function based on the Residue Number System (RNS), designed to enhance security and computational efficiency. The function leverages the parallelism and modular properties of RNS to achieve high-speed processing while maintaining strong diffusion and resistance to various cryptanalytic attacks. Experimental results confirm that the proposed function exhibits a pronounced Avalanche effect, ensuring that minor changes in the input result in significant alterations in the hash output. Additionally, statistical analysis using the ENT test demonstrates a high level of entropy and uniform distribution of hash values, reinforcing the function’s unpredictability—an essential characteristic for cryptographic security. The proposed hash function is suitable for applications in digital signatures, data integrity verification, and authentication systems, offering advantages in environments requiring high computational efficiency.

References

Ambedkar, B. R. 2025, Enhancing the Performance of Cryptographic Hash Function Using 2080 Bits Proposed Secure HashAlgorithm 160, International Journal of Scientific Researchin Network Security and Communication, 13 (1), pp. 8–11. https://doi.org/10.26438/ijsrnsc.v13i1.264

Ananda Mohan, P. 2016, Residue Number Systems: Theory andApplications

Bajard, J. & Imbert, L. 2004, A full RNS implementation ofRSA, IEEE Transactions on Computers, 53, pp. 769–774. https://doi.org/10.1109/TC.2004.2

Brockwell, P. J. & Davis, R. A. 2002, Introduction to Time Seriesand Forecasting, 2nd edn. (Springer), pp. 15–1.

Cover, T. M. & Thomas, J. A. 1991, Elements of Information Theory, Wiley Series in Telecommunications. https://doi.org/10.1002/047174882X

Cox, D. R. & Hinkley, D. V. 1980, Theoretical Statistics, Chapman& Hall, pp. 34–38. https://doi.org/10.1201/9780203758486

Gandino, F., Lamberti, F., Montuschi, P., & Bajard, J. 2011, inComputer Arithmetic (ARITH), 2011 20th IEEE Symposiumon, pp. 195–204.

Gandino, F., Lamberti, F., Paravati, G., Bajard, J., & Montuschi,P. 2012, An Algorithmic and Architectural Study on Montgomery Exponentiation in RNS, IEEE Transactions on Computers, 61 (8), pp. 1071–1083. https://doi.org/10.1109/TC.2012.84

Isupov, K. 2021, High-Performance Computation in ResidueNumber System Using Floating-Point Arithmetic, Computa-tion, 9 (2), 9. https://doi.org/10.3390/computation9020009

Kalos, M. H. & Whitlock, P. A. 2008, Monte Carlo Methods, 2ndedn. (Wiley-VCH), pp. 3–12, poglavlje o historijskoj primjeniza sa matematičkom analizom.

Köroglu, T. 2025, Hash Functions: Design Paradigms, Security,and Algorithmic Analysis, Advances in Computer Engineering,pp. 109–135. https://doi.org/10.5281/zenodo.14579277

Montgomery, P. 1985, Modular multiplication without trialdivision, Mathematics of Computation, 16, pp. 519–521. https://doi.org/10.1090/S0025-5718-1985-0777282-X

Naseem, M. T., Qureshi, I. M., Cheema, T. A., & ur Rahman, A.2013, Hash based Medical Image Authentication and Recoveryusing Chaos and Residue Number System, Journal of Basic andApplied Scientific Research.

Omondi, A. & Premkumar, B. 2007, Residue Number Systems:Theory and Implementation (London, UK)

Rogaway, P. & Shrimpton, T. 2004, in Lecture Notes in ComputerScience, Vol. 3152, Advances in Cryptology – CRYPTO 2004(Berlin, Heidelberg: Springer), pp. 371–388.

Stamenković, N. 2019, Isomorphic Transformation and Its Application to the Modulo (2n+1) Channel for RNS Based FIR FilterDesign, Bulletin of Natural Sciences Research, 9 (2), pp. 25–32. https://doi.org/10.5937/univtho9-21821

Stevens, M., Bursztein, E., & Karpman, P. e. a. 2017, The FirstCollision for Full SHA-1, Advances in Cryptology – CRYPTO2017.

Szabo, N. & Tanaka, R. 1967, Residue Arithmetic and Its Application to Computer Technology (New York, NY, USA)

Upadhyay, D., Gaikwad, N., Zaman, M., & Sampalli, S.2022, Investigating the Avalanche Effect of Various Cryptographically Secure Hash Functions and Hash-BasedApplications, IEEE Access, 10, pp. 112473–112486. https://doi.org/10.1109/ACCESS.2022.3215778

Walker, J. 2008, ENT: A Pseudorandom Number Sequence TestProgram, Online manual, the original ENT entropy test documentation with statistical foundations.

Wang, Y., Wong, K.-W., Li, C., & Yang, L. 2012, A novelmethod to design S-box based on chaotic map and genetic algorithm, Physics Letters A, 376 (6-7), pp. 827–833. https://doi.org/10.1016/j.physleta.2012.01.009