An Efficient and Provably Secure Digital Signature Scheme Based on [PDF]

International Journal of Computational and Applied Mathematics. ISSN 1819-4966 Volume 12, Number 1 (2017), pp. 45-52 © Research India Publications http://www.ripublication.com

An Efficient and Provably Secure Digital Signature Scheme Based on Elliptic Curve Jayabhaskar Muthukuru* Department of CSE, K L University, Vaddeswaram, Guntur District, Andhra Pradesh, India.

Abstract Digital Signature plays a vital role in various transactions of e-commerce for authentication. Elliptic Curve Digital Signature Algorithm (ECDSA) is the new form of Digital Signature Algorithm (DSA), which ensures higher security and performance with smaller key size, compared with other form of DSA. ECDSA security is based on complexity of solving discrete logarithm over an elliptic curve. This paper portrays a new digital signature scheme based on elliptic curves with better performance and high security. Keywords: Digital Signature, Elliptic Curve, Elliptic Curve Digital Signature, ECDSA, man-in-the-middle, known message attack

1. INTRODUCTION Digital signatures are an alternate form for hand written signatures in electronic communication or transactions for safety and security. Elliptic Curve Digital Signature Algorithm (ECDSA) is counterpart of Digital Signature (DS) based on Elliptic Curve. Elliptic Curve Digital Signature Algorithm was introduced by Scott Vanstone in the year 1992 [1] in response to NIST’s (National Institute of Standards and Technology) proposal. The strength per key bit is significantly greater in an algorithm that applies elliptic curves which does not possessing sub exponential time algorithm due to this factor Elliptic Curve

* Corresponding author. E-mail address: [email protected]

Jayabhaskar Muthukuru

46

Digital Signature Algorithm (ECDSA) provides high security. Faster computation and lesser processing power, storage space and bandwidth are accomplished by ECDSA because of its smaller key size [15]. A man-in-the-middle (MITM) attack is a form of attack which is used to modify the communication between sender and receiver without their knowledge. Thus while sending message the developer has to take more concern on this attack [14]. The private key is very essential for secure transactions, provided if it is confidential. An attack which retrieves the private key with the help of signature elements of known messages is called known message attack and it can be illustrated as: Let (r,s1) and (r,s2) be the signature elements of the messages m1 and m2 respectively, where r is obtained by using random number. In signature elements if the first component (r) is identical then the same random number is used and other components (s1 & s2) are different which indicates two different messages were involved. In this kind of scenarios, the attacker can easily retrieve the private key by using transformations technique [13].

2. LITERATURE SURVEY The Many researchers have been studied the security and performance of ECDSA and proposed variant digital signatures based on Elliptic Curve (EC), over the past one and half decade. Some of the major contributions to the study of ECDSA are: 2.1. Scott Vanstone (1992) [1] introduced a digital signature scheme based on Elliptic Curve. 2.2. John Malone-Lee et al.(2003) [2] proposed modified form of ECDSA which over comes duplicate signature related concerns. 2.3. Hung-Zih Liao et al.(2006) [3] presented a new form of ECDSA which can be used for signing different messages by using same secret key. 2.4. Tilahun Kiros et al.(2009) [4] and Shweta L et al (2013) [10] proposed two different forms of ECDSA model based on efficiency in terms of time complexity. 2.5. M.Prabu et al.(2009) [5] proposed a high security digital signature scheme on EC by using two secret keys. 2.6. Junru, H (2011) [6] proposed two different signature schemes which reduces computational cost, one in generation and the other in verification with the same security concerns. 2.7. Qiuxia Z et al.(2011) [7] presented ECDSA using Elliptic Curve Cryptography which provides significant security. 2.8. Neetesh Saxena et al. (2013) [8] proposed a variant ECDSA in the context of SMS(Short Message Services) security. 2.9. Jayabhaskar M et al. (2013) [9] presented an ECDSA scheme without inverse operation to improve the performance. 2.10. Sindhu B et al. (2016) [11] presented a secure digital signature scheme based on EC for IOT (Internet of Things).

