Parallelizing GF (p) Montgomery Elliptic Curve Crypto-System Operations to Improve Security and Performance

Abstract:

The elliptic curve crypto-system (ECC) performs two levels of computations, lower point operations, and upper scalar multiplication levels. The use of usual serial design and affine coordinates to apply ECC computations increases the time delay and weaken the security of the crypto-system against simple power attack (SPA). This work combines the inherited parallelism in both computation levels for GF (p) Montgomery ECC to improve performance and enhance the immunity of the ECC against SPA. Moreover, projective coordinates were used to apply ECC operations to eliminate the time-consuming inversion operation. In order to increase the speed even further, this paper proposes to use known NAF algorithm for scalar multiplication, as well as Montgomery multiplier to perform multiplication operations. Hardware implementations with target FPGA for GF (p) Montgomery ECC are also presented. The best performance level was achieved when parallelizing Montgomery ECC computations to eight parallel multipliers (PM) using homogeneous coordinates. Such strategy, although it requires extra resources, is worth considering due to its attractive security and performance conclusions.

• Periodical: Advanced Materials Research (Volumes 622-623)
• Pages: 1906-1911
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.622-623.1906
• Online since: December 2012
• Authors: Mohammad Alkhatib, Azmi Jaafar, Mohamad Rushdan Md Said, Zuriati Ahmad Zukarnain
• Keywords: Elliptic Curve Crypto-System, Montgomery Multipliers, NAF Algorithm, Parallelization Level, Projective Coordinates

References

[1] Wade Trappe, Lawrence. c, Introduction to Cryptography with Coding Theory. Washington, Pearson Prentice Hall, (2002).

[2] I. Blake, G. Seroussi, N. Smart, Elliptic Curves in Cryptography, Cambridge University Press, New York, (1999).

[3] Adnan Gutub and Alexandre F. Tenca, Efficient Scalable VLSI Architecture for Montgomery Inversion in G (p), Integration, the VLSI Journal, Vol. 37, No. 2, pp.103-120, (2004).

DOI: 10.1016/j.vlsi.2003.12.001

[4] P. Kocher, J. Jaffe, B. Jun, Differential Power Analysis, Advances in Cryptology - Crypto 99 Proceedings, Lecture Notes In Computer Science Vol. 1666, Springer-Verlag, (1999).

DOI: 10.1007/3-540-48405-1_25

[5] D. Hankerson, A. Menezes, S. Vanstone, Guide to Elliptic Curve Cryptography, Springer-Verlag, (2004).

[6] G. Orlando, C. Paar, A scalable GF (p) elliptic curve processor architecture for programmable hardware, CHES '01 Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, pp.348-363, (2001).

DOI: 10.1007/3-540-44709-1_29

[7] T. Kerins, E. M. Popovici, W. P. Marnane, An FPGA Implementation of a Flexible, Secure Elliptic Curve Cryptography Processor, International Workshop on Applied Reconfigurable Computing-ARC, pp.22-30, (2005).

[8] Mohammad Alkhatib, Azmi Jaafar, and Qacem Abu Al-Haija, Choices on Designing GF (p) Elliptic Curve Coprocessor Benefiting From Mapping Homogeneous Curves in Parallel Multiplications, International Journal on computer science and engineering, Vol. 3, No. 2, pp.467-480, (2011).

[9] Mohammad khatib, Qacem, and Azmi Jaafar, Hardware Architecture & Designs for Projective Elliptic Curves Point Addition Operation using Variable Levels of Parallelism, International Review on Computers and Software, Vol. 6 N. 2, pp.237-243, (2011).

[10] Mohammad Al-khatib, Azmi Jaafar, Zuriati Ahmad Zukarnain, and Mohamad Rushdan Md Said, Hardware Designs and Architectures for Projective Montgomery ECC over GF (p) Benefiting From Mapping Elliptic Curve Computations to Different Degrees of Parallelism, International Review on Computers and Software, Vol. 6, N. 6, pp.1059-1070, (2011).

[11] Adnan Abdul-Aziz Gutub and Mohammad K. Ibrahim, in: High Radix Parallel Architecture For GF(p) Elliptic Curve Processor, IEEE Conference on Acoustics, Speech, and Signal Processing, ICASSP 2003, Hong Kong, April 6-10, (2003).

DOI: 10.1109/icassp.2003.1202444

[12] Coron, J. -S, Resistance Against Differential Power Analysis for Elliptic Curve Cryptosystems, in: Cryptographic Hardware and Embedded Systems -CHES '99, (1999).

DOI: 10.1007/3-540-48059-5_25

[13] A. Gutub, M. Ibrahim, T. Al-Somani, Parallelizing GF (P) Elliptic Curve Cryptography Computations for Security and Speed, 9th International Symposium on Signal Processing and its Applications, pp.1-4, (2007).

DOI: 10.1109/isspa.2007.4555449

[14] C. McIvor, M. McLoone, J. McCanny, An FPGA Elliptic Curve cryptographic accelerator over GF (p), Irish Signals and Systems Conference, pp.589-594, (2004).

DOI: 10.1049/cp:20040606

[15] You-Bo Wang, Xiang-Jun Dong, Zhi-Guang Tian, FPGA Based Design of Elliptic Curve Cryptography Coprocessor, ICNC '07 Proceedings of the Third International Conference on Natural Computation, Vol. 5, pp.185-189, (2007).

DOI: 10.1109/icnc.2007.391

[16] U. Kocabas, J. Fan, I. Verbauwhede, Implementation of Binary Edwards Curves for Very-Constrained Devices, 21st IEEE International Conference on Application-specic Systems Architectures and Processors, pp.185-191, (2010).

DOI: 10.1109/asap.2010.5541003