Medical, Pharma, Engineering, Science, Technology and Business

**Seema Verma ^{*}, Deepak Garg**

Department of Computer Science, Thapar University, Patiala, India

- Corresponding Author:
- Seema Verma

Department of Computer Science

Thapar University

Patiala, India

**E-mail:**[email protected]

**Visit for more related articles at**
International Journal of Advancements in Technology

As RSA is the most popular and widely used in e-commerce, there is the need to make it more and more efficient. One of the RSA variant, i.e., Dual RSA, is designed to reduce the memory consumption for the two RSA instances. Based on Dual RSA Small d, a new scheme is designed such that the online encryption time becomes almost negligible having the same decryption performance as in Dual RSA small d. The scheme is implemented to reflect the theoretical results. The resulting scheme is efficient in encryption, decryption performance and memory consumption. Hence the scheme is suitable to be used in resource constrained environment. Scheme also exhibits the property of semantic security.

*Cryptography, encryption, public key*

RSA cryptosystem [1] was designed in 1977 by Ron Rivest, Adi Shamir and Leonard Adlemen. It is very popular public key algorithm because of its simplicity. The security lies on computing the factors of a large composite integer. Currently factoring 1024 bits integer is assumed to be as complex as workload of 280 which is the current benchmark used in cryptography. The high computational cost and memory usage bring the algorithm in research area. Work is done on various parameters to improve the efficiency of the algorithm. Work on RSA is categorized according to various factors. The improvement over decryption speed is done in variants [2, 3, 4, 5, 6]. Some areas have the requirement of less computational effort on decryption, while the others have the requirement of less computational effort on encryption side. Both the sides of encryption and decryption need to be balanced in many applications, the variants to balance both the sides can be found in [7, 8]. Other factor in RSA cryptosystem is the memory consumption. For the security purpose, the key size needs to be large, the variants related to reduction in memory consumption is described in [9, 10]. In this paper the information about the work related to computational and memory consumption overhead is given. The paper is structured as follows: second section describes the related study. The proposed work is given in section three. Security analysis and implementation details are given in section four and five respectively.

In RSA cryptosystem [1], the key generation system generates public key (e, N) for encryption and (d, N) for decryption operation. The keys are calculated by taking two random prime numbers p and q of approximately equal sizes to get N=p*q. Then Euler's totient function Φ(N) is computed by calculating (p-1)*(q- 1). Public key factor e is chosen as a random odd integer less than Φ(N) such that gcd(e, Φ(N))=1. Then secret component d can be computed using the congruence equation, i.e. RSA key equation; ed ≡1modΦ(N). If X wants to send a message M to Y, he/she first converts the message to a number less than N. Then X looks up the public key of Y and sends the message to Y by computing C= M^{e}mod N. Receiver Y decrypts the received data by computing M= C^{d}mod N. The RSA algorithm will work correctly if the plaintext M is relatively prime to the modulus,otherwise factorization of the modulus is revealed. Also gcd(C, N) gives the information of the multiple of the prime factor.

*RSA CRT*

Quisquater and Couvreur [2] introduced this variant in 1982. RSA CRT was designed to improve the speed of decryption method of RSA cryptosystem. With this method the decryption is done with two smaller secret keys (d_{p},d_{q}) instead of one large d. The two secret components can be calculated by calculating (d mod p-1) and (d mod q-1) for d_{p} and d_{q} respectively. The encryption method is same as that for basic RSA. Decryption method includes the computation of two factors; M_{p}=C^{dp}mod p and M_{q}=C^{dq}mod q. The plaintext can then be retrieved by combining the two factors Mp and Mq using Chinese remainder theorem (CRT).

*Dual RSA*

In 2007, Sun et al. proposed a variant, Dual RSA [10], to reduce the memory requirement. Dual RSA generates the same public and private exponent for two distinct RSA instances. The variant is useful mainly for blind signatures and authentication/secrecy.Dual RSA has three schemes in [10], namely Small-e, Small-d, and Generalized Dual RSA. The encryption and decryption methods are the same for all the schemes. The encryption algorithm is same as standard RSA and decryption is done using the CRT method.

Here we are concerned about only one scheme, i.e,, Dual RSA Small d.

*Key Generation Algorithm*

Here n_{d} < n/2,

1. Select random number x_{1} and x_{2} with bit size nd-bit and (n/2-nd) respectively, if p_{1}=x_{1}x_{2}+1 is not prime repeat for other primes.

2. Select random number y_{2} and y_{1} of bit size (n/2-nd)- bit and nd bit respectively. if p_{2}=x_{1}y_{2}+1 and q_{1}=y_{1}y_{2}+1 is not prime chose another prime.

