The Construction of ElGamal over Koblitz Curve

Abstract:

Recently elliptic curve cryptosystems are widely accepted for security applications key generation, signature and verification. Cryptographic mechanisms based on elliptic curves depend on arithmetic involving the points of the curve. it is possible to use smaller primes, or smaller finite fields, with elliptic curves and achieve a level of security comparable to that for much larger integers. Koblitz curves, also known as anomalous binary curves, are elliptic curves defined over F2. The primary advantage of these curves is that point multiplication algorithms can be devised that do not use any point doublings. The ElGamal cryptosystem, which is based on the Discrete Logarithm problem can be implemented in any group. In this paper, we propose the ElGamal over Koblitz Curve Scheme by applying the arithmetic on Koblitz curve to the ElGamal cryptosystem. The advantage of this scheme is that point multiplication algorithms can be speeded up the scalar multiplication in the affine coodinate of the curves using Frobenius map. It has characteristic two, therefore it’s arithmetic can be designed in any computer hardware. Moreover, it has more efficient to employ the TNAF method for scalar multiplication on Koblitz curves to decrease the number of nonzero digits. It’s security relies on the inability of a forger, who does not know a private key, to compute elliptic curve discrete logarithm.

• Periodical: Advanced Materials Research (Volumes 931-932)
• Pages: 1441-1446
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.931-932.1441
• Online since: May 2014
• Authors: Krissanee Kamthawee*, Bhichate Chiewthanakul
• Keywords: ElGamal Cryptosystem, Elliptic Curve, Finite Field, Koblitz Curve, Scalar Multiplication

References

[1] N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48: 203209, (1987).

[2] V. MILLER. Uses of elliptic curves in cryptography. Lecture Notes in Computer Science (CRYPTO '85), 218: 417 426, (1986).

DOI: 10.1007/3-540-39799-x_31

[3] W. Trappe, L. C. Washington. Introduction to Cryptography with Coding Theory, second ed. Pearson Prentice Hall, (2006).

[4] I. F. Blake, G. Seroussi, and N. P. Smart. Elliptic curves in cryptography. London Mathematical Society Lecture Note Series, Cambridge University Press, Cambridge, 265, (2000).

[5] FIPS 186-2, Digital signature standard (DSS), Federal Information Processing Standards Publication, 186, U. S. Dept, of Commerce/National Institute of Standards and Technology, (2000).

DOI: 10.6028/nist.fips.186-2

[6] D. Hankerson, A. Menezes and S. Vanslone. Guide to Elliptic Curve Cryptography. SpringerVerlag, (2004).

[7] S. C. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic signicance. IEEE Transactions on Information Theory, 24: 106110, (1978).

DOI: 10.1109/tit.1978.1055817

[8] D.R. Stinson. Cryptography Theory and Practice, third ed. Chapman and Hall/CRC, (2006).

[9] J. Hoftein, J Pipher, J. H. Silverman. An Introduction to Mathematical Cryptography. SpringerVerlag, (2008).

[10] D.S. Dummit, R. M. Foote. Abstract Algebra, third ed. John Wiley and Sons, Inc., (2004).

[11] W. Stein. Sage: Open Source Mathematics Software version 5. 12. The Sage Group, (2013).