3. SECURITY ANALYSIS I have applied known message attack and Man in middle attack on ECDSA schemes which were studied in previous section. In this section I present possible attack on the above ECDSA schemes. Following schemes suffer with known message attack, which is described when the same secret key k is used for signing two different messages m1 and m2.The signature elements of m1and m2 are s1 and s2 respectively.

An Efficient and Provably Secure Digital Signature Scheme Based on Elliptic Curve 3.1. Scott Vanstone Scheme [1] s1=k-1 *(e1 + x * r)

(1)

s2=k-1 *(e2 + x * r)

(2)

From equations (1) and (2) the private key x can be obtained as x = (e2*s2-1 - e1*s1-1)/(s1-1 - s2-1)*r

3.2. John Malone-Lee et al. Scheme [2] s1 = (e1 + x*r)*k-1 s2 = (e2 + x*r)*k

(3)

-1

(4) where e1=H(m1||r) and e2=H(m2||r)

From equations (3) and (4) the private key x can be obtained as x = (e2*s2-1 - e1*s1-1)/(s1-1 - s2-1)*r

3.3. Hung-Zih Liao et al. Scheme [3] s1=k-1 *(e1*k1+x*(r+r1))

(5)

s2=k-1 *(e2*k2+x*(r+r2))

(6)

From equations (5) and (6) the private key x can be obtained as x= (s2-1 * e2*k2-s1-1* e1*k1)/(s1-1 * (r+r1) - s2-1*(r+r2))

3.4. M Prabu et al. Scheme [5] s1=k-1 *(e1*k1+x*(r*r1))

(7)

s2=k-1 *(e2*k2+x*(r*r2))

(8)

Proceeding similarly from equations (7) and (8) x= (s2-1 * e2*k2 - s1-1* e1*k1)/(s1-1 * (r*r1) - s2-1*(r*r2))

3.5. Junru H Schemes [6] I am presenting attacks on the two forms of Junru, H signature schemes. First form of Junru H Scheme: s1=x-1(r*k-e1) -1

s2=x (r*k-e2)

(9) (10)

Proceeding similarly from equations (9) and (10) x=(e2-e1)/(s1-s2) Second form of form of Junru H Scheme: s1= k*(e1+rx)-1

(11)

-1

(12)

s2= k*(e2+rx)

47

Jayabhaskar Muthukuru

48 Proceeding similarly from equations (11) and (12) x = (s2*e2 - s1*e1)/ r*(s1-s2)

3.6. Neetesh Saxena et al. Scheme [8] s1= k-1(e1*k1+(r+r1)*x)

(13)

s2= k-1(e2*k2+(r+r2)*x)

(14)

Proceeding similarly from equations (13) and (14) x = (s2*e2*k2 - s1*e1*k1)/(s1*(r+r1) - s2*(r+r2)) The Middle Man can easily alter or replace the message that cannot be recognized by the receiver, by simply appending the hash value. Let m1 be Middle Man‘s message, which is alter/replaced the original message m, having the hash values e1 and e respectively. The schemes proposed by Tilahun Kiros et al.[30], Shweta L et al.[36] are suffering from this attack as explained below.

3.7. Tilahun Kiros et al. Scheme [4] s=e+k+d Calculate s1 = e + k + d – e +e1 where s1 is Middle Man’s signature element.

3.8. Shweta L et al. Scheme [10] s = (e * x) * k-1

s1= (((e * x) * k-1)*e-1)*e1 where s1 is Middle Man’s signature element. 4. PROPOSED SIGNATURE SCHEME BASED ON EC In this article I proposed a new signature scheme based on EC, which is more secure and efficient in performance.

4.1. Key Generation The public key Q is computed using generating point G and random integer number x as follows 1) Choose a random integer number x in interval [0, n-1]. 2) Compute Q = x* G 3) The key-pair is (x, Q) where x is the Private Key and Q is the Public key. 4.2. Signature Generation To sign on message m using the domain parameter and private key, the signer has to proceeds the following steps. 1. Chooses a random integer k with 1≤ k ≤ n −1.

