Journal Home > Volume 22 , Issue 5
Tsinghua Science and Technology 2017, 22(5): 511-519 https://doi.org/10.23919/TST.2017.8030540
Open Access | Issue | Published: 11 September 2017

Simple Method for Realizing Weil Theorem in Secure ECC Generation

Show Author's Information Feng Hu,  Chao Wang( ),  Huanguo Zhang,  Jie Wu
Key Laboratory of Specialty Fiber Optics and Optical Access Networks, School of Communication and Information Engineering, Shanghai University, Shanghai 200072, China.
Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA.
Key Lab of Aerospace Information Security and Trusted Computing, Wuhan University, Wuhan 430072, China.
Keywords:
Elliptic Curves (ECs), Pascal’s triangle, Weil theorem
Cite this article:
Hu F, Wang C, Zhang H, et al. Simple Method for Realizing Weil Theorem in Secure ECC Generation. Tsinghua Science and Technology, 2017, 22(5): 511-519. https://doi.org/10.23919/TST.2017.8030540
Download citation
EndNote(RIS)
BibTeX

378

Views

13

Downloads

Citations

0

Crossref

N/A

WoS

4

Scopus

3

CSCD

Abstract Full text About this article

How to quickly compute the number of points on an Elliptic Curve (EC) has been a longstanding challenge. The computational complexity of the algorithm usually employed makes it highly inefficient. Unlike the general EC, a simple method called the Weil theorem can be used to compute the order of an EC characterized by a small prime number, such as the Kobltiz EC characterized by two. The fifteen secure ECs recommended by the National Institute of Standards and Technology (NIST) Digital Signature Standard contain five Koblitz ECs whose maximum base domain reaches 571 bits. Experimental results show that the computation speed decreases for base domains exceeding 600 bits. In this paper, we propose a simple method that combines the Weil theorem with Pascals triangle, which greatly reduces the computational complexity. We have validated the performance of this method for base fields ranging from 2100 to 21000. Furthermore, this new method can be generalized to any ECs characterized by any small prime number.


menu
Abstract
Full text
Outline
About this article

Simple Method for Realizing Weil Theorem in Secure ECC Generation

Show Author's information Feng Hu, Chao Wang( ), Huanguo Zhang, Jie Wu
Key Laboratory of Specialty Fiber Optics and Optical Access Networks, School of Communication and Information Engineering, Shanghai University, Shanghai 200072, China.
Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA.
Key Lab of Aerospace Information Security and Trusted Computing, Wuhan University, Wuhan 430072, China.

Abstract

How to quickly compute the number of points on an Elliptic Curve (EC) has been a longstanding challenge. The computational complexity of the algorithm usually employed makes it highly inefficient. Unlike the general EC, a simple method called the Weil theorem can be used to compute the order of an EC characterized by a small prime number, such as the Kobltiz EC characterized by two. The fifteen secure ECs recommended by the National Institute of Standards and Technology (NIST) Digital Signature Standard contain five Koblitz ECs whose maximum base domain reaches 571 bits. Experimental results show that the computation speed decreases for base domains exceeding 600 bits. In this paper, we propose a simple method that combines the Weil theorem with Pascals triangle, which greatly reduces the computational complexity. We have validated the performance of this method for base fields ranging from 2100 to 21000. Furthermore, this new method can be generalized to any ECs characterized by any small prime number.

Keywords: Elliptic Curves (ECs), Pascal’s triangle, Weil theorem

References(25)

