DESIGN OF FIXED MODULI MODULAR REDUCTION ALGORITHMS FOR CRYPTOSYSTEMS THAT USE EXTENDED BINARY FIELD ARITHMETIC
DOI:
https://doi.org/10.35546/kntu2078-4481.2025.4.2.14Keywords:
modular reduction algorithms, extended binary fields arithmetic, reduction with fixed moduli, algorithms optimization, сryptographic algorithms.Abstract
A number of current domestic standards, including the digital signature standard [1] and the block symmetric encryption standard [2], utilize extended binary field arithmetic GF(2m) based on a polynomial basis for cryptographic transformations. To ensure a high level of cryptographic resilience, these standards recommend large values of m for the GF(2m) field. Specifically, standard [1] defines 60 variants of irreducible polynomials f(t) with prime degrees m ranging from 163 to 509, while standard [2] uses 3 variants of irreducible polynomials f(t) for even values of m (128, 256, or 512), corresponding to the cipher's block sizes. Operations within the GF(2m) field incur high computational complexity for large values of m. The operation of modular reduction by f(t) is a key limiting performance factor, and reducing its complexity is critical for real-time implementations. General methods of modular reduction do not always account for the specific optimization properties of a particular irreducible modulus f(t) of degree m (a trinomial or a pentanomial). Developing reduction algorithms optimized specifically for the fixed values of f(t) specified by standards can decrease computational complexity, particularly in hardware implementations. This complexity reduction is achieved because the modulus f(t) remains invariant throughout the session, which enables the integration of pre-calculations directly into the structure of the reduction algorithms. This article focuses on the creation and analysis of sets of algorithms for reduction by fixed moduli f(t), aiming to optimize basic operations in cryptosystems that utilize GF(2m). We consider a method for creating such algorithms that enables their formalization and partial automation. The possibility of software automation is crucial, since standards recommend a large number of GF(2m) field variants. Furthermore, it is also necessary to ensure a formalized approach for verifying the correctness and testing these implementations. The research resulted in the development of a series of optimized modular reduction algorithms tied to the specific moduli recommended by Ukrainian cryptographic standards.
References
ДСТУ 4145-2002. Інформаційні технології. Криптографічний захист інформації. Цифровий підпис, що ґрунтується на еліптичних кривих. Формування та перевіряння: [Чинний від 2003–07–01]. Київ: Держстандарт України, 2002. 35 с. (Національний стандарт України).
ДСТУ 7624:2014. Інформаційні технології. Криптографічний захист інформації. Алгоритм симетричного блокового перетворення: [Чинний від 2015–07–01]. Київ: Мінекономрозвитку України, 2014. 228 с. (Національний стандарт України).
NIST SP 800-38D. Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC. Gaithersburg, MD: National Institute of Standards and Technology (NIST), 2007. 39 p. (NIST Special Publication).
ISO/IEC 19772:2020. Information security – Authenticated encryption. Geneva: ISO/IEC, 2020. 40 p.
NIST SP 800-38E. Recommendation for Block Cipher Modes of Operation: The XTS-AES Mode for Confidentiality on Storage Devices. Gaithersburg, MD: National Institute of Standards and Technology (NIST), 2010. 21 p. (NIST Special Publication).
IEEE Std 1619-2007. Standard for Cryptographic Protection of Data on Block-Accessible Storage Devices. New York: Institute of Electrical and Electronics Engineers, 2008. 48 p. (Reaffirmed 2018).
ДСТУ ISO/IEC 14888-3:2018. Інформаційні технології. Методи захисту. Цифрові підписи з додатком. Частина 3. Механізми на основі дискретного логарифму: [Чинний від 2019–01–01]. Київ: ДП «УкрНДНЦ», 2018. 114 с. (Національний стандарт України).
ANSI X9.62-2005. Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA). Washington, D.C.: ANSI, 2005. 50 p. (Reaffirmed 2011).
FIPS 186-4. Digital Signature Standard (DSS). Gaithersburg, MD: National Institute of Standards and Technology (NIST), 2013. 98 p. (U.S. Department of Commerce).
IEEE 1363a-2004. Standard Specifications for Public-Key Cryptography – Amendment 1: Additional Public-Key Techniques. New York: Institute of Electrical and Electronics Engineers, 2004. 70 p. (Amendment to IEEE 1363-2000).
NIST SP 800-56A Rev. 3. Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography. Gaithersburg, MD: National Institute of Standards and Technology (NIST), 2018. 143 p. (NIST Special Publication).
ANSI X9.63-2011. Public Key Cryptography for the Financial Services Industry: Key Establishment Techniques. Washington, D.C.: ANSI, 2011. 82 p. (Reaffirmed 2016).
ISO/IEC 18033-2:2006. Information technology – Security techniques – Encryption algorithms – Part 2: Asymmetric ciphers. Geneva: ISO/IEC, 2006. 138 p.
ДСТУ ISO/IEC 15946-1:2017. Інформаційні технології. Методи захисту. Криптографічні методи, що ґрунтуються на еліптичних кривих. Частина 1. Загальні положення: [Чинний від 2017–12–18]. Київ: УкрНДНЦ, 2017. 42 с. (Національний стандарт України).
Hankerson D.R., Menezes A.J., Vanstone S.A. Guide to Elliptic Curve Cryptography. New York, NY: Springer-Verlag, 2004. 320 p.
Cohen H., Frey G., Bailey D. H. та ін. Handbook of Elliptic and Hyperelliptic Curve Cryptography. Boca Raton: Chapman and Hall/CRC, 2006. 824 p.
Washington L. C. Elliptic Curves: Number Theory and Cryptography. Boca Raton, FL: Chapman and Hall/CRC, 2008. 536 p.
Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. Boca Raton, FL: CRC Press, 1996. 816 p.
Hankerson D., López J. H., Menezes A. J. Software implementation of the NIST elliptic curves over binary fields. В Selected Areas in Cryptography: International Workshop (SAC 2000). Berlin; Heidelberg: Springer, 2001. P. 1–19. (Lecture Notes in Computer Science ; Vol. 2012).
Hasan S. M. A., Bandara M. L. S. D. K. S., Al-Amin S. M. K. та ін. An Efficient and Lightweight Architecture for Modular Reduction in GF(2m) based on Hybrid Polynomial Representation. IEEE Access. 2024. Vol. 12. P. 49302–49313.
Ghouma S. A., Al-Sarayrah F. S., Al-Shurman O. A. M. High-Performance Polynomial Basis Multiplier for GF(2m) using Karatsuba-like Algorithm. IEEE Access. 2023. Vol. 11. P. 11054–11065.
Chowdhury M. M. I., Hasan M. A. Efficient hardware implementation of extended Euclidean algorithm for GF(2m) on FPGA. Microprocessors and Microsystems. 2023. Vol. 101. 104889.
Islam M. S., Hwang Y. S. High-performance and efficient finite field arithmetic for cryptographic applications. Journal of Circuits, Systems and Computers. 2022. Vol. 31, Issue 4. 2250064 (16 p.).
Hasan M. A., Lwin T. K., Tso K. S. Efficient Implementation of Binary Field Multipliers using Modified Karatsuba Algorithm. IEEE Access. 2021. Vol. 9. P. 110903–110915.
Certik J., Hankerson D., Menezes A. High-speed software implementation of the NIST recommended elliptic curves over GF(2m). IEEE Transactions on Computers. 2003. Vol. 52, Issue 8. P. 1060–1070.
