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.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
RSAmoduliprescribed bitsfactoringattestation
Contact author(s)
david naccache @ ens fr
History
2021-01-25: revised
See all versions
Short URL
https://ia.cr/2021/077

CC BY

BibTeX

@misc{cryptoeprint:2021/077,
author = {Rémi Géraud-Stewart and David Naccache},
title = {Magnetic RSA},
howpublished = {Cryptology ePrint Archive, Paper 2021/077},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/077}},
url = {https://eprint.iacr.org/2021/077}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.