INTRODUCTION
The term digital signature was referred to by Diffie and Hellman (1976). Their design intended to present an algorithm having properties identical to hand written signature (i.e., simple to generate and verify but difficult to forge). Nonetheless, the signature could be generated automatically by means of a digital machine to be utilized in digitized documents (Zakerolhosseini and Malekian, 2007).
The most significant difference between the hand written and digital signatures
is the uniqueness of hand written signatures for all the documents. However,
the digital signatures are dependent on the message and do change accordingly.
In general, the mechanisms for implementation of a digital signature can be
categorized into four groups as follows (Zakerolhosseini and Malekian, 2007):
• 
Digital signatures based on the message digest 
• 
Symmetrical key digital signatures, established by a reliable center for
signature confirmation 
• 
Digital signatures based on the public key cryptosystems 
• 
Signatures based on transforms that are independent from cryptosystems 
The main focus of this research is to improve the first group of digital signatures. In this system, each document is set into a standard form and then a short digest consisting of few bytes is generated. The size of the document does not influence the size of the digest so the size of digest is constant for all the documents. The digest will intricately be affected only by changes in contents and locations of each bit in the document. The digest will be estimated in such a way that any alteration of the document will lead to great changes in its digest. After extracting the digest, the bitstring created will be encrypted by means of signer’ private key and the result is appended to the message. In fact, a digital signature is a numerical string which should be extracted from the context of a document through a complex procedure and it will be attached to the document after being encrypted by the signer’ private key (Zakerolhosseini and Malekian, 2007).
In order to verify, the receiver must decrypt the encrypted digest using the
signer’ public key and recompute the digest of the received message. Then,
the receiver compares the two results and if they are the same, the document
will be accepted; otherwise the document is deemed to have changed.
Figure 1 shows the general procedure (Zakerolhosseini and Malekian, 2007):
Estimation of the message digest: To estimate the digest, the algorithms
must satisfy the following conditions (Zakerolhosseini and Malekian, 2007):
• 
When a message m is available, computing its digest e must
be computationally fast 
• 
If a digest is available, the major context of the document can not be
reproduced (oneway procedure) 
• 
In practice, make several messages having the same digest impossible 
The public key cryptography: Many of the public key cryptography methods
have been broken, but some of them have remained tenacious (Vanstone, 1997).
These methods are categorized fundamentally into three groups:
• 
The Integer Factorization Problem (IFP) 
• 
The Discrete Logarithm Problem (DLP) 
• 
The Elliptic Curve Discrete Logarithm Problem (ECDLP) 
Increasing the key length in digital signature algorithms based on the ECDLP causes an exponential increase in the security which is the most important feature of the algorithms in this category. Thus, in order to satisfy the security requirements, the Elliptic Curve Cryptosystems (ECC) need a smaller key size compared to other algorithms (Vanstone, 1997). This feature of having a small key size simplifies the calculations significantly and also reduces the power dissipation (Caelli et al., 1999). Therefore, the algorithms based on the ECDLP are receiving much attention in applications such as communications, sensor networks and wireless devices. In recent years, the ECC has been widely established among international standards, for instance, ISO 117703, IEEE P1363, ANSI X9.62 and FIPS 1862, etc. At the end of this research, the performances of the categories mentioned earlier are compared.

