 Open Access
 Total Downloads : 1614
 Authors : P. K. Sahoo, Dr. R. K. Chhotray, Dr. Gunamani Jena, Dr. S. Pattnaik
 Paper ID : IJERTV2IS1419
 Volume & Issue : Volume 02, Issue 01 (January 2013)
 Published (First Online): 30012013
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
An Implementation Of Elliptic Curve Cryptography
1 P. K. Sahoo
1Professor, Department of Computer Science Engineering, St. Martins Engineering College, Hyderabad500014, (AP), India.,
2 Dr. R. K. Chhotray
2 Professor, Department of Computer Science Engineering, NIT Rourkela, Odisha 769008, India
3 Dr. Gunamani Jena
3 Professor, Department of Computer Science Engineering, BVCEC (JNTUK) AP 533210, India
4 Dr. S. Pattnaik.
4 Professor, P.G.Department of Information
& Communication Technology, F.M. University, Vyasa Vihar, Balasore, Odisha 756019, India,
Abstract
The internet is slowly becoming an increasingly dangerous mode of communication for all forms of highly sensitive data. The increased dependency by individuals, institutions and corporations over the Internet to carry out critical business processes have provided a playing field for the intruders to carry out different attacks on the system and on the network. The security to critically confidential information such as personal identity information, credit card details, online transactions and ecommerce is the need of the hour which depends on top of cryptography. It is thought that RSA is a very secure cryptography algorithm and almost all software products provide advanced data encryption are designed over it. The bit length for RSA has increased over the years to make the encryption very tough, which increases the processing time and storage requirement is the real concern for today. The objective of this paper is to propose an alternative algorithm for cryptography based on mathematical objects
known as elliptic curves. The proposed algorithms provide a better security with shorter bit length than RSA. Hence elliptic curve cryptography is the only solution today where better security can be achieved with a smaller key size thereby reducing the processing overhead.

INTRODUCTION

Introduction to cryptography
The term cryptography is derived from the Greek word Kryptos. Kryptos is used to describe anything that is hidden, veiled, secret or mysterious. Cryptography is the art and science of hiding information in a systematic order such that only the authorized parties have access to the correct information. Cryptography is the study of mathematical techniques for the secure transmission of a private message over an insecure channel. Cryptography is defined as the study of secret writing that concerns the ways, in which communications and data can be encoded to prevent disclosure of their contents through eavesdropping or message interception, using codes, ciphers and other methods, so that only certain people can see the real message. Cryptography is used to encrypt data residing on storage devices or traveling through communication channels in order to ensure that any illegal attempt to access the data is not successful. Cryptography also
used to secure the process of authentication of different parties, who are trying to use any function on the system.

