Published
Design of elliptic curve cryptoprocessors over GF(2^163) using the Gaussian normal basis
Diseño de criptoprocesadores de curva elíptica sobre GF(2^163) usando bases normales Gaussianas
DOI:
https://doi.org/10.15446/ing.investig.v34n2.40542Keywords:
elliptic curve cryptography, Gaussian normal basis, digit-level multiplier, scalar multiplication (en)criptografía de curva elíptica, bases normales Gaussianas, multiplicador a nivel de digito, multiplicación escalar (es)
This paper presents an efficient hardware implementation of cryptoprocessors that perform the scalar multiplication kP over a finite field GF(2163) using two digit-level multipliers. The finite field arithmetic operations were implemented using the Gaussian normal basis (GNB) representation, and the scalar multiplication kP was implemented using the Lopez-Dahab algorithm, the 2-non-adjacent form (2-NAF) halve-and-add algorithm and the w-τNAF method for Koblitz curves. The processors were designed using a VHDL description, synthesized on the Stratix-IV FPGA using Quartus II 12.0 and verified using SignalTAP II and Matlab. The simulation results show that the cryptoprocessors provide a very good performance when performing the scalar multiplication kP. In this case, the computation times of the multiplication kP using the Lopez-Dahab algorithm, 2-NAF halve-and-add algorithm and 16-τNAF method for Koblitz curves were 13.37 µs, 16.90 µs and 5.05 µs, respectively.
En este trabajo se presenta la implementación eficiente en hardware de criptoprocesadores que permiten llevar a cabo la multiplicación escalar kP sobre el campo finito GF(2163) usando dos multiplicadores a nivel de digito. Las operaciones aritméticas de campo finito fueron implementadas usando la representación de bases normales Gaussianas (GNB), y la multiplicación escalar kP fue implementada usando el algoritmo de López-Dahab, el algoritmo de bisección de punto 2-NAF y el método w-τNAF para curvas de Koblitz. Los criptoprocesadores fueron diseñados usando descripción VHDL, sintetizados en el FPGA Stratix-IV usando Quartus II 12.0 y verificados usando SignalTAP II y Matlab. Los resultados de simulación muestran que los criptoprocesadores presentan un muy buen desempeño para llevar a cabo la multiplicación escalar kP. En este caso, los tiempos de computo de la multiplicación kP usando Lopez-Dahab, bisección de punto 2-NAF y 16-τNAF para curvas de Koblitz fueron 13.37 µs, 16.90 µs and 5.05 µs, respectivamente.
References
Amara, M., & Siad, A. (2011). Hardware implementation of arithmetic for elliptic curve cryptosystems over GF(2^m). In World Congress on Internet Security (WorldCIS) (pp. 73-78). London: IEEE.
Azarderakhsh, R., & Masoleh, R. (2010). A Modified Low Complexity Digit-Level Gaussian Normal Basis Multiplier. Arithmetic of Finite Fields (pp. 25-40). Turkey: Springer.
Azarderakhsh, R., & Masoleh, R. (2013). High-performance implementation of point multiplication on Koblitz Curves. IEEE Transactions on Circuits and Systems, 60(1), 41 - 45.
Chester, R., & Mukhopadhyay, D. (2008). Progress in Cryptology - INDOCRYPT 2008. Kharagpur: Springer.
Cui, X.-N., & Yang, J. (2012). An FPGA based processor for Elliptic Curve Cryptography. In International Conference on Computer Science and Information Processing (CSIP) (pp. 343-349). Shaanxi: IEEE.
Ghanmy, N., Khlif, N., Fourati, L., & Kamoun, L. (2012). Hardware implementation of elliptic curve digital signature algorithm ECDSA on Koblitz curves. In International Symposium on Communication Systems, Networks & Digital Signal Processing (CSNDSP) (pp. 1 - 6). Poznan: IEEE.
Hankerson, D., Menezes, A., & Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer.
Huang, T., Chang, C., Chiou, C., & Tan, S. (2011). Non-XOR approach for low-cost bit-parallel polynomial basis multiplier over GF(2^m). Information Security, IET, 5(3) 152-162.
IEEE std 1363. (2000). 1363-2000 IEEE Standard Specifications for Public-Key Cryptography. IEEE Computer Society.
Itoh, T., & Tsujii, S. (1988). A fast algorithm for computing multiplicative inverses in GF(2^m) using normal bases. Information and Computation, 78(3), 171-177.
Jeevananthan, S., & Muthukumar, B. (2010). High speed hardware implementation of an elliptic curve cryptography (ECC) co-processor. In Trendz in Information Sciences & Computing (TISC) (pp. 176-180). Chennai: IEEE.
Johnson, D., Menezes, A., & Vastone, S. (2001). The Elliptic Curve Digital Signature Algorithm (ECDSA). International Journal of Information Security, 1(1), 36-63.
Juhas, T. (2007). The Use of Elliptic Curves in Cryptography. Retrieved from: http://munin.uit.no/bitstream/handle/10037/1091/thesis.pdf?sequence=5
Knudsen, W. (1999). Elliptic Scalar Multiplication Using Point Halving. Advances in Cryptology - ASIACRYPT (pp. 135-149). Berlin: Springer.
Koblitz, N. (1987). Elliptic curve cryptosystems. Mathematics of computation, 48(1987), 203-209.
Lai, J.-Y., Hung, T.-Y., Yang, K.-H., & Huang, C.-T. (2010). Proceedings of IEEE International Symposium on Circuits and Systems (ISCAS) (pp. 3933 - 3936). Paris: IEEE.
Lee, C., & Chiou, C. (2012). Scalable Gaussian Normal Basis Multipliers over GF(2^m) Using Hankel Matrix-Vector Representation. Journal of Signal Processing Systems, 69(2), 197-211.
Lopez, J., & Dahab, R. (1999). Fast Multiplication on Elliptic Curves Over GF(2^m) without precomputation. Cryptographic Hardware and Embedded Systems, 1717, 316-327.
Mahdizadeh, H., & Masoumi, M. (2013). Novel Architecture for efficient FPGA implementation of elliptic curve cryptographic processor over GF(2^163). IEEE transactions on very large scale integration (VLSI) systems, 21(12), 1-4.
Malik, M. (2010). Efficient implementation of Elliptic Curve Cryptography using low-power Digital Signal Processor. In International Conference on Advanced Communication Technology (ICACT) (pp. 1464-1468). Phoenix Park: IEEE.
Masoleh, R. (2006). Efficient algorithms and architectures for field multiplication using Gaussian normal basis. IEEE Transactions on Computers, 55(1), 34-47.
Mercurio, S., & Rodriguez, F. (2006). Elliptic Curve Scalar Multiplication using Point Halving on Reconfigurable Hardware Platforms (pp. 1-5). Mexico: CiteSeerX.
Miller, V. (1986). Advances in Cryptology. In CRYPTO '85 Proceedings. Santa Barbara: Springer.
Morales, S., Uribe, F., & Badillo, A. (2011). A reconfigurable GF(2^m) elliptic curve cryptographic coprocessor. In Southern Conference on Programmable Logic (SPL) (pp. 209 - 214). Cordoba: IEEE.
NIST. (2013). Digital Signature Standard. Gaithersburg: Federal Information Processing Standards.
Rahuman, A., & Athisha, G. (2010). Reconfigurable architecture for elliptic curve cryptography. In International Conference on Communication and Computational Intelligence (INCOCCI) (pp. 461-466). Erode: IEEE.
Schroeppel, R. (2000). United States Patent No. EP1232602.
Solinas, J. (2000). Efficient Arithmetic on Koblitz Curves. Designs, Codes and Cryptography, 19(2-3), 195-249.
Trujillo, V., & Velasco, J. (2010). Hardware Architectures for Elliptic Curve Cryptoprocessors Using Polynomial and Gaussian Normal Basis over GF(2^233). Lecture Notes in Computer Science, 6480, 79-103.
Wang, Z., & Fan, S. (2012). Efficient Montgomery-Based Semi-Systolic Multiplier for Even-Type GNB of GF(2^m). IEEE Transactions on Computers, 61(3), 415-419.
Dimensions
PlumX
Article abstract page views
Downloads
How to Cite
License
Copyright (c) 2014 Paulo Cesar Realpe, Vladimir Trujillo-Olaya, Jaime Velasco-Medina
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
