Keywords

Android Applications, Digital Signatures, Elliptic Curve Cryptography, Multisignature Scheme, Two Key Signature Scheme 
INTRODUCTION

Digital signatures play a vital role in the security of information and communication networks by providing message integrity, authentication and nonrepudiation during transmission over any insecure or hostile network based on the public key cryptography. A digital signature or digital signature scheme is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, and that it was not altered in transit. The property of message integrity guarantees that the receiver detects any alteration of the message during transmission, and the authentication property ensures the message generation by an expected sender. Compared with these two properties, the nonrepudiation property is equally important, which assures that after creating a signature, the signer cannot deny the signature generation at a later time. However, this scheme becomes less secure in cases where only one person is involved in signing an application. An approach that allows more than one person to sign the application is needed in the digital signature certification environment.Also current technological trends have improved much towards the attacking the older signature schemes. Thus improved signature schemes that make an attacker difficult to hack the signature are needed. Here the combined features of Certificate less Multisignature scheme (SK Hafizul Islam *, G.P. Biswas, 2013) and Two key Signature Scheme (N. Anil Kumar ,ChakravarthyBhagvati, 2012) are used to solve above issues 
PRELIMINARIES

Simplified Weierstrass equation for elliptic curve is 
where a, b, x and y belongs to some field with Let P and Q be two points on the elliptic curve. The line joining the two points will intersect the curve at the third point say R. The addition of points is defined asP + Q + R = identity To make elliptic curve addition a group, identity is defined to be a point at infinity denoted as O or ∞. A line is said to pass through point at infinity when it is exactly vertical. 
Let P, Q and R be the points on the elliptic curve then the following holds. 
• P+Q will be point on the curve (Closure property) 
• P+Q=Q+P (Commutative property) 
• P+Q will be point on the curve (Closure property) 
• (P+Q) +R=P+(Q+R) (Associativity property) 
• P+O=O+P=P (Existence of an identity element) 
• There exist (P) such that (−P) + P = P + (−P)= (O) (Existence of inverse) Scalar multiplication is defined a repeated addition. 
Let n be integer,nP= P + P +Ln……… times 
The points on the elliptic curve form an abelian group. 
Let P(x1,y1) Q(x2,y2)=R (x3,y3)then 
X3=m2x1x2 and y2=m(x1x3)y1 
Where M= (y2y1) / (x2x1) for P≠Q 
=(3x1^{2}+a) / 2y1 for P=Q 
The elliptic curve arithmetic which has been defined over real numbers can also be defined over finite fields. Most of the definitions over real numbers can be carried over to finite fields. 
Let q = p^{k} where p is prime. q F is the G also is field of order q. Let E be the elliptic curve. The set of points on the elliptic curve E (Fq)is 

ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM

The Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue of the Digital Signature Algorithm (DSA). We refer to this as one key ECDSA. It is the most widely standardized elliptic curvebased signature scheme, appearing in the ANSI X9.62, FIPS 1862, IEEE 13632000 and ISO/IEC 159462 standards as well as several draft standards [4, 5]. 
The Domain parameters D = (q, FR, S, a, b, P, n, h) are comprised of 
1. The field order q. 
2. An indication FR (Field Representation) of the representation used for the elements ofFq. 
3. A seed S if the elliptic curve was randomly generated. 
4. Two coefficients a, b Ã¯Â¿Â½Ã¯Â¿Â½Fqthat define the equation of the elliptic curve E over q F (i . e in the case of a prime field and in case of binary field). 
5. Two field elements p x and p y in q F that define a finite point P=(xp,yp) Ã¯Â¿Â½Ã¯Â¿Â½E(Fq)in affine coordinates. P is called the base point. 
6. The order of P is n. 
7. The cofactor h = #E (Fq ) /n . 
In the following, H denotes a cryptographic hash function whose outputs have bit length no more than that of n (if this condition is not satisfied, then the outputs of H can be truncated). 
A. ECDSA Signature Generation 
Input: Domain parameters D = (q, FR, S, a, b, P, n, h), private key d, message m. 
Output: Signature (r, s). 
B. ECDSA Signature Verificatio 
Input: Domain parameters D = (q, FR, S, a, b, P, n, h), public key Q, message m, signature (r, s). 
Output: Acceptance or rejection of the signature. 
1. Verify that r and s are integers in the interval [1,n1]. If any verification fails then return (“Reject the signature”). 
2. Compute e = H(m). 
3. Compute w = S^{1}mod n. 
4. Compute u1=ewmod n and u2= rwmod n. 
5. Compute X =U1 P+ U2 Q. 
6. If X = ∞ then return (“Reject the signature”). 
7. Convert the xcoordinate x1 of X to an integer x1’. Compute v = x1’mod n. 
8. If v = r then return (“Accept the signature”); Else return (“Reject the signature”). 
C. Proof That Signature Verification Works 
If a signature (r, s) on a message m was indeed generated by the legitimate signer, then S ≡ kÃ¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½(e + dr) mod n Rearranging gives 
K ≡S^{1}(e + dr) 
≡S^{1}e + S^{1}rd (mod n) 
≡ we + wrd 
≡ (u1 + u2) d (mod n) 
Thus X = u1P + u2Q = (u1 + u2)d =kp. 
Sov = r as required. 
TWO KEY ECDSA

The domain parameters D = (q, FR, S, a, b, P, P1, R n, h) are same as the original ECDSA except P1 and R. P1 is another base point. 
Let d and d1 be the private keys, d1P + d P1 = R1 anddP= QwhereP, P1 and R are the public parameters. H defines the hash function as in ECDSA. 
A. Two Key ECDSA Signature Generation 
Input: Domain parameters 
D = (q, FR, S, a, b, P, P1, R, n, h) private key d and d1, message m. 
Output: Signature (x1,s1,s2). 
1. Select k1 and k2Ã¯Â¿Â½Ã¯Â¿Â½R [1, n1] 
2. Compute (kP+ kP) = SxyIf S = ∞ goto step 1. 
3. Compute e = H(m). Convert the field element 1 x to an integer x (usually the first coordinate in the vector representation) 
4. Let s = ek+ x and s = ek+ xd. 
5. Return (x1,s1,s2). 
B. Two key ECDSA Signature Verification 
Input: Domain parameters 
D = (q, FR, S, a, b, P, P1, R, n, h) 
public key P,Q, P1, R message m, signature ( x1,s1,s2 ) 
Output: Acceptance or rejection of the signature. 
1. Compute e = H(m). 
2. Compute u1 = s1P + s2P1 . 
3. Computey1 and y1′fromx1 using curve equation. 

4. Compute u2 =eT +x1R. 
5. Ifu1 = u2 accept the signature, else 
If u2= eT + x1R accept the signature. 
6. Else reject the signature. 
C. Proof That the Signature Verification Works 
If a signature (x1,s1,s2) on a message m was indeed generated by the legitimate signer, then 
s1P + s2P1= (ek1 + x1d1)P1 + (ek2 + x1d1)P 
= e(dP+ d1P1) + x1( k1P + k2P2) 
=eT+ x1 R. 
MULTI SIGNATURE APPROACH

