Optimization and Performance Improvement of Elliptic Curve Digital Signature Algorithm (ecdsa)

Optimization and Performance Improvement of Elliptic Curve Digital Signature Algorithm (ECDSA) Shilpa R. Bagde1, Meghana A. Hasamnis 2 Research Scholar Professor 1, 2 Department of Electronics Engineering, Shri Ramdeobaba College of Engineering and Management Nagpur, India, [email protected] , 8390292462 Abstract Securing e-commerce and other online transactions in today’s era of the internet requires authentication which is a necessity. For securing the information cryptography plays an important role in today’s world. Elliptic curve digital signature algorithm (ECDSA) is a crypto algorithm which used for authentication. This paper presents the performance enhancement of the ECDSA algorithm. To improve the performance of the ECDSA algorithm in terms of throughput, the algorithm has been optimized. Optimization reduced the time and complexity of the program. Two optimization techniques “Loop unrolling” and “Strength Reduction” is used to optimize the ECDSA C code, through which the execution speed of the code is improved by 67.39%. C code of ECDSA and Optimized ECDSA converted into hardware by using the Vivado HLS tool. After, converting in hardware code it is implemented on Xilinx ISE 14.5. The results are obtained and the execution time for hardware implementation is improved by 25.75%. Keywords C Code Optimization Techniques, ECC, ECDSA.

I. Introduction In Today’s world, everyone uses the internet, for sending email, online chat, purchasing goods and products over the e-commerce website, their security is most important. Security of the information has the greatest importance in the world in which communication over open networks and storage of data in digital form. cryptography needs occur because, to secure certain things which are our internet passwords, credit card numbers, banking information and business documents getting into the wrong hand's.

The importance of information security has grown because new technologies have made accessing and misusing confidential information easier and more profitable. Personal information is most important but criminal misuses that information and gets profit. To protect the increasing criminal on networks cryptography is required. Cryptography makes the communications secure. It is the art and science which making a cryptosystem that is capable of giving information security. Cryptography deals with the real securing of digital information. It refers to the plan of components based on scientific calculations that give essential information security services. Cryptography permits individuals to keep confidence in the electronic world. It is used in many applications like banking transactions cards, computer passwords, and e-commerce transactions. The advantages of cryptography are:

1. Confidentiality
2. Integrity
3. Non-repudiation
4. Authentication

The cryptography has 2 types, symmetric key cryptography, and asymmetric key cryptography. Symmetric-key Cryptography: In symmetric-key cryptography, the same key is used by both parties. The sender uses this key and an encryption algorithm to encrypt data; the receiver uses the same key and the corresponding decryption algorithm to decrypt the data [2]. AES, DES, RC5 are the examples of Symmetric-key Cryptography. Asymmetric-key Cryptography: Asymmetric cryptography, also known as public key cryptography, uses public and private keys to encrypt and decrypt data. The keys are simply large numbers that have been paired together but are not identical (asymmetric). One key in the pair can be shared with everyone; it is called the public key.

The other key in the pair is kept secret; it is called the private key. Either of the keys can be used to encrypt a message; the opposite key from the one used to encrypt the message is used for decryption [3]. ECC, DSA, ECDSA, RSA are the examples of asymmetric key algorithm II.ECC Algorithm The Elliptical curve cryptography (ECC) is a public key encryption technique based on elliptic curve theory that can be used to create faster, smaller, and more efficient cryptographic keys. ECC generates keys through the properties of the elliptic curve equation instead of the traditional method of generation as the product of very large prime numbers. Because ECC helps to establish equivalent security with lower computing power and battery resource usage, it is becoming widely used for mobile applications [3]. ECC has some additional advantages such as a more compact structure, a lower bandwidth, and faster computation that all make ECC usable in both high-speed and low-resource applications [1]. Due to the better performance of ECC, the Elliptic curve has been adapted for several cryptographic schemes, such as Key agreement scheme: ECDH, Encryption scheme: ECIES, Digital signature scheme: ECDSA. Fig.1. shows the operation perform on the elliptic curve. a) Addition: P + Q = R b)Doubling P + P = R Fig.1 Geometrics addition and doubling of elliptic curve points [1]. III.ECDSA Algorithm In this paper, the ECDSA algorithm used for implementation. The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue of the Digital Signature Algorithm (DSA). It is the most widely standardized elliptic curve-based signature scheme [1]. ECDSA algorithm provides high security, faster computation and lesser processing power, storage space because of its smaller key size. Elliptic curve digital signatures used for software distribution, financial transactions, vehicles, and mobiles. This paper used the digital signature algorithm based on an elliptic curve secp256r1. By using the domain parameters of this curve the ECDSA algorithm is implemented. Key pair generation, Signature generation, and Signature verification, these are the most important part of the ECDSA algorithm. 3.1. ECDSA Key Pair Generation Before an ECDSA authenticator can work, it needs to know its private key.

