Cryptology ePrint Archive: Report 2021/077

Magnetic RSA

Rémi Géraud-Stewart and David Naccache

Abstract: In a recent paper Géraud-Stewart and Naccache \cite{gsn2021} (GSN) described an non-interactive process allowing a prover $\mathcal P$ to convince a verifier $\mathcal V$ that a modulus $n$ is the product of two randomly generated primes ($p,q$) of about the same size. A heuristic argument conjectures that $\mathcal P$ cannot control $p,q$ to make $n$ easy to factor.

GSN's protocol relies upon elementary number-theoretic properties and can be implemented efficiently using very few operations. This contrasts with state-of-the-art zero-knowledge protocols for RSA modulus proper generation assessment.

This paper proposes an alternative process applicable in settings where $\mathcal P$ co-generates a modulus $n=p_1q_1p_2q_2$ with a certification authority $\mathcal V$. If $\mathcal P$ honestly cooperates with $\mathcal V$, then $\mathcal V$ will only learn the sub-products $n_1=p_1q_1$ and $n_2=p_2q_2$.

A heuristic argument conjectures that at least two of the factors of $n$ are beyond $\mathcal P$'s control. This makes $n$ appropriate for cryptographic use provided that \emph{at least one party} (of $\mathcal P$ and $\mathcal V$) is honest. This heuristic argument calls for further cryptanalysis.

Category / Keywords: public-key cryptography / RSA, moduli, prescribed bits, factoring, attestation

Date: received 22 Jan 2021, last revised 25 Jan 2021

Contact author: david naccache at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20210125:112534 (All versions of this report)

Short URL: ia.cr/2021/077