Elliptic Curve Cryptography

Abstract-- This paper gives an introduction to elliptic curve cryptography (ECC) and how it is used in the implementation of digital signature (ECDSA) and key agreement (ECDH) Algorithms. The paper discusses the implementation of ECC on two finite fields, prime field and binary field. It also gives an overview of ECC implementation on different coordinate systems called the projective coordinate systems. The paper also discusses the basics of prime and binary field arithmetic. This paper also discusses why ECC is a better option than RSA in modern day systems. This paper also discusses why ECC's unique properties make it especially well suited to smart card applications.

Index Terms--Elliptic Curve Cryptography, Smart Cards, Discrete Logarithm problem

I. INTRODUCTION

Over the past 30 years, public key cryptography has become a mainstay for secure communications over the Internet and throughout many other forms of communications. It provides the foundation for both key management and digital signatures. In key management, public key cryptography is used to distribute the secret keys used in other cryptographic algorithms (e.g. DES). For digital signatures, public key cryptography is used to authenticate the origin of data and protect the integrity of that data. For the past 20 years, Internet communications have been secured by the first generation of public key cryptographic algorithms developed in the mid-1970's. Notably, they form the basis for key management and authentication for IP encryption (IKE/IPSEC), web traffic (SSL/TLS) and secure electronic mail.

In their day these public key techniques revolutionized cryptography. Over the last twenty years however, new techniques have been developed which offer both better performance and higher security than these first generation public key techniques. The best assured group of new public key techniques is built on the arithmetic of elliptic curves. Elliptic Curve Cryptography (ECC) is one of best public key techniques because of its small key size and high security. This paper discusses elliptic curve cryptography and discusses why it is better option than RSA in modern day systems and also why ECC is well suited for smart card applications.

II. MATHEMATICAL CONCEPTS

The mathematical operations of ECC is defined over the elliptic curve

y2 = x3 + ax + b,

Where 4a3 + 27b2 ≠ 0.

Each value of the 'a' and 'b' gives a different elliptic curve. All points (x, y) which satisfies the above equation plus a point at infinity lies on the elliptic curve. The public key is a point in the curve and the private key is a random number. The public key is obtained by multiplying the private key with the generator point G in the curve. The generator point G, the curve parameters 'a' and 'b', together with few more constants constitutes the domain parameter of ECC.

The security of ECC depends on the difficulty of Elliptic Curve Discrete Logarithm Problem. Let P and Q be two points on an elliptic curve such that kP = Q, where k is a scalar. Given P and Q, it is computationally infeasible to obtain k, if k is sufficiently large. k is the discrete logarithm of Q to the base P. Hence the main operation involved in ECC is point multiplication. i.e. multiplication of a scalar k with any point P on the curve to obtain another point Q on the curve.

A. Point Multiplication

In point multiplication a point P on the elliptic curve is multiplied with a scalar k using elliptic curve equation to obtain another point Q on the same elliptic curve i.e. kP=Q

Point multiplication is achieved by two basic elliptic curve operations

* Point addition, adding two points J and K to obtain another point L i.e., L = J + K.

* Point doubling, adding a point J to itself to obtain another point L i.e. L = 2J.

Here is a simple example of point multiplication.

Let P be a point on an elliptic curve. Let k be a scalar that is multiplied with the point P to obtain another point Q on the curve. i.e. to find Q = kP.

If k = 23 then kP = 23.P = 2(2(2(2P) + P) + P) + P.

Thus point multiplication uses point addition and point doubling repeatedly to find the result. The above method is called 'double and add' method for point multiplication. There are other efficient methods for point multiplication such as NAF (Non - Adjacent Form) and wNAF (windowed NAF) method for point multiplication.

B. Point Addition

Point addition is the addition of two points J and K on an elliptic curve to obtain another point L on the same elliptic curve.

1) Geometrical Explanation

Fig 1. Point Addition

Consider two points J and K on an elliptic curve as shown in figure (a). If K ≠ -J then a line drawn through the points J and K will intersect the elliptic curve at exactly one more point -L. The reflection of the point -L with respect to x-axis gives the point L, which is the result of addition of points J and K.

Thus on an elliptic curve L = J + K.

If K = -J the line through this point intersect at a point at infinity O. Hence J + (-J) = O. This is shown in figure (b). O is the additive identity of the elliptic curve group. A negative of a point is the reflection of that point with respect to x-axis

2) Analytical Explanation

Consider two distinct points J and K such that J = (xJ, yJ) and K = (xK, yK)

Let L = J + K where L = (xL, yL), then

xL = s2 - xJ - xK

yL = -yJ + s (xJ - xL)

s = (yJ - yK)/(xJ - xK), s is the slope of the line through J and K.

If K = -J i.e. K = (xJ, -yJ) then J + K = O. where O is the point at infinity.

If K = J then J + K = 2J then point doubling equations are used.

Also J + K = K + J

C. Point Doubling

Point doubling is the addition of a point J on the elliptic curve to itself to obtain another point L on the