Abstract
This paper presents the possibilities of combing public-key encryption and digital signature algorithms which are actually based on different mathematical hard problems. Since the output of the combination produces an Encrypted signed message. In general, most of the currently used public-key algorithms are computationally expensive with relatively lengthy key requirement due to the dependency on the number theory. Therefore, it’s important to show a combinational protocols which are based on different mathematical hard problem. In some sense, difficult to solve. In the combined scheme, we present the powerful and practical encryption digital signature scheme and its security level and execution time.
Access provided by CONRICYT-eBooks. Download conference paper PDF
Similar content being viewed by others
Keywords
1 Introduction
Cryptography algorithms can be classified into two board categories, secret key (one key, single key, symmetric) algorithms and public key (two key, asymmetric) algorithms (refer to Fig. 1). In general, Cryptography protocol employs public key cryptosystem to exchange the secret key and then uses faster secret key algorithms to ensure confidentiality, integrity, non-repudiation, authentication, and accessibility of the data stream [4, 5]. In 1976, Diffie-Hellman [2, 6] developed the concept of the public-key cryptosystem (refer to Figs. 1 and 2), and the first asymmetric encryption protocol is the RSA [7] algorithm which was published in 1978. As well as, there are many others asymmetric encryption algorithms issued since the RSA. Among them are Rabin [8], ElGamal [9], and Elliptic Curve [10].
In public-key Cryptography, Every public-key algorithm is actually based on a mathematical problem. These problems are called “mathematical hard problems” and are classified into two major groups according to the Cryptography standards. These groups are P (Polynomial) and NP (Non-deterministic polynomial). The P hard problem is defined when the problem is solved in polynomial time. Whereby, if the validity of a proposed solution can be checked only in polynomial time then the problem is considered as an NP hard mathematical problem [1–3]. Basically, public-key algorithms are classified into many major types depending on the mathematical hard problem. These problems are the discrete logarithm problem (DLP), the integer factorization problem (IFP), the Elliptic Curve discrete logarithm problem (ECDLP), the chaotic hard problem, etc. This following survey study will help us to identify the strength of the used public-key algorithms according to their mathematical hard problem (refer to Fig. 1).
In asymmetric encryption protocols, there is a pair of keys, one of which is known to encrypt the plaintext and called as the public key, while the other key is known as the private key and is used to decrypt the encrypted plaintext.
As discussed earlier, every public-key encryption algorithm is based on a NP mathematical problem that is in some sense difficult to be solved, therefore the public-key algorithms are classified according to their hard problems in this subsection. Table 1 show the key size for prime based algorithms (RSA, DSA, etc.) and integer based algorithm (ECC, Chaotic) algorithms, regarding to the resistance to brute force attacks. The keys space for RSA and DSA were calculated based on the number of primes existed for particular key sizes [14].
This paper developed a public-key encryption with digital signature scheme which are based on mathematical hard problem. The paper discusses the possibility of creating a combinational public key encryption and digital signature protocol.
2 The Proposed Encryption and Digital Signature Protocol
The combination between encryption algorithm and digital signature algorithm provides confidentiality, Integrity, authentication, and non-reputation services for messages. In this article, both algorithms are defined as any of the different mathematical problems; since it’s possible to combine encryption based IFP with digital signature based DLP in some cases. However, in the proposed solution the sender and the receiver must generate their own private and public keys. The sender must compute his/her keys for digital signature purpose while the receiver will compute the encryption and decryption keys, in parallel with the sender.
As shown by Fig. 2, the message is selected by the sender and then encrypted and signed to be sent over the insecure network to the receiver. After receiving the encrypted and signed message, the receiver should verify the signature authenticity before decrypting the ciphertext.
2.1 Combination of RSA and DSA Protocol
Figure 3 shows the combinational protocol between RSA and DSA algorithms, since RSA is based on integer factorization problem while DSA is based on discrete logarithm problem.
Key generation algorithm (generated by sender, Alice) - Alice must do:
-
1.
Choose a prime number (p s ), where 2L−1 < p s < 2L for 512 ≤ L ≤ 1024 and L a multiple of 64.
-
2.
Choose a prime numbers (q s ), where q s divisor of (p – 1), and 2159 < q s < 2160.
-
3.
Compute g as follows: g = (h (p −1)/q s s ) mod p s , where 1<h<(p s – 1), and g > 1.
-
4.
Choose a random integer x, with 0 < x < q s .
-
5.
Compute y as follows: y = g x mod p s .
Send (p s , q s , g, and y) to Bob (verifier).
Key generation algorithm (generated by receiver, Bob) - Bob must do:
-
6.
Choose two prime numbers (p r , q r ) randomly, secretly, and roughly of the same size.
-
7.
Compute the modulus n as follows: n = p r \( \times \) q r .
-
8.
Compute the Ф(n), as follows: Ф(n) = (p r −1) \( \times \) (q r −1).
-
9.
Choose the public key e, such that 1 < e < Ф(n), and GCD (e, Ф(n)) = 1.
-
10.
Compute the decryption key d, where d = e − 1 mod Ф(n).
Determine the public keys (e, n) and determine the private keys (Ф(n), d).
Encryption and Signing (sender - Alice) - Alice must do the following:
-
11.
Obtain the public keys (e, n).
-
12.
Determine the message m to be encrypt such that 0 < m < n.
-
13.
Encrypt the message as follows, c = m e mod n.
-
14.
Choose a random integer k, with 0 < k < q s .
-
15.
Compute r as follows r = (g k mod p s ) mod q s .
-
16.
Compute s as follows: s = ((k −1 ) \( \times \) (SHA-1(C) + x \( \times \) r)) mod q s .
-
The signature is (r, s).
-
Send the signature and the ciphertext (c, r, s) to the receiver.
-
k −1 is a multiplicative inverse of k in Z q
-
Verifying and Decryption (receiver - Bob) - Bob must do the following:
-
17.
Obtain the keys (p s , q s , g, and y).
-
18.
w = s −1 mod q s .
-
19.
u1 = ((SHA-1(C)) \( \times \) w) mod q s .
-
20.
u2 = (r \( \times \) w) mod q s .
-
21.
v = ((g u1 \( \times \) y u2 ) mod p s ) mod q s .
Verify the message m as follows: is v = r?.
-
22.
Obtain the ciphertext c from Alice.
-
23.
Recover the message as follows, m = c d mod n.
2.2 Combination of RSA and RSADS
Figure 4 shows the combinational protocol between RSA and RSADS algorithms, since both RSA algorithms are based on integer factorization problem.
Key generation algorithm (generated by sender, Alice) - Alice must do:
-
1.
Choose two prime numbers (p s , q s ) randomly, secretly, and roughly of the same size.
-
2.
Compute the modulus n as follows: n s = p s \( \times \) q r .
-
3.
Compute the Ф(n), as follows: Ф s (n s ) = (p s −1) \( \times \) (q s −1).
-
4.
Choose the public key e, such that 1 < e s < Ф s (n s ), and GCD (e s , Ф s (n s )) = 1.
-
5.
Compute the decryption key d s , where d s = e s − 1 mod Ф s (n s ).
Determine the public keys (e s , n s ) and determine the private keys (Ф s (n s ), d s ).
Key generation algorithm (generated by receiver, Bob)- Bob must do:
-
6.
Choose two prime numbers (p r , q r ) randomly, secretly, and roughly of the same size.
-
7.
Compute the modulus n as follows: n r = p r \( \times \) q r .
-
8.
Compute the Ф(n), as follows: Ф r (n r ) = (p r −1) \( \times \) (q r −1).
-
9.
Choose the public key e, such that 1 < e r < Ф r (n r ), and GCD (er, Ф r (n r )) = 1.
-
10.
Compute the decryption key d r , where d r = er − 1 mod Ф r (n r ).
Determine the public keys (e r , n r ) and determine the private keys (Ф r (n r ), d r ).
Encryption and Signing (sender - Alice) - Alice must do the following:
-
11.
Determine the message m to be encrypt such that 0 < m < n r .
-
12.
Encrypt the message as follows, c = m er mod n r .
-
13.
Sign the ciphertext C as: c = C ds mod n s
Send the signature and the ciphertext (C, s) to the receiver.
Verifying and Decryption (receiver - Bob) - Bob must do the following:
-
14.
v = s es mod n s
Verify the message m as follows: is v = C?
-
15.
Obtain the ciphertext C from Alice.
-
16.
Recover the message as follows, m = C dr mod n r .
3 Performance Evaluation Based on Equivalent Key Sizes for Fractal and Public-Key Encryption Protocol
We compare the performance of the integer based public-key algorithm against the well-known prime’s public-key algorithms (such as RSA and DSA) for the combined encryption and digital signature cryptosystems. Table 2 shows the performance for both approaches. Both protocols were coded in C++ with GMP library. Also, Miller-Rabin algorithm [18] is implemented for primarily test which was coded using C++ and GMP as well. However, the comparison between integers and primes based public-key cryptosystems shows that integers based public key encryption and digital signature algorithms performs better than primes based public key algorithms in general. As Fig. 5 indicate, integers based public-key algorithm (ECC), provides higher level of security at a much lower cost, both in term of key size and execution time. Moreover,
4 Conclusions
This paper presents and implemented a scheme of combining public-key encryption and digital signature algorithms and proposed an encryption digital signature protocol. However, an overall running time that compare between integers and primes based public key algorithms’ time were presented.
References
Alia, M.A.: Survey on mathematical hard problems based public-key cryptosystems. World Acad. Sci. Eng. Technol. 68, 395–402 (2010)
Alia, M.A.: Cryptosystems based on chaos theory. In: International Symposium on Chaos, Complexity and Leadership, 17–19 December 2013 (2013)
RSA Laboratories, What is a Hard Problem. RSA the Security Division of EMC (2007)
Branovic, I., Giorgi, R., Martinelli, E.: Memory performance of public-key cryptography methods in mobile environments. In: ACM SIGARCH Workshop on Memory Performance: Dealing with Applications, Systems and Architecture (MEDEA 2003), New Orleans, LA, USA, pp. 24−31 (2003)
Menezes, A., Van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography, pp. 4–15, 516. CRC Press (1996)
Diffie, W., Hellman, M. E.: New directions in cryptography. IEEE Trans. Inf. Theory IT-22, 644–654 (1976)
Rivest, R.A., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1978)
Rabin, M.O.: Digitalized signatures and public-key functions as intractable as factorization: the ACM digital library. Technical report. UMI Order Number: TR-212, Massachusetts Institute of Technology (1979)
ElGamal, T.: A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory IT-31(4), 469–472 (1985)
Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48, 203–209 (1987)
Stallings, W.: Cryptography and Network Security Principles and Practices. Pearson Education, 3 edn. (2003)
Al-Tuwaijry, F.A., Barton, S.K.: A high speed RSA processor. In: IEEE Conference, 2–6 September, Loughborough, UK, pp. 210–214 (1991)
Burnett, S., Paine, S.: RSA Security’s Official Guide to Cryptography. Osborne/McGraw-Hill, Berkeley (2001)
Elaine, B., Barker, W., Burr, W., Polk, W., Smid, M.: Recommendation for Key Management–Part 1: General NIST Special Publication 800-57 (2006)
Chaum, D., van Antwerpen, H.: Undeniable signatures. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 212–216. Springer, Heidelberg (1990)
Burrows, J.H.: Digital Signature Standard (DSS). In: Federal Information Processing Standards Publication 186, Computer Systems Laboratory, National Institute of Standards and Technology, Fips Pub, vol. 186, pp. 1–5 (1994)
Public Law, Electronic Signatures in Global and National Commerce Act. Weekly Compilation of Presidential Documents, Public Law, vol. 36, pp. 106–229 (2000)
MediaWiki: Literate Programs, Miller-Rabin (2006). http://en.literateprograms.org/Miller-Rabin_primality_test_(C,_GMP)
Acknowledgments
The authors would like to thank Al Zaytoonah University of Jordan for supporting this study.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Alia, M.A. (2017). Combining Public-Key Encryption with Digital Signature Scheme. In: Hassanien, A., Shaalan, K., Gaber, T., Azar, A., Tolba, M. (eds) Proceedings of the International Conference on Advanced Intelligent Systems and Informatics 2016. AISI 2016. Advances in Intelligent Systems and Computing, vol 533. Springer, Cham. https://doi.org/10.1007/978-3-319-48308-5_83
Download citation
DOI: https://doi.org/10.1007/978-3-319-48308-5_83
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48307-8
Online ISBN: 978-3-319-48308-5
eBook Packages: EngineeringEngineering (R0)