On using Aryabhatta Remainder Theorem to Decrypt a Message with RPrime and Rebalanced RSA
Abstract
RSA is the most world widely used asymmetric cryptosystem for network transactions. Through this article, we propose a new implementation of Aryabhatta Remainder theorem (ART) in place of the existing Chinese Remainder Theorem (CRT) to solve congruencies in the decryption phase for the faster variants of RSA such as RPrime RSA and Rebalanced RSA. Through our observations, we prove that using ART for CRT has improved the overall decryption speed of RPrime and Rebalanced RSA.
About this article
Keywords
- Aryabhatta remainder theorem
- Chinese remainder theorem
- Rebalance
- RPrime
- Rebalanced.
References
[1] Boneh D, Shacham H., “Fast variants of RSA”. CryptoBytes, Vol. 5, No.1, pp. 1-9, (2001).
[2] Fiat A, “Batch RSA”, Advances in Cryptology: Proceedings of Crypto ’89, Vol. 435, pp. 175–185, (1989).
[3] Knuth DE, “The Art of Computer Programming – Volume 2: Seminumerical Algorithms”, Addison Wesley, (1969).
[4] Paixao CAM, “Implementacao e analise comparativa de variacoes do criptossistema RSA” Master’s thesis, Inst. de Matematica e Estatıstica, Univ. de Sao Paulo., (2003).
[5] Paixao CAM., “An efficient variant of the RSA cryptosystem”, IACR Cryptology ePrint Archive, pp.159, (2003).
[6] Rao TRN, Yang CH, “Aryabhatta Remainder Theorem: Relevance to Public-key Crypto-algorithms”, Circuits, Systems and Signal Processing, Vol.25, No.1, (2006).
[7] Rivest R, Shamir A, Adleman L, “A method for obtaining digital signatures and public-key cryptosystems”, Commun. ACM, Vol.21, No.2, pp.120–126, (1978)
[8] Singh A, “Improving the RSA Crypto Computations”, Master Thesis, University of Louisiana, (2006).
[9] Takagi T, “Fast RSA-type Cryptosystem Modulo p k q”, In H. Krawczyk, ed., Proceedings of Crypto ’98, 1462 of LNCS, Springer-Verlag, pp. 318–326, (1998).
[10] WebLink to DataTrans Credit Card Data https://www.datatrans.ch/showcase/test-cc-numbers
[11] WebLink to tutorial of RSA BiInteger Implementation using Java http://www.java2s.com/Code/Java/Security/SimpleRSApublickeyencryptionalgorithmimplementation.htm
[12] Wiener MJ, “Cryptanalysis of short RSA secret exponents”, IEEE Transactions on Information Theory, Vol.36, No.3, pp. 553–558, (1990).