3. The private exponent d is selected randomly such that gcd(x_{1}x_{2}y_{1}y_{2},d)=1. Calculate e and k_{1} with RSA equation ed=1+k_{1}(p_{1}-1)(q_{1}-1)

4. Calculate q_{2}=k_{1}x_{2}+1, if q_{2} is not prime then go to the previous step.

N_{1}=p_{1}q_{1}, N_{2}=p_{2}q_{2}, k_{2}=y_{1}

Encryption is done in the same way as in the standard RSA and decryption is done in the same way as in RSA CRT.

*DRSA*

DRSA by Pointcheval [14] is an RSA variant which is based on "dependent RSA problem". Some improvement is given in [15] by Padhey. Three variants are given which are proved to be semantically secure. DRSA is based upon the problem of Computational Dependent RSA, Decisional Dependent RSA and Extraction Dependent RSA. In Computational Dependent-RSA (C-DRSA), the problem is to determine the value of (K+1)^{e}modN for the given value of KemodN where K is randomly chosen element in Z_{n}*.This problem is as hard as the RSA problem. The DRSA encryption scheme is proved to be semantically secure against chosen-plaintext attacks. In DRSA, the key generation is same as in standard RSA.For encryption method , a random number K is selected that is coprime to the modulus N, i.e., Calculate mod N and mod N . The pair (A,B) is sent as the cipher text.

For decryption algorithm, first calculate the value of K as: mod N and then the message is decrypted by calculating

In this section a scheme is proposed which results in efficient encryption, decryption and memory usage. For this purpose Dual RSA small-d [10] is combined with DRSA [14]. The key aspects of both the variants are combined to form a new scheme.

*Proposed Method*

Following is the detail of the proposed scheme. In the proposed scheme the key generation is done as in Dual RSA smalld and idea of encryption/decryption operations is from DRSA.

*Key Generation*

• Select the private exponent d with nd bit (here nd > n/2)

• Calculate e as inverse of the private exponent that comes out to be very large of the order of the modulus.

• The prime numbers p_{1}, q_{1}, p_{2}, q_{2} are chosen such that the private and public exponents (d and e) are same for the two moduli, N_{1}=p_{1}*q_{1} and N_{2}=p_{2}*q_{2}.

Thus the parameters generated are e, d, N_{1} and N_{2}. For two instances the public and private exponents are calculated as common for both, resulting in less memory consumption.

*Encryption Method*

The encryption is done in two parts; part 1 is executed any time when server is offloaded and part 2 is executed when the message is received for encryption. Here the modulus N_{1} is shown in the computations.

Part 1

The following statements can be calculated offline (before encrypting the message).

Select R as any random number R?Zn^{*}.

Calculate C’=(R-1)^{e} mod N_{1} and

Calculate R^{-1}mod N_{1}

Part 2

To encrypt any plaintextM ,

Calculate C=M*R^{-1}mod N_{1}

(C’, C) is the required cipher text.

*Decryption Method*

To decrypt the cipher text (C’, C),

Calculate R=C’^{d}mod N_{1}+1

Calculate the message M=C*^{R}mod N_{1}

*Efficiency*

In encryption operation, R^{-1} and C’ both can be computed well in advance. For the calculation of 2 C , just modular multiplication is required instead of exponent calculation, which is very less time consuming as compared to exponentiation.

The decryption cost is almost same as standard RSA but with small decryption exponent. Here the only extra cost is modular multiplication that is incurring not much cost. In Dual RSA Small-d [10], the encryption exponent e is taken very large; hence the efficiency of encryption process becomes very slow. In the proposed method, since the complex computation can be done in advance (offline calculation), therefore the online encryption requires only one multiplication modulo N_{1}. This shifting of calculation from online to offline results in very fast online encryption. Also the decryption side of the proposed scheme is computationally as expensive as the Dual RSA Small-d due to only one extra multiplication modulo N_{1}.

Due to the use Dual RSA small-d key generation memory consumption is low. For two instances of RSA only one pair of public and private exponents needs to be stored.

*Security Analysis*

According to the security constraints defined in dual RSA:

(for moduli =1024 bits) and (for moduli=2048 bits)

The study regarding Dual RSA in Hinek [17] and Sarkar and Maitra [18, 19] proved that any other attack doesn't apply to Dual RSA Small-d. Hence the scheme is secure with the present scenario.