An Efficient and Provably Secure Digital Signature Scheme Based on Elliptic Curve

49

2. Compute e = H(m) 3. Compute p = (ek) where  is Exclusive OR operator 3. r = x-coordinator(p*G) 4. Compute s = (e*x) + p mod n. If s = 0 then return to step 1. 5. Signature for the message m is (r, s). 4.3. Signature Verification For verification or authentication of the message m, I suggested the following steps to the receiver. 1. First verify that s is integer in the interval [1, n −1] 2. Compute the hash value e of the message/document m 3. Compute the point W = (x2, y2) = s*G – e*Q 4. v = x-coordinate(W), finally, authenticate the signature by checking whether the equivalence v = r holds. 4.4. Proof: W=s*G–e*Q = ((e * x) + p) * G – e * Q =e*x*G+p*G–e*Q =e*Q+p*G–e*Q =p*G X-coordinator (W) = x-coordinator(p * G) v=r 5. COMPARATIVE STUDY In this section I studied the comparison of proposed signature scheme security with variant ECDSA schemes and presented in Table 1. Table 1. Comparison of various schemes security

Scheme

Known Message Attack

Man-in-Middle- Attack

Scott Vanstone Scheme [1]

Yes

No

John Malone-Lee et al. Scheme [2]

Yes

No

Jayabhaskar Muthukuru

50 Hung-Zih Liao et al. Scheme [3]

Yes

No

Tilahun Kiros et al. Scheme [4]

No

Yes

M.Prabu et al. Scheme [5]

Yes

No

Junru, H Scheme -1 [6]

Yes

No

Junru, H Scheme -2 [6]

Yes

No

Qiuxia Z et al. Scheme [7]

No

No

Neetesh Saxena et al. Scheme [8]

Yes

No

Jayabhaskar M et al. Scheme [9]

No

No

Shweta L et al. Scheme [10]

No

Yes

Sindhu B et al. Scheme [11]

No

No

Proposed Scheme

No

No

6. COMPUTATIONAL COST The Elliptic Curve point multiplication and point addition respectively needs 29 and 0.12 units in terms of time complexity of a modular multiplication (TMUL), where as Modular inverse requires 0.073 TMUL and cost of addition operation is negligible as mentioned by Morteza Nikooghadam et al. [12]. The computational cost for signing and verification of variant schemes under study and proposed scheme are calculated and presented in table-2 and table-3.

Required Computation cost in terms of Multiplication(TM LL)

Modular Multiplication (MUL)

Modular inverse (INV)

Scheme

Elliptic Curve Point Multiplication (ECPM) Elliptic Curve Point Addition (ECPA)

Table 2. Computational cost for signature generation of various schemes.

Scott Vanstone Scheme [1]

1

0

1

2

31.073

John Malone-Lee et al. Scheme [2]

1

0

1

2

31.073

Hung-Zih Liao et al. Scheme [3]

2

0

1

3

61.073

Tilahun Kiros et al. Scheme [4]

1

0

1

2

31.073

M.Prabu et al. Scheme [5]

2

0

1

4

62.073

Junru, H Scheme -1 [6]

1

0

1

1

30.073

Junru, H Scheme -2 [6]

1

0

1

2

31.073

Qiuxia Z et al. Scheme [7]

2

0

0

3

61

An Efficient and Provably Secure Digital Signature Scheme Based on Elliptic Curve

51

Neetesh Saxena et al. Scheme [8]

2

0

1

2

60.073

Jayabhaskar M et al. Scheme [9]

2

0

0

2

60

Shweta L et al. Scheme [10]

1

0

1

2

31.073

Sindhu B et al. Scheme [11]

3

0

1

4

91.073

Proposed Scheme

1

0

0

1

30

7.

Conclusions

In this paper I compared my proposed scheme with variant ECDSA schemes. Table 1 and Table 2 results illustrates that the proposed scheme is secured and it provides better performance in signing when compare with variant signing schemes respectively. Shweta L et al. signature scheme suffers lack of security even though it has better performance in verification than the proposed scheme; the results were shown in table 3.

