Software Implementation of Modular Reduction by Pseudo-mersenne Primes
Автор: Mariia Kovtun, Vladyslav Kovtun, Oleksandr Stokipnyi, Andrew Okhrimenko
Журнал: International Journal of Information Technology and Computer Science @ijitcs
Статья в выпуске: 4 Vol. 15, 2023 года.
Бесплатный доступ
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.
Pseudo-mersenne Prime, Modular Reduction, Multiplication, Barrett Reduction, Electronic Signature, MAC, Finite Field, TLS
Короткий адрес: https://sciup.org/15018939
IDR: 15018939 | DOI: 10.5815/ijitcs.2023.04.01
Список литературы Software Implementation of Modular Reduction by Pseudo-mersenne Primes
- Elie Saad and Rick Mitchell, "OWASP Web Security Testing Guide", OWASP Foundation, 2021. [Online]. Available: https://owasp.org/www-project-web-security-testing-guide/
- The Transport Layer Security (TLS) Protocol Version 1.3, RFC 8446, E. Rescorla, August 2018. [Online]. Available: https://www.rfc-editor.org/info/rfc8446.
- 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
- Edwards-Curve Digital Signature Algorithm (EdDSA), RFC8032, S. Josefsson, I. Liusvaara, January 2017. [Online]. Available: https://tools.ietf.org/html/rfc8032
- Information technologies. Protection methods. Cryptographic methods based on elliptic curves. Generation of elliptic curves, DSTU ISO/IEC 15946-3:2019, August 2019.
- Elliptic Curves for Security, RFC7748, A. Langley, M. Hamburg, S. Turner, January 2016. [Online]. Available: https://tools.ietf.org/html/rfc7748.
- Information technologies. Cryptographic protection information. Short message encryption algorithm based on Edwards twisted elliptic curves, DSTU 9041:2020.
- ChaCha20 and Poly1305 for IETF Protocols, RFC8439, Y. Nir, A. Langley, June 2018. [Online]. Available: https://tools.ietf.org/html/rfc8439.
- 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.
- 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.
- 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.
- 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.
- 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
- H. Wu, “On Modular Reduction,” July 2000. [Online]. Available: https://cacr.uwaterloo.ca/techreports/2000/tech_reports2000.html
- 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
- 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
- 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
- SEC 2: Recommended Elliptic Curve Domain Parameters, SEC2, January 2010. [Online]. Available: https://www.secg.org/sec2-v2.pdf
