Paper 2021/077

Magnetic RSA

Rémi Géraud-Stewart and David Naccache


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
RSAmoduliprescribed bitsfactoringattestation
Contact author(s)
david naccache @ ens fr
2021-01-25: revised
2021-01-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rémi Géraud-Stewart and David Naccache},
      title = {Magnetic RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2021/077},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.