See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/272162532 Implementation of ElGamal Elliptic Curve Cryptography over prime field using C Conference Paper · February 2014 DOI: 10.1109/ICICES.2014.7033751 CITATIONS 3 READS 188 1 author: Monjul Saikia North Eastern Regional Institute of Science … 29 PUBLICATIONS 34 CITATIONS SEE PROFILE Available from: Monjul Saikia Retrieved on: 04 August 2016ICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE Implementation of ElGamal Elliptic Curve Cryptography Over Prime Field Using C Debabrat Boruah Department of Computer Science & Engineering NERIST, Nirjuli-791109, Arunachal Pradesh, India [email protected] Monjul Saikia Department of Computer Science & Engineering NERIST, Nirjuli-791109, Arunachal Pradesh, India [email protected] Abstract— Elliptic Curve Cryptography recently gained a lot of attention in industry. The principal attraction of ECC compared to RSA is that it offers equal security for a smaller key size, thereby reducing processing overhead. There is no sub exponential time algorithm in solving the Elliptic curve discrete logarithm problem. ElGamal Elliptic Curve Cryptography is a public key cryptography analogue of the ElGamal encryption schemes which uses Elliptic Curve Discrete Logarithm Problem. The ElGamal Elliptic Curve Cryptosystem is implemented using C language in our work. We divided the whole cryptosystem into seven different phases. The paper also describes different efficient algorithms used in the implementation to perform various mathematical manipulations. Keywords– ElGamal; Elliptic Curve Cryptography; Finite field; public key; Encryption; Decryption. I. INTRODUCTION Cryptography is the science of protecting information by encrypting them into unreadable format, called cipher text. Only those who possess a secret key can decipher (or decrypt) the message into plaintext. Public-key cryptography and symmetric-key cryptography are two main categories of cryptography. Symmetric Key scheme requires sharing of a secret key between the parties who want to make communications. This secret key is used in both encryption and decryption processes. On the other hand Public Key schemes use different keys for encryption and decryption. Public key cryptography contains two keys, which are public and private keys. Only the particular user knows the private key whereas the public keys are distributed to all users taking part in the communication. The well-known public-key cryptography algorithms are RSA (Rivest, et al. 1978)[3], ElGamal and Elliptic Curve Cryptography[5]. In 1976, Diffie Hellman introduced the concept of public key cryptosystem by describing a public key distribution scheme. The security of this scheme based on intractability of discrete logarithm problem in the multiplicative group of a large finite field. On the other hand the strength of RSA[3] lies in integer factorization problem. That is when we are given a number; we have to find its prime factors. It becomes quite complicated when dealing with large numbers. This is the strength of RSA and to an extent, is the disadvantage associated with it. In 1985, ElGamal made use of discrete logarithm problem to construct a practical public key cryptosystem with security equivalent to Diffie Hellman scheme. Although the discrete logarithm problem referred explicitly to the problem of finding logarithm respect to a primitive element in the multiplicative group of the field modulo a prime p, this idea can be extended to other arbitrary groups with the difficulty of the problem varying with representation of the group. So the cryptosystem ElGamal can be generalized to an arbitrary finite cyclic group. In 1985, Kobiltz[2] and Miller[1] independently proposed the implementation of public key cryptosystem using elliptic curve group over finite field which is known as Elliptic curve cryptography(ECC). This elliptic curve forms finite cyclic group so that the elliptic curves groups over finite field can be used to implement ElGamal public key cryptosystem. ElGamal Elliptic Curve Cryptography is a public key cryptography analogue of the ElGamal encryption schemes which uses Elliptic Curve Discrete Logarithm Problem. Elliptic curves discrete logarithm problem appear to be much harder than the discrete logarithm problem in other groups(DSA) and integer factorization problem(RSA). Hence elliptic curve cryptosystem can match the security of other cryptosystems while using smaller key. For example an elliptic curve cryptosystem with public key of size 160 bits is as secure as RSA and DSA cryptosystems with public key of size 1024 bits. With smaller key size, elliptic curve cryptosystem can offer lower memory requirement, faster implementation and lower bandwidth requirement. There are lots of research works going on in recent years on the ECC. The ElGamal ECC implementation described in [4] and [5] mainly focuses on the elliptic curve point manipulations for encryption and decryption over finite fields. ECC encryption and decryption process can only encrypt and decrypt a point on the curve and not messages. The encoding (converting message to a point), decoding (converting a point to a message) and public key validation are important functions in encryption and decryption in ECC. In this paper we have described different algorithms and their implementation for the proposed ElGamal Elliptic Curve Cryptosystem in C programming language. The paper discusses Koblitz's method to represent a message to a point and vice versa which is used in our cryptosystem.ICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE II. ELLIPTIC CURVE CRYPTOGRAPHY Elliptic Curve Cryptography (ECC) is a public key cryptography. In public key cryptography each user or the device taking part in the communication generally have a pair of keys, a public key and a private key, and a set of operations associated with the keys to do the cryptographic operations. Only the particular user knows the private key whereas the public key is distributed to all users taking part in the communication. Some public key algorithm may require a set of predefined constants to be known by all the devices taking part in the communication. 'Domain parameters' in ECC is an example of such constants. Public key cryptography, unlike private key cryptography, does not require any shared secret between the communicating parties but it is much slower than the private key cryptography. Understanding ECC needs full mathematical background on elliptic curves. The general cubic equation of elliptic curves is y2+axy+by=x3+cx2+dx+e. But for our purpose it is sufficient to limit the equation to the form y2 = x3 + ax +b where 4a3 + 27b2  0. Let E p(a,b) be the set consisting of all the points (x,y) that satisfy the above equation together with element at infinity O. An abelian group can be defined based on the set Ep(a,b) over addition operation for specific values of a and b[8]. If P,Q and R are points on Ep(a,b) the relations commutativity, associativity, existence of an identity element and existence of inverse hold good[8]. Such a group can then be used to create an analogue of the discrete logarithm problem which is the basis for ElGamal public key cryptosystems. Each value of the 'a' and 'b' gives a different elliptic curve. The public key is a point in the curve and the private key is a random number in the interval [1, n-1],'n' is the curve's order. The public key is obtained by multiplying the private key with the generator point G in the curve. The generator point G is the point on the curve. The generator point G, the curve parameters 'a' and 'b', together with few more constants constitutes the domain parameters of ECC. III. ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM 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. But it is relatively easy to find Q where k and P are known. k is the discrete logarithm of Q to the base P. Thus, point multiplication is the basic operation in ECC. For example, the multiplication of a scalar 'k' with any point 'P' on the curve in order to obtain another point 'Q' on the curve. IV. FINITE FIELDS Generally in mathematics elliptic curve operations are defined over real numbers. However, operations over the real numbers are inaccurate and slow due to round off errors, whereas cryptographic operations need to be accurate and fast. To make operations on elliptic curve accurate and more efficient, the curve cryptography is defined over two finite fields: Prime field F p and Binary field F2m The field is chosen with finitely large number of points suited for cryptographic operations. In our work we have implemented elliptic curve over Prime finite field for the ElGamal Elliptic Curve Cryptosystem. So the following discussions will be bound to the elliptic curves over prime finite field only. The operations in these sections are defined on affine coordinate system [12]. Affine coordinate system is the normal coordinate system that we are familiar with in which each point in the coordinate system is represented by the vector (x, y). A. Elliptic Curve on Prime field Fp: The equation of the elliptic curve on a prime field Fp is y 2 mod p= x3 + ax + b mod p, where 4a3 + 27b2 mod p  0. p is a prime number. Here the elements of the finite field are integers between 0 and p – 1. All the operations such as addition, subtraction, division, multiplication involves integers between 0 and p – 1. This is modular arithmetic. The prime number p is chosen such that there is finitely large number of points on the elliptic curve to make the cryptosystem secure. SEC[1] specifies curves with p ranging between 112 to 521 bits. B. Point Multiplication Scalar point multiplication is a block of all elliptic curve cryptosystems. It is an operation of the form k.P. 'P' is a point on the elliptic curve and 'k' is a positive integer. Computing k.P means adding the point 'P' exactly k-1 times to itself, which results in another point 'Q' on the same elliptic curve. Point multiplication uses two basic elliptic curve operations: a) Point addition (add two points to find another point) b) Point doubling (adding point P to itself to find another point) For example to calculate kP=Q if k is 23 then kP=23P=2(2(2(2P) + P) + P) + P so to get the result, point addition and point doubling is used repeatedly. The above method of point multiplication which uses point addition and point doubling repeatedly to find the result is known as 'double and add' method. There are other efficient methods for point multiplication such as NAF (Non – Adjacent Form) and Binary NAF method for point multiplication. In our work we have used NAF as well as Binary NAF methods for point multiplication. C. Point Addition: Consider two distinct points P and Q such that P = (x1, y1) and Q = (x2, y2). Let R = P + Q where R = (x3, y3), then x3= Ȝ2 – x1 – x2 mod p y3 = Ȝ(x1 – x3)-y1 mod pICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE Ȝ = (y2 – y1)/(x2 – x1) mod p, Ȝ is the slope of the line through P and Q. If Q = -P i.e. Q = (x1, -y1 mod p) then P + Q = O. where O is the point at infinity. If Q = P then P + Q = 2P then point doubling equations are used. Also P + Q = Q +P. Figure 1: Addition of two points on the elliptic curve. Consider P and Q be two different points on the elliptic curve E as shown in fig1. Since we are crossing a line with a cubic curve, the line that connects P and Q must intersect through a third point on the curve; the point is noted as -R. Another point called R will be resolved from the reflection of this point -R in the x-axis, where R = P+Q. D. Point Doubling Figure 2: Point Doubling Consider a point P in the elliptic curve such that P = (x1, y1), where y1  0. Let R = 2P where R = (x2, y2), then x2 = Ȝ2 – 2x1 mod p y2 = Ȝ(x1 – x2) -y1 mod p Ȝ = (3x12 + a) / (2y1) mod p, Ȝ is the tangent at point P and a is one of the parameters chosen with the elliptic curve. If y1 = 0 then 2P = O, where O is the point at infinity. To double a point P on the elliptic curve, a tangent line to the curve and passing by P is taken as shown in fig2. The line must cross the curve through another point; the point is noted as -R. Then we reflect the point –R in the x-axis to the point R where R=2P. E. Point Subtraction Consider two distinct points P and Q such that P = (x1, y1) and Q = (x2, y2). Then P - Q = P + (-Q) where -Q = (x2, -y2 mod p).Point subtraction is used in certain implementation of point multiplication such as NAF. V. MODULAR ARITHMETIC Modular arithmetic over a number p involves arithmetic between numbers 0 and p – 1. If the number happens to be out of this range in any of the operation the result is wrapped around into the range 0 and p – 1. A. Addition Let p = 23, a = 15, b = 20 a + b (mod p) = 15 + 20 (mod 23) = 35 mod 23 = 12 Since the result of a + b = 35 which is out of the range [0,22], the result is wrapped around into the range [0,22] by subtracting 35 with 23 till the result is in range [0,22]. a mod b is thus explained as remainder of division a/b. B. Subtraction Let p = 23, a = 15, b = 20 a - b (mod p) = 15 - 20 (mod 23) = -5 mod 23 = 18 Since the result of a - b = -5 which is negative and out of the range [0,22], the result is wrapped around into the range [0,22] by adding -5 with 23 till the result is in range [0,22]. C. Multiplication Let p = 23, a = 15, b = 20 a * b (mod p) = 15 * 20 (mod 23) = 300 mod 23 = 1 Since the result of a * b = 300 which is out of the range [0,22], The result is wrapped around into the range [0,22] by subtracting 300 with 23 till the result is in range [0,22]. D. Division The division a/b (mod p) is defined as a * b-1 (mod p).b-1 is the multiplicative inverse of b over p. E. Multiplicative Inverse Multiplicative inverse of number b with respect to mod p is defined as a number b-1 such that b*b-1 (mod p) = 1. The algorithm such as Extended Euclidean algorithm[12][8] can be used to find the multiplicative inverse of a number efficiently. Finding multiplicative inverse is a costly operation. F. Finding x mod y x mod y is the remainder of the division x/y. Finding x mod y by repeatedly subtracting y with x till the result is in range [0,y-1] is a costly operation. Methods such as Barrett Reduction[15] can be used to find modulus of a number in efficient manner. VI. ELLIPTIC CURVE DIFFIE-HELLMAN (ECDH) KEY EXCHANGEICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE ECDH operates by providing the two parties sharing a secret key with a public key, which in this case is a point P on elliptic curve E. Alice performs scalar multiplication using this point P and a random number a, which is the secret key of Alice. a.P now becomes public key of Alice which she can share with the other party. On the other end, Bob performs scalar multiplication using point P and a random number of his choice i.e. b, which is secret key of Bob. b.P becomes public key of Bob which he shares with Alice. Alice performs scalar multiplication of public key of Bob(b.P) with her secret key a to get a.b.P. Bob also does the same with his secret key b and public key of Alice(a.P) to get the same a.b.P. This entity i.e. a.b.P is same for both the parties and is their shared key. VII. ECC DOMAIN PARAMETERS OVER FP As stated earlier the domain parameters are the parameters or constants to be agreed upon or known by all the devices taking part in cryptosystem [7]. Elliptic curve domain parameters over the prime finite field Fp can be described by one sextuple: T=(p,a,b,G,n,h) 'p': the prime number that defines the field and at the same time decides the curve form; 'a' and 'b': define the curve y2 mod p= x3 + ax + b mod p and is chosen depending on the security requirement; G: the generator point, G = (xG, yG), one element in E(Fp), which has the largest order n; n: the order of G, large prime; Order of a point G on the curve can be defined as a value n such that nG = G+G+....upto n times = O(Point at infinity). 'h': if #E(Fp) is the number of points on an elliptic curve then 'h' is the cofactor where h=#E(Fp)/n. VIII. ELGAMAL ELLIPTIC CURVE CRYPTOSYSTEM Generally we have two entities in the process of encryption and decryption. The one at the encryption side(Let us assume: Alice) and the other at the decryption side(Let us assume: Bob) Now Alice wants to send a message to Bob securely. The implementation of the ElGamal Elliptic Curve Cryptosystem can be divided into seven different phases which are explained below. A. System Setup: Setting up an elliptic curve cryptosystem requires both the entities to select and agree upon a) the same set of ECC domain parameters, i.e. the underlying finite field F p, the elliptic curve coefficients 'a' and 'b' for an appropriate elliptic curve, the generator point G in the curve, the order of G i.e. n and the cofactor h=#E(Fp)/n. b) the same set of algorithms for representing the elliptic curve points and implementing the elliptic curve operations in the chosen finite field. B. Key Generation: The next step is to generate the public and private key pair by both entities. Algorithm for key generation: a) Select a random number k from the interval[1,n-1]; b) Compute Q=k*G; 'k' is the private key and 'Q' is the public key. Suppose the private key and public key pair of Alice is (ka,Qa) and the same of Bob is (kb,Qb). C. Public Key Validation When receiving other's public key(say Q), the entity needs to take the following steps to validate the public key's legitimacy. a) Check that QO, the point at infinity ; b) Check that (xQ,yQ)∈Fp, where xQ and yQ denote the x-coordinate and y-coordinate of point Q. c) Check that Q lies on the elliptic curve defined by a and b; d) Check that n*Q=O, the point at infinity. (as n*Q=n*k*G=k*n*G=k*O=O where G's order is n) The public key validation without Step 3 is called the partial public-key validation. Without Step 4, the entity could be attacked. However, we can carefully select h to reduce the threat. D. Message Encoding (Representation of Message into Elliptic Curve Point): ECC Encryption and Decryption methods can only encrypt and decrypt a point on the curve not messages. Unfortunately, there is no known polynomial time algorithm for finding a large number of points on an arbitrary curve. We are not simply looking for random points on E, here. We want a systematic way of finding points on Ep(a,b) relating somehow to the plaintext message. Therefore, we are forced to use probabilistic algorithms to do this, where the chance of failure is acceptably small. Thus Encoding (message to a point) and Decoding (point to a message) methods are important while Encryption and Decryption. Let us suppose a text file has to be encrypted. All the points on the elliptic curve can be directly mapped to an ASCII value, select a curve on which we will get a minimum of 128 points(due to 8-bits in the ASCII character), so that we fix each point on the curve to an ASCII value. For example, 'ENCRYPT' can be written as sequence of ASCII characters that is '69' '78' '67' '82' '89' '80' '84'. We can map these values to fixed points on the curve. This is the easiest method for embedding a message but less efficient in terms of security. The method proposed by Koblitz represents a message as a point or a set of points on an elliptic curve. We used this method for message encoding which is given bellow: Suppose E is an elliptic curve given by y2 mod p= x3+ ax + b mod p over a field Fp where p is a large prime. Using the following steps a message can be mapped to elliptic curve points. a) Divide the message into blocks of fixed size. Express each block as number x. (For example, if the alphabet consists of the digits 0,1,2,3,4,5,6,7,8,9 and the letters A,B,C,. . . , X,Y,Z coded as 10,11,. . . , 35. This converts the message into a series of numbers between 0 and 35 where the block size is 1 character. We can also take the ASCII values of the characters.) b) Compute Į=x³+ax+b mod p. c) Compute į=Į(p-1)/2 mod p. d) If į 1 set x = x + 1, go to step b).ICICES2014 - S.A.Engineering College, Chennai, Tamil Nadu, India ISBN No.978-1-4799-3834-6/14/$31.00©2014 IEEE e) Compute the square root ȕ of Į mod p (We used Las Vegas Algorithm); f) Set y=ȕ. g) The point Pm=(x, y) represents the particular block of the message. E. Encryption a) Alice gets Bob's public key (Qb). b) Alice checks the validity of Bob's public key using the method discussed above. c) Then she selects a random number r where r∈ [1,n - 1] compute C1= r*G where G is the generator point. d) Compute C2= r*Qb +Pm, where Pm is the output elliptic curve point from message encoding algorithm given above. C=(C1,C2) is the ciphertext pair of points for the plaintext point Pm and is sent to Bob. F. Decryption a) Bob computes M=kb*C1 where kb is his private key. b) Computes Pm = C2– M, because C2– M=C2-kb*C1 = r*Qb +Pm – kb*r*G = r*kb*G + Pm – kb*r*G=Pm. c) The point Pm is the representation of the message block. G. Message Decoding(Representation of Elliptic Curve Point into Message): a) Consider each point Pm= (x,y) and set m to be the greatest integer less than x. Then the point (x,y) decodes as the symbol m. b) Convert m to message. IX. ALGORITHMS USED FOR C IMPLEMENTATION A. Algorithm 1- Binary Inversion Algorithm: This algorithm computes the inverse of a non-zero field element 'a' belongs to [1,p-1] using a variant of the Extended Euclidean Algorithm (EEA)[12][8]. The algorithm maintains the invariants Aa + dp = u and Ca + ep = v for some d and e which are not explicitly computed. The algorithm terminates when u = 0, in which case v = 1 and Ca + ep= 1, hence C = a-1 mod p. Input: Prime p, a∈ [1,p - 1] Output: a-1 mod p 1. uĸa; vĸp; Aĸ1; Cĸ0; 2. While u0 do: 3. While u is even do: 4. uĸu/2; 5. If A is even then:AĸA/2; 6. Else:A ĸ(A + p)/2; EndIf; 7. EndWhile; 8. While v is even do: 9. vĸv/2; 10. If C is even then:CĸC/2; 11. Else:Cĸ(C + p)/2; EndIf; 12. EndWhile; 13. If u•v then: uĸu – v; A ĸA - C; 14. Else: v ĸv – u; CĸC – A; 15. EndIf; 16. EndWhile; 17. Return(C); B. Algorithm 2- Barrett Reduction: In modular arithmetic, Barrett reduction [15] is a reduction algorithm introduced in 1986 by P.D. Barrett. Input: b the "base" of the integers used, p, k = floor(logbp) +1, x:0” x