[1]
Laiswal P., Kumar A., and Tripathi S., Design of secure group key agreement protocol using elliptic curve cryptography, present at 2014 International Conference on High Performance Computing and Applications (ICHPCA), IEEE, Bhubaneswar, India, 2014.
DOI
[2]
Wang C., Zhang H. G., and Liu L. L., Koblitz elliptic curves generating based on evolutionary cryptography theory and verifying parameters recommended by NIST, China Communications, vol. 8, no. 4, pp. 41-49, 2011.
Google Scholar
[3]
Wang C., Zhang H. G., and Liu L. L., Evolutionary cryptography theory based generating method for a secure Koblitz elliptic curve and its improvement by a hidden Markov models, Sciece China Information Sciences, vol. 55, no. 4, pp. 911-920, 2012.
DOI Google Scholar
[4]
Guo R., Wen Q., and Jin Z., Pairing based elliptic curve encryption scheme with hybrid problems in smart house, presented at Fourth International Conference on Intelligent Control and Information Processing, Beijing, China, 2013.
DOI
[5]
Xu J. W., Wang K. D., Wang C., Hu F., Zhang Z. H., Xu S. Y., and Wu J., Byzantine fault-tolerant routing for large-scale wireless sensor networks based on fast ECDSA, Tsinghua Science and Technology, vol. 20, no. 6, pp. 627-633, 2015.
DOI Google Scholar
[6]
Jia H. H., Wang C., and Gu J., Error bit correction of ECC attack based on grover quantum intermediate encounter search algorithm, Netinfo Security, no. 6, pp. 28-34, 2016.
Google Scholar
[7]
Chen Y. H., Jia H. H., and Jiang L. Y., ECC scanning attack based on grover algorithm, Netinfo Security, no. 2, pp. 28-32, 2016.
Google Scholar
[8]
Schoof R., Elliptic curves over finite fields and the computation of square roots mod P, Mathematics of Computation, vol. 44, no. 170, pp. 483-494, 1985.
DOI Google Scholar
[9]
Elkies N., Elliptic and modular curves over finite fields and related computational issues, presented at the Computational Perspectives on Number Theory, Chicago, IL, USA, 1995.
[10]
Satoh T., The canonical lift of an ordinary elliptic curve over a finite field and its point counting, Journal of the Ramanujan Mathematical Society, vol. 15, no. 4, pp. 247-270, 2000.
Google Scholar
[11]
Harley R., Counting points with the arithmetic-geometric mean, PhD dissertation, University of Reading, Whiteknights, UK, 1996.
[12]
Wang M., Dai G., and Hu H., Selection of security elliptic curve based on evolution algorithm, in Proc. Int. Conf. Computational Intelligence and Natural Computing, Wuhan, China, 2009.
DOI
[13]
Silverman J., The Arithmetic of Elliptic Curves. World Book Inc, 1986.
DOI
[14]
Shen G. and Zhen Y., Application of elliptic curve cryptography in node authentication of Internet of Things, in Proc. Int. Conf. Intelligent Information Hiding and Multimedia Signal Processing, Bejing, China, 2013.
[15]
Sridhar K., Raguram M., and Prakash B., Secured elliptic curve cryptosystems for scan based VLSI architecture, in Proc. Int. Conf. Information Communication and Embedded Systems, Chennai, Thailand, 2014.
DOI
[16]
Loi K. and Ko S., Scalable elliptic curve cryptosystem FPGA processor for NIST prime curves, IEEE Transactions on Very Large Scale Integration Systems, vol. 23, no. 11, pp. 2753-2756, 2015.
DOI Google Scholar
[17]
Thiranant N., Lee Y., and Lee H., Performance comparison between RSA and elliptic curve cryptography-based QR Code Authentication, in Proc. Int. Conf. Advanced Information NETWORKING and Applications Workshops, Gwangiu, South Korea, 2015.
DOI
[18]
Indaco M., Lauri F., and Miele A., An efficient many-core architecture for elliptic curve cryptography security assessment, in Proc. Int. Conf. Field Programmable Logic and Applications, Imperial College, London, UK, 2015, pp. 1-6.
DOI
[19]
He D. and Zeadally S., An analysis of RFID authentication schemes for Internet of Things in healthcare environment using elliptic curve cryptography, IEEE Internet of Things Journal, vol. 2, no. 1, pp. 72-83, 2015.
DOI Google Scholar
[20]
Reyhanimasoleh A., Parallel and high-speed computations of elliptic curve cryptography using hybrid-double multipliers, IEEE Transactions on Parallel & Distributed Systems, vol. 26, no. 6, pp. 1668-1677, 2015.
DOI Google Scholar
[21]
Jilna P., Deepthi P., and Sameer S., FPGA implementation of an elliptic curve based integrated system for encryption and authentication, in Proc. Int. Conf. Signal Processing, Informatics, Communication and Energy Systems, Kozhikode, India, 2015, pp. 1-6.
DOI
[22]
Daniel S., Robert L., and Oldham N., Optimization of elliptic curve operations for ECM using double & add algorithm, in Proc. Int. Conf. E-Technologies and Networks for Development, 2015, pp. 2835-2841.
[23]
Zhang X., Ma S., and Han D., Implementation of elliptic curve Diffie-Hellman key agreement scheme on IRIS nodes, in Proc. Int. Conf. International Conference on Intelligent Computing and Internet of Things, Harbin, China, 2015, pp. 160-163.
DOI
[24]
Digital Signature Standard (DSS), Federal Information Processing Standard Publication 186-3, http://csrc.nist.gov/publications/fips/fips186-3/fip_186-3.pdf, 2009.
[25]
Koblitz N., Elliptic curve cryptosystems, Mathematics of Compution, vol. 48, no. 177, pp. 203-309, 1987.
DOI Google Scholar
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 14 November 2016
Accepted: 06 February 2017
Published: 11 September 2017
Issue date: October 2017

Copyright

© The author(s) 2017

Acknowledgements

This research was supported by the National Natural Science Foundation of China (Nos. 61332019, 61572304, 61272056, and 60970006), the Innovation Grant of Shanghai Municipal Education Commission (No. 14ZZ089), and Shanghai Key Laboratory of Specialty Fiber Optics and Optical Access Networks (No. SKLSFO2014-06).

Rights and permissions

Return