Home > CSC-OpenAccess Library > Manuscript Information

This is an Open Access publication published under CSC-OpenAccess Policy.

Preference of Efficient Architectures for GF(p) Elliptic Curve Crypto Operations using Multiple Parallel Multipliers

Adnan Abdul-Aziz Gutub

Pages - 46 - 63 | Revised - 30-08-2010 | Published - 30-10-2010

Published in International Journal of Security (IJS)

MORE INFORMATION

KEYWORDS

Modulo multipliers, Cryptography Hardware, Elliptic curve cryptography, Jacobian projective coordinates, Parallel multipliers crypto hardware

ABSTRACT

This paper explores architecture possibilities to utilize more than one multiplier to speedup the computation of GF(p) elliptic curve crypto systems. The architectures considers projective coordinates to reduce the GF(p) inversion complexity through additional multiplication operations. The study compares the standard projective coordinates (X/Z,Y/Z) with the Jacobian coordinates (X/Z2,Y/Z3) exploiting their multiplication operations parallelism. We assume using 2, 3, 4, and 5 parallel multipliers and accordingly choose the appropriate projective coordinate efficiently. The study proved that the Jacobian coordinates (X/Z2,Y/Z3) is preferred when single or two multipliers are used. Whenever 3 or 4 multipliers are available, the standard projective coordinates (X/Z,Y/Z) are favored. We found that designs with 5 multipliers have no benefit over the 4 multipliers because of the data dependency. These architectures study are particularly attractive for elliptic curve cryptosystems when hardware area optimization is the key concern.

1 | Sakthivel, A., & Nedunchezhian, R. (2013). Improved the execution speed of ecdsa over gf (2 n) algorithm for concurrent computation. Journal of Theoretical & Applied Information Technology,50(1). |

2 | Senekane, M., Qhobosheane, S., & Taele, B. M. (2011). Elliptic Curve Diffie-Hellman Protocol Implementation Using Picoblaze. IJCSNS, 11(6), 30. |

1 | Google Scholar |

2 | Academic Index |

3 | CiteSeerX |

4 | refSeek |

5 | iSEEK |

6 | Socol@r |

7 | Scribd |

8 | slideshare |

9 | PDFCAST |

10 | PdfSR |

1 | V. S. Miller, “Use of Elliptic Curves in Cryptography”, Proceedings of Advances in Cryptology (Crypto), (1986), p. 417–426. |

2 | N. Koblitz, “Elliptic Curve Cryptosystems”, Math. Computing, 48 (1987), p. 203–209. |

3 | Blake, Seroussi, and Smart, Elliptic Curves in Cryptography, Cambridge University Press: New York, 1999. |

4 | G. V. S. Raju, R. Akbani, “Elliptic Curve Cryptosystem and its Applications”, IEEE International Conference on Systems, Man and Cybernetics, 2 (2003), p.1540 – 1543. |

5 | Paar, Fleischmann, and Soria-Rodriguez, “Fast Arithmetic for Public-Key Algorithms in Galois Fields with Composite Exponents”, IEEE Transactions on Computers, 48:10 (1999). |

6 | R. L. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Publickey Cryptosystems”, Communications of the ACM, 21:2 (1978), p. 120–126. |

7 | IEEE P1363, http://grouper.ieee.org/groups/1363. |

8 | The ATM Forum, http://www.atmforum.com/meetings/rich_bios. html |

9 | The Internet Engineering Task Force, http://www.ietf.cnri.reston.va.us |

10 | Chung, Sim, Lee, “Fast Implementation of Elliptic Curve Defined over GF(pm) on CalmRISC with MAC2424 Coprocessor”, Workshop on Cryptographic Hardware and Embedded Systems(CHES), (2000). |

11 | Okada, Torii, Itoh, Takenaka, “Implementation of Elliptic Curve Cryptographic Coprocessor over GF(2m) on an FPGA”, Workshop on Cryptographic Hardware and Embedded Systems (CHES),(2000). |

12 | Orlando and Paar, “A High-Performance Reconfigurable Elliptic Curve Processor for GF(2m)”,Workshop on Cryptographic Hardware and Embedded Systems (CHES), (2000). |

13 | Hankerson, Hernandez, and Menezes, “Software Implementation of Elliptic Curve Cryptography Over Binary Fields”, Workshop on Cryptographic Hardware and Embedded Systems (CHES),(2000). |