The proposed scheme is semantically secure against chosen plaintext attack. Semantic security is equivalent to indistinguishable chosen plaintext attack (IND-CPA). For a cryptosystem to be semantically secure probabilistic encryption algorithm and deterministic decryption algorithm are required. For probabilistic encryption algorithm, randomization must be used. With the use of randomization, by knowing any (plain text, cipher text) pair, an adversary couldn't predict any function that can result in knowing the value of cipher text for any other unrelated plain text. No deterministic public key encryption gives message indistinguishability.

RSA is semantically secure with OAEP [12]. The proposed scheme is the combination of Dual RSA Small-d and DRSA. DRSA as described in the previous section (2), was introduced by Pointcheval [14] in 1999. He proved DRSA and its variants to be semantically secure against indistinguishability of encryption against chosen plaintext attack and adaptive chosen-ciphertext attacks. Basic DRSA is semantically secure against chosen plaintext attack. In the proposed scheme basic DRSA is used. Pointcheval proved that the DRSA encryption scheme is semantically secure and the DRSA problem is intractable with e greater than 260. In the proposed scheme, e is much larger than this factor; hence this scheme follows the constraints of the standard model proposed by Pointcheval. For the proof of the semantic security, reader may refer to [14].

In the proposed scheme, to determine any information about the plaintext from the cipher text (C’, C) attacker need to have some information about R^{-1}mod N, where R is randomly chosen element. The only way to as certain any information about the value of R^{-1}mod N_{1} is to first compute R. It is not possible without knowing the secret key d. The concept of complete randomization is practical according to [16]. Hence the proposed scheme is semantically secure against chosen plaintext attack.

The proposed scheme is implemented on a laptop with 2.3GHz CPU and 5GB RAM. Implementation is done using NTL [11] with GMP using Cygwin tools on Windows 7 operating system. Dual RSA is also implemented with the same configuration for better analysis. All the algorithms, key generation, encryption, decryption are run 100 times and the time (in ms) is recorded by calculating the average. As the most popular modulus size is 1024 bits and 2048, the scheme is run by using both the sizes and performance is recorded.

**Table 1** shows the time taken by key generation, encryption and decryption algorithms by the proposed scheme for n=1024 and n=2048 bits. The value was recorded for different values of nd. In each record encryption time comes out as negligible.

With moduli 1024 bits, the following values are recorded:

n_{1}=1024 bits

n_{2}=1024 bits

n_{d}=342 bits

n_{e}=1024 bits

N1=11143337828858814366486156618227338718869534 226211308043399448576532953697846053194804738765775952 588598393272590728285364054451123007398461490588899283 893458025237613487439142619826398395122309090155444122 406398173158358889991455501957019508037542481271792552 7511139485600833414408136385101191814152834553677

N2=16552094368653430106896469724901042369672746 925198440164787953304234433796935151878967829423305638 300108782992628268153327326394643395136131652974120716 631197890571357619614173041417607188311648059379933136 383837656521695051862563508126582384261189543129113319 6171447985665971359850417584242492652867114392499

e=1576217757545912697385567198873369056723373423 685143843479046129529674161475012301428197814554686728 017119839626308774606296057399465983765562494051906779 284311573378004691403327404811563655996195372869360357 248188739254440568304240625834450913779861151933039950 58163024278890439269701112033638547829950033327

d=894214583801872834743653745327188985129635735 782298100041069585299004582874552344355042251104367582 1743

The algorithm is also implemented with moduli 2048 bits and the following values were recorded:

n_{1}=2047 bits

n_{2}=2048 bits

n_{d}=684 bits

n_{e}=2047 bits

**Table II** shows the comparison of the proposed scheme and other RSA variants.

As shown in **Table II**, the encryption time comes out to be negligible as compared to Dual RSA Small-d. Here the comparison results are shown for the modulus size 1024 bits.

In this work the most popular public key cryptosystem, RSA, is improved. The improvement is done in Dual RSA Small d, so that the high computations involved towards encryption side are lower down. The proposed scheme is shown to get the improved variant of RSA. The implementation results show that besides less memory consumption, the proposed scheme is efficient in both encryption and decryption sides. The proposed scheme can be efficiently used for saving memory as well as computation cost. The scheme has its application in any area where the workload on the system is not balanced or in any memory constrained device.

[1] R. Rivest, A. Shamir and L. Adleman., "A method for obtaining digital signatures and public key cryptosystems", Communications of the ACM, 1978; 21(2):120-126.

[2] J J Quisquater and C Couvreur., "Fast decipherment algorithm for RSA public-key cryptosystem", Electronic Letters, 1982; 18:905–907.

[3] A. Fiat, "Batch RSA", Advances in Cryptology, 1989; 435:175–185.

[4] T. Collins, D. Hopkins, S. Langford and M. Sabin, "Public key cryptographic apparatus and method", US Patent #5, 1997; 848;159.

