Paper 2021/1610

Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes

Giuseppe Vitto


We describe a technique to backdoor a prime factor of a composite odd integer $N$, so that an attacker knowing a possibly secret factor base $\mathcal{B}$, can efficiently retrieve it from $N$. Such method builds upon Complex Multiplication theory for elliptic curves, by generating primes $p$ associated to $\mathcal{B}$-smooth order elliptic curves over $\mathbb{F}_p$. When such primes $p$ divide an integer $N$, the latter can be efficiently factored using a generalization of Lenstra's Factorization Method over rings bigger than $\mathbb{Z}_N$, and with no knowledge other than $N$ and $\mathcal{B}$. We then formalize semiprimality certificates that, based on a result by Goldwasser and Kilian, allow to prove semiprimality of an integer with no need to reveal any of its factors. We show how our prime generation procedure can be used to efficiently produce semiprimality certificates, ultimately allowing us to sketch a multi-party distributed protocol to generate semiprimes with unknown factorisation, particularly relevant in the setting of distributed RSA modulus generation. We provide and discuss implementations of all proposed protocols and we address security of semiprimality certificates by showing that semiprimes generated within our methods result at least as secure as random semiprimes of same size.

Note: fixed typos

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
elliptic curvescomplex-multiplicationbackdoorsemiprimecertificateMPCRSAECM
Contact author(s)
giuseppe vitto @ uni lu
2021-12-22: last of 6 revisions
2021-12-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giuseppe Vitto},
      title = {Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1610},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.