Fig. 2: 
Addition on elliptic curves 
The elliptic curves over finite fields: Elliptic curves introduced by
Miller (1985) and Koblitz (1987) play an important role in cryptography (Hwang
and Liao, 2005; Tzeng and Hwang, 2004). Let GF(2^{m}) be a finite field
of 2^{m} elements, where m is an integer. An elliptic curve over GF
(2^{m}) is defined as Zheng and Imai (1998) and Johnson et al.
(2001):
An elliptic curve over GF(2^{m}) consists of all points (x,y), where
x, y ε GF(2^{m}) together with the point of infinite o, do satisfy
(1) earlier. The addition of two points and doubling a point on an elliptic
curve in a geometrical space, are shown in Fig. 2 and
3, respectively.
Considering an elliptic curve C on GF(2^{m}), the addition of points
follows specific rules indicated below (Johnson et al., 2001; Coombes,
1999; Yu and Chen, 2005):
• 
O + O = O. 
• 
P + O = P for all values of P = (x, y) ε C. Namely, C has O as its
identity element. 
• 
P + Q = O for all values of P = (x, y) ε C and Q = (x, xy) ε
C namely the inverse of (x, y) is simply (x, xy) 
• 
Adding two distinct points: 
For all P = (x_{1}, y_{1}) ε C and Q = (x_{2},
y_{2}) ε C with x_{1} # x_{2}, P + Q = (x_{3},
y_{3}) is defined as:
For any P = (x_{1}, y_{1}) ε C with y_{1} # 0,
2P = (x_{2}, y_{2}) is defined as:
The scalar multiplication: The scalar multiplication is a fundamental operation in ECCs. The operation is simply an accumulation of a point P to itself for k times (k is an m bit long scalar) (Johnson et al., 2001):
The discrete logarithm problem on elliptic curves: Let P and Q be the two points on an elliptic curve with an order of n where n is a prime. The point Q = kP where k < n. Given the points P and Q, estimating the value of k is computationally infeasible (Smart, 1999).
Previous works: Here, some previous algorithms based on the ECDLP are
briefly investigated. The weakness of these protocols is examined which is the
motive behind designing a new protocol. Generally, there are four operational
phases in digital signatures based on the ECDLP as listed below:
• 
The system initialization phase 
• 
The key generation phase 
• 
The signature generation phase 
• 
The signature verification phase 
In Table 1, a brief description of two well known algorithms
is presented. In both these algorithms it is assumed that entity A wishes to
sign a message m and selects a random integer d_{A} from the interval
[1, n1] as the private key and publishes Q_{A} = d_{A}G as
the public key.
In Elliptic Curve Digital Signature Algorithm (ECDSA) (Johnson et al.,
2001), The problem is due to resetting "s" to zero in step 4 of signature generation
phase, that leads to a jump to start of the phase and in turn, recomputing
some costly operations like scalar multiplication, modular inversion and modular
multiplication. This jump to start of the phase is due to s having a value of
zero and in that case the s^{1} in the verification phase can not be
computed. Also as stated in EC ElGamal Digital Signature Scheme (Rabah, 2005),
resetting "s" to zero leads to incorrect result in the verification phase. Therefore,
in the algorithms stated in Table 1 if s is set to zero,
the signature generation phase must become recurring.
In order to correct this weakness and also to improve the performance of such algorithms, some approaches such as the method presented in Chung et al. (2007) and the proposed method, are presented here. A comparison of these methods is also presented here.
THE PROPOSED METHOD
Here, a new and improved protocol based on the ECDLP is proposed. Initially, the structure of the protocol is described and then, the effectiveness and the security of the protocol are investigated. This algorithm is divided into four steps similar to other digital signature protocols.
Step 1: System initialization phase
• 
A field size q = p which defines the underlying finite
field Fq, where either q = p in case that p is an odd prime, or q = 2^{m}
that q is a prime power 
• 
Specifying an appropriate elliptic curve by selecting two parameters a
and b of elliptic curve equation E over Fq: y^{2} +xy = x^{3}
+ ax^{2} + b. 
• 
The base point G = (_{Gx},_{Gy}), is a finite point on
elliptic curve having the largest order n 
• 
The order n of the base point G, is a large prime number in E(Fq). N =
#E(Fq) is divisible by n 
Step 2: Key generation phase
Signer "A" generates the public and private keys, as follows:
• 
Select a random integer d from the interval [1, n1] as the
private key 
• 
Compute Q = dG as the public key 
Table 1: 
The signature generation and verification phases of two known
algorithms 