The social aspects of cryptography
In an age of explosive worldwide growth of electronic data storage and communications, many vital national interests require the effective protection of critical information. The Internet has now become the main mode of data communication and critical infrastructure for firms to carry out critical business processes. Although Internet offers several potential benefits, including improved efficiency, productivity and convenience with reduced costs, it exposes firms to new level of risks such as security breaches. The risk is more pronounced for private companies, where loss of important data could mean a tremendous advantage for the competitor. Even among the companies, the threat to pharmaceutical companies is far more serious where intellectual properties of drugs are always prone to theft. Everyone is vulnerable. However, if I have to rank in terms of merit, the IT/BPO sector has the highest standards of security because of the pressure of foreign countries, followed by banks and then telecom, says Kamlesh Bajaj, CEO, Data Security Council of India and former head of Certin [1]. In 2010, as tensions rose between the West and Iran over the Irans nuclear plants, an internet worm called Stuxnet, was discovered at Irans nuclear enrichment centre at Natanz. The worm was attacking the computers that controlled the centre, by taking over the control of the centrifuges at the plant. It was partially successful. The worm then escaped the nuclear plant and spread over the internet, infecting computers worldwide. India was the third most affected country, with 8.31 per cent computers affected, following Iran (58.85 per cent) and Indonesia (18.22 per cent). According to the security firm Sophos around 453491 email passwords were posted online by hacker group D33DS Company. In the biggestever series of cyber attacks uncovered, hackers are found to have broken into networks of the Indian government, the united nations and the U.S defense companies. Seventytwo organizations, including major US defense groups, have been victims of the cyber attack that began in 2006, making it one of the largest concerted hacking attempts in the history. The long list of victims in the five year cyber attack campaign include the government of US, India, Taiwan, South Korea, Vietnam and Canada; the Association of Southeast Asian Nations (ASEAN); the international Olympic committee (IOC), the world AntiDoping Agency, Us
energy Department labs as well as agencies and companies in Denmark, Germany, Indonesia and Singapore. The hackers also broke into the computer system of UN secretariat in Geneva in 2008, accessing the secret data for nearly two years [2]. In todays era of the ubiquitous computing, the Internet has become the main mode of data communication. Most of the devices used in wireless mobile environments, that from wireless networks, adhoc networks and wireless sensor networks etc. have low computational power and memory. In such a Pervasive Computing environment, providing security to data becomes a complex task [3]. There are constant occurrences of Internet security problems due to rapid development [4]. The table 1 given below shows the various security attacks from 2004 to 2010.
Table 1 shows the details of the various attacks from 2004 to 2010.
Security Incidents
2004
2005
2006
2007
2008
2009
2010
Phishing
3
101
339
392
604
374
508
Network Scanning
/Probing
11
40
177
223
265
303
477
Virus/M alicious Code
5
95
19
358
408
596
1817
Spam
—
—
—
—
305
285
981
Malware Propagat ion
—
—
—
—
835
6548
6344
Others
4
18
17
264
148
160
188
Total
23
254
552
1237
2565
8266
1031
5

Types of cryptography
In private key cryptography both the sender and the receiver share the same key, that must be kept private. In order to communicate with each other, the key must be passed between them; the process is known as key distribution. The concept of publickey cryptography evolved from an attempt to attack two of the most difficult problems associated with the conventional encryption. The first problem is that of key distribution and the second problem is that of digital signatures. The publickey cryptography is asymmetric involving the use of two separate keys, in contrast to symmetric conventional encryption, which uses only one key. The public key system eliminates the key distribution process that hampers all private key systems since there is no need to communicate
secret keys among communicating parties. A public key cryptosystem is an asymmetric cryptosystem where each party has two sets of keys; the key is constructed of a public key and a private key. The public key, known to all, can be used to encrypt messages where as the other is kept secret and only known to the owner, the private key. Only a person that has the corresponding private key can decrypt the message. In a publickey cryptographic scheme, a key pair is selected so that the problem of deriving the private key from the corresponding public key is equivalent to solving a computational problem that is believed to be intractable. Numbertheoretic problems whose intractability forms the basis for the security of commonly used publickey schemes are:

The integer factorization problem, whose hardness is essential for the security of RSA publickey encryption.

The discrete logarithm problem, whose hardness is essential for the security of the ElGamal publickey encryption and signature schemes and their variants such as the Digital Signature Algorithm (DSA).

The elliptic curve discrete logarithm problem, whose hardness is essential for the security of all elliptic curve cryptographic schemes.


Key length and encryption strength
Breaking an encryption algorithm is basically finding the key to access the encrypted data in plain text. For symmetric algorithms, breaking the algorithm means trying to determine the key used to encrypt the text. For public key cryptography breaking the algorithm means accessing the secret information that shared between the two recipients. The key strength of an algorithm is determined by finding the fastest method to break the algorithm and comparing it to a brute force attack. Encryption strength is often described in terms of size or length of the keys used to perform the encryption, longer keys generally provides stronger encryption. As an example the 128bit RC4 encryption is 3*1026 times stronger than 40bit RC4 encryption. An encryption key is considered full strength if the best known attack to break the key is no faster than a brute force attempt to test every key possibility. As it is relatively trivial to break an RSA key, an RSA publickey encryption cipher must have
a very long key, at least 1024 bits, to be considered cryptographically strong.

