Mariia Kovtun; Vladyslav Kovtun; Oleksandr Stokipnyi; Andrew Okhrimenko

Software Implementation of Modular Reduction by Pseudo-mersenne Primes

Full Text (PDF, 584KB), PP.1-9

Views: 0 Downloads: 0

Author(s)

Mariia Kovtun ^1,* Vladyslav Kovtun ² Oleksandr Stokipnyi ² Andrew Okhrimenko ³

1. Department of Computer Engineering, National Aviation University, 1, Liubomyra Huzara ave., Kyiv, 03058, Ukraine

2. Cipher Company, 25/27, Nahirna Str., Kyiv, 04107, Ukraine

3. Department of System Analysis and Information Technology, Mariupol State University, 6/4, Preobrazhenska Str., Kyiv, 03037, Ukraine

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2023.04.01

Received: 20 Mar. 2023 / Revised: 3 May 2023 / Accepted: 11 Jun. 2023 / Published: 8 Aug. 2023

Index Terms

Pseudo-mersenne Prime, Modular Reduction, Multiplication, Barrett Reduction, Electronic Signature, MAC, Finite Field, TLS

Abstract

Modern cryptosystems allow the use of operation in prime fields with special kind of modules that can speed up the prime field operation: multiplication, squaring, exponentiation. The authors took into account in the optimizations: the CPU architecture and the multiplicity of the degree of the modulus in relation to the machine word width. As example, shown adopted module reduction algorithms hard-coded for modern CPU in special form of pseudo-Mersenne prime used in MAC algorithm Poly1305, - in electronic signature algorithm EdDSA and - in short message encryption algorithm DSTU 9041. These algorithms have been software implemented on both 32-bit and 64-bit platforms and compared with Barrett modular reduction algorithm for different pseudo-Mersenne and generalized-Mersenne modules. Timings for proposed and Barrett algorithms for different modules are presented and discussed.

Cite This Paper

Mariia Kovtun, Vladyslav Kovtun, Oleksandr Stokipnyi, Andrew Okhrimenko, "Software Implementation of Modular Reduction by Pseudo-mersenne Primes", International Journal of Information Technology and Computer Science(IJITCS), Vol.15, No.4, pp.1-9, 2023. DOI:10.5815/ijitcs.2023.04.01

Reference

[1]Elie Saad and Rick Mitchell, "OWASP Web Security Testing Guide", OWASP Foundation, 2021. [Online]. Available: https://owasp.org/www-project-web-security-testing-guide/
[2]The Transport Layer Security (TLS) Protocol Version 1.3, RFC 8446, E. Rescorla, August 2018. [Online]. Available: https://www.rfc-editor.org/info/rfc8446.
[3]Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA), RFC 6979, T. Pornin, August 2013. [Online]. Available: https://www.rfc-editor.org/info/rfc6979
[4]Edwards-Curve Digital Signature Algorithm (EdDSA), RFC8032, S. Josefsson, I. Liusvaara, January 2017. [Online]. Available: https://tools.ietf.org/html/rfc8032
[5]Information technologies. Protection methods. Cryptographic methods based on elliptic curves. Generation of elliptic curves, DSTU ISO/IEC 15946-3:2019, August 2019.
[6]Elliptic Curves for Security, RFC7748, A. Langley, M. Hamburg, S. Turner, January 2016. [Online]. Available: https://tools.ietf.org/html/rfc7748.
[7]Information technologies. Cryptographic protection information. Short message encryption algorithm based on Edwards twisted elliptic curves, DSTU 9041:2020.
[8]ChaCha20 and Poly1305 for IETF Protocols, RFC8439, Y. Nir, A. Langley, June 2018. [Online]. Available: https://tools.ietf.org/html/rfc8439.
[9]P.D. Barrett, “Implementing the Riveat ShaInir and Adleman public key encryp tion algorithm on a standard digital signal processor,” Advances in Cryptology, Proc. Crypto’86, LNCS 263, A.M. Odlyzko, Ed., Springer-Verlag, 1987, pp. 311- 323.
[10]C. D. Walter, “Hardware Aspects of Montgomery Modular Multiplication,” in Topics in Computational Number Theory Inspired by Peter L. Montgomery, J. W. Bos and A. K. Lenstra, Eds. Cambridge: Cambridge University Press, 2017, pp. 40–81.
[11]A. Okhrimenko, V. Kovtun, “Method for Improving the Performance of a Prime Modulo Cast Operation,” in Information systems in management, education, industry, Kharkiv, Ukraine, 2014, pp. 204–220.
[12]W. Hasenplaugh, G. Gaubatz and V. Gopal, “Fast Modular Reduction,” 18th IEEE Symposium on Computer Arithmetic (ARITH '07), Montpellier, France, 2007, pp. 225-229, doi: 10.1109/ARITH.2007.18.
[13]J.A. Solinas, “Generalized Mersenne numbers,” Technical Report CORR 99-39, University of Waterloo, 1999. [Online]. Available: https://www.researchgate.net/publication/238426205_Generalized_Mersenne_Prime
[14]H. Wu, “On Modular Reduction,” July 2000. [Online]. Available: https://cacr.uwaterloo.ca/techreports/2000/tech_reports2000.html
[15]M. Taschwer, “Modular Multiplication Using Special Prime Moduli,” in: Horster, P. (eds) Kommunikationssicherheit im Zeichen des Internet. DuD-Fachbeiträge. Vieweg+Teubner Verlag. https://doi.org/10.1007/978-3-322-89557-8_30
[16]J. C. Bajard, S. Duquesne, “Montgomery-friendly primes and applications to cryptography,” in Journal of Cryptographic Engineering, 11(4), 399–415. https://doi.org/10.1007/s13389-021-00260-z
[17]Digital Signature Standard (DSS), NIST FIPS-186-4, National Institute of Standards and Technology, July 2013. [Online]. Available: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf
[18]SEC 2: Recommended Elliptic Curve Domain Parameters, SEC2, January 2010. [Online]. Available: https://www.secg.org/sec2-v2.pdf

International Journal of Information Technology and Computer Science (IJITCS)