Step 3: Signature generation phase
Signer "A" generates a signature for the message m, as follows:
• 
Select a random integer k from the interval [1, n1], where
k # d (d is the private key for signer "A") 
• 
Compute F = kG = (x_{0}, y_{0}) and r = x_{0 }
mod n. If r = 0 then go to step 1 
• 
Convert the message m into an integer e using the hashfunction operation,
e = Hash(m) 
• 
Compute s = (dre + k) mod n 
• 
(s, F) is the signature generated by signer "A" for the message
m 
Step 4: Signature verification phase
The verifier confirms the validity and authenticity of the signature m, as:
• 
Compute the digest of received message as e^{*}
= Hash(m^{*}), 
• 
Compute v = s^{*} G 
• 
Compute u = e^{*} r^{*} Q + G^{*} 
• 
If v = u then validate the signature; otherwise reject 
Note: It is assumed the message received for the verification is m* and the received signature is (s^{*}, F^{*}). The use of these new symbols indicates that message and signature may have been altered.
Proof: Assume the message and its signature have not been altered,
i.e., F^{*} = F, s^{*} = s, e^{*} = e. Since an elliptic
curve over GF(2^{m}) forms an Abelian group (Lawrence, 2003) under an
addition on points, then the consistency of the scheme will be evaluated by
Eq. 2.
In this protocol, the modular inversion operation in signature generation and
verification phases could be avoided. Also, compared to other schemes as shown
in Table 1, when "s" in step 4 of the signature generation
phase becomes zero, the verification phase can still be performed using a signature
that it's "s" is equal to zero and thus the signature generation phase does
not repeat.
Having s = 0 results in sG = o (point of infinity) (Rabah, 2005). If this case occurs, then according to (2), u = v = O (point of infinity) and the verification phase is also will be performed correctly. This feature increases the performance of the protocol. The security of this protocol depends on the difficulty of solving the ECDLP and the resistances of hashfunction against attacks as well other similar protocols.
Signature generation by means of a reliable method: In all corresponding protocols, it is required to embed and hide the digest into the signature such that it would be impossible to detect the digest in the signature. In other word, digest’ presence in the signature cannot be tracked or detected. Hence, no one can forge the signature. In all known similar protocols, this uniqueness is achieved by means of two parameters that are unknown to everyone except to the owner of the signature. These parameters are the private key d and the integer k where k is randomly generated by the signer for each message and d # k.
In general, if X and Y are some unknown values that are generated by d and k, then the signature will be Xe + Y. As an instance, in ECDSA (Johnson et al., 2001) and EC ELGamal Digital Signature Scheme (Rabah, 2005), the signature is employed as (k^{1})e + (drk^{1}). However, in the proposed scheme the signature is (dr)e + k which employs the parameters d, k and r. The effect of employing r parameter along with the unknown parameters d and k for generating the signature will be appeared later.
The impossibility of signature forging: Here, we examine how forging
the signature is not possible in the proposed protocol. In general, assume a
forged signature for the message m is (s + y = s^{*}, F^{*}),
instead of the original signature (s, F). We shall prove that no values can
be found for y and F^{*} such that satisfies the Eq.
3 for the verification.
Initially it will be presented that even with selection of y appropriately
and arbitrarily, no value can be found for F^{*}. From Eq.
3, the relation of Eq. 4 can be emerged. In this equation,
in order to estimate an appropriate value of F^{*}, the attacker has
access to all the left side parameters except the r^{*} e^{*}(dG)
value, where r^{*} is the xcoordinate of F^{*}.
Hence, since the value of F* is not available, then r* will be unknown as well.
Therefore, the left term of the Eq. 4 can not be computed.
Consequently, calculating an appropriate value for F* is not possible. Another
approach by the attacker may be by means of selecting the y value appropriately
and eliminating the r^{*} from the left side of the equation. For this
approach, the attacker has to select the y value equal to dr^{*}e^{*}.
However, since the value of d is not available for signature forger, the r^{*}
can not be eliminated and the appropriate value of F* can not be generated.
It will be presented at this section that if the value of F^{*} is
chosen appropriately and arbitrarily with no precondition, it would be impossible
to calculate the value of y alone and therefore rendering the forging
impossible. From Eq. 3 the relation Eq. 5
is concluded:
The parameters on the right of Eq. 5 are available to the
forger, in other words, the forger has the value of the product yG. However,
according to ECDLP it is not possible to estimate the value of y. Hence, even
with an arbitrary value of F^{*}, y value cannot be estimated and making
the forging impossible.
RESULTS AND DISCUSSION
Table 2 defines our notation. From Koblitz et al.
(2000), the time complexity for various operation units in terms of time complexity
of modular multiplication is shown in Table 3.
The time complexity of the proposed protocol and some other protocols in terms
of modular multiplication operation, modular inverse operation and oneway hash
function is shown in Table 4. The proposed protocol does
not require any inverse computation for the signature generation phase and the
verification phase. Initially, required computational cost for each protocol
has been estimated by means of adding the execution time of required operations.
Table 2: 
Definition of given notations 

Table 3: 
Unit conversion of various operations in terms of T_{MUL} 

Latter based on Table 3, all the estimated times have
been exhibited in terms of the required execution time for modular multiplication
or inversion.
Table 4 shows that the proposed method in comparison to
other protocols, has less time complexity for the signature generation and verification
phases.
Since the method developed in Chung et al. (2007), similar to our method, does not require recomputing signature when s = 0, a further comparison is essential. Assuming the time complexity of the hash function is neglected, then we can estimate the speedup of the proposed protocol in comparison with Chung et al. (2007), as follows:
Hence the speedup of signature generation and verification phases can be calculated
as (6) and (7), respectively below:
Therefore, in comparison to the method in Chung et al. (2007), the signature
generation and signature verification phases of our method is improved by 93
and 47%, respectively.
Table 4: 
Required time complexity in unit of T_{MUL} 

†:
Recomputing signature when s = 0 in step 4 of signature generation phase 
Therefore, it is clear that the proposed protocol can substantially raise
the efficiency of signature generation and signature verification.
In general, elliptic curve discrete logarithm problem has a stronger mathematical base than the integer factorization (Nyang and Song, 2000) and discrete logarithm problem (Li et al., 2005; Pointcheval and Stern, 2000; Hwang et al., 2002; Hwang et al., 2001). In some well known algorithms like RSA (Hwang et al., 2000), the key length has to be 1024 bits for achieving high security (Rivest et al., 1978). The same level of security is achieved in ECC by a key length of 160 bits. Therefore with the same level of security, the speed of ECC is several times faster than RSA cryptosystems.
CONCLUSION
In this research, the weakness of other protocols for digital signature based on the ECDLP is highlighted. A protocol based on the ECDLP is proposed for overcoming this weakness. The time complexity of the proposed protocol is compared with the previous works and results indicate the proposed protocol based on the ECDLP is more efficient than algorithms based on the IFP and DLP. Furthermore, the results also indicate the protocol has less time complexity even compared to other family protocols based on the ECDLP.