Printer Friendly

RSA Cryptosystem Encryption Based on Three Moduli Set With Common Factor {2n+2, 2n+1,2n}.

1 Introduction

The recent paradigm shift in Information Technology cannot be overemphasized. Security has come to be an essential component in many application implementations such as Virtual Private Network (VPN) and electronic commerce. There are many methods for securing information and data; such as cryptography and intrusion detection system.Cryptography is important whenever sensitive information is to be communicated in a network. Computer security has an important role in securing information (Damrudi and Norafida, 2013).

According to Saheed and Gbolagade (2017a), cryptography presents methods for preserving information secret, for determining that information has not been tampered with, and for deciding who authored pieces of information. RSA Algorithm is one of the most important public cryptosystems used for high secure transmission of data. The security of asymmetrickey encryption such as RSA depends on the problem of integer factorization (Menezes, Vanstone and Oorschot, 1996).

The cryptography algorithms can be categorized as symmetric key cryptography and asymmetric key cryptography. In symmetric key cryptography, the same key is used for encryption and decryption operations, whereas two keys are employed for encryption and decryption operations of messages in asymmetric key cryptography. Asymmetric key cryptography provides more security compared to symmetric key cryptography (Abu, Deepthi and Puskar, 2015). The problem with the RSA cryptosystem is that it requires a lot of computational power in order to provide high level of security (Saraiva, 2009). The main bottleneck of public key algorithms is that they are slower compared to symmetric-key simply because of their foundation in modular arithmetic. Hence, how to make a faster and more efficient implementation of public key algorithms such as RSA is a challenge to researchers in cryptography field.

Recently, Saheed and Gbolagade (2017a) proposed an improved RSA algorithm based on RNS. In their paper, two optimizations were investigated to make the RSA cryptosystem operation easy.Abu et al. (2015) presented a parallel algorithm to handle the RSA decryption by investigating the effect of Pthread and computing a unified device architecture (CUDA) on decryption operation in RSA cryptosystem. Mohammed, Heba and Jawad (2016) presented an acceleration of the RSA Processes based on Parallel Decomposition and Chinese Remainder theorem. They proposed variant decompositions to gain extra speed. Saxena and Kapoor (2014) proposed the new Parallel RSA algorithm based on repeated square and multiply method. Also, a few researchers have worked on parallel RSA such as Fan et al. (2010), Li et al., (2010) and Qing et al. (2010). Fewer multiplications and less delay in a new parallel exponentiation algorithm for RSA were presented by Sepahvandi et al. (2009).

This paper proposes a new encryption approach for RSA cryptosystem based on three moduli set {2n+2,2n+1,2n} with a common factor. This paper is organized in sections.In sections 2 and 3 the RSA cryptosystem and RNS are discussed. Section 4 highlights the proposed RSA cryptosystem and hardware performance comparison, and section 5 concludes the paper.

2 RSA Cryptosystem

The RSA cryptosystem was invented by Ron Rivest, Adi Shamir, and Leonard Adleman in 1977 and was publishedfirst in the August 1978 issueof Scientific American. The RSA algorithm can be used for public key encryption and digital signatures. The RSA cryptosystem is generally used for ensuring authenticity of digital data and providing privacy. Recently, RSA has been deployed in many businesses and commercial systems. It is used in web server applications and to secure web traffic in browsers. It is used to provide authenticity and privacy to emails. It is at the heart of electronic credit card payment systems and also used to secure login sessions (Saheed and Gbolagade, 2017b).

3 Residue Number System

In RNS, a set of moduli which are all relatively prime and independent of one another are given. In this approach, integer numbers are represented by the remainders also known as residues of each modulus and operations of the arithmetic are individually based on those residues (Gbolagade, 2010; Luu,2004). The foundation for an RNS representation is a set of relatively prime integers {[m.sub.1],[m.sub.2],[m.sub.3], :::;mk} such that gcd ([m.sub.i], [m.sub.j]) = 1 for i [not equal to] j, where the greatest common divisor gcd is of mi and mj . For such a system, M = [[PI].sub.i]=i kmi is the dynamic range and any integer X [member of][0; M-1] and can be represented uniquely as X= ([x.sub.1], [x.sub.2], [x.sub.3]....; [x.sub.k]), where [x.sub.1] = |x|[m.sub.i],0[less than or equal to] xi < mi. The quest for RNS is the capability to afford carry-free addition as this results in high-speed arithmetic units.

The carry-propagation problem of conventional binary number system representation was then the main bottleneck and challenge of fast arithmetic operation and became the key justification and motivation driving and making researchers to venture into this alternative number system known as RNS for which the residue arithmetic operation in each of the modulus channels is carry free and independent (Chang, Molahosseini, Zarandi and Tay, 2015). The significant property of RSD number representation systems is the ability to perform borrow-free subtraction and carry-free addition (Parhami, 1990).

