Fast Exponentiation in Galois Fields GF(2n)
DOI:
https://doi.org/10.47839/ijc.24.1.3879Keywords:
multiplication operation on Galois fields, cryptographic algorithms based on Galois Fields algebra, Galois Fields exponentiation, Montgomery reduction, precomputationAbstract
Algebraic operations in Galois fields present properties that render them suitable for use in implementations of cryptographic primitives. Two fundamental operations of interest are modulo squaring and multiplication, whose implementations can be accelerated by using Galois field algebra. An approach is proposed for the acceleration of the calculation of modulo exponentiation in Galois fields, an operation that is fundamental for a wide spectrum of cryptographic algorithms. The approach is based on two developed procedures, namely fast exponentiation to the square and multiplication with a constant number in Galois fields. The proposed innovative accelerated calculation is attained via the use of the properties of the second order polynomial, the Montgomery group reduction and the derivation of pre-calculated tabular results. The mathematical foundation of the proposed method is given, followed by numerical examples that illustrate its operation. The amount of memory required is also calculated. It has been proved, both theoretically and experimentally that the proposed approach renders possible the acceleration of exponentiation in Galois fields by 5 to 7 times, in comparison with known methods.
References
U. Jetzek, Galois Fields, Linear Feedback Shift Registers and Their Applications. Carl Hanser Verlag GmbH Co KG, 2018. https://doi.org/10.1007/978-3-446-45613-6
D. Canright, "A very compact S-box for AES," In Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems, pp. 441-455. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005. https://doi.org/10.1007/11545262_32
J. Daemen, V. Rijmen, "The advanced encryption standard process," The Design of Rijndael: AES—The Advanced Encryption Standard (2002): 1-8. https://doi.org/10.1007/978-3-662-04722-4_1
Y. N. Shivani, A. Srinivas, B. K. Thanmayi, V. Vignesh, and B. V. Srividya, "EdDSA over Galois Field GF (p^m) for Multimedia Data," Journal of Engineering Research and Reports, vol. 4, no. 4, pp. 1-7, 2019. https://doi.org/10.9734/jerr/2019/v4i416911
J. Luo, K. D. Bowers, A. Oprea, and L. Xu, "Efficient software implementations of large finite fields GF (2 n) for secure storage applications," ACM Transactions on Storage (TOS), vol. 8, no. 1, pp. 1-27, 2012. https://doi.org/10.1145/2093139.2093141
Nikolaos G. Bardis, O. P. Markovskyi, and N. Doukas, "A method for strict remote user identification using non-reversible Galois field transformations," In MATEC Web of Conferences, vol. 125, p. 05017, 2017. https://doi.org/10.1051/matecconf/201712505017
Nikolaos G. Bardis, O. P. Markovskyi, N. Doukas, and A. Drigas, "Fast implementation zero knowledge identification schemes using the Galois Fields arithmetic," In Proceedings of the 2012 IX IEEE International Symposium on Telecommunications (BIHTEL), 2012, pp. 1-6. https://doi.org/10.1109/BIHTEL.2012.6412094
J.-L. Danger, Y. El Housni, A. Facon, C. T. Gueye, S. Guilley, S. Herbel, O. Ndiaye, E. Persichetti, and A. Schaub, "On the performance and security of multiplication in GF (2 N)," Cryptography, vol. 2, no. 3, 25, 2018. https://doi.org/10.3390/cryptography2030025
A. Ibrahim, and F. Gebali, "Low power semi-systolic architectures for polynomial-basis multiplication over GF (2m) using progressive multiplier reduction," Journal of Signal Processing Systems, 82, pp. 331-343, 2016. https://doi.org/10.1007/s11265-015-1000-x
A. A. Moustafa, "Fast exponentiation in Galois Fields GF (2 m) using precomputations," Contemporary Engineering Sciences, vol. 7, no. 4, pp. 193-206, 2014. https://doi.org/10.12988/ces.2014.3955
I. Dychka, M. Onai, A. Severin, C. Hu, "Method of performing operations on the elements of GF(2m) using a sparse table," International Journal of Computer Network and Information Security (IJCNIS), vol. 16, no. 1, pp. 61-72, 2024. https://doi.org/ 10.5815/ijcnis.2024.01.05
S. Gao, D. Panario, and V. Shoup, "Algorithms for exponentiation in finite fields," Journal of Symbolic Computation, vol. 29, no. 6, pp. 879-889, 2000. https://doi.org/10.1006/jsco.1999.0309
D. Ihor, and S. Viktor, "Fast exponential method on Galois fields for cryptographic applications," In Proceedings of the 2023 13th IEEE International Conference on Dependable Systems, Services and Technologies (DESSERT), 2023, pp. 1-4. https://doi.org/10.1109/DESSERT61349.2023.10416519.
E. M. Popovici, and P. Fitzpatrick, "Algorithm and architecture for a Galois field multiplicative arithmetic processor," IEEE Transactions on Information Theory, vol. 49, no. 12, pp. 3303-3307, 2003. https://doi.org/10.1109/TIT.2003.820026
M. Zholubak, V. S. Hlukhov, "Galua Field multipliers core generator," International Journal of Computer Network and Information Security (IJCNIS), vol. 15, no. 3, pp. 1-14, 2023. https://doi.org/10.5815/ijcnis.2023.03.01
C. K. Koc, and T. Acar, "Montgomery multiplication in GF (2k)," Designs, Codes and Cryptography, vol. 14, pp. 57-69, 1998. https://doi.org/10.1023/A:1008208521515
G. Hachez, and J.-J. Quisquater, "Montgomery exponentiation with no final subtractions: Improved results," In Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems CHES 2000, Worcester, MA, USA, August 17–18, 2000, pp. 293-301. Springer Berlin Heidelberg, 2000. https://doi.org/10.1007/3-540-44499-8_23
R. Skuratovskii, and V. Osadchyy, "The order of Edwards and Montgomery curves," WSEAS Transactions on Mathematics, vol. 19, pp. 253-264, 2020. https://doi.org/10.37394/23206.2020.19.25
H. Wu, M. Anwarul Hasan, I. F. Blake, and S. Gao, "Finite field multiplier using redundant representation," IEEE Transactions on Computers, vol. 51, no. 11, pp. 1306-1316, 2002. https://doi.org/10.1109/TC.2002.1047755
T. John, S. Haider, H. Omar, & M. van Dijk, “Connecting the dots: privacy leakage via write-access patterns to the main memory,” IEEE Transactions on Dependable and Secure Computing, vol. 17, issue 2, pp. 436-442, 2020. https://doi.org/10.1109/tdsc.2017.2779780
S. Vollala, K. Geetha, & N. Ramasubramanian, “Efficient modular exponential algorithms compatible with hardware implementation of public‐key cryptography,” Security and Communication Networks, vol. 9, issue 16, pp. 3105-3115, 2016. https://doi.org/10.1002/sec.1511
T. Wu, “High-performance RNS modular exponentiation by sum-residue reduction,” IEEE Canadian Journal of Electrical and Computer Engineering, vol. 46, issue 2, pp. 137-143, 2023. https://doi.org/10.1109/icjece.2023.3243888
V. Yatskiv, N. Yatskiv, Su Jun, A. Sachenko, and Hu Zhengbing, "The use of modified correction code based on residue number system in WSN," In Proceedings of the 2013 IEEE 7th International Conference on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS), vol. 1, pp. 513-516, 2013. https://doi.org/10.1109/IDAACS.2013.6662738
J. Chen, V. Yatskiv, A. Sachenko, and J. Su, "Wireless sensor networks based on modular arithmetic," Radioelectronics and Communications Systems, vol. 60, pp. 215-224, 2017. https://doi.org/10.3103/S073527271705003X
M. Iavich, T. Kuchukhidze, G. Iashvili, and S. Gnatyuk, "Hybrid quantum random number generator for cryptographic algorithms," Radioelectronic and Computer Systems, no. 4, pp. 103-118, 2021. doi: https://doi.org/10.32620/reks.2021.4.09.
V. Avramenko, and V. Demianenko, "Serial encryption using the functions of real variable," Radioelectronic and Computer Systems, no. 2, pp. 39-50, 2021. https://doi.org/10.32620/reks.2021.2.04.
T. Wu, S. Li, & L. Liu, “Fast, compact and symmetric modular exponentiation architecture by common-multiplicand Montgomery modular multiplications,” Integration, vol. 46, issue 4, pp. 323-332, 2013. https://doi.org/10.1016/j.vlsi.2012.09.002
B. Zhang, Z. Cheng and M. Pedram, "Design of a high-performance iterative Barrett modular multiplier for crypto systems," in IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 32, no. 5, pp. 897-910, May 2024, https://doi.org/10.1109/TVLSI.2024.3368002
L. Didier, A. Mrabet, P. Glandus, and Y. Robert, "Truncated multiplication and batch AVX512 implementation for faster Montgomery multiplications and exponentiation," arXiv preprint arXiv:2410.18129, 2024. https://arxiv.org/abs/2410.18129
O. Prots’ko, and V. Gryshchuk, "Implementing Montgomery multiplication to speed-up modular exponentiation of multi-bit numbers," CEUR Workshop Proceedings, vol. 3702, 2024, pp. 228–235. https://ceur-ws.org/Vol-3702/paper23.pdf
V. Attias, L. Vigneri, and V. S. Dimitrov, "Rethinking modular multi-exponentiation in real-world applications," IACR Cryptology ePrint Archive, vol. 2022, 263, 2022. https://eprint.iacr.org/2022/263
H. Böck, "Exponent-blinded RSA-CRT with sliding window – side-channel analysis," In Proceedings of the 32nd USENIX Security Symposium, 2023, pp. 951–967. https://www.usenix.org/conference/usenixsecurity23/presentation/boeck
T. Wu, X. Wu, C. Chang, and J. Zhang, "High-performance RNS modular exponentiation by sum-residue reduction," Integration, vol. 90, pp. 43–51, 2023. https://doi.org/10.1016/j.vlsi.2022.12.003
S. Ahsan, M. U. Wahab, S. A. Qazi, and A. A. Khan, "Efficient FPGA implementation of RNS Montgomery multiplication using balanced RNS bases," Journal of Circuits, Systems and Computers, vol. 31, no. 12, 2250208, 2022. https://doi.org/10.1142/S0218126622502080
C. Buhrow, S. Nejad, and R. Rivest, "Block product scanning: Parallel modular multiplication using 512-bit AVX-512 instructions," In Proc. of the 30th USENIX Security Symposium (2022): 163–180. https://www.usenix.org/conference/usenixsecurity22/presentation/buhrow
M. F. Esgin, A. K. Kocabas, and M. S. Siddiqui, "ASIC-friendly VDF evaluation: Efficient modular exponentiation architectures for verifiable delay functions," IEEE Transactions on Computers, vol. 72, no. 4, pp. 961–974, 2023. https://doi.org/10.1109/TC.2023.3249126
M. Rath, R. Pathan, and M. S. Khan, "On efficient parallel secure outsourcing of modular exponentiation to cloud for IoT," Concurrency and Computation: Practice and Experience, vol. 36, no. 2, e7709, 2024. https://doi.org/10.1002/cpe.7709
T.-H. Nguyen, C.-K. Pham, and T.-T. Hoang, "A high-efficiency modular multiplication digital signal processing for lattice-based post-quantum cryptography," Cryptography, vol. 7, no. 4, 46, 2023. https://doi.org/10.3390/cryptography7040046.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
