Paper 2024/061

Partial Key Exposure Attack on Common Prime RSA

Abstract

In this paper, we focus on the common prime RSA variant and introduces a novel investigation into the partial key exposure attack targeting it. We explore the vulnerability of this RSA variant, which employs two common primes $p$ and $q$ defined as $p=2ga+1$ and $q=2gb+1$ for a large prime $g$. Previous cryptanalysis of common prime RSA has primarily focused on the small private key attack. In our work, we delve deeper into the realm of partial key exposure attacks by categorizing them into three distinct cases. We are able to identify weak private keys that are susceptible to partial key exposure by using the lattice-based method for solving simultaneous modular univariate linear equations. To validate the effectiveness and soundness of our proposed attacks, we conduct experimental evaluations. Through these examinations, we demonstrate the validity and practicality of the proposed partial key exposure attacks on common prime RSA.