Cryptology ePrint Archive: Report 2002/063
On some Attacks on Multi-prime RSA
M Jason Hinek and 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.
Category / Keywords: public-key cryptography / RSA, cryptanalysis, number theory
Publication Info: To appear at SAC 2002
Date: received 15 May 2002, last revised 18 Jul 2002
Contact author: eteske at math uwaterloo ca
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Note: Several corrections and updates.
Version: 20020718:170024 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]