4 Proposed RSA Cryptosystem

The exponentiation is optimized as explained in this section. To compute [m.sup.3]mod n, we compute [m.sup.2] mod n and one modular squaring, again [m.sup.3] mod n and a modular multiplication with m.Then, we convert the encrypted message into residue number system using three moduli sets{2n + 2, 2n+1, 2n} with a common factor. The decryption operation is done in a similar way: first computes [c.sup.2] mod n, then [c.sup.3] mod n, and [c.sup.6] mod n, and [c.sup.7]mod n by alternating modular multiplication and squaring.

Key Pair

Public key: n= 55, e = 3

Private key: n = 55, d = 7

Key Pair Generation

Primes: p = 5, q =11

modulus: n = pq = 55

Public exponent: e = 3

Private exponent: d = [3.sup.-1] mod 20 =7

The main operation of modular exponentiation is multiplication and we have tried to reduce the number of multiplications in our approach and also introduced a residue number system based on three moduli sets{2n+2,2n+1,2n}with a common factor which was proposed by Gbolagade(2010) for further transformation of the cipher-text so as to create more confusion to cryptanalyst. The reduction in the size of the power as showed in table 1 makes the computation of the proposed approach to be faster and reduce computational time.

Figures 3.1 and 3.2 illustrate the hardware realization of the converter by Ahmad, Wang and Swamy (1999) and Gbolagade and Cotofana (2008) respectively. As can be observed from table 2, this proposal requires less delay and area, and operates on small operands of magnitude. Specifically, this proposed scheme requires four (4) 2:1 adders and two (2) multipliers; figure 3.2 requires one (1) 3:1 adder, two (2) 2:1 adders, and four (4) multiplexers while figure 3.3 requires one (1) 3:1 adder, three (3) 2:1 adders and two (2) multiplexers. In view of critical delay, our proposal requires three (3) additions and one (1) multiplication with mod-n operations. The converter in Gbolagade and Cotofana (2008)requires two (2) additions and two (2) multiplications with mod-2n operations whereas the converter by Ahmad, Wang and Swamy (1999) requires three (3) additions, two (2) multiplications with mod [m.sub.1]/[2m.sub.3] operations. Thus, our scheme requires less area with the same delay. Also, due to the reason that the proposed scheme operates on smaller operands of magnitude, less complex multipliers and adders are required which results potentially in even faster implementation.

5 Conclusion

In this paper, we suggest a better way to enhance the speed of RSA algorithm by splitting and reducing the power operation. Theoretically, our proposed approach optimizes the exponentiation of the RSA algorithm compared to the traditional RSA cryptosystem. Our scheme requires less delay with the same area or less. Also, the total number of arithmetic operations is reasonably reduced by our proposed scheme. In the future work, we intend to look at the implementation of RSA cryptosystem based on Montgomery exponentiation with RNS.


Abu, Asaduzzaman, Deepthi Gummadi, & Puskar Waichal (2015) A Promising ParallelAlgorithm to Manage the RSA Decryption Complexity In: Proceeding of the IEEE Southeast Con 2015, April 9-12, 2015 - Fort Lauderdale, Florida.

Ahmad, M. O., Wang, Y. & Swamy, M. N. S. (1999). Residue to binarynumber converters for three moduli set.IEEE Trans. on Circuits and Systems-II,46(7), 180-183, Feb.

Chip-Hong, Chang Amir Sabbagh Molahosseini, Azadeh Alsadat Emrani Zarandi, & Thian Fatt Tay (2015) Residue Number Systems: A New Paradigm to Datapath Optimization for Low-Power and High Performance Digital Signal Processing Applications IEEE circuits and systems magazine. 26-44, 1531-636X/15.2015IEEE.

Damrudi, Masumeh & Norafida, Ithnin (2013) Parallel RSA encryption based on tree architecture. Journal of the Chinese Institute of Engineers, 36(5), 658-666.

Fan, W., Chen, X. & Li, X., (2010) Parallelization of RSA algorithm basedon compute unified device architecture. In: 9th international conference on gridand cooperativecomputing (GCC), 1-5November 2010, Nanjing, China. Washington, DC: IEEE Computer Society, 174-178.

Gbolagade, K. A. & S. D. Cotofana (2008) Residue number system operandsto decimalconversion for 3-moduli sets. In Proceedings of 51st IEEE Midwest Symposium on Circuits and Systems,791-794, Knoxville, USA, August, 2008.

Gbolagade, K. A. (2010) Effective Reverse Conversion in Residue Number System Processors. ISBN 978-90-72298-10-2.PhD Thesis. Printed in The Netherlands.

