Mathematical Model of Digital Signature based on ECDSA and Schmidt-Samoa Cryptosystem

 

Bhavadip Moghariya ¹, Ravi Gor ²

 

¹ Research Scholar, Department of Applied Mathematical Science, Actuarial Science and Analytics, Gujarat University, India

² Department of Applied Mathematical Science, Actuarial Science and Analytics, Gujarat University, India

 

1. INTRODUCTION

In E-commerce business and cloud technology, authentication, and confidentiality are very important property. Similarly, non-repudiation is the important property of information security in blockchain technology. Digital Signature is cryptographic tool to verify the integrity of a file or a message. Different methods and algorithms of cryptography have been used to achieve these types of goals.

The purpose of Digital Signature is the same as handwritten signature. Instead of using pen and paper, a Digital Signature can be generated using digital keys. An essential benefit of Digital Signature is that one cannot generate fake Digital Signature. Digital signature is always a part of shared document or data.

Some of the standard approach was defined by National Institute of Standards and Technology (NIST)of US called Digital Signature Standard (DSS). Digital Signature Algorithm (DSA) is the part of DSS developed by NIST. Elliptic Curve Digital Signature Algorithm (ECDSA) is the elliptic curve analogue of the Digital Signature Algorithm (DSA).

Elliptic Curve Digital Signature Algorithm (ECDSA) is a public key cryptosystem which is based on Elliptic Curve Cryptography (ECC). In ECC, Elliptic curves are defined over finite field and algebraic structure of these elliptic curves are used for Digital signature algorithms. Discrete logarithm problem (DLP) is defined on an elliptic curve. Without knowing some parameters, it is very unlikely to solve DLP which gives strong security for an algorithm based on ECC.

Compared to other techniques, ECDSA has a relatively high computational complexity, which provides superior protection against various kinds of attacks. So, ECDSA is frequently used in wide range of applications. ECDSA is based on Elliptic Curve Cryptography, which requires some different algebraic operations.

Mathematical Model of ECDSA

An Elliptic Curve is defined over a field . Which is the set of points satisfying an equation ,where  and .

Here, characteristic of  is neither 2 nor 3.

Different values of  and  gives different elliptic curves. These elliptic curves also contain a special point , called the point at infinity.

Set of points on Elliptic Curve form a group under a specific binary operation. This binary operation is defined over finite fields. The main operation, point multiplication is achieved by two basic elliptic curve operations.

(1) Point addition      (2) Point doubling

1)    Point addition

Figure 1                                                                        Figure 2                                 

 

Figure 1 (Point Addition)

Figure 2 (Point Doubling)

 

Consider two distinct points  and  on an elliptic curve as shown in Figure 1. If  then a line drawn through the points  and  will intersect the elliptic curve at exactly one more point  (negative of ).The reflection of the point  with respect to  gives the point , which is the addition of points  and .Thus, on an elliptic curve, . If , the line through this point does not intersect to Elliptic Curve at any point. So, it is considered that line intersects a point at infinity .Hence,. Negative of a point is the reflection of that point with respect to .

 

(2) Point doubling

Point doubling is the addition of a point  on the elliptic curve to itself. It obtains another point  on the same elliptic curve. i.e.,.

Consider a point  on an elliptic curve as shown in Figure 2. If coordinate of the point  is nonzero, then the tangent line at  will intersect the elliptic curve at exactly one more point say.The reflection of the point  with respect to  gives the point , which is the result of doubling the point . i.e., .

If  coordinate of the point  is zero, then the tangent at this point intersects a point at infinity . Hence,  when .

Algebraically, addition can be defined as follows:

Let  and Q are two points on the elliptic curve then,

Where

and

Where

 

Let an entity A wants to send a message to B then the steps are as follows:

Before the key generation, signer choose some parameters, prime numbers  and .These parameters are used to define a specific elliptic curve.

Select a point  on curve  which generates a group of prime order . Sometimes point also known as base point.

1)    Key Generation

·      Select a random integer  in the interval

·      Compute

·      A’s public key is  and A’s private key is

2)    Signature Generation

·        Select a random integer 𝑘 in the interval

·      Compute  and  (where  is regarded as an integer between  and ). If , then reselect

·        Compute

·      Compute,  where is the hash value compute by secure hash algorithm. If , then reselect

·      The signature for the message is the pair of integers (𝑟, 𝑠)

3)    Signature Verification

·        Obtain an authenticated copy of sender’s public key

·      Verify that the integers  and  are in the interval

·      Compute  and

·      Compute  and

·      Compute  and

·      Accept the signature if and only if

 

SSC encryption technique

SSC algorithm introduced by Schmidt-Samoa (2005). It is based on difficulty of integer factorization as prime numbers.

