Paper 2002/063

On some Attacks on Multi-prime RSA

M Jason Hinek, Mo King Low, and Edlyn Teske

Abstract

Using more than two factors in the modulus of the RSA cryptosystem has the arithmetic advantage that the private key computations can be speeded up using Chinese remaindering. At the same time, with a proper choice of parameters, one does not have to work with a larger modulus to achieve the same level of security in terms of the difficulty of the integer factorization problem. However, numerous attacks on specific instances on the RSA cryptosystem are known that apply if, for example, the decryption or encryption exponent are chosen too small, or if partial knowledge of the private key is available. Little work is known on how such attacks perform in the multi-prime case. It turns out that for most of these attacks it is crucial that the modulus contains exactly two primes. They become much less effective, or fail, when the modulus factors into more than two distinct primes.

Note: Several corrections and updates.

Metadata
Available format(s)
PS
Category
Public-key cryptography
Publication info
Published elsewhere. To appear at SAC 2002
Keywords
RSAcryptanalysisnumber theory
Contact author(s)
eteske @ math uwaterloo ca
History
2002-07-18: revised
2002-05-24: received
See all versions
Short URL
https://ia.cr/2002/063
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2002/063,
      author = {M Jason Hinek and Mo King Low and Edlyn Teske},
      title = {On some Attacks on Multi-prime RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2002/063},
      year = {2002},
      note = {\url{https://eprint.iacr.org/2002/063}},
      url = {https://eprint.iacr.org/2002/063}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.