Seema Verma*, Deepak Garg
Department of Computer Science, Thapar University, Patiala, India
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  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 , 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= Memod N. Receiver Y decrypts the received data by computing M= Cdmod 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.
Quisquater and Couvreur  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 (dp,dq) instead of one large d. The two secret components can be calculated by calculating (d mod p-1) and (d mod q-1) for dp and dq respectively. The encryption method is same as that for basic RSA. Decryption method includes the computation of two factors; Mp=Cdpmod p and Mq=Cdqmod q. The plaintext can then be retrieved by combining the two factors Mp and Mq using Chinese remainder theorem (CRT).
In 2007, Sun et al. proposed a variant, Dual RSA , 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 , 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 nd < n/2,
1. Select random number x1 and x2 with bit size nd-bit and (n/2-nd) respectively, if p1=x1x2+1 is not prime repeat for other primes.
2. Select random number y2 and y1 of bit size (n/2-nd)- bit and nd bit respectively. if p2=x1y2+1 and q1=y1y2+1 is not prime chose another prime.
3. The private exponent d is selected randomly such that gcd(x1x2y1y2,d)=1. Calculate e and k1 with RSA equation ed=1+k1(p1-1)(q1-1)
4. Calculate q2=k1x2+1, if q2 is not prime then go to the previous step.
N1=p1q1, N2=p2q2, k2=y1
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 by Pointcheval  is an RSA variant which is based on "dependent RSA problem". Some improvement is given in  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)emodN for the given value of KemodN where K is randomly chosen element in Zn*.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  is combined with DRSA . The key aspects of both the variants are combined to form a new scheme.
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.
• 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 p1, q1, p2, q2 are chosen such that the private and public exponents (d and e) are same for the two moduli, N1=p1*q1 and N2=p2*q2.
Thus the parameters generated are e, d, N1 and N2. For two instances the public and private exponents are calculated as common for both, resulting in less memory consumption.
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 N1 is shown in the computations.
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 N1 and
Calculate R-1mod N1
To encrypt any plaintextM ,
Calculate C=M*R-1mod N1
(C’, C) is the required cipher text.
To decrypt the cipher text (C’, C),
Calculate R=C’dmod N1+1
Calculate the message M=C*Rmod N1
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 , 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 N1. 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 N1.
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.
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  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 . 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  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 .
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-1mod N, where R is randomly chosen element. The only way to as certain any information about the value of R-1mod N1 is to first compute R. It is not possible without knowing the secret key d. The concept of complete randomization is practical according to . 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  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:
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:
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.
 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.
 J J Quisquater and C Couvreur., "Fast decipherment algorithm for RSA public-key cryptosystem", Electronic Letters, 1982; 18:905–907.
 A. Fiat, "Batch RSA", Advances in Cryptology, 1989; 435:175–185.
 T. Collins, D. Hopkins, S. Langford and M. Sabin, "Public key cryptographic apparatus and method", US Patent #5, 1997; 848;159.
 T. Takagi, "Fast RSA-type cryptosystem modulo pkq", Crypto’98, 1998;1462:318–326.
 M. Wiener, "Cryptanalysis of short RSA secret exponents", IEEE Transactions on Information Theory, 1990; 36(3):553–558.
 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.
 S.D.Galbraith, C. Heneghan, J.F McKee, "Tunable balancing of RSA", In Proceedings of ACISP’05, 2005; 3574:280–292.
 A.K.Lenstra, BM De Weger, "Twin RSA", Progress in Cryptology- MyCrypt 2005; 3715:222–228.
 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.
 V. Shoup, NTL: A Library for doing number theory. 2008, version 5.3.1. <http://shoup.net/ntl/>
 M. Bellare and P. Rogaway, "Optimal Asymmetric Encryption- How to Encrypt with RSA", In Eurocrypt '94, LNCS 950, 1995, 92-111.
 S. Golwasser, M. Micali, "Probabilistic Encryption", Journal of Computer and System Sciences, 1984; 28:270-299.
 D. Pointcheval, "New public key cryptosystem based on the dependent RSA problem", Eurocrypt’99 Springer-Verlag, 1999; 1592:239-254.
 S. Padhye, "On DRSA public key cryptosystem", International Arab Journal of Information Technology, 2006; 3(4):334-336.
 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.
 M.J Hinek, "On the security of some variants of RSA", Ph.D. thesis, University of Waterloo, 2007.
 S. Sarkar, S. Maitra, "Cryptanalysis of Dual CRT-RSA", IACR Cryptology eprint 2010
 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.