The public key is derived from the private key and the domain parameters. As the name implies, the private key is not accessible from the outside world. The public key, in contrast, must be openly read accessible. Fig.2 shows the generation of the key pair [4]. Fig.2. Key Pair Generation [4] This step needs one pseudo-random number generator to choose d and one point multiplication to compute Q for more security. For generating Keys sender does the following: Select an elliptic curve E defined over Fp. The number of points in E should be divisible by a large prime n. Select a point generator P € E (a, b) of order n. Select a statistically unique and unpredictable integer d from [1, n - 1]. Compute the point Q= d.P Sender's public key is Q; sender's private key is d. 3.2. ECDSA Signature generation A digital signature allows the variable-length message is converted to a fixed-length message digest H (m) using a secure hash algorithm. After the message digest is computed, a random number generator is activated to provide a value k for the elliptic curve computations [4]. Fig.3 shows the process of signature generation. Fig.3. Signature generation [4] The signature is the set (r, s). To sign a message m, Select a statistically unique and unpredictable integer k from [1, n - 1]. Compute k.P = (x1, y1). Compute r = x1 mod n Compute e = h (m) with e the message digest and h the hash function Compute s = k-l. (e + d.r) mod n 3.3. ECDSA Signature verification The signature verification is the counterpart of the signature computation. Its purpose is to verify the message’s authenticity using the sender’s public key [3]. Fig.4 shows the process of signature verification Fig.4. Signature verification [4] To verify the sender’s signature (r, s) on m, the receiver must compare v and r. If v = r then the signature is identical else it is not identical. Compute e = h (m) Compute ul = e.s-1 mod n Compute u2 = r.s-1 mod n Compute ul.P + u2.Q = (xl, y2) Compute v = x2 mod n Accept the signature if and only if v = r. IV. Software Implementation 4.1. ECDSA Algorithm The ECDSA algorithm written in C language using Dev- C++ 5.11 GCC compiler it has been compiled and run. Fig.5. shows the timing analysis of the ECDSA algorithm Fig.5.Timing analysis of ECDSA Algorithm The key pair of public key and the private key of user 1 and user 2 generated by the use of elliptic curve properties. Using the ECDSA algorithm hash the data. Hashing utilized for the digital signature process where the message is passed through a hash function, with a private key of user 1 and the public key of user 2 generate the signature. The obtained signature is given to user 2, where the user 2 verify the signature using the public key of user 1 and the private key of user 2.

The obtained signature is matched with the received signature, and both are found to be same thus the signature is identical if the signature not matched then the signature is not identical. When by using the same public and private keys of the same user the signature not match, thus it indicates that the algorithm is working properly. 4.2. Optimized ECDSA Algorithm To enhance the performance of the ECDSA algorithm, the optimization techniques Loop unrolling, Strength Reduction, Code Motion, Constant folding, Constant propagation, Dead Code Elimination, Common Sub-Expression Elimination etc. have been studied. According to the expression used in the C code of the ECDSA algorithm loop unrolling and Strength Reduction, these two techniques applied and optimized the C code which increases the speed. 4.4.1 Optimization using loop unrolling Loop unrolling, is also known as loop unwinding, which is a loop transformation technique that attempts to optimize a program's execution speed. It increments the program efficiency and Reduces loop overhead. By the use of loop unrolling technique, the two for loop unrolled of ECDSA algorithm so that code executed rapidly. 4.4.2 Optimization using Strength Reduction It is an optimization technique in which a type of operation is replaced by another type of operation, those operations which are computationally expensive replaced by the simpler ones having an equivalent effect. The C code of the ECDSA algorithm has so many operations of multiplication, addition, inversion etc. In which the addition operation takes less time as compared with multiplication operation hence the multiplication operation replaced by the addition operation. In this paper, the ECDSA C code has 15 expressions which contain multiplication operations hence the multiplication operation is replaced by addition so that the execution speed of the code has increased. The optimization of the ECDSA algorithm using C code optimization techniques has been done. The timing analysis of optimized ECDSA algorithm is shown in Fig.6. Fig.6. Timing analysis of optimized ECDSA Algorithm V. Hardware Implementation To implement the software code into the hardware the high-level synthesis tool is most applicable because it’s converted the c code into hardware. The high-level synthesis improved the productivity and performance of the system. Both the software implemented C code of the ECDSA algorithm is converted into hardware using the Vivado high-level synthesis 14.4 tools. 5.1. Steps for tool and conversion of the ECDSA and Optimized ECDSA Algorithm from C to Verilog 1] Create a new project on Vivado HLS, Add/remove C-based sources files (design specification). 2] Create Vivado HLS solution for selected technology. 3] Open the source from the left side and write ECDSA C code after that save this file. 4] Solution from the upper side tab and select run all active solution. 5] The Solution ’s subfolder Verilog contains generated hardware code in.

Generated hardware code of the ECDSA and optimized ECDSA algorithm implemented. Virtex6 xc6vlx760-2ff1760 is used for implementing the hardware code on Xilinx ISE 14.5 and analyzed the execution time for ECDSA and Optimized ECDSA algorithm. Table .1 shows the Execution Time for ECDSA algorithm. Table 1: Execution Time for ECDSA algorithm ECDSA Algorithm Execution Time Un- Optimized Code 2.768ns Optimized Code 2.055ns VI. Conclusion It has been analyzed that after compiling the ECDSA C code on GCC compiler the algorithm works properly and verified the signature. For performance improvement, the ECDSA algorithm is optimized by using the two C code optimization techniques loop unrolling and strength reduction, thus the execution speed of the optimized algorithm increases. Further, improvement in the performance the C code of both the algorithm converted into the hardware language by using Vivado HLS 2014.4 tool.