Paper 2021/1610

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

Giuseppe Vitto

Abstract

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