СТВОРЕННЯ АЛГОРИТМІВ ПРИВЕДЕННЯ ПО ФІКСОВАНИМ МОДУЛЯМ ДЛЯ КРИПТОСИСТЕМ, ЩО ВИКОРИСТОВУЮТЬ АРИФМЕТИКУ РОЗШИРЕНИХ ДВІЙКОВИХ ПОЛІВ
DOI:
https://doi.org/10.35546/kntu2078-4481.2025.4.2.14Ключові слова:
алгоритми приведення за модулем, арифметика розширених двійкових полів, приведення за фіксованими модулями, оптимізація алгоритмів, криптоалгоритми.Анотація
Низка діючих вітчизняних стандартів, зокрема цифрового підпису [1] та блокового симетричного шифрування [2], використовує арифметику розширених двійкових полів GF(2m) на основі поліноміального базису для криптографічних перетворень. Для високого рівня стійкості криптографічні стандарти рекомендують великі значення m для поля GF(2m). Зокрема, стандарт [1] визначає 60 варіантів незвідних поліномів f(t) з простими степенями m від 163 до 509. А стандарт [2] використовує 3 варіанти незвідних поліномів f(t) для парних значень m, визначених бітовими розмірами блоку шифру (128, 256 чи 512). При великих m операції в полі GF(2m) мають високу обчислювальну складність. Одним із ключових обмежувальних факторів швидкодії є операція приведення по модулю f(t) (редукція), і зменшення її складності є критично важливим для реалізацій у режимі реального часу. Загальні методи модулярної редукції не завжди враховують особливості оптимізації для конкретного незвід- ного модуля f(t) m-го степеню (триному чи пентаному). Розробка алгоритмів редукції, оптимізованих саме з прив’язкою до рекомендованих стандартами фіксованих значень f(t), може зменшувати обчислювальну склад- ність, в тому числі й при апаратній реалізації. Зменшення складності досягається завдяки незмінності модуля f(t) протягом сеансу, що дозволяє інтегрувати попередні розрахунки безпосередньо в структуру алгоритмів приведення по модулю. Стаття присвячена створенню та дослідженню множин алгоритмів приведення по фіксованим модулям f(t) з метою оптимізації базових операцій у криптосистемах, що використовують GF(2m). Розглянуто методику створення подібних алгоритмів, яка дозволяє формалізувати та частково автоматизувати їх створення. Можливість програмної автоматизації цього процесу є важливою, оскільки стандарти рекомендують велику кількість варіантів полів GF(2m). Також вона необхідна для забезпечення формалізованого підходу до перевірки коректності та тестування цих реалізацій. Результатом роботи є розробка серії оптимізованих алгоритмів приведення по модулю, прив’язаних до модулів, які рекомендовані українськими криптографічними стандартами.
Посилання
ДСТУ 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.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