Multisignature approach is the process of signing an application or document by more than one signer. Here the signature by each signer is represented by Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½and it is generated by the two key ECDSA method proposed above. This makes the signature more selfsecured than other ordinary signature methods. 
A. Signing Algorithm 
In order to generate a sequential short multisignature for a given message mÃ¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½{0, 1}*, each signer Ai(1≤i≤n)performs the following operations: 
Step 1: The signer A1 
(a) Computes Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½=x1H2(m) + D1. 
(b)Sends the messagesignature pair(m,Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½)to the next signerA2. 
Step 2: The signerA2 
(a) Verifies (m,Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½) by determining whether the equation ê(Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½,P)=ê(H2(m),P1)ê(Q1,P0) holds. 
(b) If it holds, A2 computes Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½ = Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½+ x2H2(m) + D2 i.e.Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½=x1H2(m) + x2H2(m) + D1 +D2 and then sends (m,Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½) to the signer A3. Similarly, the signer A3 fghhisigns and sends to A4 and so on up to An2 to An1. All sequentially compute their signatures and complete the multisignature process. 
Step n: The last signer An 
(a) Verifies (m,Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½n1) received fromby determiningwhether the equationê(Ã¯Â¿Â½Ã¯Â¿Â½nÃ¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½Ã¯Â¿Â½,P) – 

C.Verification Algorithm 
In order to verify (m, r), the following steps are to be executed by the verifier: 


D.Correctness of theMultisignature Scheme 
The received messagesignature pair (m, r) is accepted bythe verifier since the following holds: 



PROPOSED APPROACH

To make the digital signature seem too hard to break and to simultaneously maintain the simplicity of such algorithm combined efficiency of above two methods has been proposed. This includes signing a single application by more than one authority. Each signer should use two key ECDSA methodology of digital signature to sign the application. This method thus removes complexities or issues arose when signed by only one signer 
COMPARISON OF ECDSA, TWO KEY ECDSA AND COMBINED APPROACH

The brute force method to attack the ECDSA is to find d (private key) from public key Q and domain parameter P which satisfy the relationship Q=d P. The order of P is n so to find Q we have to check n possibilities. So the time complexity is O(n). The brute force method to attack the Two key ECDSA is to find d and d1 (private keys) from P1, P and S which satisfy the relationship dP + d1*P1 = S. The order of P is n1 and order of P1 is n2. To find S we have to check n1×n2 possibilities. So the time complexity is O( n1 × n2 ). 
The brute force attack for combined approach of multisignature and two key ECDSA involves the finding of d & d1 private keys of Signer An, then same for An1upto An and thus for each pair of keys to be found, the complexity is O(n1 xn2) thus accounting a total complexity of O(n x n1 x n2) where n is the number of signers. Thus usage of multiple signatures makes it practically impossible to crack the code in finite period of time within which the application is valid. Also, the signer has the option to choose between multiple signature and single signature. 
CONCLUSION

The method proposed above is thus an efficient method that can be used for signing any application which is more vulnerable. Thus it can be a best suit for android as well as other applications. It not only makes an application harder to crack but also brings out a means for signing an application by more than one authority still leaving the signing mechanism less complex than the other ones.The method can be applied to any type of application signing processes. 
Figures at a glance





Figure 1 
Figure 2 
Figure 3 
Figure 4 

References

 N. Anil Kumar, ChakravarthyBhagvati “Two Key Signature Scheme with Application to Digital Certificates” in 1st Int’l Conf. on Recent Advances in Information Technology  RAIT2012.
 Islam, S.H., Biswas, G.P., “Certificateless short sequential and broadcast multisignature schemes using elliptic curve bilinear pairings” in Journal of King Saud University – Computer and Information Sciences (2013).
 Chu, H., Zhao, Y., 2008. Two Efficient Digital MultisignatureSchemes. In: Proceedings of the International Symposium onComputational Intelligence and Design (ISCISD’08), pp. 258–261.
 V. Miller, “Use of elliptic curves in cryptography,” Lecture notesin computer sciences; 218 on Advances in cryptology—CRYPTO 85, pp. 417–426, 1986.
 Chen, T.S., Huang, K.H., Chung, Y.F., 2004. Digital multisignaturescheme based on the elliptic curve cryptosystem. J.Comput. Sci. Technol. 19 (4), 57570–573.
 N.Anil Kumar, R.Tandon and ChakravarthyBhagvati, “Modifiedelliptic curve digital signature algorithm,” In Proceedings of theInternational Conference o on Mathematics and Computer Science2009, Vol: 1, pp: 304306, 2009.