RSA algorithm and cryptography
In 1977 Shamir, Rivest and Adelman proposed the first publickey cryptosystem called RSA as a principal object for publickey cryptography. RSA is known as the best algorithm for digital signatures and publickey cryptography. The RSA cryptosystem is an official standard worldwide. The International Organization for Standardization (ISO) 9796 standard lists RSA as a compatible algorithm as ITUT X.509 security standard. The RSA is the official standard of Society for Worldwide Interlake Financial Telecommunications (SWIFT). X9.44 draft standard for the US banking standard and French Financial Industrys ETEBAC 5 Standard also accepted RSA cryptography. The RSA cryptography algorithm also built into current operating systems such as Microsoft, Apple, Sun and Novell.

Comparison between RSA and ECC
The best known algorithm for digital signatures and publickey cryptography is RSA (Rivest, Shamir & Adleman). Even though RSA is highly secure and widely used, there are many problems in its implementation. The security of RSA is thought to be equivalent to the problem of factorizing the modulus n and the size of an RSA key usually is a function of the number of bits in the modulus. The bruteforce attack over RSA can be easily overcome by increasing the key size but decryption time increases 8fold as key size double. The threat to larger key sizes is twofold: the continuing increase in computing power and the continuing refinement of factoring problem [5]. Because RSA is based on modular arithmetic with very long operands, the performance of RSA is quite slow on limited environments with low memory and processor power. Also, because there has been some progress on the factorization problem, the key sizes that are considered to be secure today are relatively long. Commonly used key size for RSA is 1024bits. The entire processing time increases significantly as key size increase. Compared to RSA, the prevalent publickey scheme of the Internet today, Elliptic Curve Cryptography (ECC) offers smaller key sizes, faster computation as well as memory, energy and bandwidth [6]. The elliptic curve cryptography appears to offer equal security level for a far smaller key size, thereby reducing processing overhead. It is generally accepted that a 160bit elliptic curve key provides the same level of security as a 1024bit RSA key. The key advantages that can be gained from smaller key sizes include speed and efficient use of power, bandwidth and storage [7]. The celebrated RSA cryptosystem is the most largely deployed
cryptosystem but things are becoming to change. More and more applications propose to use the elliptic curve digital signature algorithm (ECDSA) to sign digital documents or messages [8]. In February 2005, the National Security Agency in the United States released a document known as Suite B, to recommend the use of Elliptic Curve cryptography as the basis for all cryptographic algorithms. It indicates that the current RSA cryptography is becoming more susceptible to attacks and hence is slowly becoming outdated. Many national and international organizations have acknowledged the use of elliptic curve as an official standard for cryptography. The International Organization for Standardization (ISO) has issued ISO 15946 (Information technology, Security techniques, Cryptographic techniques based on elliptic curves) Part 1 (General) , Part2 (Digital Signatures) ; Part 3 (Key Establishment) , ISO 14888 (Information technology, Security techniques, Digital Signatures with appendix) Part 3 (Discrete logarithm based techniques) [912]. The American National Standard Institute (ANSI) also standardized the use of elliptic curves such as X9.62 (Public Key Cryptography for the Financial Services Industry, The Elliptic Curve Digital Signatures Algorithm (ECDSA) and X9.63 (Public Key Cryptography for the Financial Services Industry, Key Agreement and Key Transport Using Elliptical Curve Cryptography) [13]. The Institute of Electrical and Electronics Engineers (IEEE) has also issued P1363 (Standard Specifications for Public Key Cryptography) and P1363a amendment of P1363 as the standard for the use of elliptic curves [14]. The development of elliptic curve cryptography is the greatest and perhaps the only true revolution in the entire history of cryptography. To quote, Lang it is possible to write endlessly on Elliptic Curves (This is not a threat) [15].

Introduction to Elliptic Curve Cryptography
Even though elliptic curves cryptography (ECC) has been studied for more than a hundred years, their practical aspect in public key cryptography was independently invented by Koblitz and Miller in 1984 [1617]. Since then elliptic curve cryptography (ECC)
has drawn more attention of different research communities. Because of the hardness of the elliptic curve discrete logarithm problem over that of other public key cryptographic algorithms, such as RSA and ElGamal Elliptic Curve Cryptosystems (ECCs) have been recently attracting increased attention [18]. Originally pursued mainly for aesthetic reasons, elliptic curves have recently become a tool in several important applied areas, including coding theory, pseudorandom bit generation; digital certificates in web server authentication and number theory algorithms. The elliptic curve cryptography appears to offer equal security level for a far smaller key size, thereby reducing processing overhead. It is generally accepted that a 160bit elliptic curve key provides the same level of security as a 1024bit RSA key.
Table 2: Shows parameter keysizes for comparable strength of ECC and RSA
Elliptic Curve Cryptography Key Size
RSA KeySize
KeySize Ratio
106 bits
512 bits
1:4
132 bits
768 bits
1:5
160 bits
1024 bits
1:6
224 bits
2048 bits
1:9
256 bits
3072 bits
1:12
384 bits
7680 bits
1:20
The table 2 shown above is the comparison between the Elliptic Curve Cryptography and RSA in terms of key size for the same security level.
Elliptic curve cryptography (ECC) is a public key cryptography system superior to the well known RSA cryptography: for the same key size, it gives a higher security level than RSA [19].

Mathematical Backgrounds of ECC
Elliptic curves are not ellipses. The name is given as elliptic curves because these are described by cubic equations, similar to those used for calculating the circumference of an ellipse. The cubic equations for elliptic curves are of the form y2 + axy + by=x3 +cx2
+dx + e, where a, b, c, d and e are real numbers that satisfy some simple conditions.
Y axis
Curves of this Nature are called Elliptic Curves
X axis
Elliptic curve cryptographic algorithms are implemented using point operations on the Elliptic curve: Addition, doubling a point and scalar multiplication. The basic mathematics required to understand elliptic curves cryptography is discussed below.

MODULAR ARITHMETIC
Given any positive integer n and any nonnegative integer a, if we divide a by n, we get an integer quotient q and an integer remainder r that follows the below relation
A=qn + r 0 r < n; q=[a / n] and r= a mod
n. Two integers a and b are said to be congruent modulo n, if (a mod n) = (b mod n). This is written as a b (mod n). Modular arithmetic fixes an integer n
> 1 called the modulus. The fundamental operation in the context of modular arithmetic is the reduction modulo n.

GROUPS
Let G be a nonempty set and * be a binary operation on G. A group G sometimes denoted by < G, * > is a set of elements with a binary operation denoted by *, that associates to each ordered pair (a, b) of elements in G an element (a * b) in G, such that the following axioms are hold:

Associative: a* (b*c) = (a*b)*c for all a, b, c in G.

Identity element: there is an element e in G such that a*e=e*a=a for all a in G.

Inverse element: for every a in G, there is an element a in G such that a*a=a*a=e.

Closure: if a and b belongs to G, then a*b also belongs to G.

A group G is said to be commutative or abelian if ab=ba for all a, b in G.
3.4.1 CYCLIC GROUPS
A group G is said to be cyclic if there exists an element g in G such that every element a of G is an integral power of g, that is a is of the form gn for some integer n. Then the element g is called a generator of the group. For any element a in G, we define the integral power of a as: a0 =e, a1=a, a2 =a*a, a3 =a*a*a. A cyclic group G generated by g is represented by < g >.

FINITE FIELDS
A field F, sometimes denoted by {F, +, *}, is a set of elements with two binary operations, called addition and multiplication, such that for all a, b, c in F the followings are hold
1. +: F Ã— FF and *: F Ã— FF.



(F, +) is an abelian group. 3. (a + b) * c = a * c + b * c.
4. (F,\ {0}, *) is an abelian group.
A finite field is a field with finitely many elements. It is denoted by GF(p) or Fp. It is a fundamental theorem of the theory of finite fields, that a finite field of p = qm elements exists if and only if p is a
prime power that is q is prime and m is an integer with m 1.
Then Fp = {0, 1, 2,, p1) denote the set of integers modulo p, where p is a prime number. Then (Fp, +), where the operation + is defined to be addition of integers modulo p, is a finite additive group of order p with (additive) identity element 0. In addition to this, for a given prime power p there exist essentially only one finite field Fp. In Cryptography applications, two classes of fields are commonly used. They are as follows:

Prime fields: GF(p) or Fp, where p is prime.

Binary fields GF(2m), where m is large.
In elliptic curve cryptography, we are concerned with a restricted form of elliptic curve that is defined over a finite field.

ELLIPTIC CURVES OVER FINITE FIELD ( Fp)
Let E be an elliptical curve over Fp. From the point of view of cryptography we are interested in elliptic curve group mod p, where p is a prime number. Then E may be described as 4a3 + 27b2 (mod p) 0, where a and b are two positive integers less than the prime number p. Then Ep (a, b) denotes the elliptic group mod p, whose elements (x, y) are pairs of positive integers less then p satisfying y2 x3 + ax + b(mod p) together with the point at infinity O. As an example, if E is an elliptic curve over F7 describing by the equation y2=x3+2x+4, then the points on E are E(F7)={, (0,2), (0,5), (1,0), (2,3), (2,4), (3,3), (3,4),
(6,1), (6,6)}. Now there is a wellknown method for adding two elliptic curve points (x1, y1) and (x2, y2) to produce a third point on the elliptic curve.

Security Level Test by Certicom Pvt. Ltd
Much like the RSA challenge, the Certicom Elliptic Curve Cryptography (ECC) challenge offers prize money for finding various key sizes of the ECDLP. The current record was set in November 2002 where a 109bit encryption key was broken with 10,000 computers running 24 hours a day for 549 days. The Certicom ECC challenge website reports that breaking a 163bit key, which is the standard applied to most commercial ECC applications that Certicom uses, would be a hundred million times harder than breaking the 109bit key. It is worthy to note that a 160bit ECC key has about the same level of security as a 1024bit RSA key. The comparison in key lengths of RSA, DSA and ECC are shown in the graph (Fig 2) below. In RSA a public key is constructed by multiplication of two very large
primes. To completely break RSA one needs to find the prime factors. Clearly, ECC keys take much more effort to break compared to RSA and DSA keys. Due to this, many people believe that ECDLP is intrinsically harder than the other two problems. The most important difference between ECC and other conventional cryptosystems is that for a wellchosen curve, the best method currently known for solving the ECDLP is fully exponential, while sub exponential algorithms exist for conventional cryptosystems.
Figure 2: shows comparative study of ECC and RSA/DSA
As shown in the above figure 2 clearly roved that the algorithm based on Elliptic Curve Cryptography takes much more time to break as compared to algorithm based on RSA and DSA for the same key size. The security of Elliptic Curve Cryptography depends on how much difficult it is to determine k given the value of kP and P. Hence Elliptic Curve Cryptography is fully exponential.

ELLIPTIC CURVE CRYPTOGRAPHY

ELLIPTIC CURVE KEY GENERATION
Let E be an elliptic curve over finite field Fp. Let P be a point on E (Fp) and suppose that P has prime order n. Then the cyclic subgroup of E (Fp) generated by P is <P>= {, P, 2P, 3P.(n1)P}. The prime p, the equation of the elliptic curve E, and the point P and its order n are the public domain parameters. A private key is an integer d that is selected uniformly at random from the range [1, n1], and the corresponding public key is Q=d*P.
Algorithm 1 Elliptic curve key pair generation
Input: Elliptic curve domain parameters (p, E, P, n).
Output: Public key Q and private key d.

Select d R [1, n1].

Compute Q= d*P.

Return (Q, d).


ELLIPTIC CURVE ENCRYPTION/DECRYPTION

The first task is to encode the plain text message m to be sent as an xy point Pm. It is the point Pm that will be encrypted as a cipher text and subsequently decrypted. To encrypt and send a message Pm to B, A chooses a random positive integer k and produces the cipher text Cm = {kP, Pm + k Q}, where Q is Bs public key. The sender transmits the points C1= kP, and C2= Pm + k Q to the recipient. To decrypt the cipher text, B multiplies the first point in the pair by Bs secret key and subtract the result from the second point as Pm + k Q d (kP) = Pm + k (dP) – d (kP)= Pm.
Algorithm 2 Elliptic curve encryption
Input: Elliptic curve domain parameters (p, E, P, n), public key Q, Plain text m.
Output: Cipher text Cm.

Represent the plain text m as a point Pm in E (Fp).

Select k R [1, n1].

Compute C1= K*p

Compute C2= Pm + k*Q.

Return (C1, C2).
Algorithm 2 Elliptic curve decryption
Input: curve domain parameters (p, E, P, n), private key d, Cipher text Cm.
Output: Plain text m.

Compute Pm = C2dC1.

Return (Pm).

CONCLUSION
The potential hackers are using Internet as a platform to perform various attacks over the network, the system and the society as a whole. There are continuous report of tempering of individuals confidential information and organizations vital data. Security related threats are becoming disrupting and more damaging day by day and becoming the headlines for news papers and magazines. Hence providing strong security to critically sensitive data is the need of the hour. The most popular RSA algorithm is slowly becoming outdated because of its processing overhead and time complexity. Hence the only solution in public key cryptosystem is Elliptic curve cryptography, where a higher degree of security can be achieved with a smaller key size with a much less processing overhead. This paper demonstrates implementing Elliptic curve cryptography over finite fields for providing better security to critical data with less processing overhead.

REFERENCES
2004.
[7]. Darrel Hankerson, Alfred J Menezes, Scott Vanstone, Guide to elliptic curve cryptography, ISBN 038795273X. [8]. S Qing, D Gollmann and J Zhou, ICICS, pages 348359, 2003. [9]. ISO/ IEC 1594612008, (Information Technology, Security techniques, Cryptographic techniques based on elliptic curves) Part 1: General, 2008. [10]. ISO/ IEC 1594622002, (InformationTechnology, Security techniques, Cryptographic techniques based on elliptic curves) Part 2:
Digital Signatures, 2002
[11]. ISO/ IEC 1594632002, (InformationTechnology, Security techniques, Cryptographic techniques based on elliptic curves) Part 3: Key Establishment, 2002.
[12]. ISO/ IEC 1488832006, (InformationTechnology, Security techniques, Digital Signatures with appendix) Part 3: Discrete logarithm based Mechanisms, 2006.
[13]. ANSI X9.63. Public Key Cryptography for the Financial Services Industry: Key Agreement and Key Transport Using Elliptic Curve Cryptography, 2001.[14]. IEEE P1363, Standard Specifications for Public Key Cryptography, 2000.
[15]. Lang, Serge, Elliptic curve: Diophantine Analysis, SpringerVerlag, New York, 1978. [16]. N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, vol. 48, Pages 203209, 1987. [17]. V. S. Miller, Use of elliptic curves in cryptography, in CRYPTO 85: Proceedings of the Advances in cryptology, vol. 218 of Lecture notes in computer sciences, (New York, NY, USA),Pages 417426, Springer Verlag New York, Inc., 1986. [18]. Hankerson, D., Menezes, A. and S. Vanstone, Guide to Elliptic Curve Cryptography, 1st edition, Springer, ISBN13: 9780387952734, 2004. [19]. L. Batina, S. B. Ã–rs, B. Preneel, and J. Vandewalle, Hardware architectures for public key cryptography, Integration, the VLSI Journal, vol. 34, Pages 164, 2003. [20]. N. Nguyen, K. Gaj, D. Caliga, and T. El Ghazawi, Implementation of elliptic curve cryptosystems on a reconfigurable computer, Proceedings of IEEE Field Programmable Technology, Pages 6067, 2003.