Towards High-Performance FPGA Implementation of ECDSA for Koblitz Curve: An Instruction-Set Approach
Received: 19 March 2025 | Revised: 5 April 2025 | Accepted: 23 April 2025 | Online: 31 May 2025
Corresponding author: Linh Tran
Abstract
This paper presents a novel instruction-set-based hardware implementation of the Elliptic Curve Digital Signature Algorithm (ECDSA) for a 256-bit Koblitz curve on FPGA. The research contribution under consideration utilizes the integration of Koggle-Stone Adders (KSAs) into the modified structure of modular multiplication and inversion units, thereby enabling high-speed performance in modular computation architecture. Furthermore, by employing an instruction-set-based approach for the control unit instead of the conventional finite state machine for the implementations of ECDSA and point multiplications, we can complete a scalar multiplication operation in less than 2 ms. Our design achieved 110.44 MHz in clock speed on Xilinx Artix-7, occupying 6.4K slices in resource utilization. The modified algorithms employed are constant time, thereby preventing timing attacks. The design is efficient in terms of speed, area, and throughput.
Keywords:
elliptic curve digital signature algorithm, Koblitz curve, koggle-stone adders, instruction-set approachDownloads
References
N. Koblitz, "Elliptic curve cryptosystems," Mathematics of Computation, vol. 48, no. 177, pp. 203–209, 1987.
V. S. Miller, "Use of Elliptic Curves in Cryptography," in Advances in Cryptology — CRYPTO ’85 Proceedings, Santa Barbara, CA, USA, 1985, pp. 417–426.
H. C. A. Tilborg and S. Jajodia, Encyclopedia of Cryptography and Security, 2nd ed. New York, NY, USA: Springer, 2011.
A. J. Menezes, S. A. Vanstone, and P. C. V. Oorschot, Handbook of Applied Cryptography, 1st ed. Boca Raton, FL, USA: CRC Press, Inc., 1996.
S. Mangard, E. Oswald, and T. Popp, Power Analysis Attacks: Revealing the Secrets of Smart Cards, 1st ed. New York, NY, USA: Springer, 2007.
L. Breveglieri, I. Koren, D. Naccache, and J.-P. Seifert, Eds., Fault Diagnosis and Tolerance in Cryptography: Third International Workshop, FDTC 2006, Yokohama, Japan, October 10, 2006. Proceedings, 1st ed. Berlin, Heidelberg, Germany: Springer, 2006.
K. Jarvinen and J. Skytta, "On Parallelization of High-Speed Processors for Elliptic Curve Cryptography," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 16, no. 9, pp. 1162–1175, Sep. 2008.
H. M. Choi, C. P. Hong, and C. H. Kim, "High Performance Elliptic Curve Cryptographic Processor Over GF(2^163)," in 4th IEEE International Symposium on Electronic Design, Test and Applications (delta 2008), Hong Kong, China, 2008, pp. 290–295.
B. Yang, K. Wu, and R. Karri, "Scan based side channel attack on dedicated hardware implementations of Data Encryption Standard," in 2004 International Conferce on Test, Charlotte, NC, USA, 2004, pp. 339–344.
R. Azarderakhsh, K. U. Järvinen, and M. Mozaffari-Kermani, "Efficient algorithm and architecture for elliptic curve cryptography for extremely constrained secure applications," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, no. 4, pp. 1144–1155, Apr. 2014.
T. Oliveira, J. López, and F. Rodríguez-Henríquez, "Software Implementation of Koblitz Curves over Quadratic Fields," in 18th International Conference on Cryptographic Hardware and Embedded Systems, Santa Barbara, CA, USA, 2016, pp. 259–279.
J. Fan, X. Guo, E. De Mulder, P. Schaumont, B. Preneel, and I. Verbauwhede, "State-of-the-art of secure ECC implementations: a survey on known side-channel attacks and countermeasures," in 2010 IEEE International Symposium on Hardware-Oriented Security and Trust, Anaheim, CA, USA, 2010, pp. 76–87.
A. Verri Lucca, G. A. Mariano Sborz, V. R. Q. Leithardt, M. Beko, C. Albenes Zeferino, and W. D. Parreira, "A Review of Techniques for Implementing Elliptic Curve Point Multiplication on Hardware," Journal of Sensor and Actuator Networks, vol. 10, no. 1, Mar. 2021, Art. no. 3.
E. S. I. Harba, "Secure Data Encryption Through a Combination of AES, RSA and HMAC," Engineering, Technology & Applied Science Research, vol. 7, no. 4, pp. 1781–1785, Aug. 2017.
Md. M. Islam, Md. S. Hossain, Moh. K. Hasan, Md. Shahjalal, and Y. M. Jang, "FPGA Implementation of High-Speed Area-Efficient Processor for Elliptic Curve Point Multiplication Over Prime Field," IEEE Access, vol. 7, pp. 178811–178826, 2019.
B. K. Do-Nguyen, C. Pham-Quoc, N.-T. Tran, C.-K. Pham, and T.-T. Hoang, "Multi-Functional Resource-Constrained Elliptic Curve Cryptographic Processor," IEEE Access, vol. 11, pp. 4879–4894, 2023.
X. Hu, X. Zheng, S. Zhang, S. Cai, and X. Xiong, "A Low Hardware Consumption Elliptic Curve Cryptographic Architecture over GF(p) in Embedded Application," Electronics, vol. 7, no. 7, Jul. 2018, Art. no. 104.
Y. Hao et al., "Lightweight Architecture for Elliptic Curve Scalar Multiplication over Prime Field," Electronics, vol. 11, no. 14, Jul. 2022, Art. no. 2234.
M. A. Javed, E. Ben Hamida, and W. Znaidi, "Security in Intelligent Transport Systems for Smart Cities: From Theory to Practice," Sensors, vol. 16, no. 6, Jun. 2016, Art. no. 879.
T. Kudithi and S. R, "An efficient hardware implementation of the elliptic curve cryptographic processor over prime field," International Journal of Circuit Theory and Applications, vol. 48, no. 8, pp. 1256–1273, Mar. 2020.
T. Kudithi and J. A. Solinas, "Generalized Mersenne Numbers," Center for Applied Cryptographic Research, University of Waterloo, Technical report CORR-99-39, 1999. [Online]. Available: https://cacr.uwaterloo.ca/techreports/1999/corr99-39.pdf.
P. L. Montgomery, "Speeding the Pollard and elliptic curve methods of factorization," Mathematics of Computation, vol. 48, no. 177, pp. 243–264, 1987.
H. Xiao, S. Yu, B. Cheng, and G. Liu, "FPGA-based high-throughput Montgomery modular multipliers for RSA cryptosystems," IEICE Electronics Express, vol. 19, no. 9, pp. 20220101–20220101, 2022.
E. Savaş and Ç. K. Koç, "Montgomery inversion," Journal of Cryptographic Engineering, vol. 8, no. 3, pp. 201–210, Sep. 2018.
M. Rogawski, E. Homsirikamol, and K. Gaj, "A novel modular adder for one thousand bits and more using fast carry chains of modern FPGAs," in 2014 24th International Conference on Field Programmable Logic and Applications (FPL), Munich, Germany, 2014, pp. 1–8.
Downloads
How to Cite
License
Copyright (c) 2025 Phu Nguyen, Hung Nguyen, Kim Anh Phan Vo, Linh Tran
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain the copyright and grant the journal the 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) after its publication in ETASR with an acknowledgement of its initial publication in this journal.