Required Computation cost in terms of Multiplication(TMLL)

Modular Multiplication (MUL)

Modular inverse (INV)

Elliptic Curve Point Addition (ECPA)

Elliptic Curve Point Multiplication (ECPM)

Scheme

Table 3. Computational cost for signature verification of various schemes.

Scott Vanstone Scheme [1]

2

1

1

2

60.193

John Malone-Lee et al. Scheme [2]

2

1

1

2

60.193

Hung-Zih Liao et al. Scheme [3]

2

1

1

3

61.193

Tilahun Kiros et al. Scheme [4]

2

1

1

2

60.193

M.Prabu et al. Scheme [5]

2

1

1

3

61.193

Junru, H Scheme -1 [6]

2

1

2

2

60.266

Junru, H Scheme -2 [6]

2

1

0

2

60.12

Qiuxia Z et al. Scheme [7]

2

1

1

0

58.193

Neetesh Saxena et al. Scheme [8]

2

1

2

3

61.266

Jayabhaskar M et al. Scheme [9]

2

1

0

1

59.12

Shweta L et al. Scheme [10]

1

0

1

0

29.073

Sindhu B et al. Scheme [11]

2

1

0

0

58.12

Proposed Scheme

2

1

0

0

58.12

Jayabhaskar Muthukuru

52 REFERENCES [1] [2] [3] [4] [5] [6]

[7] [8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Vanstone S. A.: Responses to NIST’s Proposal. Communications of the ACM. 1992. John Malone-Lee, Nigel P. Smart: Modifications of ECDSA. Springer LNCS. 2003: 1-12. Hung-Zih Liao, Yuan-Yuan Shen: On the Elliptic Curve Digital Signature Algorithm. Tunghai Science. 2006; 8: 109-126. Tilahun Kiros, Kumudha Raimond: An Efficient Modified Elliptic Curve Digital Signature Algorithm. Journal of EEA 2009; 26:65-72. M.Prabu, R.Shanmugalakshmi: An Efficient Variant Signature Scheme on ECDSA. ICoMMS 2009:11-13. Junru, H: The Improved Elliptic Curve Digital Signature Algorithm. International Conference on Electronic & Mechanical Engineering and Information Technology;2011;,Harbin;2011: 257-259. Qiuxia Z, Zhan L, Chao S: The implement of Digital Signature Algorithm Based on Elliptic Curve Cryptography. IEEE 2011:1689-1691. Neetesh Saxena, Narendra S. Chaudhari, Jaya Thomas: Solution to An Attack on Digital Signature in SMS Security. 5th International Conference on Modeling, Simulation and Applied Optimization; Apr-2013; Hammamet, Tunisia; IEEE 2013:28-30. Jayabhaskar Muthukuru, B. Sathyanarayana: A Secure Elliptic Curve Digital Signature Approach without Inversion. International Journal of Engineering and Advanced Technology 2013; 3,(2):454-456. Shweta Lamba, Monika Sharma: An Efficient Elliptic Curve Digital Signature Algorithm (ECDSA). International Conference on Machine Intelligence Research and Advancement;2013;IEEE 2013:179-183. B.Sindhu, Dr.R.M.Noorullah: Secure Elliptic Curve Digital Signature Algorithm for Internet of Things. Global Journal of Computer Science and Technology 2016;16(3): 27-30. Morteza Nikooghadam, Ali Zakerolhosseini: An Efficient Blind Signature Scheme Based on the Elliptic Curve Discrete Logarithm Problem. The ISC Int'l Journal of Information Security 2009:125-131. O.S.Adebayo,V.O.Waziri,J.A.Ojeniyi, S.A.Bashir,Amit Mishra: Information Security On The Communication Network In Nigeria Based On Digital Signature. International Journal of Computer Science and Information Security 2012; 10(11):57-63. Amit K Awasthi: On the Authentication of the User from the Remote Autonomous Object. International Journal of Network Security 2005;1(3):166-167. Darrel Hankerson, Alfred Menezes and Scott Vanstone: Guide to Elliptic Curve Cryptography. Springer; 2004.