Towards Efficient FPGA Implementation of Elliptic Curve Crypto-Processor for Security in IoT and Embedded Devices

Abu Khadra, Shaimaa; Abdulrahman, Salah Eldin S. E.; Ismail, Nabil A.

doi:10.21608/mjeer.2020.103280

Towards Efficient FPGA Implementation of Elliptic Curve Crypto-Processor for Security in IoT and Embedded Devices

Document Type : Original Article

Authors

¹ Al-Mahala High Institute of Engineering, Al-Mahala

² Dept. of Computer Sci. & Engineering, Faculty of Engineering, Menoufia University.

10.21608/mjeer.2020.103280

Abstract

An Elliptic Curve Crypto-Processor (ECCP) is a favorite public-key cryptosystem due to its small key size and its high security arithmetic unit. It is applied in constrained devices which often run on batteries and have limited processing, storage capabilities and low power. This research work presents an effective ECCP architecture for security in IoT and embedded devices. A finite field polynomial multiplier takes the most implementation effort of an ECCP because it is the most consuming operation for time and area. So, the objective is to implement the main operation of Point Multiplication (PM) 𝑄=𝑘𝑃 using FPGA. The aim is to obtain the optimal registers number for an area optimization of ECCP architecture. Moreover, it proposes a time optimization of ECCP based on the liveness analysis and exploiting forward paths. Also, a comparison between sequential and parallel hardware design of PM based on Montgomery ladder algorithm is provided.
The developed ECCP design is implemented over Galois Fields GF (2163) and GF (2409) on Xilinx Integrated Synthesizes Environment (ISE) Virtex 6 FPGA. In case of GF (2163), this work achieved an area saving that uses 2083 Flip Flops (FFs), 40876 Lookup Tables (LUTs) and 19824 occupied slices. The execution time is 1.963 s runs at a frequency of 369.529 MHz and consumes 5237.00 mW. In case of GF (2409), this work achieved an area saving that uses 8129 Flip Flops (FFs), 42300 Lookup Tables (LUTs) and 18807 occupied slices. The execution time is 29 s runs at a frequency of 253.770 MHz and consumes 2 W. The obtained results are highly comparable with other state-of-the-art crypto-processor designs. The developed ECCP is applied as a case study of a cryptography protocol in ATMs.

Keywords

References