SSC encryption technique also has three steps:

(1) Key Generation                   (2) Encryption      (3) Decryption

1)    Key Generation

·        Choose two distinct large prime numbers p and q.

·      Calculate N.

·      Calculate .

·      Public key is N and private key is .

2)    Encryption

·      Compute

·      Cipher text is  and send it to the receiver.

3)    Decryption

·      Compute

·       is the required plaintext.

 

2. LITERATURE REVIEW

Thangavel & Varalakshmi (2016) proposed a novel and efficient public key cryptosystem, enhanced Schmidt Samoa (ESS) to safeguard the data confidentiality in the cloud. The ESS cryptosystem deal with composition of four prime numbers, which increase the complexity to break the cryptosystem compared to SSC. The performance of the ESS cryptosystem has been tested with brute force attack and integer factorisation method. Performance analysis highlights that the execution time for ESS encryption as well as ESS decryption comparatively too lesser than SSC encryption and decryption in in both cases (i) file size variation and (ii) key size variation.

Al-Haija et al. (2018) provide a systematic review of Schmidt Samoa Cryptosystem to help crypto designers in efficient implementation in hardware or software-based applications.

Panjwani & Mehta (2015) presented the hardware-software co-design of ECDSA, where the focus has been to reduce the hardware resource utilisation and increase the throughput of the signature generation and verification process. The main module which has been implemented in software is the key generation of ECDSA. Proposed implementation is comparatively faster than other implementations. Significant timing advantage has been achieved due to wordwise Montgomery multiplication implementation over both  and  which are basic building blocks of the entire implementation.

Khalique et al. (2010) describes the implementation of ECDSA over elliptic curve P-192 and discusses related security issues. ECDSA has no sub exponential algorithm to solve the elliptic curve discrete logarithm problem on a properly chosen elliptic curve. So, it takes full exponential time. The key generated in the implementation is highly secured and it consumes lesser bandwidth because of small key size used by the elliptic curves.

Farooq et al. (2019) proposed a light-weight Elliptic Curve Digital Signature Algorithm. Which is certificate-based authentication mechanism by utilizing different elliptic curves. It has been shown that ECDSA authentication scheme has much better timing performance compared to RSA and can be safely used for authentication in Advanced Metering Infrastructure.

Koblitz et al. (2000) introduced Elliptic Curve Cryptography. Further, Elliptic Curve Cryptosystems are defined based on the discrete logarithm problem. This paper discussed Elliptic Curves and different operations of points over finite field.

Zhang et al. (2011) proposed the improved digital signature algorithm based on the elliptic curve cryptography and enhance the security of the digital signature. This proposed method increased one step that encrypt signature with signer’s private key and then sent the encrypted result to the verifier. Verifier verifies the encrypted result before verifying the signature.

Kavin & Ganapathy (2021) proposed an Enhanced Digital Signature Algorithm (EDSA) for verifying the data integrity while storing the data in cloud database. Proposed EDSA had been developed according to the Elliptic Curve Square points that were generated by using an upgraded equation and these points were used as public key. Also, a new base formula was introduced for signing and verification process. This work introduced a new compression technique which had been used for reducing the bit size of the signature.

 

3. PROPOSED METHOD

A sender wants to send a message to a receiver. Then the model work as given below:

Step 1: Sender chooses parameters of ECDSA algorithm and receiver chooses parameters of SSC technique.

Step 2: Using above parameters sender generates a key for signing and receiver generates a key for encryption and share this key to sender.

Step 3: Using the key shared by receiver, sender encrypts the message by SSC technique.

Step 4: Sender generates signature for this encrypted message by ECDSA.

Step 5: Sender sends this signature to receiver along with encrypted message and key which are required for signature verification.

Step 6: Receiver verifies the signature by ECDSA.

Step 7: If signature is verified, receiver decrypts the cipher text by SSC technique to read the original message. If it is not verified, then someone has forged the original data.

 

 

4. NUMERICAL EXAMPLE OF THE PROPOSED METHOD

Let sender Bob wants to send a message ‘’ to receiver Alice. Then Bob and Alice will follow the following phases and steps.

·        Phase I: Selection of Parameters

Step 1: Bob chooses following parameters for ECDSA: prime , .

So, elliptic curve becomes . Select generator point .

                                                                      Then order of group generated by  is  which is prime.

·        Phase II: Key Generation

Step 1: Bob chooses , where  and calculate .

So, private key  and public key  for ECDSA.

Step 2: Alice chooses prime  and .

Calculate .

 is the public key for SSC encryption technique.

Alice sharesthis public key toBob for encryption.

