Reference : Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes
E-prints/Working papers : Already available on another site
Engineering, computing & technology : Computer science
Computational Sciences
Factoring Primes to Factor Moduli: Backdooring and Distributed Generation of Semiprimes
Vitto, Giuseppe mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > Cryptolux >]
[en] elliptic curves ; complex-multiplication ; backdoor ; semiprime ; certificate ; MPC ; RSA ; ECM
Fonds National de la Recherche - FnR
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 B, can efficiently retrieve it from N. Such method builds upon Complex Multiplication theory for elliptic curves, by generating primes p associated to B-smooth order elliptic curves over Fp. 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 ZN, and with no knowledge other than N and 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.
FnR ; FNR11684537 > Alex Biryukov > FinCrypt > Security, Scalability, And Privacy In Blockchain Applications And Smart Contracts > 01/08/2018 > 31/07/2021 > 2017

File(s) associated to this reference

Fulltext file(s):

Open access
factoring_primes.pdfAuthor preprint464.65 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.