[1] S. Kumari et. al., “A secure authentication scheme based on elliptic curve cryptography for IoT and cloud servers,” J. Supercomputer, Springer, Published online, April 2017.
[2] C. Lee and H. Chien, “An Elliptic Curve Cryptography-Based RFID Authentication Securing E-Health System,” International Journal of Distributed Sensor Networks, 2015.
[3] C. H. Gebotys, Security in Embedded Devices, New York, Springer, 2010.
[4] R. Hankerson, A. Menezes, and S. Vanstone, Guide to Elliptic Curve Cryptography, Chapter 3 “Elliptic Curve Arithmetic”, New York: Springer Professional Computing, 2004.
[5] Institute of Electrical and Electronics Engineers, Standard Specifications for Public Key Cryptography, (IEEE P1363: IEEE), 2000.
[6] National Institute of Standards and Technology (NIST), Digital Signature Standard (DSS), (NIST: NIST FIPS 186-4), 2009. https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.186-4.pdf
[7] M. Imran, M. Rashid, A. R. Jafri, and M. Najam ul Islam, "ACryp-Proc: Flexible Asymmetric Crypto Processor for Point Multiplication," IEEE Access, Vol. 6, pp. 22778-22793, 2018.
[8] Realpe P C and Velasco-medina J, High-Performance Elliptic Curve Cryptoprocessors over GF(2m) on Koblitz Curve, Analog Integr Circ Sig Process. Springer. 85 129–138, 2015.
[9] M.S. Albahri, M. Benaissa, and Zia Uddin A. Khan, “Parallel Implementation of ECC Point Multiplication on a Homogeneous Multi-Core Microcontroller,” Proceeding of 12th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN), IEEE, 16-18 Dec., Hefei, China, pp. 386-389, 2016.
[10] Loi K C C and Ko S-B, "Parallelization of Scalable Elliptic Curve Cryptoprocessors in GF(2m)," Microprocessors and Microsystems, Volume 45, Part A, Elsevier 45 Pages 10–22, August 2016.
[11] Rashidi B., Farashahi R. R. and Sayedi S. M., " High-Speed and Pipelined Finite Field Bit-Parallel Multiplier over GF(2m) for Elliptic Curve Cryptosystems," 11th Int. ISC Conferene on Information Security and Cryptology, Tehran 15-20, 2014.
[12] Rashidi B., Farashahi R. R. and Sayedi S. M., “High-Performance and High-Speed Implementation of Polynomial Basis Itoh-Tsujii Inversion Algorithm over GF(2m),” IET Information Security, Vol. 11, Iss. 2, pp. 66-77, 2017.
[13] P. L. Montgomery, “Speeding the Pollard and Elliptic Curve Methods of Factorization,” Math. Computing, Vol. 48 - pp. 243–264, 1987.
[14] J. López, and R. Dahab, “Improved Algorithms for Elliptic Curve Arithmetic in GF(2n),” Proc. Sel. Areas Cryptography, pp. 201–212, 1999.
[15] T. Itoh, and S. Tsujii, “A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) using Normal Bases,” Information Computing, Vol. 78, No. 3, pp. 171–177, 1988.
[16] A. P. Fournaris, C. Dimopoulos, and O. Koufopavlou, "A Design Strategy for Digit Serial Multiplier Based Binary Edwards Curve Scalar Multiplier Architectures," Proc. Euromicro Conference on Digital System Design (DSD), 2017.
[17] Rashidi B, Farashahi R R and Sayedi S M, "High-Speed Hardware Architecture of Scalar Multiplication for Binary Elliptic Curve Cryptosystems," Microelectronics Journal, 2016.
[18] A. B. El-Sisi, S. M. M Shohdy, and N. Ismail, “Reconfigurable Implementation of Karatsuba Multiplier for Galois Field Elliptic Curves,” Tarek Sobh, Khalid Ellithy, and Ausif Mahmood (Editors), Novel Algorithms and Techniques in Telecommunications and Networking, Springer Nature America, pp 87-92 Inc, 2010.
[19] F. Rodriguez-Henriquez and Q. K. Kog. “On Fully Parallel Karatsuba Multipliers for GF (2m)”. Proc. International Conference on Computer Science and Technology (CST), pp. 405-410, 2003.
Fig. 8: The scalar multiplication architecture
Table 9: A comparison with state-of-the-art Architecture PM algorithm FF multiplier FPGA Frequency in MHz # of occupied slices Time in s
[23]
Montgomery Ladder
Bit parallel with K-O
Virtex 7
294
3041
4.6
[22]
Segmented pipeline
Virtex 5
113
11777
3.99
[8]
Digit parallel
Virtex 7
351
3107
11.28
This work
Bit parallel
Virtex 6
369.5
19,824
1.9
11 8
[20] H. Modares, Y. Salem, R. Salleh and M. T. Shahgoli "A Bit-Serial Multiplier Architecture for Finite Fields Over Galois Fields," Journal of Computer Science, 2010.
[21] M. Keller and W. Marnane "Low Power Elliptic Curve Cryptography," Lecture Notes in Computer Science, and Proceeding of PATMOS’07, pp. 310-319, 2007.
[22] M. N. Ismail, “Towards Efficient Hardware Implementation of Elliptic and Hyperelliptic Curve Cryptography,” Ph.D. Thesis, Dept. of Electrical and Computer Engineering, University of Waterloo, Ontario, Canada, July 2012.
[23] H. Cohen and G. Frey, Eds. Handbook of Elliptic and Hyperelliptic Curve Cryptography, “Arithmetic of elliptic curves,” D. Doche and T. Lange, Chapman & Hall/CRC, Boca Raton, FL, Chapter 13, pp. 267-302,2006.
[24] B. Ansari and M. A. Hasan, “High-Performance Architecture of Elliptic Curve Scalar Multiplication,” IEEE Transactions on Computers, Vol. 57, No. 11, pp. 1443-1453, 2008.
[25] Zia U. A. Khan and M. Benaissa, “High-Speed and Low-Latency ECC Processor Implementation Over GF(2m) on FPGA,” IEEE Transactions on Very Large-Scale Integration (VLSI) Systems, Vol. 25, no. 1, pp. 165-176, Jan. 2017.
[26] P. K. Mishra, P. Pal and P. Sarkar, "Towards Minimizing Memory Requirement for Implementation of Hyperelliptic Curve Cryptosystems," Lecture Notes in Computer Science, Vol. 4464, and ISPEC, pp. 269-283, 2007.
[27] W. N. Chelton and M. Benaissa "Fast Elliptic Curve Cryptography on FPGA,” IEEE Transactions on Very Large-Scale Integration (VLSI) Systems, vol.16, Issue 2, pp. 198-205, 2008.
[28] L. Lijuan and L. Shuguo, “High-Performance Pipelined Architecture of Elliptic Curve Scalar Multiplication over GF(2m),” IEE Transactions on VLSI Systems, pp. 1223-1232, 2016.
[29] P. Zode et.al. “Fast Architecture of Modular Inversion Using Itoh-Tsujii Algorithm,” International Symposium on VLSI Design and Test VDAT, pp. 48-55, 2017.
[30] Shohdy S, El-Sisi A and Ismail N., “FPGA Implementation of Elliptic Curve Point Multiplication over GF(2191),” Advances in Information Security and Its Applications (ISA), Lecture Notes in Computer Science, Springer-Verlag Berlin. Germany, 5576 619–634, 2009.
[31] Kudithi T, Sakthivel R., “High-Performance ECC Processor Architecture Design for IoT Security Applications,” Supercomputer J. Springer. 75 447–474, 2019.
[32] David Hutchison, and et., " Information Security and Cryptology", ICISC 2004, 7th International Conference Seoul, Korea, Springer, December 2-3, 2004.
[33] Y. W. Hau1 Mohamed Khalil-Hani and Muhammad N. Marsono, "Systemc-Based Hardware/Software Co-Design of Elliptic Curve Cryptographic System for Network Mutual Authentication", Malaysian Journal of Computer Science, Vol. 24(2), 2011.