An efficient variant of the RSA cryptosystem

• Cesar Alison Monteiro Paixão USP
• Décio Luiz Gazzoni Filho USP

DOI: https://doi.org/10.5753/sbseg.2005.21521

Abstract

We describe an efficient combination of two variants of the RSA cryptosystem (MPrime and Rebalanced RSA) analyzed by Boneh and Shacham [Boneh and Shacham 2002]. For 2048-bit moduli, the resulting decryption process is about 8 times faster than that presented by Quisquater and Couvreur [Quisquater and Couvreur 1982] and about 27 times faster than the original cryptosystem.

References

Atkin, A. O. L. and Morain, F. (1993). Elliptic curves and primality proving. Mathematics of Computation, 61:29-68.

Boneh, D. (1999). Twenty years of attacks on the RSA. Notices of the American Mathematical Society, 46(2):203-213.

Boneh, D. and Shacham, H. (2002). Fast variants of RSA. RSA Laboratories.

Broadhurst, D. (2005a). A proof of semiprimality at 35205 digits. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0503&L=nmbrthry&P=1303.

Broadhurst, D. (2005b). Proven hard-to-factor semiprime. http://groups.yahoo.com/group/primeform/message/5449.

Cohen, H. (1996). A Course in Computational Algebraic Number Theory, volume 138 of Graduate Texts in Mathematics. Springer, second edition.

Collins, T., Hopkins, D., Langford, S., and Sabin, M. (1997). Public key cryptographic apparatus and method. US Patent 5,848,159.

Coppersmith, D., Howgrave-Graham, N., and Nagaraj, S. V. (2004). Divisors in residue classes, constructively. Cryptology ePrint Archive, Report 2004/339.

Crandall, R. and Pomerance, C. (2000). Prime Numbers: A Computational Perspective. Springer-Verlag, New York.

Fiat, A. (1989). Batch RSA. In Advances in Cryptology: Proceedings of CRYPTO '89, volume 435 of Lecture Notes in Computer Science, pages 175-185.

Gazzoni Filho, D. L. (2005). Re: Proven hard-to-factor semiprime. http://groups.yahoo.com/group/primeform/message/5481.

Goldwasser, S. and Kilian, J. (1986). Almost all primes can be quickly certified. In Proc. 18th Annual ACM Symp. Theory of Computing, pages 316-329.

Granlund, T. (2005). GNU MP arithmetic library. http://www.swox.com/gmp.

Hinek, M. J. (2002). Low public exponent partial key and low private exponent attacks on multi-prime RSA. Master's thesis, Waterloo University.

Jones, G. A. and Jones, J. M. (1998). Elementary Number Theory. Springer Undergraduate Mathematics Series. Springer-Verlag, New York.

Lenstra Jr., H. W. (1987). Factoring integers with elliptic curves. Ann. Math., 2:649-673.

Morain, F. (1998). Primality proving using elliptic curves: an update. In Alg. Number Theory: Proc. ANTS-III, volume 1423 of LNCS, pages 111-127. Springer-Verlag.

Paixão, C. A. M. (2003). Implementação e análise comparativa de variações do criptossistema RSA. Master's thesis, Inst. de Matemática e Estatística, Univ. de São Paulo.

Quisquater, J.-J. and Couvreur, C. (1982). Fast decipherment algorithm for RSA publickey cryptosystem. Eletronic Letters, 18:905-907.

Reble, D. (2005). Untitled mailing list post. http://www.graysage.com/djr/isp.txt.

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

Takagi, T. (1998). Fast RSA-type cryptosystem modulo pkq. In Proceedings of CRYPTO'98, volume 1462 of Lecture Notes in Computer Science, pages 318-326.

Wiener, M. (1990). Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory, 36(3):553-558.