Step 3: Find .

             Calculate .

 is the private key for SSC encryption technique.

·        Phase III: Signature Generation

Step 1: For ECDSA, Bob chooses , where .

Calculate . So, .

Step 2: To encrypt the message by SSC encryption technique,

Bob encrypt the message , by calculating

                                                                              

             So, encrypted message is .

Step 3: Compute the Hash value of encrypted message,

Compute

So, signature is .

Bob shares encrypted message  and signature  along with public key  and parameters .

·        Phase IV: Signature Verification and Decryption of Cipher text

·        Signature Verification

Step 1: Alice verifies that  and  lies in the interval

Find the hash value of encrypted message .

which is,

Step 2: Now, calculate .

Step 3: Calculate

                                                     

Also,.

Step 4: Find .

So, .

Step 5: Verify that  or not. Here, .

 So, signature is verified.

If signature is not verified, someone has forged the shared data.

 

·        Decryption of Message

Step 6: If Signature is verified, decrypt the cipher text by SSC encryption technique to read the original text.

Compute .

So, original message is .

Hence, using this method Alice got the unforged and signed message sent by Bob.

 

5. TIME COMPLEXITY IN RUN TIME OF PROPOSED SCHEME

Table 1 and Table 2 shows the run time of Digital Signature scheme using ECDSA and SSC encryption technique. Here, encryption and decryption time for SSC encryption techniques, signature generation and verification time for ECDSA, signature generation and verification time for proposed signature scheme and combined time for encryption and signature generation as well as signature verification and decryption time is described. These timings are denoted for different lengths of messages. Here, we considered standard elliptic curve NIST256 and SHA-256.­

Table 1

Table 1
Algorithm	Process	Message Length (in Bit)
		128	256
SSC (ms)	Encryption	3006.11457824707	6207.09295272827
	Decryption	4.26497459411621	8.42375755310058
ECDSA (ms)	Signing	1.1199951171875	1.08008384704589
	Verification	3.89752388000488	4.38675880432128
Proposed Scheme (ms)	Signing	3007.4019908905	6208.39200019836
	Verification	8.02445411682129	12.6346588134765
Combined (ms)	Signing + Encryption	3007.23457336425	6208.17303657531
	Verification + Decryption	8.16249847412109	12.8105163574218

 

Table 2

Table 2
Algorithm	Process	Message Length (in Bit)
		512	1024
SSC (ms)	Encryption	12854.2956829071	26501.6244411468
	Decryption	17.8483009338378	36.2663269042968
ECDSA (ms)	Signing	1.08251571655273	1.07722282409668
	Verification	4.04844284057617	3.97439002990722
Proposed Scheme (ms)	Signing	12855.621767044	26502.9312133788
	Verification	21.9624042510986	40.7961368560791
Combined (ms)	Signing + Encryption	12855.3781986236	26502.7016639709
	Verification + Decryption	21.896743774414	40.2407169342041

 

From the tables, a vast difference between SSC encryption time and decryption time has been observed. Also, encryption and decryption time is highly influenced by the size of message.

From Chart 1, it is observed that there is a significant difference between SSC encryption time and ECDSA signature generation time. Also, encryption time and signature generation time for proposed method is significantly increasing as size of message is increased. A positive result is that the addition of SSC encryption time and ECDSA signature generation time is almost equal to the signature generation time of the proposed scheme.

Chart 1

Chart 1

 

From Chart 2, it is observed that signature verification time is increased with size of messages increased. The difference between verification time of proposed method and combined time of ECDSA verification and SSC decryption is almost zero.

Chart 2

Chart 2

 

6. CONCLUSION

In this paper, proposed method uses Elliptic Curve Digital Signature Algorithm (ECDSA) to generate signature and Schmidt-Samoa Cryptosystem (SSC) to encrypt the message. This method preserve data confidential because of encryption algorithm. It prevents the forgery of shared data and the receiver can also detect any forgery in shared data if it happens. Additionally, this approach offers non-repudiation and authenticity because of ECDSA. Proposed scheme provide strong security against various attacks as there is no plaintext in calculation of algorithm as well as in the sharing.

The Digital Signature scheme based on ECDSA and SSC encryption technique is very effective for all sizes of messages. The signature generation time by proposed method is almost same to the addition of SSC encryption time and ECDSA signature generation time. The same case happens for signature verification and decryption.

 

CONFLICT OF INTERESTS

None. 

 

ACKNOWLEDGMENTS

None.

 

REFERENCES

Al-Haija, Q. A., Asad, M. M., & Marouf, I. (2018). "A Systematic Expository Review of Schmidt-Samoa cryptosystem". International Journal of Mathematical Sciences and Computing (IJMSC), 4(2), 12-21. https://doi.org/10.5815/ijmsc.2018.02.02

