An efficient variant of the RSA cryptosystem
Resumo
Descrevemos uma combinação eficiente de duas variantes do criptossistema RSA (MPrime e Rebalanced RSA) analisadas por Boneh e Shacham [Boneh and Shacham 2002]. Para módulos de 2048 bits, o processo de decriptação resultante é cerca de 8 vezes mais rápido que o apresentado por Quisquater e Couvreur [Quisquater and Couvreur 1982], e cerca de 27 vezes mais rápido que o criptossistema original.Referências
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.
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.
Publicado
26/09/2005
Como Citar
PAIXÃO, Cesar Alison Monteiro; GAZZONI FILHO, Décio Luiz.
An efficient variant of the RSA cryptosystem. In: SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 5. , 2005, Florianópolis.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2005
.
p. 14-27.
DOI: https://doi.org/10.5753/sbseg.2005.21521.