[5] T. Takagi, "Fast RSA-type cryptosystem modulo pkq", Crypto’98, 1998;1462:318–326.

[6] M. Wiener, "Cryptanalysis of short RSA secret exponents", IEEE Transactions on Information Theory, 1990; 36(3):553–558.

[7] H.M. Sun, M.J Hinek and Wu ME, "Trading decryption for speeding encryption in Rebalanced-RSA", Journal of Systems and Software, 2009; 82(9):1503-1512.

[8] S.D.Galbraith, C. Heneghan, J.F McKee, "Tunable balancing of RSA", In Proceedings of ACISP’05, 2005; 3574:280–292.

[9] A.K.Lenstra, BM De Weger, "Twin RSA", Progress in Cryptology- MyCrypt 2005; 3715:222–228.

[10] H.M Sun, M.E Wu, W.CTing and M.J Hinek, "Dual RSA and its security analysis", IEEE Transactions on Information Theory, 2007; 53(8):2922-2933.

[11] V. Shoup, NTL: A Library for doing number theory. 2008, version 5.3.1. <http://shoup.net/ntl/>

[12] M. Bellare and P. Rogaway, "Optimal Asymmetric Encryption- How to Encrypt with RSA", In Eurocrypt '94, LNCS 950, 1995, 92-111.

[13] S. Golwasser, M. Micali, "Probabilistic Encryption", Journal of Computer and System Sciences, 1984; 28:270-299.

[14] D. Pointcheval, "New public key cryptosystem based on the dependent RSA problem", Eurocrypt’99 Springer-Verlag, 1999; 1592:239-254.

[15] S. Padhye, "On DRSA public key cryptosystem", International Arab Journal of Information Technology, 2006; 3(4):334-336.

[16] M. Bellare, P. Rogaway, "Random Oracles are Practical: a Paradigm for designing efficient protocols", in Proceedings of the 1st CCCS, ACM Press, 1993; 62-73.

[17] M.J Hinek, "On the security of some variants of RSA", Ph.D. thesis, University of Waterloo, 2007.

[18] S. Sarkar, S. Maitra, "Cryptanalysis of Dual CRT-RSA", IACR Cryptology eprint 2010

[19] S. Sarkar and S. Maitra, "Cryptanalytic results on Dual CRT-RSA and Common Prime RSA", Journal of Design and Codes Cryptography, 2013; 66:157-174.

Select your language of interest to view the total content in your interested language

- ACS Nano
- AI Algorithm
- Advanced Materials
- Animation
- Antenna Design
- Architect
- Architectural Drawing
- Architectural Engineering
- Architecture
- Artificial Intelligence
- Automated Mining
- Automation
- Behavior-based systems
- Bioinformatics Techniques
- Biomechanics
- Biomechanics and Robotics
- Bionics
- Building design
- Communication Systems
- Computational Neuroscience
- Computer Networking
- Computer Networks
- Concrete
- Construction
- Construction Engineering
- Construction Estimating Software
- Cordless
- Cyber Physical System
- Cyber Security
- Cyber Technologies
- Data Engineering
- Datamining
- Digital Image Processing
- Digital Signal Processing
- Engineering Drawing
- Fabric Formwork
- Fluid Engineering
- Fuzzy Logic
- Gaming Technology
- Genomics
- Graphic design
- Graphic designing
- Image Processing
- Industrial Robotics
- Information Science
- Information Theory
- Intelligent Robotics
- Interior Design
- Interior Designing
- Landscape Architecture
- Lovotics
- Machine Vision
- Manufacturing
- Medical Device
- Medical Robotics
- Mobile Device
- Mobile Repots
- Modeling
- Motion picture
- Multimedia Network
- Neural Networks
- Neurorobotics
- Product Modeling
- Radar Imaging
- Radio Waves
- Robotic Rehabilitation
- Satellite Communication
- Search Engine Design
- Sensors
- Simulation
- Simulation and Visualization
- Simulation and Visualization Effects
- Smart Grid
- Social Robots
- Sociology of Architecture
- Soft Computing
- Spatial Database
- Telecommunications Journal
- Telerobotics
- Tribology
- Urban Design
- Urban Planner
- Virtual Reality
- Virtual Reality Technology
- Wave Length
- Web Developer
- Wireless Journals
- swarm intelligence and robotics

- Total views:
**11424** - [From(publication date):

July-2014 - Nov 19, 2017] - Breakdown by view type
- HTML page views :
**7682** - PDF downloads :
**3742**

Peer Reviewed Journals

International Conferences
2017-18