14 | G. A. Orton and others, “VLSI implementation of public-key encryption algorithms”, Advances in Cryptology (CRYPTO), 263 (1986), p. 277-301. |

15 | Orlando and Paar, “A scalable GF(p) elliptic curve processor architecture for programmable hardware”, Cryptographic Hardware and Embedded Systems (CHES), (2001). |

16 | Royo, Moran, and Lopez, “Design and implementation of a coprocessor for cryptography applications”, European Design and Test Conference Proceedings, (1997), p. 213–217. |

17 | Agnew, Mullin, and Vanstone, “An Implementation of Elliptic Curve Cryptosystems Over F2 155”,IEEE Journal on Selected Areas in Communications, 11:5 (1993), p. 804–813. |

18 | Siddika Berna Ors and others, “Hardware Implementation of an Elliptic Curve Processor over GF(p)”, Proceedings of the IEEE International Conference on Application-Specific Systems,Architectures, and Processors (ASAP), (2003), p. 433 – 443. |

19 | G.B. Agnew, R.C. Mullin, and S.A.Vanstone, “An implementation of elliptic curve cryptosystems over F2155”, IEEE Journal on Selected Areas in Communications, 11:5 (1993), p.804-813. |

20 | Chi Huang, Jimnei Lai, Junyan Ren, and Qianling Zhang, “Scalable Elliptic Curve Encryption Processor for Portable Application”, Proceedings of the 5th International Conference on ASIC, 2(2003), p. 1312-1316. |

21 | J. R. Michener and S. D., “Mohan, Internet Watch: Clothing the E-Emperor, Computer –Innovative Technology for Computer Professionals”, IEEE Computer Society, 34:9 (2001), p.116-118. |

22 | Adnan Abdul-Aziz Gutub, A. F. Tenca, and C. K. Koc, “Scalable VLSI architecture for GF(p)Montgomery modular inverse computation”, IEEE Computer Society Annual Symposium on VLSI, (2002), p. 53-58. |

23 | A. F. Tenca and C. K. Koc, “A Scalable Architecture for Modular Multiplication Based on Montgomery's Algorithm”, IEEE Transactions on Computers, 52:9 (2003), p. 1215-1221. |

24 | A. Miyaji, “Elliptic Curves over FP Suitable for Cryptosystems”, Advances in cryptologyAUSCRUPT’92,Australia, (1992). |

25 | Mentor Graphics Co., http://www.mentor.com/partners/hep/AsicDesignKit/dsheet/ami05databook.html, ASIC Design Kit. |

26 | Adnan Gutub, “Efficient Utilization of Scalable Multipliers in Parallel to Compute GF(p) Elliptic Curve Cryptographic Operations”, Kuwait Journal of Science & Engineering (KJSE), Vol . 34,No. 2, Pages: 165-182, December 2007. |

27 | Daniel J. Bernstein1 and Tanja Lange, ”Faster Addition and Doubling On Elliptic Curves,”Springer Berlin /Heidelberg, Supported in Part by The European Commission Through The 1st Programme, Vol. 4833/2008, November 05, 2007. |

28 | Adnan Gutub, Mohammad Ibrahim, and Turki Al-Somani, “Parallelizing GF(P) Elliptic Curve Cryptography Computations for Security and Speed”, IEEE International Symposium on Signal Processing and its Applications in conjunction with the International Conference on Information Sciences, Signal Processing and their Applications (ISSPA), Sharjah, United Arab Emirates,February 12-15,2007. |

29 | Adnan Gutub, “Fast 160-Bits GF(p) Elliptic Curve Crypto Hardware of High-Radix Scalable Multipliers”, International Arab Journal of Information Technology (IAJIT), Vol. 3, No. 4, Pages:342-349, October 2006. |

30 | L. Tawalbeh and A. Tenca, “An Algorithm and Hardware Architecture for Integrated Modular Division and Multiplication in GF(P) and GF(2N),” IEEE International Conference on ApplicationSpecific Systems, April 2004. |

31 | L. Tawalbeh, “A Novel Unified Algorithm And Hardware Architecture for Integrated Modular Division and Multiplication in GF(P) and GF(2N) Suitable for Public-Key Cryptography”, Ph.D.Thesis, School of Electrical Engineering and Computer Science, Oregon State University,October 28, 2004. |

Dr. Adnan Abdul-Aziz Gutub

Umm Al-Qura University - Saudi Arabia

adnangutub@gmail.com