Farooq, S. M., Hussain, S. S., & Ustun, T. S. (2019, March). "Elliptic Curve Digital Signature Algorithm (ECDSA) Certificate-Based Authentication Scheme for Advanced Metering Infrastructure". In 2019 Innovations in Power and Advanced Computing Technologies (i-PACT), 1, 1-6. IEEE. https://doi.org/10.1109/i-PACT44901.2019.8959967

Hieu, M. N., & Tuan, H. D. (2012, October). "New Multisignature Schemes with Distinguished Signing Authorities". In The 2012 International Conference on Advanced Technologies for Communications, 283-288. https://doi.org/10.1109/ATC.2012.6404277

Jarusombat, S., & Kittitornkun, S. (2006). "Digital Signature on Mobile Devices Based on Location." In 2006 International Symposium on Communications and Information Technologies, IEEE, 866-870. https://doi.org/10.1109/ISCIT.2006.339860

Kavin, B. P., & Ganapathy, S. (2021). "A New Digital Signature Algorithm for Ensuring the Data Integrity in Cloud Using Elliptic Curves". The International Arab Journal of Information Technology, 18(2), 180-190. https://doi.org/10.34028/iajit/18/2/6

Khalique, A., Singh, K., & Sood, S. (2010). "Implementation of Elliptic Curve Digital Signature Algorithm". International Journal of Computer Applications, 2(2), 21-27. https://doi.org/10.5120/631-876

Koblitz, N., Menezes, A., & Vanstone, S. (2000). "The State of Elliptic Curve Cryptography", Designs, Codes and Cryptography, 19, 173-193. https://doi.org/10.1023/A:1008354106356

Neal, K. (1985). "Elliptic Curve Cryptosystems", Mathematics of Computation, 48(177), 203-209. https://doi.org/10.1090/S0025-5718-1987-0866109-5

Paar, C., & Pelzl, J. (2009). "Understanding Cryptography: A Textbook for Students and Practitioners". Springer Science & Business Media. https://doi.org/10.1007/978-3-642-04101-3

Panjwani, B., & Mehta, D. C. (2015, August). "Hardware-Software Co-Design of Elliptic Curve Digital Signature Algorithm Over Binary Fields". In 2015 International Conference on Advances in Computing, Communications and Informatics (ICACCI), 1101-1106. https://doi.org/10.1109/ICACCI.2015.7275757

Rahat, A., & Mehrotra, S. C. (2011). "A Review on Elliptic Curve Cryptography for Embedded Systems". International Journal of Computer Science & Information Technology (IJCSIT), 3(3). https://doi.org/10.5121/ijcsit.2011.3307

Schmid, M. (2015). "ECDSA-Application and Implementation Failures".  

Schmidt-Samoa, K. (2005). "A New Rabin-Type Trapdoor Permutation Equivalent to Factoring and Its Applications". Cryptology ePrint Archive. https://doi.org/10.1016/j.entcs.2005.09.039

Sowmiya, B., Poovammal, E., Ramana, K., Singh, S., & Yoon, B. (2021). "Linear Elliptical Curve Digital Signature (LECDS) with Blockchain Approach for Enhanced Security on Cloud Server". IEEE Access, 9, 138245-138253. https://doi.org/10.1109/ACCESS.2021.3115238

Stinson, D. R. (2005). "Cryptography: Theory and Practice". Chapman and Hall Book, CRC Press. https://doi.org/10.1201/9781420057133

Thangavel, M., & Varalakshmi, P. (2016). "Enhanced Schmidt-Samoa Cryptosystem for Data Confidentiality in Cloud Computing". International Journal of Information Systems and Change Management, 8(2), 160-188. https://doi.org/10.1504/IJISCM.2016.079567

Timothy, D. P., & Santra, A. K. (2017, August). "A Hybrid Cryptography Algorithm for Cloud Computing Security". International Conference on Microelectronic Devices, Circuits and Systems (ICMDCS), 1-5. https://doi.org/10.1109/ICMDCS.2017.8211728

Utama, K. D. B., Al-Ghazali, Q. R., Mahendra, L. I. B., & Shidik, G. F. (2017, October). "Digital Signature Using MAC Address-Based AES-128 and SHA-2 256-bit". International Seminar on Application for Technology of Information and Communication (iSemantic), 72-78. https://doi.org/10.1109/ISEMANTIC.2017.8251846

Zhang, Q., Li, Z., & Song, C. (2011, August). "The Improvement of Digital Signature Algorithm Based on Elliptic Curve Cryptography". In 2011 2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC), IEEE, 1689-1691.