Efficient Hardware Implementation of an Elliptic Curve Cryptographic Processor Over GF (2 163)

Authors: Massoud Masoumi, Hosseyn Mahdizadeh

Abstract:

A new and highly efficient architecture for elliptic curve scalar point multiplication which is optimized for a binary field recommended by NIST and is well-suited for elliptic curve cryptographic (ECC) applications is presented. To achieve the maximum architectural and timing improvements we have reorganized and reordered the critical path of the Lopez-Dahab scalar point multiplication architecture such that logic structures are implemented in parallel and operations in the critical path are diverted to noncritical paths. With G=41, the proposed design is capable of performing a field multiplication over the extension field with degree 163 in 11.92 s with the maximum achievable frequency of 251 MHz on Xilinx Virtex-4 (XC4VLX200) while 22% of the chip area is occupied, where G is the digit size of the underlying digit-serial finite field multiplier.

Keywords: Elliptic curve cryptography, FPGA implementation, scalar point multiplication.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1329671

References:

[1] D. Hankerson, A. Menezes, S. Vanstone, Guide to elliptic curve cryptography, Springer, 2004.
[2] Rodriguez-Henriquez et.al, Cryptographic Algorithms on Reconfigurable Hardware, Springer, 2006.
[3] T. Wollinger, J. Guajardo, and C. Paar, "Security on FPGAs: State-ofthe- art and Implementations Attacks," ACM Trans. on Embedded Computing Sys., 3(3):534- 574, 2004.
[4] J. Lopez and R. Dahab, "Fast multiplication on elliptic curves over GF(2m) without precomputation,", CHES, MA, USA, 1999.
[5] T. Itoh and S. Tsujii, "A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) Using Normal Basis," Information and Computing, 78:171-177, 1988.
[6] W. Stallings, Cryptography and Network Security, 4th Ed., Prentice-Hall, 2006.
[7] S. Kummar, T. Wollinger, and C. Paar, "Optimum Digit Serial GF(2m) Multipliers for Curve Based Cryptography," IEEE Trans. Comp., vol. 55, no 10. 2006
[8] G. Orlando and C. Paar., "A high-performance reconfigurable elliptic curve processor for GF(2m)," CHES, MA, USA, 2000.
[9] N. Gura, S. C. Shantz, H. Eberle, S. Gupta, V. Gupta, D. Finchelstein, E. Goupy, and D. Stebila, "An end-to-end systems approach to elliptic curve cryptography," CHES, CA, USA, 2002.
[10] K. Jarvinen, M. Tommiska, and J. Skytta, "A scalable architecture for elliptic curve point multiplication," ICFPT, Brisbane, Australia, 2004.
[11] F. Rodriguez-Henriquez, N. A. Saqib, and A. Diaz-Perez, "A fast parallel implementation of elliptic curve point multiplication over GF(2m)," Microprocessors Microsyst., vol. 28, pp. 329-339, 2004.
[12] R. C. C. Cheung, N. J. Telle, W. Luk, and P. Y. K. Cheung, "Customizable elliptic curve cryptosystems," IEEE Trans. Very Large Scale Integr. (VLSI) Syst.", vol. 13, no. 9, pp. 1048-1059, Sep. 2005.
[13] K. Sakiyama, L. Batina, B. Preneel, and I. Verbauwhede, "Superscalar coprocessor for high-speed curve-based cryptography," CHES, Yokohama, Japan, 2006
[14] W.N. Chelton and M. Benaissa, "Fast elliptic curve cryptography on FPGA, "IEEE Trans. on Very Large Scale Integration (VLSI) Systems," vol. 16, no. 2, Feb. 2008, pp. 198-205.
[15] B. Ansari and a. Hasan, "High-Performance Architecture of Elliptic Curve Scalar multiplication", IEEE Trans. on Comp., Vol. 57, No. 11, pp. 1443-1453, Nov. 2008.
[16] Yong-ping Dan et. al., "High-performance hardware architecture of elliptic curve cryptography processor over GF(2163), J. Zhejiang Univ. Sci., A 2009 10(2):301-310
[17] J. Lutz and Hasan, A., "High performance FPGA based elliptic curve cryptographic coprocessor," ITCC, Las Vegas, USA, Apr. 5-7, vol. 2, pp. 486-492, 2004,
[18] K. Jarvinen and J. Skytta, "On parallelization of high-speed processors for elliptic curve cryptography," IEEE Trans. on Very Large Scale Integration (VLSI) Systems, 16 (9) (2008) 1162-1175.
[19] C. H. Kim, S. Kwon, C. P. Hong, "FPGA implementation of high performance elliptic curve cryptographic processor over GF(2163)," J. of Sys. Architecture, 54 (10) (2008) 893-900