Li, Y., Liu, Q. & Li, T., (2010) Designand implementation of an improved RSA algorithm. In: International conference on e-health networking, digital ecosystems and technologies (EDT), 17-18 April 2010, Shenzhen, China. Piscataway, NJ:IEEE Computer Society, 390-393.

Luu, Mi (2004) Arithmetic and logic in Computer systems. New Jersey: John Wiley and Sons.

Menezes, A. J., Vanstone, S.A. & Oorschot, P. C. V. (1996) Handbook of Applied Cryptography. Florida: CRC Press.

Mohammed, Issam Younis, Heba, Mohammed Fadhil, Jawad, Zainab Nadhim (2016) Acceleration of the RSA Processes based on Parallel Decomposition and Chinese Remainder Theorem, International Journal of Application or Innovation in Engineering & Management, 5(1), January, 12-23.

Parhami, B. (1990) Generalized signed-digit number system: a unifying framework for redundant number representation. IEEE Transactions on Computers, 39(1), 89-98.

Qing, L., Yunfei, L. & Lin, H. (2010). On the design and implementation of anefficient RSAvariant. In: 3rd international conferenceon advanced computer theory and engineering (ICACTE), 20-22 August 2010, China. Piscataway, NJ: IEEE Computer Society 3,533-536.

Saheed Y. K. & Gbolagade K.A. (2017b) Efficient RSA Cryptosystem Decryption Based on Chinese Remainder Theorem and Strong Prime. Anale. Serial Informatica. XV(2), 43-47.

Saheed Y. K., & Gbolagade K. A. (2017a). An Improved RSA algorithm based on Residue Number System. In: Proceedings of the 13th Nigeria Computer Society International Conference, 28, 86-91.

Saxena, S. & Kapoor, B. (2014) An efficient Parallel Algorithm for Secured Data Communications using RSA Public Key Cryptography Method. IACC, 4th IEEE International Advance Computing Conference.

Sepahvandi, S., Hosseinzadey, M. & Jalali, Amin (2009) An improved exponentiation algorithm for RSA cryptosystem. In: International conference on research challenges incomputer science, 2009. ICRCCS '09, 28-29.

(1) Saheed Y. Kayode and (2) Gbolagade K. Alagbe

(1) Department of Computer Science, Al-Hikmah University, Ilorin, Nigeria

(2) Department of Computer Science, Kwara State University, Malete, Nigeria (1), (2)
Table 1: RSA Encryption and Decryption using moduli set {2n+2,2n+1,2n}

Message  Encrypti        Ciphertex       Ciphertext ([C.sub.2])
         on              t(C1)
M        [m.sup.2]mod n  [m.sup.3]mod n  {2n+2,2n+1,2n}

0         0               0              {0,0,0}
1         1               1              {1,1,1}
2         4               8              {2,2,2}
3         9              27              {3,3,3}
4        16               9              {4,4,0}
5        25              15              {5,0,1}
6        36              51              {0,1,2}
7        49              13              {1,2,3}
8         9              17              {2,3,0}
9        26              14              {3,4,1}

Message  Decryption          Decrypti        Decrypti         Message
         M = [c.sup.7]mod n  on ([C.sub.1])  ion ([C.sub.2])
M        [C.sup.2] mod n     [c.sup.3]mod n  [c.sup.6]mod n   [c.sup.7]
                                                              mod n

0         0                   0               0               0
1         1                   1               1               1
2         9                  17              14               2
3        14                  48              49               3
4        26                  14              31               4
5         5                  20              15               5
6        16                  46              26               6
7         4                  52               9               7
8        14                  18              49               8
9        31                  49              36               9

Table 2: Hardware requirements performance comparison

Metrics             (Ahmad, Wang and       (Gbolagade and
                    Swamy, 1999)           Cotofana, 2008)

Area                four(4) adders         Three (3) adders
                    two(2) multipliers     Four(4)multipliers
Delay               three (3) additions    Two (2) additions
                    two(2)multiplications  Two(2)multiplications
Modular operations  [M.sub.1]/2 [m.sub.3]  [M.sub.3]

Metrics             Propose scheme

Area                Four (4) adders
Delay               Three(3)additions
Modular operations  [M.sub.3]/2
COPYRIGHT 2018 University of the West of Scotland, School of Computing
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Rivest Shamir Adleman
Author:Kayode, Saheed Y.; Alagbe, Gbolagade K.
Publication:Computing and Information Systems
Article Type:Report
Date:Oct 1, 2018
Previous Article:Skin Diseases Predictive Model Using Individual Base and Ensemble Base Approach.
Next Article:Linear Quadratic Gaussian (LQG) Control Design for Position and Trajectory Tracking of the Ball and Plate System.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |