×

Small primitive roots and malleability of RSA moduli. (English) Zbl 1245.11007

Summary: P. Paillier and J. Villar [Lect. Notes Comput. Sci. 4284, 252–266 (2006; Zbl 1172.94593)] made a conjecture about the malleability of an RSA modulus. In this paper we present an explicit algorithm refuting the conjecture. Concretely we can factorize an RSA modulus \(n\) using very little information on the factorization of a concrete \(n'\) coprime to \(n\). However, we believe the conjecture might be true, when imposing some extra conditions on the auxiliary \(n'\) allowed to be used. In particular, the paper shows how subtle the notion of malleability is.

MSC:

11A07 Congruences; primitive roots; residue systems
11A51 Factorization; primality
94A60 Cryptography

Citations:

Zbl 1172.94593
PDFBibTeX XMLCite
Full Text: arXiv