Abstract: Digital signature and cryptography algorithms based on the Elliptic Curve Discrete Logarithm Problem (ECDLP) have recently received significant attention by researchers due to their high performances. In this research, a novel protocol for digital signature based on the ECDLP has been presented which in comparison with the other protocols is shown to be more efficient. An acceptable security level of the proposed protocol similar to other protocols is also verified. The performance and the time complexity of the proposed protocol in comparison to previous protocols is analyzed and some advantages outlined.
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 bit-string 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 re-compute 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 (one-way 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) |
| Fig. 1: | The procedures for digital signature based on the message digest |
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 11770-3, IEEE P1363, ANSI X9.62 and FIPS 186-2, 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(2m) be a finite field of 2m elements, where m is an integer. An elliptic curve over GF (2m) is defined as Zheng and Imai (1998) and Johnson et al. (2001):
| (1) |
An elliptic curve over GF(2m) consists of all points (x,y), where x, y ε GF(2m) 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(2m), 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, -x-y) ε C namely the inverse of (x, y) is simply (x, -x-y) |
| • | Adding two distinct points: |
For all P = (x1, y1) ε C and Q = (x2, y2) ε C with x1 # x2, P + Q = (x3, y3) is defined as:
| Fig. 3: | Doubling a point |
| • | Doubling a point: |
For any P = (x1, y1) ε C with y1 # 0, 2P = (x2, y2) 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 dA from the interval [1, n-1] as the private key and publishes QA = dAG 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, re-computing 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 El-Gamal 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 = 2m 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: y2 +xy = x3 + ax2 + 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, n-1] 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, n-1], where k # d (d is the private key for signer "A") |
| • | Compute F = kG = (x0, y0) and r = x0 mod n. If r = 0 then go to step 1 |
| • | Convert the message m into an integer e using the hash-function 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(2m) forms an Abelian group (Lawrence, 2003) under an addition on points, then the consistency of the scheme will be evaluated by Eq. 2.
| (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 hash-function 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 EL-Gamal 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.
| (3) |
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 x-coordinate of F*.
| (4) |
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:
| (5) |
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 one-way 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 TMUL |
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 re-computing 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:
| (6) |
| (7) |
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 TMUL |
| †: Re-computing 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.